Fractions in Ruby
For a cooking website I recently worked on, I needed to display decimal floating point numbers as fractions. I needed to come up with the fraction closest to what the user typed. For example, 0.33 should resolve to ⅓. When I googled for a solution, most of the code I found was slow, buggy, and too precise (returning 33/100 for the above example.)
I decided to widen my search to C, and found a piece of code on Stack Overflow written by David Eppstein in 1993. It uses the theory of continued fractions to approach the correct value, but stops when the denominator reaches some value.
The limitation of such an algorithm is that we can't choose to leave out unnatural denominators (that's a topic for some future post: why don't people like to use 7 as a denominator?).
Anyway, I ended up wrapping up Eppstein's code in a Ruby gem entitled "fraction" and throwing it up on Gemcutter in case anyone needs similar functionality. Using this gem is easy:
require 'fraction' num, den = 0.33.fraction # num==1, den==3 # You can also get the error num,den,err = 0.33.fraction #=> [1, 3, -0.0033333333333333] # you can choose a different maximum denominator than the default value of 10: num, den = 0.51.fraction(100) #[51, 100, 0.0]
You can get fraction from gemcutter
Here is a quick test of this code:
require 'rubygems'
require 'fraction'
# Google for "ruby fraction" and you find this code
class Float
def number_decimal_places
self.to_s.length-2
end
def to_fraction
higher = 10**self.number_decimal_places
lower = self*higher
gcden = greatest_common_divisor(higher, lower)
return (lower/gcden).round, (higher/gcden).round
end
private
def greatest_common_divisor(a, b)
while a%b != 0
a,b = b.round,(a%b).round
end
return b
end
end
starttime = Time.now
1_000_000.times do
n,d=0.5.to_fraction
end
endtime = Time.now
feeling_lucky=endtime-starttime
puts "I'm Feeling Lucky: " + feeling_lucky.to_s + "s"
starttime = Time.now
1_000_000.times do
n,d=0.5.fraction
end
endtime = Time.now
fractionmod=endtime-starttime
puts "fraction: " + fractionmod.to_s + "s"
starttime = Time.now
1_000_000.times do
n,d=[1,2]
end
endtime = Time.now
max_speed=endtime-starttime
n,d=(fractionmod-max_speed).fraction
puts "algorithm itself requires only #{n}/#{d} of a second for 1,000,000 iterations"
