[Tutor] converting decimals to fractions

[B***@dana.com]

This is less of a Python question than it is an algorithm question, but it
should still apply since Python has some cool data structures available to
apply to the solution.

I have a script that does some length calculations and prints out results
in decimal inches. (e.g. 1.537", 4.230", etc.) Converting these to
fractions of an inch is simple enough (e.g. 1+537/1000, 4+23/100, etc.),
but suppose I only want answers in the standard fractions of an inch (i.e.
fourths of and inch, thirty-seconds of an inch, etc.).

I'm looking for suggestions on implementation. My approach is to use a
lookup table, probably in dictionary form. The table will contain "bins"
of fractions in increments of 1/32 with upper and lower limits for the
decimal equivlent. The limits would be calculated by adding and
subtracting 1/64 to the base number. For instance, a given decimal would
be determined to be 3/32 if the decimal equivalent was between
0.09375+0.015625 and 0.09375-0.015625.

The program could create the lookup table right at the beginning, and the
table would hold all of these upper and lower limits along with their
corresponding fraction. The fraction itself (in string form) would
probably be the dictionary key. To convert a decimal, I would just use a
loop to compare the number to each set of limits.

Does anyone have a better method for this?

Thanks,
Blake Garretson

[Tim Peters]

Post by B***@dana.com
This is less of a Python question than it is an algorithm question, but
it should still apply since Python has some cool data structures
available to apply to the solution.

In this case, I think some simple arithmetic will suffice.

Post by B***@dana.com
I have a script that does some length calculations and prints out results
in decimal inches. (e.g. 1.537", 4.230", etc.) Converting these to
fractions of an inch is simple enough (e.g. 1+537/1000, 4+23/100, etc.),
but suppose I only want answers in the standard fractions of an inch
(i.e. fourths of and inch, thirty-seconds of an inch, etc.).

The "etc" is important: how far down do you want to go? That is, is 1/32
the smallest granularity you care about?

BTW, in my college days, I applied for a job on the Harley-Davidson assembly
line. I barely made it: during the interview, the foreman looked me in the
eyes and demanded "how many sixty-fourths of an inch are in an inch?". It
seemed like *such* a stupid question, I asked him to repeat it. He did.
Then it seemed like it must be a trick question, and my mind raced futilely
looking for "the trick". After about a minute, he lost patience and asked
for my answer. Hesitant and defeated, I weakly asked "umm, 64?". "Right!"
he beamed, "Now let's see if you can read a micrometer.".

def tofrac(x, largest_denominator=32):
"""Return triple (i, j, k) where x ~= i + j/k.

x >= 0 is required.
i, j and k are integers >= 0, and k is > 0.
j and k have no factors in common, unless j is 0.

Optional argument largest_denominator (default 32) should be a
power of 2, and is the largest value k can have.
"""

if not x >= 0:
raise ValueError("x must be >= 0")
scaled = int(round(x * largest_denominator))
whole, leftover = divmod(scaled, largest_denominator)
if leftover:
while leftover % 2 == 0:
leftover >>= 1
largest_denominator >>= 1
return whole, leftover, largest_denominator

format = "%d %d/%d"
print format % tofrac(1.537)
print format % tofrac(4.230)
print format % tofrac(4.230, 128)
print format % tofrac(4.240)
print format % tofrac(8)

That prints

1 17/32
4 7/32
4 29/128
4 1/4
8 0/32

Post by B***@dana.com
I'm looking for suggestions on implementation. My approach is to use a
lookup table, probably in dictionary form. The table will contain "bins"
of fractions in increments of 1/32 with upper and lower limits for the
decimal equivlent. The limits would be calculated by adding and
subtracting 1/64 to the base number. For instance, a given decimal
would be determined to be 3/32 if the decimal equivalent was between
0.09375+0.015625 and 0.09375-0.015625.

The code above gets the same effect, pretty much by answering the question
"How many 32nds of an inch are in an inch?" <wink>: multiply by 32, round
to an int, then take the quotient and remainder from dividing by 32.

[B***@dana.com]

Thanks, Tim! I have an uncanny knack for finding a brute force method even
if there is a more obvious and very elegant solution available. Thanks for
the great code.

Blake Garretson




"Tim Peters"
<***@home To: <***@dana.com>, <***@python.org>
.com> cc:
Subject: RE: [Tutor] converting decimals to fractions
10/08/2001
01:47 PM

Post by Tim Peters
"""Return triple (i, j, k) where x ~= i + j/k.
x >= 0 is required.
i, j and k are integers >= 0, and k is > 0.
j and k have no factors in common, unless j is 0.
Optional argument largest_denominator (default 32) should be a
power of 2, and is the largest value k can have.
"""
raise ValueError("x must be >= 0")
scaled = int(round(x * largest_denominator))
whole, leftover = divmod(scaled, largest_denominator)
leftover >>= 1
largest_denominator >>= 1
return whole, leftover, largest_denominator

[Kirby Urner]

Probably easier to calculate on the fly, vs. do a
lookup table.

One algorithm is: take the decimal part of n and
convert it to the nearest x/32. Then reduce x/32 to
lowest terms by dividing x, 32 by their gcd (greatest
common divisor).

def div32(n):
"x for closest x/32"
return round((n-int(n))*1000/32.)

def gcd(a,b):
"Euclidean Algorithm (recursive form)"
if b==0: return a
else: return gcd(b,a%b)

def mkinch(n):
numer = div32(n)
thegcd = gcd(numer,32)
return "%s %s/%s" % \
(int(n),int(numer/thegcd),int(32/thegcd))

mkinch(1.133)

'1 1/8'

mkinch(1.185)

'1 3/16'

mkinch(1.1)

'1 3/32'

Since writing this, I've seen Tim's. His is no doubt
faster, as it takes advantage of the base 2 aspect of
your problem thru bit shifting.

Kirby

[a***@bt.com]

Hi Blake,

Two points to make:

1) Your method will work.

2) Its not the most efficient way to use a dictionary.

Given (2), another approach which might(I haven't tested
this!) be more efficient is to extract the fractional part,
round to the required precision - looks like 6 digits then
do a binary chop search on a list of tuples. The
indexing/sequential access of the list might in this
case be better than searching the values of a dictionary.
(Wth 64 entries your *worst* case should be 6 tests...)

The tuples would of course contain the fraction string
and the equivalent number equivalent. As ever with floats
beware of rounding errors.

Just some thoughts.

Alan G.