Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Find rational approximation to given real number (ruby c extension). Float to Rational

branch: master

Fetching latest commit…

Octocat-spinner-32-eaf2f5

Cannot retrieve the latest commit at this time

Octocat-spinner-32 ext
Octocat-spinner-32 lib
Octocat-spinner-32 test
Octocat-spinner-32 .gitignore
Octocat-spinner-32 CHANGELOG.md
Octocat-spinner-32 Gemfile
Octocat-spinner-32 README.rdoc
Octocat-spinner-32 Rakefile
Octocat-spinner-32 VERSION
Octocat-spinner-32 frac.gemspec
README.rdoc

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)

Difference from Ruby 1.9 built-in Float#to_r

# 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)

Installation

gem install frac

Source

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.

License

Frac is released under the MIT license.

Something went wrong with that request. Please try again.