Symbolic representation vs floating point as a trade of elegance? The suggestion of maintaining non-numeric representations falls flat very quickly in a number of cases:
5th root of a polynomial. There is no closed form solution that could be carried through other computations.
Integrals. There is no general method for symbolic integration. A physics simulation cannot maintain closed form solutions and it would not be elegant even if you could.
Representations of geometry - as in CAD programs. The intersection of 2 curved surfaces is usually higher order than the surfaces in question and can balloon very quickly.
Anything with sampled data - why even bother trying.
Sometimes numeric representations are necessary, not just some kind of trade. Unless one thinks the non-existence of some fantasy ideal representation is a kind of tragedy in need of fixing. And that seems to be his point at the end - you'll get frustrated very quickly looking for an elegant solution that may not even exist.
I recently started playing an Android game called Euclidea. It teaches the basics of compass and ruler construction (geometry) and asks you to complete various tasks such as bisecting an angle or finding a circle equally spaced between four points, etc. The goal is to do so with a certain minimal number of moves.
Having never taken a geometry class, but being an experienced programmer, I was struck by the difference in the approaches I gravitate to versus the geometer's approach the game seems to be trying to teach me.
For example, I might want to approach a point by successive approximation, but that doesn't count because the game is looking for an exact solution - to say nothing of the points-penalty incurred by using constructions of dozens of moves where the game knows it can be solved by just 3 or 4.
Another example, to reach something I might start by defining a "coordinate system", perhaps a strange triangular coordinate system defined by osculating circles. In this case I do reach the exact solution, eventually, but again fail to get the most points for golfing the number of moves. This because I was thinking in layers of abstraction and drawing all the possible circles first, and then saying "oh here's the point(s) I needed" rather than just getting from A to B.
I think it would no stretch to associate the elegant/minimal geometric construction of this game with the symbolic approach the author of the original post is advocating. The Euclidea game really opened my eyes to how ingrained numeric, successive approximation is in my approach to problem solving and how it contrasts to the symbolic, geometric approach. I don't know if I'd change how I approach problem solving or programming, but I think it's helpful to be aware both that you're doing it and that it's not the only approach.
There is an elegant universal notation for integers, called "variable-width integers" or "varints" or "bigints" or similar. It is reviled amongst many, and doesn't see much use.
There is an elegant universal notation for rationals, called "quote notation" or "finite continued fractions" or "p-adic rationals". It is largely unknown and sees next-to-no use.
There is an elegant universal notation for computable reals, called "computability". We use this all the time, but almost never for computing reals.
Floating-point numbers are fussy and require careful management in order to avoid buggy algorithms. In contrast, there exists an algorithm (although it's an open problem to express it in a quick way!) for taking the fifth root of any generalized continued fraction or any Turing-computable real, in a way that allows the result to be used in further computation. Somebody should tackle the Gaussian distributions next!
Nitpick: There is no closed form solution for the 5th root of a polynomial in terms of only additions, subtractions, multiplications, divisions and root extractions. This is what Galois showed. However, it can be expressed in closed form using trigonometric functions [1]. There is a summary here of the many closed form solutions that exist [2].
There's room for both, though. While some functions can't be integrated, others can. You can save yourself a lot of effort and get a more correct answer by taking a symbolic definite integral and then computing a result, compared with numerical integration.
It's not my experience that efficiency is "fundamentally" at odds with elegance. Elegance can be a hard concept to pin down and has a somewhat subjective component but I often find situations where code can be made both more efficient and more elegant. There are certainly cases where I can't see a way to make the code more efficient without sacrificing elegance however. They don't seem to be fundamentally at odds but neither are they always aligned.
I disagree with several of the specific examples given in the article but to pick one, the author says "C++ rather obviously does pay with programmer efficiency for runtime efficiency, without an option to opt out of the deal. Every allocation can leak, every reference can be dangling, every buffer can overflow, etc. etc. etc.". Most of the ways that modern C++ addresses these problems inherited from C such as unique_ptr, containers and ranges are more elegant to my taste, more convenient to use and generally no less efficient.
I find garbage collection very inelegant and the approach to memory management taken by Rust and even C++ in most cases more elegant but I'm not clear if that's something the author was intending to include in his above statement. This seems somewhat subjective however. I know there are arguments some people might make for garbage collection being elegant and even efficient in comparison to manual memory management.
Where elegance and efficiency seem to have some natural alignment is in the realm of simplicity and doing only what is necessary. Code can often be made both more efficient and more elegant in my experience by distilling out the essence of the problem and removing the unnecessary.
The underlying need is to traverse and update data structures, so language designers went with universally mutable objects with arbitrary references. That makes the representation of an individual object quite simple, and it does centralize the complexity of memory management in garbage collection, so it's a good engineering decision. But real GC requires extensive tuning (different "generations", stop-the-world pauses, etc) and that's simply not an elegant solution.
My approach was to revisit that underlying need, and I settled on a data model that simply prohibits cyclic data structures, so memory management doesn't have to be more complex than reference counting. Now, I'm still going to have to implement zippers and paths and such to handle traversal, but I think that will still be far cleaner. I have some notes here if you're curious: https://tenet-lang.org/types.html
I don’t think the author really addresses the examples presented.
The example of the FAST decision tree is based on a code generator, an abstraction which is presumably more elegant than the generated code which is littered with goto statements.
And what about std::sort? Say what you want about C++ in general, but it is definitely superior to a rudimentary qsort in C in terms of elegance and at least equivalent in terms of runtime efficiency.
There are plenty of examples in either direction. It would seem that this is yet another case of “it depends.”
std::sort and other templates make you pay in terms of header complexity (no circular includes for example) and compilation time.
For the most part it’s a good trade off, particularly std::sort and some of the other <algorithms>. But I’ve yet to work on a long lived low latency/high performance C++ project where some wizard coworker has not tanked the code base for purely theoretical gains that turn out to not meaningfully change the assembly or change it by an instruction or two.
Godbolt is a revelation when these situations arise, but good luck even then convincing someone who just spent 4 days writing a dispatch or whatever that it was all a waste.
I guess what I’m saying is that when it comes to template-oriented performance programming, std::sort is the exception, not the rule.
Or maybe the good templates are small and modular so their footprint is 1/10th that of a bad template such that we just don’t notice them as much.
"One of the things I discovered as early as the 1960s is that mathematical elegance is not a question of aesthetics, of taste or fashion, but something you can translate into a technical notion.
"The Concise Oxford Dictionary gives as one of the meanings of 'elegant' 'ingeniously simple and effective'.
"In practice a program is manageable if you make a truly elegant program, firstly because it is shorter than most alternatives and consists of discrete parts, each of which you can replace by an alternative implementation without influencing the rest of the program, but also, curiously, the most elegant programs are often the most efficient."
I've seen this tradeoff firsthand with dsp video algorithms. The naive code just implements the algorithm straight away. The performant version has to ensure that the inner loop all fits in cache while running. It also does tricks like prefetching data into cache so the code doesn't stall on a data load. These sort of tricks really impact the readability of the code.
I wouldn't say elegance here - there is something fundamentally elegant about the utilisation of 8-bit integers in scenarios where they can be used.
It is on the other hand, fundamentally at odds with accuracy - which is already well and widely known (at very least implicitly) and is the reason we so readily accept approximations in computing.
I've been writing firmware to run a DC motor controller where this efficiency/elegance tradeoff is very apparent. I can write "slower" code in a very elegant way, such as reading the throttle input. But when it comes to implementing the high-frequency control loop with all its ADC readings and filtering, I have to trade much of my elegance for raw efficiency.
There is a lot of truth to that, although I also see a third trade-off, which is robustness to change (not so much in the code but rather the inputs).
I think you can have in some cases efficiency and elegance, but then the solution will be either too abstract or specialized that it won't really be practical, and a small change in problem conditions will cause it not to work. (An example from the article - a matrix solver that only does a well-conditioned systems so the floating point errors never accumulate.)
Similarly, you can have robustness to change and elegance without efficiency (mathematically beautiful code), and robustness to change and efficiency without elegance (lot of copy pasting the code to deal with special cases).
In any case, I think we are generally trying to present elegant code to humans (using more abstract programming languages) and then use compilers to convert the elegance into efficiency. But it requires that somebody takes the pains to actually deal with all the possible cases (and write a working compiler).
I find this discussion tiring, also I have actually seen people vividly defending both positions: that the most efficient code is also very elegant and the opposite, as here.
It depends so much on the situation, skill/experience of the person/team building the stuff and what focus one has.
Sometimes an elegant solution opens completely new perspectives on performance optimizations.
Symbolic manipulation is undecidable, hence programmers prefer numeric approaches. But, symbolic approaches are clearly superior if the programmer does them a priori. I can convert a completely intractable bruteforce combinatorics problem into a very tractable algorithm with some human symbolic preprocessing (i.e. math).
What you are saying that there are a lot of programs that are neither elegant nor efficient. Few would dispute this, but I think this case is still covered by the original formulation.
For example I do not see "being drunk is fundamentally at odds with performing surgery" being invalidated by a bunch of folks writing programs in offices and fitting in neither bin. Caveat: I am not a native English speaker.
function isPalindrome(str) {
return str == str.split('').reverse().join('');
}
efficient (~50x faster than above)
function isPalindrome(str) {
var len = Math.floor(str.length / 2);
for (var i = 0; i < len; i++)
if (str[i] !== str[str.length - i - 1])
return false;
return true;
}
I would probably say elegance and efficiency are not aligned rather than at odds IMO because they may overlap or may not, they don't have the same goals.
I must say, I disagree with the very first paragraph of this article. You need numerical recipes for any real-word problem whether you have full precision or not.
This just seems like survivorship bias. An algorithm / tool / technology tends not to remain in use if something that is both more elegant and more efficient is available. Therefore, if you survey the well known options you'll see a negative relationship between elegance and efficiency. It doesn't imply a general relationship nor does it preclude the discovery of an approach that is both more elegant and more efficient than anything available today.
[+] [-] phkahler|7 years ago|reply
5th root of a polynomial. There is no closed form solution that could be carried through other computations.
Integrals. There is no general method for symbolic integration. A physics simulation cannot maintain closed form solutions and it would not be elegant even if you could.
Representations of geometry - as in CAD programs. The intersection of 2 curved surfaces is usually higher order than the surfaces in question and can balloon very quickly.
Anything with sampled data - why even bother trying.
Sometimes numeric representations are necessary, not just some kind of trade. Unless one thinks the non-existence of some fantasy ideal representation is a kind of tragedy in need of fixing. And that seems to be his point at the end - you'll get frustrated very quickly looking for an elegant solution that may not even exist.
[+] [-] phaedrus|7 years ago|reply
Having never taken a geometry class, but being an experienced programmer, I was struck by the difference in the approaches I gravitate to versus the geometer's approach the game seems to be trying to teach me.
For example, I might want to approach a point by successive approximation, but that doesn't count because the game is looking for an exact solution - to say nothing of the points-penalty incurred by using constructions of dozens of moves where the game knows it can be solved by just 3 or 4.
Another example, to reach something I might start by defining a "coordinate system", perhaps a strange triangular coordinate system defined by osculating circles. In this case I do reach the exact solution, eventually, but again fail to get the most points for golfing the number of moves. This because I was thinking in layers of abstraction and drawing all the possible circles first, and then saying "oh here's the point(s) I needed" rather than just getting from A to B.
I think it would no stretch to associate the elegant/minimal geometric construction of this game with the symbolic approach the author of the original post is advocating. The Euclidea game really opened my eyes to how ingrained numeric, successive approximation is in my approach to problem solving and how it contrasts to the symbolic, geometric approach. I don't know if I'd change how I approach problem solving or programming, but I think it's helpful to be aware both that you're doing it and that it's not the only approach.
[+] [-] myWindoonn|7 years ago|reply
There is an elegant universal notation for rationals, called "quote notation" or "finite continued fractions" or "p-adic rationals". It is largely unknown and sees next-to-no use.
There is an elegant universal notation for computable reals, called "computability". We use this all the time, but almost never for computing reals.
Floating-point numbers are fussy and require careful management in order to avoid buggy algorithms. In contrast, there exists an algorithm (although it's an open problem to express it in a quick way!) for taking the fifth root of any generalized continued fraction or any Turing-computable real, in a way that allows the result to be used in further computation. Somebody should tackle the Gaussian distributions next!
[+] [-] ctchocula|7 years ago|reply
[1] https://math.stackexchange.com/questions/1537069/the-trigono...
[2] https://math.stackexchange.com/questions/1555743/how-do-you-...
[+] [-] sevensor|7 years ago|reply
[+] [-] mattnewport|7 years ago|reply
I disagree with several of the specific examples given in the article but to pick one, the author says "C++ rather obviously does pay with programmer efficiency for runtime efficiency, without an option to opt out of the deal. Every allocation can leak, every reference can be dangling, every buffer can overflow, etc. etc. etc.". Most of the ways that modern C++ addresses these problems inherited from C such as unique_ptr, containers and ranges are more elegant to my taste, more convenient to use and generally no less efficient.
I find garbage collection very inelegant and the approach to memory management taken by Rust and even C++ in most cases more elegant but I'm not clear if that's something the author was intending to include in his above statement. This seems somewhat subjective however. I know there are arguments some people might make for garbage collection being elegant and even efficient in comparison to manual memory management.
Where elegance and efficiency seem to have some natural alignment is in the realm of simplicity and doing only what is necessary. Code can often be made both more efficient and more elegant in my experience by distilling out the essence of the problem and removing the unnecessary.
[+] [-] ben509|7 years ago|reply
My approach was to revisit that underlying need, and I settled on a data model that simply prohibits cyclic data structures, so memory management doesn't have to be more complex than reference counting. Now, I'm still going to have to implement zippers and paths and such to handle traversal, but I think that will still be far cleaner. I have some notes here if you're curious: https://tenet-lang.org/types.html
[+] [-] rbranson|7 years ago|reply
The example of the FAST decision tree is based on a code generator, an abstraction which is presumably more elegant than the generated code which is littered with goto statements.
And what about std::sort? Say what you want about C++ in general, but it is definitely superior to a rudimentary qsort in C in terms of elegance and at least equivalent in terms of runtime efficiency.
There are plenty of examples in either direction. It would seem that this is yet another case of “it depends.”
[+] [-] diegoperini|7 years ago|reply
[+] [-] CoolGuySteve|7 years ago|reply
For the most part it’s a good trade off, particularly std::sort and some of the other <algorithms>. But I’ve yet to work on a long lived low latency/high performance C++ project where some wizard coworker has not tanked the code base for purely theoretical gains that turn out to not meaningfully change the assembly or change it by an instruction or two.
Godbolt is a revelation when these situations arise, but good luck even then convincing someone who just spent 4 days writing a dispatch or whatever that it was all a waste.
I guess what I’m saying is that when it comes to template-oriented performance programming, std::sort is the exception, not the rule.
Or maybe the good templates are small and modular so their footprint is 1/10th that of a bad template such that we just don’t notice them as much.
[+] [-] edjroot|7 years ago|reply
https://youtu.be/RCCigccBzIU?t=1125
"One of the things I discovered as early as the 1960s is that mathematical elegance is not a question of aesthetics, of taste or fashion, but something you can translate into a technical notion.
"The Concise Oxford Dictionary gives as one of the meanings of 'elegant' 'ingeniously simple and effective'.
"In practice a program is manageable if you make a truly elegant program, firstly because it is shorter than most alternatives and consists of discrete parts, each of which you can replace by an alternative implementation without influencing the rest of the program, but also, curiously, the most elegant programs are often the most efficient."
[+] [-] bwoj|7 years ago|reply
[+] [-] yarg|7 years ago|reply
It is on the other hand, fundamentally at odds with accuracy - which is already well and widely known (at very least implicitly) and is the reason we so readily accept approximations in computing.
[+] [-] cosmolev|7 years ago|reply
[+] [-] jonahrd|7 years ago|reply
[+] [-] js8|7 years ago|reply
I think you can have in some cases efficiency and elegance, but then the solution will be either too abstract or specialized that it won't really be practical, and a small change in problem conditions will cause it not to work. (An example from the article - a matrix solver that only does a well-conditioned systems so the floating point errors never accumulate.)
Similarly, you can have robustness to change and elegance without efficiency (mathematically beautiful code), and robustness to change and efficiency without elegance (lot of copy pasting the code to deal with special cases).
In any case, I think we are generally trying to present elegant code to humans (using more abstract programming languages) and then use compilers to convert the elegance into efficiency. But it requires that somebody takes the pains to actually deal with all the possible cases (and write a working compiler).
[+] [-] blablabla123|7 years ago|reply
It depends so much on the situation, skill/experience of the person/team building the stuff and what focus one has.
Sometimes an elegant solution opens completely new perspectives on performance optimizations.
[+] [-] yters|7 years ago|reply
[+] [-] dmichulke|7 years ago|reply
Strangely though their absence coincides in roughly 80% of all programmes, so "being at odds with" is meant as
(Efficiency -> NOT Elegance) AND (Elegance -> NOT Efficiency)
but not as
Elegance XOR Efficiency
[+] [-] ptero|7 years ago|reply
For example I do not see "being drunk is fundamentally at odds with performing surgery" being invalidated by a bunch of folks writing programs in offices and fitting in neither bin. Caveat: I am not a native English speaker.
[+] [-] sebringj|7 years ago|reply
elegant (readable / compact)
function isPalindrome(str) { return str == str.split('').reverse().join(''); }
efficient (~50x faster than above)
function isPalindrome(str) { var len = Math.floor(str.length / 2); for (var i = 0; i < len; i++) if (str[i] !== str[str.length - i - 1]) return false; return true; }
I would probably say elegance and efficiency are not aligned rather than at odds IMO because they may overlap or may not, they don't have the same goals.
[+] [-] kazinator|7 years ago|reply
[+] [-] gameswithgo|7 years ago|reply
Would F# or Nim be a much faster Python with less ugly C FFI?
[+] [-] szemet|7 years ago|reply
[+] [-] hardlianotion|7 years ago|reply
[+] [-] m4r35n357|7 years ago|reply
[+] [-] unknown|7 years ago|reply
[deleted]
[+] [-] socketnaut|7 years ago|reply
[+] [-] someguy1234567|7 years ago|reply