4 ms·

Here is a fun little anecdote you may consider incorporating into part 2: The default Excel number format (known as General) draws numbers with up to 11 charac

by sheetjs 12y ago

Here is a fun little anecdote you may consider incorporating into part 2: The default Excel number format (known as General) draws numbers with up to 11 characters, granular enough to mask the ulps in common numbers like 0.1+0.2. Excel also supports fraction number formats. The format "?/?" writes the closest fraction whose denominator is less than 10. The algorithm used to calculate the fraction seems to agree with the Oliver Aberth paper "A method for exact computation with rational numbers". Based on this algorithm, 0.3 is represented as "2/7" and any number slightly larger than 0.3 is represented as "1/3". Try setting A1 to 0.3, A2 to =0.1+0.2 and change the cell format to Fraction .. Up to one digit. Both cells appear to be 0.3 when rendered under the General format. However, when using the fraction, the cells differ. Google Docs renders both numbers as 2/7, but the XLSX export correctly preserves the IEEE754 numbers. Unfortunately, LibreOffice clobbers the last few bits, leading to incorrect results.

hawkice 12y ago
Fun fact: to find the fraction closest to a number with a denominator that doesn't exceed a certain amount can be generated using the following algorithm: (1) Find the N/1 rationals corresponding to the closest integers on either side of the number. (2) For rationals a/b and c/d, calculate (a + c) / (b + d). This is not a common operation, but you read it right. It'll be between a/b and c/d, and be the number with the smallest denominator between them. (3) Reduce the range to the segment from above containing your number. If the new denominator exceeds your limit, choose the smaller-denominator value. Otherwise, go back to step (2). [There are some delightful proofs of this using tessellation that I strongly encourage you to try to figure out, one of the most interesting puzzles I got from a guy named Anton, the first user of MathOverflow and current Googler.]
- sheetjs 12y ago
  That's commonly referred to as the Mediant algorithm https://en.wikipedia.org/wiki/Mediant_(mathematics) 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 https://github.com/SheetJS/frac implements the mediant as well as the Aberth algorithm.
  - hawkice 12y ago
    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? :)
    - robinhouston 12y ago
      Yes, this is explained in http://en.wikipedia.org/wiki/Stern–Brocot_tree http://en.wikipedia.org/wiki/Stern–Brocot_tree Such a beautiful circle of ideas!
    - sheetjs 12y ago
      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]]
  - jwmerrill 12y ago
    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.
haberman 12y ago
Ha, interesting. This will fit in perfectly with my plans to describe the printing of floating point numbers in detail.

by sheetjs 12y ago

hawkice 12y ago

Fun fact: to find the fraction closest to a number with a denominator that doesn't exceed a certain amount can be generated using the following algorithm: (1) Find the N/1 rationals corresponding to the closest integers on either side of the number. (2) For rationals a/b and c/d, calculate (a + c) / (b + d). This is not a common operation, but you read it right. It'll be between a/b and c/d, and be the number with the smallest denominator between them. (3) Reduce the range to the segment from above containing your number. If the new denominator exceeds your limit, choose the smaller-denominator value. Otherwise, go back to step (2). [There are some delightful proofs of this using tessellation that I strongly encourage you to try to figure out, one of the most interesting puzzles I got from a guy named Anton, the first user of MathOverflow and current Googler.]

sheetjs 12y ago
That's commonly referred to as the Mediant algorithm https://en.wikipedia.org/wiki/Mediant_(mathematics) 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 https://github.com/SheetJS/frac implements the mediant as well as the Aberth algorithm.
- hawkice 12y ago
  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? :)
  - robinhouston 12y ago
    Yes, this is explained in http://en.wikipedia.org/wiki/Stern–Brocot_tree http://en.wikipedia.org/wiki/Stern–Brocot_tree Such a beautiful circle of ideas!
  - sheetjs 12y ago
    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]]
- jwmerrill 12y ago
  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.

haberman 12y ago

Ha, interesting. This will fit in perfectly with my plans to describe the printing of floating point numbers in detail.