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.)
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"
