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:]) + ')'

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

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

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

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

-
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

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

-
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

-
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

StackExchange Code Review Q#39642, answer score: 7