# Helper function to solve Project Euler question 26

Project Euler problem 26 asks us to:

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

I wrote this function in Python to find the decimal representation of a rational number p/q. How can I improve it? Also suggest good coding styles.

#! /usr/bin/env python
# -*- coding - utf-8 -*-

"""This program converts a rational number
into its decimal representation.

A rational number is a number of the form p/q
where p and q are integers and q is not zero.
The decimal representation of a rational number
is either terminating or non-terminating but
repeating.

"""

def gcd(a, b):
"""Computes gcd of a, b
using Euclid algorithm.

"""

if not isinstance(a, int) or not isinstance(b, int):
return None

a = abs(a)
b = abs(b)

while b != 0:
a, b = b, a % b

return a

def decimal(p, q):
"""Computes the decimal representation
of the rational number p/q. If the
representation is non-terminating, then
the recurring part is enclosed in parentheses.
The result is returned as a string.

"""

if not isinstance(p, int) or not isinstance(q, int):
return ''

if q == 0:
return ''

abs_p = abs(p)
abs_q = abs(q)

s = (p / abs_p) * (q / abs_q)
g = gcd(abs_p, abs_q)

p = abs_p / g
q = abs_q / g

rlist = []
qlist = []

quotient, remainder = divmod(p, q)
qlist.append(quotient)
rlist.append(remainder)

if remainder == 0:
return str(quotient)

while remainder != 0:
remainder *= 10
quotient, remainder = divmod(remainder, q)
qlist.append(quotient)

if remainder in rlist:
break
else:
rlist.append(remainder)

qlist = map(str, qlist)

if remainder:
recur_index = rlist.index(remainder) + 1
dstring = qlist[0] + '.' + ''.join(qlist[1:recur_index]) + \
'(' + ''.join(qlist[recur_index:]) + ')'

if s < 0:
dstring = '-' + dstring
else:
dstring = qlist[0] + '.' + ''.join(qlist[1:])

if s < 0:
dstring = '-' + dstring

return dstring

if __name__ == '__main__':
p = raw_input('p: ')
q = raw_input('q: ')

try:
p = int(p)
q = int(q)

if q == 0:
raise ValueError

print '%d/%d =' % (p, q), decimal(p, q)
except ValueError:
print 'invalid input'

• Probably not worth an actual answer but gcd and decimal should probably raise ValueError if type is wrong or q is 0. Also, you are computing much more than what you realy need for the problem 26. Actual solution should be much simpler. – SylvainD Jan 20 '14 at 9:18
• How can I simplify it to just solve the problem 26? – ajay Jan 20 '14 at 9:31
• Do you really have to care that a and b are ints? – cHao Jan 20 '14 at 21:33
• gcd is defined for ints only, so yes. – ajay Jan 21 '14 at 6:06

Trying to generate the actual string representation is interesting to understand the problem but you do not need to keep all that complexity in your code for problem 26. Indeed, you are only interested in the length of the cycle for 1/d. Thus, what I did was to :

• remove all the logic corresponding to string construction at the end of the function
• simplify argument handling by removing p (always 1) and considering only positive q (renamed d).
• notice that we can actually return the value directly from the while loop and 0 if we get out of the loop.
• notice that we don't actually need the content of qlist but we do need its length.
• notice that the first iteration is somehow just an iteration like the other to remove a bit of code.
• notice that we don't need the quotients anymore

At the end, here's what the code is like :

def cycle_length(d):
"""Computes the length of the recurring cycle in the decimal representation
of the rational number 1/d if any, 0 otherwise
"""

if not isinstance(d, int) or d <= 0:
raise ValueError("cycle_length(d): d must be a positive integer")

rlist = []
qlist_len = 0
remainder = 1

while remainder:
remainder = remainder % d
if remainder in rlist:
return qlist_len - rlist.index(remainder)
rlist.append(remainder)
remainder *= 10
qlist_len+=1

return 0

if __name__ == '__main__':
for d in range(1,20): #d = raw_input('d: ')
try:
print '1/%s =' % (d), cycle_length(int(d))
except ValueError:
print 'invalid input'

• Won't your remainder overflow if the cycle is long enough? – ChrisWue Jan 20 '14 at 19:26
• Integers do not overflow in Python, do they ? – SylvainD Jan 21 '14 at 8:34
• @Josey, Ah true, didn't realize that they are arbitrary precision. – ChrisWue Jan 21 '14 at 8:45

I'm just going to comment on your gcd function.

1. The docstring mixes up the function's interface ("computes gcd of a, b") with its implementation ("using Euclidean algorithm"). It's best to restrict the docstring to the interface (which is what the user needs to know); if you also need to document the implementation, put it in comments.

2. Your gcd implementation returns None if its arguments are not integers. This behaviour should be mentioned in the docstring.

3. But returning exceptional values is generally a bad idea: it pushes the complexity of error handling onto the caller, where it would be easy to forget to do the checking. And in fact you have failed to check that the result is not None:

g = gcd(abs_p, abs_q)
p = abs_p / g   # What if g is None here?


It is better for a function to raise an exception if it is given the wrong arguments: that way the caller doesn't need to take any special precautions, but the error is reliably detected and reported.

4. The test isinstance(a, int) is too restrictive. Euclid's GCD algorithm will work on other kinds of numbers too, and it would be nice to be able to support:

>>> from fractions import Fraction
>>> gcd(Fraction(1, 3), Fraction(1,4))
Fraction(1, 12)


or:

>>> from decimal import Decimal
>>> gcd(Decimal('11.1'), Decimal('2.1'))
Decimal('0.3')


instead of having to write separate gcd implementations for these other types.

So in fact the best thing to do is not to have any type-checking at all in your gcd function. If someone calls it with the wrong type of object, they will get a TypeError:

>>> gcd('hello', 'world')
Traceback (most recent call last):
...
TypeError: not all arguments converted during string formatting

5. You call abs on the arguments a and b. But in fact you only ever call gcd with arguments that have non-negative values already. So the extra calls to abs are wasted.

6. So in summary, I would write the gcd function like this:

def gcd(a, b):
"""Return the greatest common divisor of a and b."""
while b != 0:
a, b = b, a % b
return a

7. But in fact Python already has a built-in gcd function (in the fractions module), so all you actually have to do is write:

from fractions import gcd