Project P081
Big numbers
Whole numbers of any size kept exact: factorials with their digits and trailing zeros checked by Legendre's formula, binomial coefficients built from prime powers without dividing, powers by repeated squaring, and long division of one big number by another.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
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
Whole numbers of any size, kept exact. Factorials, with their digits and trailing zeros checked against Legendre's formula; binomial coefficients built from prime powers, without dividing; powers by repeated squaring; and long division of one big number by another.
main.eml- the menu, reading numbers, and the reportsbignum.eml- long division, factorials, the sieve, Legendre's formula, binomial coefficients from prime powers, powers, digit sums and zeros
How each part works:
- Division: EML-P has no // operator, and int(a / b) goes through a float, which is exact only below 2^53. So, as in the corpus case
long-division-exact, division is long division, one decimal digit at a time. The running remainder stays below the divisor, so each digit takes at most 9 subtractions, however big the numbers are. The program checks every answer: quotient x divisor + remainder is the number, and the remainder is smaller than the divisor. - Factorials: as in the corpus case
factorial-exact-digits, the zeros at the end are checked by Legendre's formula. The power of a prime p in n! is n/p + n/p^2 + ... rounded down. These are divisions of small numbers, so the float route is exact. The power of 2 is always larger than the power of 5, so the count of 5s is the count of zeros. The program counts the zeros on the digits too. - Binomial coefficients: n choose k is the product of primes, each to its power in n! less its powers in k! and (n - k)!. Only multiplication is needed, so nothing is divided.
- Powers: repeated squaring, one squaring for each bit of the exponent and one more multiplication for each 1 bit: 2^1000 takes 15 multiplications.
What is checked: menu choices 1 to 5; n from 0 to 1000 and k from 0 to n; a base from 2 to 999,999 and an exponent from 1 to 2000; numbers to divide of up to 100 digits, and a divisor that is not 0. An empty answer cancels. A number of more than 60 digits shows its first and last 25.
Sessions: sessions/basic.in gives: - 50!, 1000! (2568 digits, 249 zeros) and 0!; - 1000 choose 500 (300 digits), 52 choose 5 (2,598,960 poker hands) and 10 choose 3; - 2^1000 and 3^4; - 123456789012345678901234567890 divided by 7, and 2^100 by 3^40.
sessions/bad-input.in gives: - menu choices 0 and x; - n of 1001, -5 and abc; k above n; base 1 and exponent 2001; each then cancelled; - "12a" and a 101-digit number to divide, then a division by 0.
Built on the verified corpus cases long-division-exact (division digit by digit, exact at any size) and factorial-exact-digits (50! checked by Legendre's formula rather than by itself).
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== Big numbers ==
Exact factorials, binomial coefficients, powers and long division - no digit lost.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 0
Pick a number from 1 to 5.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> x
Pick a number from 1 to 5.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 1
n (0 to 1000)> 1001
Type a whole number from 0 to 1000.
n (0 to 1000)> -5
Type a whole number from 0 to 1000.
n (0 to 1000)> abc
Type a whole number from 0 to 1000.
n (0 to 1000)>
Cancelled.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 2
n (0 to 1000)> 5
k (0 to 5)> 6
Type a whole number from 0 to 5.
k (0 to 5)>
Cancelled.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 3
base (2 to 999999)> 1
Type a whole number from 2 to 999999.
base (2 to 999999)> 2
exponent (1 to 2000)> 2001
Type a whole number from 1 to 2000.
exponent (1 to 2000)>
Cancelled.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 4
number to divide (up to 100 digits)> 12a
Type a whole number of up to 100 digits.
number to divide (up to 100 digits)> 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
Type a whole number of up to 100 digits.
number to divide (up to 100 digits)> 100
divide by (up to 100 digits, not 0)> 0
Dividing by 0 has no answer.
divide by (up to 100 digits, not 0)>
Cancelled.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 5
Bye.
What was typed (23 lines)
0
x
1
1001
-5
abc
2
5
6
3
1
2
2001
4
12a
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
100
0
5
basic
interpreter: byte-equal== Big numbers ==
Exact factorials, binomial coefficients, powers and long division - no digit lost.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 1
n (0 to 1000)> 50
50! = 3041409320171337804361260...7641568960512000000000000 (65 digits)
Digits: 65; their sum: 216.
Zeros at the end: 12 counted, and Legendre's n/5 + n/25 + n/125 + ... gives 12.
The power of 2 in it is 47, more than the 12 of 5, so every 5 finds a 2 to make a 10.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 1
n (0 to 1000)> 1000
1000! = 4023872600770937735437024...0000000000000000000000000 (2568 digits)
Digits: 2568; their sum: 10539.
Zeros at the end: 249 counted, and Legendre's n/5 + n/25 + n/125 + ... gives 249.
The power of 2 in it is 994, more than the 249 of 5, so every 5 finds a 2 to make a 10.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 1
n (0 to 1000)> 0
0! = 1
Digits: 1; their sum: 1.
Zeros at the end: 0 counted, and Legendre's n/5 + n/25 + n/125 + ... gives 0.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 2
n (0 to 1000)> 1000
k (0 to 1000)> 500
1000 choose 500 = 2702882409454365695156146...8109296905863799821216320 (300 digits)
As primes: 2^6 x 3^4 x 5 x 13 x 17 x 23^2 x 29 x 31 x 37 x 43 x 47 x 73 x ... (116 primes in all)
Each prime's power is its power in n! less those in k! and (n - k)!, so nothing is divided.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 2
n (0 to 1000)> 52
k (0 to 52)> 5
52 choose 5 = 2598960
As primes: 2^4 x 3 x 5 x 7^2 x 13 x 17
Each prime's power is its power in n! less those in k! and (n - k)!, so nothing is divided.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 2
n (0 to 1000)> 10
k (0 to 10)> 3
10 choose 3 = 120
As primes: 2^3 x 3 x 5
Each prime's power is its power in n! less those in k! and (n - k)!, so nothing is divided.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 3
base (2 to 999999)> 2
exponent (1 to 2000)> 1000
2^1000 = 1071508607186267320948425...1652624386837205668069376 (302 digits)
Repeated squaring took 15 multiplications; one factor at a time takes 999.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 3
base (2 to 999999)> 3
exponent (1 to 2000)> 4
3^4 = 81
Repeated squaring took 3 multiplications; one factor at a time takes 3.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 4
number to divide (up to 100 digits)> 123456789012345678901234567890
divide by (up to 100 digits, not 0)> 7
quotient 17636684144620811271604938270
remainder 0
Check: quotient x divisor + remainder is the number, and the remainder is less than the divisor.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 4
number to divide (up to 100 digits)> 1267650600228229401496703205376
divide by (up to 100 digits, not 0)> 12157665459056928801
quotient 104267600099
remainder 5856291598919654077
Check: quotient x divisor + remainder is the number, and the remainder is less than the divisor.
1) factorial 2) n choose k 3) power 4) divide 5) quit
choice> 5
Bye.
What was typed (28 lines)
1
50
1
1000
1
0
2
1000
500
2
52
5
2
10
3
3
2
1000
3
3
4
4
123456789012345678901234567890
7
4
1267650600228229401496703205376
12157665459056928801
5
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# P081 big numbers: exact factorials, binomial coefficients, powers and
# division of big numbers, each checked against something that does not
# use the number itself.
import bignum
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, most):
# A whole number of up to `most` digits, or -1.
if len(s) == 0 or len(s) > most:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def ask(prompt, low, high):
while True:
trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => a
if a == "":
return -1
whole(a, 6) => n
if n >= low and n <= high:
return n
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
def shown(x):
# The whole number if it is short; otherwise its first and last 25
# digits and how many there are.
str(x) => t
if len(t) <= 60:
return t
return t[0:25] + "..." + t[len(t) - 25:len(t)] + " (" + str(len(t)) + " digits)"
def fact():
ask("n", 0, 1000) => n
if n == -1:
"Cancelled." ^0
return
bignum.factorial(n) => f
(str(n) + "! = " + shown(f)) ^0
("Digits: " + str(len(str(f))) + "; their sum: " + str(bignum.digit_sum(f)) + ".") ^0
bignum.legendre(n, 5) => z
bignum.zeros_at_end(f) => counted
("Zeros at the end: " + str(counted) + " counted, and Legendre's n/5 + n/25 + n/125 + ... gives " + str(z) + ".") ^0
if n >= 2:
("The power of 2 in it is " + str(bignum.legendre(n, 2)) + ", more than the " + str(z) + " of 5, so every 5 finds a 2 to make a 10.") ^0
def choose():
ask("n", 0, 1000) => n
if n == -1:
"Cancelled." ^0
return
ask("k", 0, n) => k
if k == -1:
"Cancelled." ^0
return
bignum.binomial(n, k) => b
(str(n) + " choose " + str(k) + " = " + shown(b[0])) ^0
if len(b[1]) == 0:
"No prime divides it: it is 1." ^0
return
"" => line
0 => shown_count
for pe in b[1]:
if shown_count < 12:
if line != "":
line + " x " => line
if pe[1] == 1:
line + str(pe[0]) => line
else:
line + str(pe[0]) + "^" + str(pe[1]) => line
shown_count + 1 => shown_count
if shown_count > 12:
line + " x ... (" + str(shown_count) + " primes in all)" => line
("As primes: " + line) ^0
"Each prime's power is its power in n! less those in k! and (n - k)!, so nothing is divided." ^0
def pow_():
ask("base", 2, 999999) => a
if a == -1:
"Cancelled." ^0
return
ask("exponent", 1, 2000) => e
if e == -1:
"Cancelled." ^0
return
bignum.power(a, e) => r
(str(a) + "^" + str(e) + " = " + shown(r[0])) ^0
("Repeated squaring took " + str(r[1]) + " multiplications; one factor at a time takes " + str(e - 1) + ".") ^0
def ask_big(prompt):
while True:
trim(input(prompt)) => s
if s == "":
return -1
whole(s, 100) => n
if n >= 0:
return n
"Type a whole number of up to 100 digits." ^0
def div():
ask_big("number to divide (up to 100 digits)> ") => a
if a == -1:
"Cancelled." ^0
return
while True:
ask_big("divide by (up to 100 digits, not 0)> ") => b
if b == -1:
"Cancelled." ^0
return
if b > 0:
bignum.divide(a, b) => qr
("quotient " + shown(qr[0])) ^0
("remainder " + shown(qr[1])) ^0
if qr[0] * b + qr[1] == a and qr[1] < b:
"Check: quotient x divisor + remainder is the number, and the remainder is less than the divisor." ^0
return
"Dividing by 0 has no answer." ^0
"== Big numbers ==" ^0
"Exact factorials, binomial coefficients, powers and long division - no digit lost." ^0
True => running
while running:
"" ^0
"1) factorial 2) n choose k 3) power 4) divide 5) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
fact()
elif choice == "2":
choose()
elif choice == "3":
pow_()
elif choice == "4":
div()
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import bignum
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, most):
if len(s) == 0 or len(s) > most:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def ask(prompt, low, high):
while True:
a = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if a == "":
return -1
n = whole(a, 6)
if n >= low and n <= high:
return n
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
def shown(x):
t = str(x)
if len(t) <= 60:
return t
return t[0:25] + "..." + t[len(t) - 25:len(t)] + " (" + str(len(t)) + " digits)"
def fact():
n = ask("n", 0, 1000)
if n == -1:
print("Cancelled.")
return
f = bignum.factorial(n)
print(str(n) + "! = " + shown(f))
print("Digits: " + str(len(str(f))) + "; their sum: " + str(bignum.digit_sum(f)) + ".")
z = bignum.legendre(n, 5)
counted = bignum.zeros_at_end(f)
print("Zeros at the end: " + str(counted) + " counted, and Legendre's n/5 + n/25 + n/125 + ... gives " + str(z) + ".")
if n >= 2:
print("The power of 2 in it is " + str(bignum.legendre(n, 2)) + ", more than the " + str(z) + " of 5, so every 5 finds a 2 to make a 10.")
def choose():
n = ask("n", 0, 1000)
if n == -1:
print("Cancelled.")
return
k = ask("k", 0, n)
if k == -1:
print("Cancelled.")
return
b = bignum.binomial(n, k)
print(str(n) + " choose " + str(k) + " = " + shown(b[0]))
if len(b[1]) == 0:
print("No prime divides it: it is 1.")
return
line = ""
shown_count = 0
for pe in b[1]:
if shown_count < 12:
if line != "":
line = line + " x "
if pe[1] == 1:
line = line + str(pe[0])
else:
line = line + str(pe[0]) + "^" + str(pe[1])
shown_count = shown_count + 1
if shown_count > 12:
line = line + " x ... (" + str(shown_count) + " primes in all)"
print("As primes: " + line)
print("Each prime's power is its power in n! less those in k! and (n - k)!, so nothing is divided.")
def pow_():
a = ask("base", 2, 999999)
if a == -1:
print("Cancelled.")
return
e = ask("exponent", 1, 2000)
if e == -1:
print("Cancelled.")
return
r = bignum.power(a, e)
print(str(a) + "^" + str(e) + " = " + shown(r[0]))
print("Repeated squaring took " + str(r[1]) + " multiplications; one factor at a time takes " + str(e - 1) + ".")
def ask_big(prompt):
while True:
s = trim(input(prompt))
if s == "":
return -1
n = whole(s, 100)
if n >= 0:
return n
print("Type a whole number of up to 100 digits.")
def div():
a = ask_big("number to divide (up to 100 digits)> ")
if a == -1:
print("Cancelled.")
return
while True:
b = ask_big("divide by (up to 100 digits, not 0)> ")
if b == -1:
print("Cancelled.")
return
if b > 0:
qr = bignum.divide(a, b)
print("quotient " + shown(qr[0]))
print("remainder " + shown(qr[1]))
if qr[0] * b + qr[1] == a and qr[1] < b:
print("Check: quotient x divisor + remainder is the number, and the remainder is less than the divisor.")
return
print("Dividing by 0 has no answer.")
print("== Big numbers ==")
print("Exact factorials, binomial coefficients, powers and long division - no digit lost.")
running = True
while running:
print("")
print("1) factorial 2) n choose k 3) power 4) divide 5) quit")
choice = trim(input("choice> "))
if choice == "1":
fact()
elif choice == "2":
choose()
elif choice == "3":
pow_()
elif choice == "4":
div()
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
bignum.eml
eml# P081 big numbers - whole numbers of any size, kept exact: factorials,
# binomial coefficients, powers, and division of one big number by another.
# EML-P has no // operator, and int(a / b) goes through a float, which is
# exact only below 2^53; so division here is long division, digit by digit.
def divide(a, b):
# The corpus case long-division-exact: [quotient, remainder] of a >= 0
# by b > 0, one decimal digit of a at a time. The running remainder
# stays below b, so each step needs at most 9 subtractions.
0 => q
0 => r
for ch in str(a):
r * 10 + int(ch) => r
0 => d
while r >= b:
r - b => r
d + 1 => d
q * 10 + d => q
return [q, r]
def factorial(n):
1 => out
for k in [2:n]:
out * k => out
return out
def primes_to(n):
# The primes up to n, by the sieve of Eratosthenes.
[True] * (n + 1) => flags
[] => out
for p in [2:n]:
if flags[p]:
out + [p] => out
p * p => m
while m <= n:
False => flags[m]
m + p => m
return out
def legendre(n, p):
# The power of the prime p in n!: n/p + n/p^2 + ... rounded down
# (Legendre). These divisions are of small numbers, far below 2^53, so
# the float route int(n / q) is exact here.
0 => e
p => q
while q <= n:
e + int(n / q) => e
q * p => q
return e
def binomial(n, k):
# n choose k without dividing at all: its power of each prime p is the
# power in n! less the powers in k! and (n - k)! (Kummer), and the
# number is the product of the primes to those powers. Returns
# [value, [[p, power], ...] for the powers above 0].
1 => out
[] => used
for p in primes_to(n):
legendre(n, p) - legendre(k, p) - legendre(n - k, p) => e
if e > 0:
used + [[p, e]] => used
for i in [1:e]:
out * p => out
return [out, used]
def power(a, e):
# a^e by repeated squaring: [value, multiplications made].
1 => out
a => b
0 => count
e => left
while left > 0:
if left % 2 == 1:
out * b => out
count + 1 => count
divide(left, 2)[0] => left
if left > 0:
b * b => b
count + 1 => count
return [out, count]
def digit_sum(x):
0 => s
for ch in str(x):
s + int(ch) => s
return s
def zeros_at_end(x):
# Counted on the digits themselves, independently of Legendre.
str(x) => t
0 => k
while k < len(t) - 1 and t[len(t) - 1 - k] == "0":
k + 1 => k
return k
Python projection (bignum.py)
def divide(a, b):
q = 0
r = 0
for ch in str(a):
r = r * 10 + int(ch)
d = 0
while r >= b:
r = r - b
d = d + 1
q = q * 10 + d
return [q, r]
def factorial(n):
out = 1
for k in range(2, n+1):
out = out * k
return out
def primes_to(n):
flags = [True] * (n + 1)
out = []
for p in range(2, n+1):
if flags[p]:
out = out + [p]
m = p * p
while m <= n:
flags[m] = False
m = m + p
return out
def legendre(n, p):
e = 0
q = p
while q <= n:
e = e + int(n / q)
q = q * p
return e
def binomial(n, k):
out = 1
used = []
for p in primes_to(n):
e = legendre(n, p) - legendre(k, p) - legendre(n - k, p)
if e > 0:
used = used + [[p, e]]
for i in range(1, e+1):
out = out * p
return [out, used]
def power(a, e):
out = 1
b = a
count = 0
left = e
while left > 0:
if left % 2 == 1:
out = out * b
count = count + 1
left = divide(left, 2)[0]
if left > 0:
b = b * b
count = count + 1
return [out, count]
def digit_sum(x):
s = 0
for ch in str(x):
s = s + int(ch)
return s
def zeros_at_end(x):
t = str(x)
k = 0
while k < len(t) - 1 and t[len(t) - 1 - k] == "0":
k = k + 1
return k