Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Efficiency is fundamentally at odds with elegance (2013)

yosefk.com

Post reply on HN
Print view View original

41–46 of 46 posts

Re: Efficiency is fundamentally at odds with elegance (2013)

#41

Post by logfromblammo »

phaedrus wrote: post #16
phkahler wrote: post #12

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 b…

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…

Exact answers are nice, but sometimes you need to know whether two ellipses do or don't intersect, as fast as possible, and then do the more computationally intensive math only for the interesting cases.

For instance, if the distance between centers is greater than the sum of the major radiuses, the ellipses do not have a real area of intersection, and imaginary areas are not useful for the problem at hand, so you stop calculating and move on to the next pair. If the distance between centers is smaller than the larger minor radius, there is a real area of intersection, and you can put it on the list to calculate it later.

In seven steps, you can determine the desired answer to the limit of floating point precision faster than the exact symbolic answer determined by actually solving the quartic as a "single step", which is actually encapsulating quite a lot of multiplications, and at least six distinct conditional cases.

But on the other hand, the rapid approximation is the work of one afternoon, and can be debugged one step at a time, while the exact answer is a doctoral-level thesis.

And if you're drawing your ellipses on the surface of an ellipsoid, like the WGS84 geoid, the value of approximations becomes even greater, because the exact answers will come from an even higher-order polynomial equation.

In this, the "don't care" part of the problem space is always used to make the shape of the solution as simple as possible. So when you always care about exact answers, discovered elegantly, you're actually discarding the means to make the solution more elegant in way you might not have realized.

Re: Efficiency is fundamentally at odds with elegance (2013)

#43

Post by ctchocula »

phkahler wrote: post #12

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 b…

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].

[1] https://math.stackexchange.com/questions/1537069/the-trigono...

[2] https://math.stackexchange.com/questions/1555743/how-do-you-...

Re: Efficiency is fundamentally at odds with elegance (2013)

#44

Post by gugagore »

logfromblammo wrote: post #41
phaedrus wrote: post #16

Earlier quoted context omitted.

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…

Exact answers are nice, but sometimes you need to know whether two ellipses do or don't intersect, as fast as possible, and then do the more computationally intensive math only for the interesting cases. For instance, if the distance between centers is greater than the sum of the major radiuses, the ellipses do not have a real area of intersection, and imaginary areas are not useful for the problem at hand, so you st…

What is the iterative method for determining the area of intersection ?

Re: Efficiency is fundamentally at odds with elegance (2013)

#45

Post by jstimpfle »

Jtsummers wrote: post #40
jstimpfle wrote: post #25

Earlier quoted context omitted.

Again, it was an artificial benchmark. I sorted millions of integers. 2x is not measured in a real-life program. It's the absolute upper limit what you can ever expect. Most programs don't spend a noticeable amount time in sorting at all. Program performance usually is dominated by other things, like I/O. Now what is 50% of "not a noticeable amount of time"? Right, it's irrelevant. But 2x is a hard number, so people…

> Most programs don't spend a noticeable amount time in sorting at all. I think a more important point is that most programs that depend on sorting data will use a data structure which can sort itself rather than trying to sort lists/arrays of such large numbers (especially when exceeding a certain threshold of data records). Consider if you're getting millions of records and need them in some order (potentially diff…

I'm not positive that most sorts are "online" with I/O that reads the data to be sorted. It's not what I wanted to imply anyway.

The kind of I/O I meant is just generally time consuming I/O (large amounts of data, too many small requests, too much synchronization) that most applications are doing. For other, non-I/O intensive applications, most of them likely have bottlenecks other than sorting.

In any case I wouldn't want to tie my data to an incremental sorting structure (like a search tree instead of a flat array) before I've ensured that this online aspect was critical. If it is not critical choosing a more complicated incremental structure is probably premature optimization which constrains the project structure, and thus is likely to negatively affect performance and maintainability in the end.

Re: Efficiency is fundamentally at odds with elegance (2013)

#46

Post by logfromblammo »

gugagore wrote: post #44
logfromblammo wrote: post #41

Earlier quoted context omitted.

Exact answers are nice, but sometimes you need to know whether two ellipses do or don't intersect, as fast as possible, and then do the more computationally intensive math only for the interesting cases. For instance, if the distance between centers is greater than the sum of the major radiuses, the ellipses do not have a real area of intersection, and imaginary areas are not useful for the problem at hand, so you st…

What is the iterative method for determining the area of intersection ?

I don't remember the whole thing, and I couldn't take it with me, but what I can recall is this:

It is much more important to determine whether there is a real intersection at all, than it is to determine how big the area of intersection is.

Calculate distance between centers.

Add both major radiuses.

If distance >= sum, skip this pair. Intersection area is entirely imaginary.

If distance Find the maximum extents of each ellipse, when projected onto the segment between centers. If the sum is greater than the distance, there is a real intersection. Put it on the list and go on to the next pair.

Then there was a bit of a race against time through increasingly esoteric tests that relied heavily on the calculations from previous steps. The goal was to produce a list of ellipses, sorted by decreasing real area of intersection greater than zero with a single reference ellipse. So if there was only one on the list, you didn't even need to calculate area. That was the answer, and you're done.

At some point, the reference ellipse was transformed into a circle at the origin, with the center of the comparison ellipse on the x axis. Some tests only used one quadrant of an ellipse at a time. Each test refined the bounds on the fraction of the reference ellipse that could be in the intersection, so again, if those limits were enough to sort the list, the area calculation was skipped.

If there were still enough ambiguous tests, then finally you calculate the points of intersection. For zero or one, the area is exactly the area of the smaller ellipse. For four, first approximation is the area of the quadrilateral, as minimum. For three, the area of the triangle, as minimum. Two was the worst case, because then you needed to pick out a third point for the triangle, which was probably one of the four where a major axis intersected an ellipse. If you needed a maximum area, it was the smallest circle enclosing the points. Each test either increased the lower bound, or decreased the upper bound, until there was no more overlap in the sorted list.

After all that, if the list was still not clearly ordered, you finally calculated and added chord areas to get exact results. You couldn't really get here with real-world test data, so now you had to invent test data specifically to make it this far, to be sure that if any real-world data set ever does execute this branch, it ends up ordered correctly. But I don't think we ever got funding to bulletproof it. Customer was fine with the possibility that a tiny fraction of inputs might end up ordered incorrectly, so long as the wrong answer came out quickly.

Clearly, if all the areas had to be calculated exactly, it would have been more efficient to just do that from the start. But that wasn't the problem.

Post reply on HN