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