Helper function to solve Project Euler question 26

Question

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'

Answer 1

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'

Answer 2

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