Project P067
Fraction tutor
A fraction put in lowest terms with every step of Euclid's algorithm shown, its decimal with the repeating part found by long division, a repeating decimal like 0.1(6) turned back into a fraction, the continued fraction with its convergents, and Egyptian fractions by Fibonacci's greedy rule.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
A fraction put in lowest terms, with every step of Euclid's algorithm shown. Its decimal, with the repeating part found by long division. A repeating decimal like 0.1(6) turned back into a fraction. The continued fraction with its convergents, and an Egyptian fraction - a sum of different unit fractions - by Fibonacci's greedy rule. All the arithmetic is on whole numbers, so every answer is exact.
main.eml- the menu, reading fractions and decimals, and the messagesrational.eml- exact division, Euclid's algorithm, decimals both ways, continued fractions with their convergents, and Egyptian fractions
How each part works:
- Lowest terms: as in the corpus case
euclidean-gcd-recursive, gcd(a, b) = gcd(b, a mod b) until the remainder is 0, and each step a = q x b + r is printed. Top and bottom are divided by the last remainder that was not 0. The corpus casefraction-arithmeticreduces its fractions the same way after every operation. - Division is exact long division by doubling, never a float: a / b goes through a float, which rounds once numbers pass 2^53.
- To a decimal: long division that remembers each remainder and the digit it came at. When a remainder comes back, the digits from that point on repeat: 7/12 = 0.58(3). The division ends only if a remainder reaches 0, and that happens exactly when the reduced denominator has no prime factor but 2 and 5.
- From a decimal: 1.2(45) is 12/10 plus 45/990 (the repeating digits over as many 9s, shifted past the fixed digits), reduced to 137/110. 0.(9) comes back as 1.
- Continued fraction: take the whole part (rounded down, so -7/3 starts at -3), turn what is left upside down, and repeat - the same divisions as Euclid's algorithm. Convergents come from p = a p' + p'', q = a q' + q''. 103993/33102 gives 3, 22/7, 333/106 and 355/113, the convergents of pi. Each convergent is closer than any fraction with a smaller denominator. From the second on, each is also the closest fraction with a denominator no larger than its own; the first need not be: -7/3 starts at -3, though -2 is closer.
- Egyptian fraction: the greedy rule takes the largest unit fraction that fits, 1/ceil(d/n), and repeats on what is left. The numerator left over is smaller every time, so the rule always ends, but the denominators can grow fast: 5/121 ends with a 25-digit one. The program stops at 12 terms and says so.
What is checked: menu choices 1 to 6; a fraction as a/b or a whole number, with a minus sign allowed, up to 12 digits on each side and a bottom that is not 0; a decimal as digits, a point if there is a fraction part, and repeating digits in brackets after it, up to 1000 digits; for an Egyptian fraction, a value strictly between 0 and 1. An empty answer cancels.
Sessions: sessions/basic.in gives: - 1071/462 = 51/22, through three steps of Euclid's algorithm; - the decimals of 1/7, 7/12 and 3/8 - repeating 6 at a time, repeating after a fixed part, and ending; - 0.1(6) = 1/6 and 1.2(45) = 137/110; - the continued fractions of 415/93 and 103993/33102; - 4/13 = 1/4 + 1/18 + 1/468, and the five greedy terms of 5/121.
sessions/bad-input.in gives: - menu choices 0 and x; - the fractions abc, 1/0, 1/2/3 and a 13-digit top, then a cancel; - 0/5, and the decimal of -22/7; - the decimals abc, .5 and "1.(", then a cancel; - the continued fraction of -7/3, starting below at -3; - 3/2 and -1/2 refused for an Egyptian fraction.
Built on the verified corpus cases euclidean-gcd-recursive (Euclid's algorithm by recursion) and fraction-arithmetic (fractions held as [numerator, denominator] pairs, reduced by their greatest common divisor).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Fraction tutor ==
Fractions in lowest terms, their decimals, continued fractions and Egyptian fractions.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 0
Pick a number from 1 to 6.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> x
Pick a number from 1 to 6.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 1
fraction> abc
Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0.
fraction> 1/0
Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0.
fraction> 1/2/3
Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0.
fraction> 1234567890123/1
Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0.
fraction>
Cancelled.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 1
fraction> 0/5
0 = 0 x 5 + 0
0/5 is 0.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 2
fraction> -22/7
-22/7 = -3.(142857)
The digits 142857 repeat for ever, 6 at a time.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 3
decimal (repeating digits in brackets, like 0.1(6))> abc
Type digits, with a point if there is a fraction part and any repeating digits in brackets after it - like 3, 2.5, 0.(3) or 1.2(45).
decimal (repeating digits in brackets, like 0.1(6))> .5
Type digits, with a point if there is a fraction part and any repeating digits in brackets after it - like 3, 2.5, 0.(3) or 1.2(45).
decimal (repeating digits in brackets, like 0.1(6))> 1.(
Type digits, with a point if there is a fraction part and any repeating digits in brackets after it - like 3, 2.5, 0.(3) or 1.2(45).
decimal (repeating digits in brackets, like 0.1(6))>
Cancelled.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 4
fraction> -7/3
-7/3 = [-3; 1, 2]
Convergents - each closer than any fraction with a smaller denominator:
-3, -2, -7/3
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 5
fraction between 0 and 1> 3/2
Egyptian fractions here are for a fraction strictly between 0 and 1.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 5
fraction between 0 and 1> -1/2
Egyptian fractions here are for a fraction strictly between 0 and 1.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 6
Bye.
What was typed (24 lines)
0
x
1
abc
1/0
1/2/3
1234567890123/1
1
0/5
2
-22/7
3
abc
.5
1.(
4
-7/3
5
3/2
5
-1/2
6
basic
interpreter: byte-equal== Fraction tutor ==
Fractions in lowest terms, their decimals, continued fractions and Egyptian fractions.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 1
fraction> 1071/462
1071 = 2 x 462 + 147
462 = 3 x 147 + 21
147 = 7 x 21 + 0
The greatest common divisor is 21, so 1071/462 = 51/22.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 2
fraction> 1/7
1/7 = 0.(142857)
The digits 142857 repeat for ever, 6 at a time.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 2
fraction> 7/12
7/12 = 0.58(3)
The digit 3 repeats for ever.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 2
fraction> 3/8
3/8 = 0.375
The decimal ends: the denominator has no prime factor but 2 and 5.
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 3
decimal (repeating digits in brackets, like 0.1(6))> 0.1(6)
0.1(6) = 1/6
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 3
decimal (repeating digits in brackets, like 0.1(6))> 1.2(45)
1.2(45) = 137/110
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 4
fraction> 415/93
415/93 = [4; 2, 6, 7]
Convergents - each closer than any fraction with a smaller denominator:
4, 9/2, 58/13, 415/93
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 4
fraction> 103993/33102
103993/33102 = [3; 7, 15, 1, 292]
Convergents - each closer than any fraction with a smaller denominator:
3, 22/7, 333/106, 355/113, 103993/33102
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 5
fraction between 0 and 1> 4/13
4/13 = 1/4 + 1/18 + 1/468
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 5
fraction between 0 and 1> 5/121
5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit
choice> 6
Bye.
What was typed (21 lines)
1
1071/462
2
1/7
2
7/12
2
3/8
3
0.1(6)
3
1.2(45)
4
415/93
4
103993/33102
5
4/13
5
5/121
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P067 fraction tutor: a fraction in lowest terms with Euclid's steps shown,
# its decimal with the repeating part found, a decimal - repeating or not -
# turned back into a fraction, the continued fraction with its convergents,
# and Egyptian fractions.
import rational
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def whole(s):
# A whole number, maybe negative, of up to 12 digits, as [ok, value].
s => digits
1 => sg
if len(s) > 1 and s[0] == "-":
s[1:len(s)] => digits
-1 => sg
if digits == "" or len(digits) > 12:
return [False, 0]
for c in digits:
if not (c >= "0" and c <= "9"):
return [False, 0]
return [True, sg * int(digits)]
def ask_fraction(prompt):
# [n, d] with d != 0 from "a/b" or a whole number, or [] when empty.
while True:
trim(input(prompt)) => s
if s == "":
return []
0 => k
while k < len(s) and s[k] != "/":
k + 1 => k
whole(trim(s[0:k])) => n
[True, 1] => d
if k < len(s):
whole(trim(s[k + 1:len(s)])) => d
if n[0] and d[0] and d[1] != 0:
return [n[1], d[1]]
"Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0." ^0
def text(f):
if f[1] == 1:
return str(f[0])
return str(f[0]) + "/" + str(f[1])
def simplify():
ask_fraction("fraction> ") => f
if len(f) == 0:
"Cancelled." ^0
return
rational.reduced(f[0], f[1]) => r
for st in r[1]:
(" " + str(st[0]) + " = " + str(st[2]) + " x " + str(st[1]) + " + " + str(st[3])) ^0
if f[0] == 0:
("0/" + str(abs(f[1])) + " is 0.") ^0
return
("The greatest common divisor is " + str(r[2]) + ", so " + text(f) + " = " + text(r[0]) + ".") ^0
def to_decimal():
ask_fraction("fraction> ") => f
if len(f) == 0:
"Cancelled." ^0
return
rational.reduced(f[0], f[1])[0] => r
rational.decimal(r[0], r[1]) => parts
(text(r) + " = " + rational.decimal_text(parts)) ^0
if len(parts[2]) == 1:
("The digit " + parts[2] + " repeats for ever.") ^0
elif parts[2] != "":
("The digits " + parts[2] + " repeat for ever, " + str(len(parts[2])) + " at a time.") ^0
else:
"The decimal ends: the denominator has no prime factor but 2 and 5." ^0
def from_decimal():
while True:
trim(input("decimal (repeating digits in brackets, like 0.1(6))> ")) => s
if s == "":
"Cancelled." ^0
return
rational.from_decimal(s) => f
if len(f) > 0:
(s + " = " + text(f)) ^0
return
"Type digits, with a point if there is a fraction part and any repeating digits in brackets after it - like 3, 2.5, 0.(3) or 1.2(45)." ^0
def continued():
ask_fraction("fraction> ") => f
if len(f) == 0:
"Cancelled." ^0
return
rational.reduced(f[0], f[1])[0] => r
rational.continued(r[0], r[1]) => terms
"[" => s
for k in [0:len(terms) - 1]:
if k == 1:
s + "; " => s
elif k > 1:
s + ", " => s
s + str(terms[k]) => s
(text(r) + " = " + s + "]") ^0
"Convergents - each closer than any fraction with a smaller denominator:" ^0
"" => line
for c in rational.convergents(terms):
if line != "":
line + ", " => line
line + text(c) => line
(" " + line) ^0
def egyptian():
ask_fraction("fraction between 0 and 1> ") => f
if len(f) == 0:
"Cancelled." ^0
return
rational.reduced(f[0], f[1])[0] => r
if r[0] <= 0 or r[0] >= r[1]:
"Egyptian fractions here are for a fraction strictly between 0 and 1." ^0
return
rational.egyptian(r[0], r[1]) => e
"" => s
for k in e[0]:
if s != "":
s + " + " => s
s + "1/" + str(k) => s
if e[1]:
(text(r) + " = " + s) ^0
else:
(text(r) + " = " + s + " + ... - the greedy rule has gone 12 terms and the denominators keep growing.") ^0
"== Fraction tutor ==" ^0
"Fractions in lowest terms, their decimals, continued fractions and Egyptian fractions." ^0
True => running
while running:
"" ^0
"1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
simplify()
elif choice == "2":
to_decimal()
elif choice == "3":
from_decimal()
elif choice == "4":
continued()
elif choice == "5":
egyptian()
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import rational
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def whole(s):
digits = s
sg = 1
if len(s) > 1 and s[0] == "-":
digits = s[1:len(s)]
sg = -1
if digits == "" or len(digits) > 12:
return [False, 0]
for c in digits:
if not (c >= "0" and c <= "9"):
return [False, 0]
return [True, sg * int(digits)]
def ask_fraction(prompt):
while True:
s = trim(input(prompt))
if s == "":
return []
k = 0
while k < len(s) and s[k] != "/":
k = k + 1
n = whole(trim(s[0:k]))
d = [True, 1]
if k < len(s):
d = whole(trim(s[k + 1:len(s)]))
if n[0] and d[0] and d[1] != 0:
return [n[1], d[1]]
print("Type a fraction like 1071/462 or -3/4, or a whole number - up to 12 digits each, and the bottom not 0.")
def text(f):
if f[1] == 1:
return str(f[0])
return str(f[0]) + "/" + str(f[1])
def simplify():
f = ask_fraction("fraction> ")
if len(f) == 0:
print("Cancelled.")
return
r = rational.reduced(f[0], f[1])
for st in r[1]:
print(" " + str(st[0]) + " = " + str(st[2]) + " x " + str(st[1]) + " + " + str(st[3]))
if f[0] == 0:
print("0/" + str(abs(f[1])) + " is 0.")
return
print("The greatest common divisor is " + str(r[2]) + ", so " + text(f) + " = " + text(r[0]) + ".")
def to_decimal():
f = ask_fraction("fraction> ")
if len(f) == 0:
print("Cancelled.")
return
r = rational.reduced(f[0], f[1])[0]
parts = rational.decimal(r[0], r[1])
print(text(r) + " = " + rational.decimal_text(parts))
if len(parts[2]) == 1:
print("The digit " + parts[2] + " repeats for ever.")
elif parts[2] != "":
print("The digits " + parts[2] + " repeat for ever, " + str(len(parts[2])) + " at a time.")
else:
print("The decimal ends: the denominator has no prime factor but 2 and 5.")
def from_decimal():
while True:
s = trim(input("decimal (repeating digits in brackets, like 0.1(6))> "))
if s == "":
print("Cancelled.")
return
f = rational.from_decimal(s)
if len(f) > 0:
print(s + " = " + text(f))
return
print("Type digits, with a point if there is a fraction part and any repeating digits in brackets after it - like 3, 2.5, 0.(3) or 1.2(45).")
def continued():
f = ask_fraction("fraction> ")
if len(f) == 0:
print("Cancelled.")
return
r = rational.reduced(f[0], f[1])[0]
terms = rational.continued(r[0], r[1])
s = "["
for k in range(0, len(terms)):
if k == 1:
s = s + "; "
elif k > 1:
s = s + ", "
s = s + str(terms[k])
print(text(r) + " = " + s + "]")
print("Convergents - each closer than any fraction with a smaller denominator:")
line = ""
for c in rational.convergents(terms):
if line != "":
line = line + ", "
line = line + text(c)
print(" " + line)
def egyptian():
f = ask_fraction("fraction between 0 and 1> ")
if len(f) == 0:
print("Cancelled.")
return
r = rational.reduced(f[0], f[1])[0]
if r[0] <= 0 or r[0] >= r[1]:
print("Egyptian fractions here are for a fraction strictly between 0 and 1.")
return
e = rational.egyptian(r[0], r[1])
s = ""
for k in e[0]:
if s != "":
s = s + " + "
s = s + "1/" + str(k)
if e[1]:
print(text(r) + " = " + s)
else:
print(text(r) + " = " + s + " + ... - the greedy rule has gone 12 terms and the denominators keep growing.")
print("== Fraction tutor ==")
print("Fractions in lowest terms, their decimals, continued fractions and Egyptian fractions.")
running = True
while running:
print("")
print("1) lowest terms 2) to a decimal 3) from a decimal 4) continued fraction 5) Egyptian fraction 6) quit")
choice = trim(input("choice> "))
if choice == "1":
simplify()
elif choice == "2":
to_decimal()
elif choice == "3":
from_decimal()
elif choice == "4":
continued()
elif choice == "5":
egyptian()
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
rational.eml
eml# P067 fraction tutor - Euclid's steps, decimals with their repeating part,
# continued fractions and Egyptian fractions. Fractions are [n, d] with
# d > 0. Egyptian fractions can reach denominators far past what a float
# holds, so whole-number division is written out exactly.
def div(a, b):
# a // b for a >= 0 and b > 0, exact at any size: long division by
# doubling, taking away the largest b * 2^k that still fits.
0 => q
while a >= b:
b => m
1 => k
while m + m <= a:
m + m => m
k + k => k
a - m => a
q + k => q
return q
def floor_div(n, d):
# n // d for any n and d > 0: rounding down, also below zero.
if n >= 0:
return div(n, d)
return 0 - div(0 - n + d - 1, d)
def euclid(a, b, steps):
# The corpus case euclidean-gcd-recursive: gcd(a, b) = gcd(b, a mod b),
# and gcd(a, 0) = a. Each step [a, b, quotient, remainder] is added to
# steps (a one-item list holding the list, so every call adds to it).
if b == 0:
return a
steps[0] + [[a, b, div(a, b), a % b]] => steps[0]
return euclid(b, a % b, steps)
def reduced(n, d):
# [n, d] in lowest terms with d > 0, and the Euclid steps that found the
# divisor.
[[]] => steps
euclid(abs(n), abs(d), steps) => g
if g == 0:
1 => g
if d < 0:
0 - n => n
0 - d => d
return [[div(abs(n), g) * sign(n), div(d, g)], steps[0], g]
def sign(n):
if n < 0:
return -1
return 1
def decimal(n, d):
# The decimal of n/d (d > 0) as [whole part text, digits before the
# repeat, repeating digits]: long division, remembering at which digit
# each remainder first came - when one comes again, the digits since
# then repeat for ever. A remainder of 0 means the decimal ends.
"" => minus
if n < 0:
"-" => minus
abs(n) => a
str(div(a, d)) => whole
a % d => r
{} => seen
"" => digits
while r != 0 and not (r in seen):
len(digits) => seen[r]
r * 10 => r
digits + str(div(r, d)) => digits
r % d => r
if r == 0:
return [minus + whole, digits, ""]
seen[r] => start
return [minus + whole, digits[0:start], digits[start:len(digits)]]
def decimal_text(parts):
parts[0] => s
if parts[1] != "" or parts[2] != "":
s + "." + parts[1] => s
if parts[2] != "":
s + "(" + parts[2] + ")" => s
return s
def from_decimal(s):
# "0.125", "-2.5", "0.(3)", "0.1(6)", "3" as an exact fraction [n, d], or
# []. The repeating part is in brackets: 0.1(6) = 1/6.
1 => sg
if len(s) > 0 and s[0] == "-":
-1 => sg
s[1:len(s)] => s
"" => whole
"" => fixed
"" => rep
0 => state
for ch in s:
if ch >= "0" and ch <= "9":
if state == 0:
whole + ch => whole
elif state == 1:
fixed + ch => fixed
elif state == 2:
rep + ch => rep
else:
return []
elif ch == "." and state == 0:
1 => state
elif ch == "(" and state == 1:
2 => state
elif ch == ")" and state == 2 and rep != "":
3 => state
else:
return []
# Whole numbers have no size limit, so long repeats (1/97 has 96 digits)
# read fine; 1000 digits is a guard against nonsense input.
if whole == "" or state == 2 or len(whole) + len(fixed) + len(rep) > 1000:
return []
# x = whole.fixed(rep): with k fixed digits and m repeating ones,
# x = (whole fixed rep - whole fixed) / (10^k (10^m - 1)); with no
# repeat, x = whole fixed / 10^k.
1 => tk
for c in fixed:
tk * 10 => tk
int(whole + fixed) => wf
if rep == "":
return reduced(sg * wf, tk)[0]
1 => tm
for c in rep:
tm * 10 => tm
int(whole + fixed + rep) => wfr
return reduced(sg * (wfr - wf), tk * (tm - 1))[0]
def continued(n, d):
# [a0; a1, a2, ...] for n/d by the same divisions as Euclid's algorithm:
# each quotient is the next term, rounding down (so a0 can be negative).
[] => terms
while d != 0:
floor_div(n, d) => a
terms + [a] => terms
n - a * d => r
d => n
r => d
return terms
def convergents(terms):
# p_k / q_k from p_k = a_k p_(k-1) + p_(k-2), likewise q - each the best
# fraction with a denominator that small.
[] => out
1 => p1
0 => p2
0 => q1
1 => q2
for a in terms:
a * p1 + p2 => p
a * q1 + q2 => q
out + [[p, q]] => out
p1 => p2
p => p1
q1 => q2
q => q1
return out
def egyptian(n, d):
# 0 < n/d < 1 as a sum of different unit fractions by Fibonacci's greedy
# rule: take the largest 1/k not above what is left, and repeat. It
# always ends, since each step leaves a smaller numerator. Stops after
# 12 terms (returning [] for the rest) - greedy denominators can grow
# very fast.
[] => out
while n > 0:
if len(out) == 12:
return [out, False]
div(d + n - 1, n) => k
out + [k] => out
n * k - d => n
d * k => d
reduced(n, d)[0] => f
f[0] => n
f[1] => d
return [out, True]
Python projection (rational.py)
def div(a, b):
q = 0
while a >= b:
m = b
k = 1
while m + m <= a:
m = m + m
k = k + k
a = a - m
q = q + k
return q
def floor_div(n, d):
if n >= 0:
return div(n, d)
return 0 - div(0 - n + d - 1, d)
def euclid(a, b, steps):
if b == 0:
return a
steps[0] = steps[0] + [[a, b, div(a, b), a % b]]
return euclid(b, a % b, steps)
def reduced(n, d):
steps = [[]]
g = euclid(abs(n), abs(d), steps)
if g == 0:
g = 1
if d < 0:
n = 0 - n
d = 0 - d
return [[div(abs(n), g) * sign(n), div(d, g)], steps[0], g]
def sign(n):
if n < 0:
return -1
return 1
def decimal(n, d):
minus = ""
if n < 0:
minus = "-"
a = abs(n)
whole = str(div(a, d))
r = a % d
seen = {}
digits = ""
while r != 0 and not r in seen:
seen[r] = len(digits)
r = r * 10
digits = digits + str(div(r, d))
r = r % d
if r == 0:
return [minus + whole, digits, ""]
start = seen[r]
return [minus + whole, digits[0:start], digits[start:len(digits)]]
def decimal_text(parts):
s = parts[0]
if parts[1] != "" or parts[2] != "":
s = s + "." + parts[1]
if parts[2] != "":
s = s + "(" + parts[2] + ")"
return s
def from_decimal(s):
sg = 1
if len(s) > 0 and s[0] == "-":
sg = -1
s = s[1:len(s)]
whole = ""
fixed = ""
rep = ""
state = 0
for ch in s:
if ch >= "0" and ch <= "9":
if state == 0:
whole = whole + ch
elif state == 1:
fixed = fixed + ch
elif state == 2:
rep = rep + ch
else:
return []
elif ch == "." and state == 0:
state = 1
elif ch == "(" and state == 1:
state = 2
elif ch == ")" and state == 2 and rep != "":
state = 3
else:
return []
if whole == "" or state == 2 or len(whole) + len(fixed) + len(rep) > 1000:
return []
tk = 1
for c in fixed:
tk = tk * 10
wf = int(whole + fixed)
if rep == "":
return reduced(sg * wf, tk)[0]
tm = 1
for c in rep:
tm = tm * 10
wfr = int(whole + fixed + rep)
return reduced(sg * (wfr - wf), tk * (tm - 1))[0]
def continued(n, d):
terms = []
while d != 0:
a = floor_div(n, d)
terms = terms + [a]
r = n - a * d
n = d
d = r
return terms
def convergents(terms):
out = []
p1 = 1
p2 = 0
q1 = 0
q2 = 1
for a in terms:
p = a * p1 + p2
q = a * q1 + q2
out = out + [[p, q]]
p2 = p1
p1 = p
q2 = q1
q1 = q
return out
def egyptian(n, d):
out = []
while n > 0:
if len(out) == 12:
return [out, False]
k = div(d + n - 1, n)
out = out + [k]
n = n * k - d
d = d * k
f = reduced(n, d)[0]
n = f[0]
d = f[1]
return [out, True]