Home > project euler, python > Decimal expansion of the digits of a fraction

Decimal expansion of the digits of a fraction

Problem
If you want to expand the digits of a fraction to arbitrary precision (for instance “find 100 digits of the fraction 1/7“), floating point division won’t work since its precision is limited:

>>> 1/7.0
0.14285714285714285

This problem is related to Problem 26 in Project Euler.

Solution
Let’s see the fraction 1/7. 1 divided by 7 is 0, the remainder is 1. Now repeat the following steps: multiply the remainder (here 1) by 10 and divide it by 7 (result: 1), the remainder is 3. Multiply 3 by 10 and divide by 7, etc. See the process in the following table:

(1 * 10) / 7 = 1 * 7 + 3
(3 * 10) / 7 = 4 * 7 + 2
(2 * 10) / 7 = 2 * 7 + 6
(6 * 10) / 7 = 8 * 7 + 4
(4 * 10) / 7 = 5 * 7 + 5
(5 * 10) / 7 = 7 * 7 + 1
(1 * 10) / 7 = 1 * 7 + 3
(3 * 10) / 7 = 4 * 7 + 2

The numbers in bold are exactly the first few digits of 1/7 = 0.14285714

Python code #1
Here is the implementation of this method:

#!/usr/bin/env python

PRECISION = 100
SHOW_ZEROS = False

def decimal_expansion(a, b):
    q = a/b
    r = a%b

    s1 = str(q)
    l2 = []
    for i in range(PRECISION):
        a = r * 10
        q = a/b
        r = a%b
        l2.append(q)

        if r == 0 and not SHOW_ZEROS:
            break

    s2 = ''.join([str(x) for x in l2])
    return s1, s2

def main():
    a = 1
    b = 7

    s1, s2 = decimal_expansion(a, b)
    print "{0}.{1}".format(s1, s2)

if __name__ == "__main__":
    main()

Python code #2
There is an easier way: the standard library contains a module called “decimal” that provides support for decimal floating point arithmetic.

#!/usr/bin/env python

from decimal import getcontext, Decimal

PRECISION = 100

def main():
    a = 1
    b = 7

    getcontext().prec = PRECISION
    result = Decimal(a) / Decimal(b)
    s = str(result)
    print s

if __name__ == "__main__":
    main()

Credits
I’ve read about this decimal expansion method in this post.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: