Find rational approximation to given real number¶ ↑

Convert Float or String to Fraction with given denominator maximum.

Math::Fraction.new(0.2)               # => Fraction (1/5)
Math::Fraction.new("-3 1/8")          # => Fraction (-3 1/8)

Math::Fraction.new(0.333)             # => Fraction (1/3)
Math::Fraction.new("0.333")           # => Fraction (1/3)
Math::Fraction.new(0.33, 100)         # => Fraction (33/100)
Math::Fraction.new(1.to_f / 3)        # => Fraction (1/3)

Math::Fraction.new(0.2).to_s          # => String "1/5"
Math::Fraction.new(1.2).to_s          # => String "1 1/5"
Math::Fraction.new(1.2).to_r          # => Rational (6/5)
Math::Fraction.new(1.2).to_a          # => Array [1, 1, 5]
Math::Fraction.new("0.333").to_a      # => Array [0, 1, 3]

Math::Fraction.new(0.2, 100).to_r     # => Rational (1/5)
Math::Fraction.new(0.33, 10).to_r     # => Rational (1/3)
Math::Fraction.new(0.33, 100).to_r    # => Rational (33/100)

# Built-in
1.1.to_r # => (2476979795053773/2251799813685248)

# Math::Fraction with big max denominator
Math::Fraction.new(1.1, 1_000_000_000_000_000_000).to_r  # => (11/10)

gem install frac

Idea and most implementation from www.ics.uci.edu/~eppstein/numth/frap.c

Based on the theory of continued fractions

if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))

then best approximation is found by truncating this series (with some adjustments in the last term).

Note the fraction can be recovered as the first column of the matrix

( a1 1 ) ( a2 1 ) ( a3 1 ) ...
( 1  0 ) ( 1  0 ) ( 1  0 )

Instead of keeping the sequence of continued fraction terms, we just keep the last partial product of these matrices.

Frac is released under the MIT license.