News for hackers. Stuff that matters.
Re:What every computer programmer should know about floating... by sheetjs on Tuesday September 16, 2014 @12:35AM (#8323027)
That's commonly referred to as the Mediant algorithm https://en.wikipedia.org/wiki/Mediant_(mathematics) -- GDocs, LO and other programs use this algorithm when rendering.

Shameless plug: our JS fraction library https://github.com/SheetJS/frac implements the mediant as well as the Aberth algorithm.

Re:What every computer programmer should know about floating... by jwmerrill on Tuesday September 16, 2014 @11:13AM (#8324882)
Just a heads up--the mediant algorithm can be O(d) in the size of the denominator for fractions that are close to 0 or close to 1 (it's possible for the denominator to increase by only 1 at each step).

The Aberth algorithm (I hadn't heard it called that; nice to know) is much more efficient--it converges quadratically.

Re:What every computer programmer should know about floating... by hawkice on Tuesday September 16, 2014 @12:42AM (#8323046)
I did not know this! :) Thanks for sharing.

Another thing I heard, but have not been able to prove (and is not in the Wiki article), is that if you record whether you take the Left or Right segments in the algorithm, you can construct a continued fraction for any real number as int(N) + 1 / (1 (L -> -, R -> +) (number of times you took that direction before "turning around") / 1 (L -> -, R -> +) (#direction) ... ))).

My inability to prove may be primarily because I never really got the flavor of proofs about continued/infinite fractions -- considering the source I'd say it's likely true (or I misremembered).

You don't happen to know where I'd look for hints on the proof there, do you? :)

Re:What every computer programmer should know about floating... by sheetjs on Tuesday September 16, 2014 @02:20AM (#8323293)
I'm sure it's hiding somewhere in Concrete Mathematics (knuth/graham/patashnik), and I'm sure there are more elegant proofs, but it's not too hard to work out this proof yourself. Here is a hint:

Suppose you were at a point in the mediant algorithm where the two terms were a/b and c/d. Taking the left segment transforms this to [a/b, (a+c)/(b+d)] and taking the right segment transforms this to [(a+c)/(b+d), c/d].

Represent this as a matrix of the form [[a,b],[c,d]]. In this form, what does "take the left segment" look like in terms of a matrix operation? what does "take the right segment" look like? Can you find any useful properties (for example, how do you repeat)

A convenient root matrix is [[0,1],[1,0]]

Re:What every computer programmer should know about floating... by robinhouston on Tuesday September 16, 2014 @03:20AM (#8323408)
Yes, this is explained in http://en.wikipedia.org/wiki/Stern–Brocot_tree

Such a beautiful circle of ideas!