Project P150
Fixed-width integers
A string hash, a binary-search midpoint, factorials and a division in Python's integers and in a 32-bit int as C and Java have it: where it wraps, where it turns negative, and where the two divisions part.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-18
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
The same arithmetic in Python's integers and in a 32-bit int as C and Java have it: a string hash, a midpoint, factorials and a division.
main.eml- the menu, a text hashed one character at a time, a midpoint, a table of factorials, and a division both wayswidth.eml- two's complement wrapping, character codes, the hash steps, division toward minus infinity and toward zero with their remainders, the three midpoints, and the factorials
How each part works:
- As in the corpus case
fixed-width-overflow, Python never overflows and a 32-bit int wraps, quietly, to a number of the right type. Two's complement is arithmetic mod 2^32 with the top half read as negative, so it is written with %, there being no bitwise operators. - The hash is h = h * 31 + code, as Java's String.hashCode. "Hello world" wraps at the space and ends at -832992604, negative though every code is positive. As in the corpus case
integer-division-sign, C's remainder takes the sign of the hash: its bucket of 16 is -12, an index outside the table. Written ((hash % 16) + 16) % 16 it is 4, Python's bucket - because 16 divides 2^32, the wrap keeps the last four bits. - The midpoint of a binary search: (lo + hi) / 2 wraps once lo + hi passes 2147483647, giving a negative midpoint; lo + (hi - lo) / 2 never does.
- Factorials: 13! is the first past 32 bits; from there the 32-bit column is plausible and wrong, and some of it negative.
- Division: Python rounds toward minus infinity and C toward zero. Both keep q * b + r = a; they differ, by one in q, exactly when the signs differ and the division is not exact, and then C's remainder is no slot of a ring of b.
What is checked: menu choices 1 to 5; a text of 1 to 12 letters, digits, spaces, dots, dashes or underscores; lo from 0 to 2147483647 and hi from lo; a factorial up to 1 to 20; a and b from -9999 to 9999, b not 0. An empty answer cancels.
Sessions: sessions/basic.in gives: - hello, which fits, and Hello world, which wraps; - the midpoint of 1500000000 and 2000000000, and of 10 and 20; - factorials to 20; -7 and 7 by 2, and -7 and 7 by -2.
sessions/bad-input.in gives: - menu choices 0 and x; - texts: a cancel, 14 characters and a!b; - midpoints: a cancel, -1, 2147483648, then lo 100 with a cancel, 50 and x; - factorials: a cancel, 0, 21 and x; - divisions: a cancel, 10000, then a 7 with a cancel, 0 and x, and a lone minus sign.
Built on the verified corpus cases fixed-width-overflow (a hash, a midpoint and a factorial in 32 bits, written with modulo) and integer-division-sign (floor and truncating division, both against q * b + r = a, and where they disagree).
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== Fixed-width integers ==
Arithmetic in Python's integers and in a 32-bit int as C and Java have it.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 0
Pick a number from 1 to 5.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> x
Pick a number from 1 to 5.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 1
text (letters, digits, space . - _, up to 12)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 1
text (letters, digits, space . - _, up to 12)> toolongtext123
Type 1 to 12 letters, digits, spaces, dots, dashes or underscores.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 1
text (letters, digits, space . - _, up to 12)> a!b
Type 1 to 12 letters, digits, spaces, dots, dashes or underscores.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> -1
Type a whole number from 0 to 2147483647.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 2147483648
Type a whole number from 0 to 2147483647.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 100
hi (lo to 2147483647)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 100
hi (lo to 2147483647)> 50
Type a whole number from 100 to 2147483647.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 100
hi (lo to 2147483647)> x
Type a whole number from 100 to 2147483647.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 3
up to (1 to 20)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 3
up to (1 to 20)> 0
Type a whole number from 1 to 20.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 3
up to (1 to 20)> 21
Type a whole number from 1 to 20.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 3
up to (1 to 20)> x
Type a whole number from 1 to 20.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 10000
Type a whole number from -9999 to 9999.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 7
b (-9999 to 9999, not 0)>
Cancelled.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 7
b (-9999 to 9999, not 0)> 0
Type a whole number from -9999 to 9999, not 0.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 7
b (-9999 to 9999, not 0)> x
Type a whole number from -9999 to 9999, not 0.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> -
Type a whole number from -9999 to 9999.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 5
Bye.
What was typed (47 lines)
0
x
1
1
toolongtext123
1
a!b
2
2
-1
2
2147483648
2
100
2
100
50
2
100
x
3
3
0
3
21
3
x
4
4
10000
4
7
4
7
0
4
7
x
4
-
5
basic
interpreter: byte-equal== Fixed-width integers ==
Arithmetic in Python's integers and in a 32-bit int as C and Java have it.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 1
text (letters, digits, space . - _, up to 12)> hello
h = h * 31 + code, one character at a time:
char Python 32-bit
'h' 104 104
'e' 3325 3325
'l' 103183 103183
'l' 3198781 3198781
'o' 99162322 99162322
The hash fits in 32 bits: both give the same number.
Bucket of 16: Python hash % 16 = 2; C, with its hash, hash % 16 = 2; written ((hash % 16) + 16) % 16, 2.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 1
text (letters, digits, space . - _, up to 12)> Hello world
h = h * 31 + code, one character at a time:
char Python 32-bit
'H' 72 72
'e' 2333 2333
'l' 72431 72431
'l' 2245469 2245469
'o' 69609650 69609650
' ' 2157899182 -2137068114 <- wraps here
'w' 66894874761 -1824601975
'o' 2073741117702 -728086266
'r' 64285974648876 -1095837652
'l' 1992865214115264 388771264
'd' 61778821637573284 -832992604
The 32-bit hash is negative, -832992604, though every code is positive.
Bucket of 16: Python hash % 16 = 4; C, with its hash, hash % 16 = -12; written ((hash % 16) + 16) % 16, 4.
C's remainder takes the sign of the hash: a negative index, outside the table.
The safe index matches Python's because 16 divides 2^32: the wrap keeps the last four bits.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 1500000000
hi (lo to 2147483647)> 2000000000
Python (lo + hi) // 2: 1750000000
32-bit (lo + hi) / 2: -397483648
32-bit lo + (hi - lo) / 2: 1750000000
lo + hi is 3500000000, past 2147483647: it wraps, and the midpoint comes out -397483648. Written lo + (hi - lo) / 2, nothing overflows.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 2
lo (0 to 2147483647)> 10
hi (lo to 2147483647)> 20
Python (lo + hi) // 2: 15
32-bit (lo + hi) / 2: 15
32-bit lo + (hi - lo) / 2: 15
lo + hi fits in 32 bits: all three agree.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 3
up to (1 to 20)> 20
k k! in Python in 32 bits
1 1 1
2 2 2
3 6 6
4 24 24
5 120 120
6 720 720
7 5040 5040
8 40320 40320
9 362880 362880
10 3628800 3628800
11 39916800 39916800
12 479001600 479001600
13 6227020800 1932053504 wrapped
14 87178291200 1278945280 wrapped
15 1307674368000 2004310016 wrapped
16 20922789888000 2004189184 wrapped
17 355687428096000 -288522240 negative
18 6402373705728000 -898433024 negative
19 121645100408832000 109641728 wrapped
20 2432902008176640000 -2102132736 negative
13! is the first that does not fit: from there the 32-bit column is a plausible number and wrong.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> -7
b (-9999 to 9999, not 0)> 2
Python, toward minus infinity: q -4, r 1; q * b + r = -7
C and Java, toward zero: q -3, r -1; q * b + r = -7
Both keep q * b + r = a and differ by one in q: the signs differ and the division is not exact.
As an index into 2 slots, Python's r is slot 1; C's is -1, outside them.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 7
b (-9999 to 9999, not 0)> 2
Python, toward minus infinity: q 3, r 1; q * b + r = 7
C and Java, toward zero: q 3, r 1; q * b + r = 7
The two agree: the quotient is exact, or a and b have the same sign.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> -7
b (-9999 to 9999, not 0)> -2
Python, toward minus infinity: q 3, r -1; q * b + r = -7
C and Java, toward zero: q 3, r -1; q * b + r = -7
The two agree: the quotient is exact, or a and b have the same sign.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 4
a (-9999 to 9999)> 7
b (-9999 to 9999, not 0)> -2
Python, toward minus infinity: q -4, r -1; q * b + r = 7
C and Java, toward zero: q -3, r 1; q * b + r = 7
Both keep q * b + r = a and differ by one in q: the signs differ and the division is not exact.
1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit
choice> 5
Bye.
What was typed (25 lines)
1
hello
1
Hello world
2
1500000000
2000000000
2
10
20
3
20
4
-7
2
4
7
2
4
-7
-2
4
7
-2
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# P150 fixed-width integers: a string hash, a midpoint, factorials and a
# division, each in Python's integers and in a 32-bit int, and where the two
# part.
import width
def plain(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 pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def lpad(s, n):
s => out
while len(out) < n:
" " + out => out
return out
def number(t, most):
# [True, the value] for an integer of at most most digits, a - allowed
# in front, or [False, 0]
if len(t) == 0:
return [False, 0]
0 => start
if t[0] == "-":
1 => start
if len(t) == start or len(t) - start > most:
return [False, 0]
0 => v
for c in t[start:len(t)]:
if c < "0" or c > "9":
return [False, 0]
v * 10 + int(c) => v
if start == 1:
return [True, 0 - v]
return [True, v]
def hash_text():
plain(input("text (letters, digits, space . - _, up to 12)> ")) => t
if t == "":
"Cancelled." ^0
return
if len(t) > 12:
"Type 1 to 12 letters, digits, spaces, dots, dashes or underscores." ^0
return
for c in t:
if width.code(c) < 0:
"Type 1 to 12 letters, digits, spaces, dots, dashes or underscores." ^0
return
width.hash_steps(t) => st
("h = h * 31 + code, one character at a time:") ^0
(" " + pad("char", 6) + lpad("Python", 24) + lpad("32-bit", 14)) ^0
False => parted
for x in st:
(" " + pad("'" + x[0] + "'", 6) + lpad(str(x[1]), 24) + lpad(str(x[2]), 14)) => line
if x[1] != x[2] and not parted:
line + " <- wraps here" => line
True => parted
line ^0
st[len(st) - 1] => last
last[1] => h
last[2] => w
if h == w:
"The hash fits in 32 bits: both give the same number." ^0
elif w < 0:
("The 32-bit hash is negative, " + str(w) + ", though every code is positive.") ^0
else:
("The 32-bit hash is " + str(w) + ", a plausible number and not Python's.") ^0
width.floor_mod(h, 16) => a
width.trunc_mod(w, 16) => b
width.trunc_mod(width.trunc_mod(w, 16) + 16, 16) => c
("Bucket of 16: Python hash % 16 = " + str(a) + "; C, with its hash, hash % 16 = " + str(b) + "; written ((hash % 16) + 16) % 16, " + str(c) + ".") ^0
if b < 0:
"C's remainder takes the sign of the hash: a negative index, outside the table." ^0
if h != w:
"The safe index matches Python's because 16 divides 2^32: the wrap keeps the last four bits." ^0
def midpoint():
plain(input("lo (0 to 2147483647)> ")) => t
if t == "":
"Cancelled." ^0
return
number(t, 10) => a
if not a[0] or a[1] < 0 or a[1] > 2147483647:
"Type a whole number from 0 to 2147483647." ^0
return
plain(input("hi (lo to 2147483647)> ")) => t
if t == "":
"Cancelled." ^0
return
number(t, 10) => b
if not b[0] or b[1] < a[1] or b[1] > 2147483647:
("Type a whole number from " + str(a[1]) + " to 2147483647.") ^0
return
width.midpoints(a[1], b[1]) => m
(" Python (lo + hi) // 2: " + str(m[0])) ^0
(" 32-bit (lo + hi) / 2: " + str(m[1])) ^0
(" 32-bit lo + (hi - lo) / 2: " + str(m[2])) ^0
if m[1] != m[0]:
("lo + hi is " + str(a[1] + b[1]) + ", past 2147483647: it wraps, and the midpoint comes out " + str(m[1]) + ". Written lo + (hi - lo) / 2, nothing overflows.") ^0
else:
"lo + hi fits in 32 bits: all three agree." ^0
def factorials():
plain(input("up to (1 to 20)> ")) => t
if t == "":
"Cancelled." ^0
return
number(t, 2) => n
if not n[0] or n[1] < 1 or n[1] > 20:
"Type a whole number from 1 to 20." ^0
return
(" " + lpad("k", 3) + lpad("k! in Python", 22) + lpad("in 32 bits", 14)) ^0
0 => first
for x in width.factorials(n[1]):
(" " + lpad(str(x[0]), 3) + lpad(str(x[1]), 22) + lpad(str(x[2]), 14)) => line
if x[1] != x[2]:
if first == 0:
x[0] => first
if x[2] < 0:
line + " negative" => line
else:
line + " wrapped" => line
line ^0
if first == 0:
"Every one fits in 32 bits." ^0
else:
(str(first) + "! is the first that does not fit: from there the 32-bit column is a plausible number and wrong.") ^0
def divide():
plain(input("a (-9999 to 9999)> ")) => t
if t == "":
"Cancelled." ^0
return
number(t, 4) => a
if not a[0]:
"Type a whole number from -9999 to 9999." ^0
return
plain(input("b (-9999 to 9999, not 0)> ")) => t
if t == "":
"Cancelled." ^0
return
number(t, 4) => b
if not b[0] or b[1] == 0:
"Type a whole number from -9999 to 9999, not 0." ^0
return
a[1] => x
b[1] => y
width.floor_div(x, y) => q1
width.floor_mod(x, y) => r1
width.trunc_div(x, y) => q2
width.trunc_mod(x, y) => r2
(" Python, toward minus infinity: q " + str(q1) + ", r " + str(r1) + "; q * b + r = " + str(q1 * y + r1)) ^0
(" C and Java, toward zero: q " + str(q2) + ", r " + str(r2) + "; q * b + r = " + str(q2 * y + r2)) ^0
if q1 == q2:
"The two agree: the quotient is exact, or a and b have the same sign." ^0
else:
"Both keep q * b + r = a and differ by one in q: the signs differ and the division is not exact." ^0
if y > 0:
("As an index into " + str(y) + " slots, Python's r is slot " + str(r1) + "; C's is " + str(r2) + ", outside them.") ^0
"== Fixed-width integers ==" ^0
"Arithmetic in Python's integers and in a 32-bit int as C and Java have it." ^0
True => running
while running:
"" ^0
"1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
hash_text()
elif choice == "2":
midpoint()
elif choice == "3":
factorials()
elif choice == "4":
divide()
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import width
def plain(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 pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def lpad(s, n):
out = s
while len(out) < n:
out = " " + out
return out
def number(t, most):
if len(t) == 0:
return [False, 0]
start = 0
if t[0] == "-":
start = 1
if len(t) == start or len(t) - start > most:
return [False, 0]
v = 0
for c in t[start:len(t)]:
if c < "0" or c > "9":
return [False, 0]
v = v * 10 + int(c)
if start == 1:
return [True, 0 - v]
return [True, v]
def hash_text():
t = plain(input("text (letters, digits, space . - _, up to 12)> "))
if t == "":
print("Cancelled.")
return
if len(t) > 12:
print("Type 1 to 12 letters, digits, spaces, dots, dashes or underscores.")
return
for c in t:
if width.code(c) < 0:
print("Type 1 to 12 letters, digits, spaces, dots, dashes or underscores.")
return
st = width.hash_steps(t)
print("h = h * 31 + code, one character at a time:")
print(" " + pad("char", 6) + lpad("Python", 24) + lpad("32-bit", 14))
parted = False
for x in st:
line = " " + pad("'" + x[0] + "'", 6) + lpad(str(x[1]), 24) + lpad(str(x[2]), 14)
if x[1] != x[2] and not parted:
line = line + " <- wraps here"
parted = True
print(line)
last = st[len(st) - 1]
h = last[1]
w = last[2]
if h == w:
print("The hash fits in 32 bits: both give the same number.")
elif w < 0:
print("The 32-bit hash is negative, " + str(w) + ", though every code is positive.")
else:
print("The 32-bit hash is " + str(w) + ", a plausible number and not Python's.")
a = width.floor_mod(h, 16)
b = width.trunc_mod(w, 16)
c = width.trunc_mod(width.trunc_mod(w, 16) + 16, 16)
print("Bucket of 16: Python hash % 16 = " + str(a) + "; C, with its hash, hash % 16 = " + str(b) + "; written ((hash % 16) + 16) % 16, " + str(c) + ".")
if b < 0:
print("C's remainder takes the sign of the hash: a negative index, outside the table.")
if h != w:
print("The safe index matches Python's because 16 divides 2^32: the wrap keeps the last four bits.")
def midpoint():
t = plain(input("lo (0 to 2147483647)> "))
if t == "":
print("Cancelled.")
return
a = number(t, 10)
if not a[0] or a[1] < 0 or a[1] > 2147483647:
print("Type a whole number from 0 to 2147483647.")
return
t = plain(input("hi (lo to 2147483647)> "))
if t == "":
print("Cancelled.")
return
b = number(t, 10)
if not b[0] or b[1] < a[1] or b[1] > 2147483647:
print("Type a whole number from " + str(a[1]) + " to 2147483647.")
return
m = width.midpoints(a[1], b[1])
print(" Python (lo + hi) // 2: " + str(m[0]))
print(" 32-bit (lo + hi) / 2: " + str(m[1]))
print(" 32-bit lo + (hi - lo) / 2: " + str(m[2]))
if m[1] != m[0]:
print("lo + hi is " + str(a[1] + b[1]) + ", past 2147483647: it wraps, and the midpoint comes out " + str(m[1]) + ". Written lo + (hi - lo) / 2, nothing overflows.")
else:
print("lo + hi fits in 32 bits: all three agree.")
def factorials():
t = plain(input("up to (1 to 20)> "))
if t == "":
print("Cancelled.")
return
n = number(t, 2)
if not n[0] or n[1] < 1 or n[1] > 20:
print("Type a whole number from 1 to 20.")
return
print(" " + lpad("k", 3) + lpad("k! in Python", 22) + lpad("in 32 bits", 14))
first = 0
for x in width.factorials(n[1]):
line = " " + lpad(str(x[0]), 3) + lpad(str(x[1]), 22) + lpad(str(x[2]), 14)
if x[1] != x[2]:
if first == 0:
first = x[0]
if x[2] < 0:
line = line + " negative"
else:
line = line + " wrapped"
print(line)
if first == 0:
print("Every one fits in 32 bits.")
else:
print(str(first) + "! is the first that does not fit: from there the 32-bit column is a plausible number and wrong.")
def divide():
t = plain(input("a (-9999 to 9999)> "))
if t == "":
print("Cancelled.")
return
a = number(t, 4)
if not a[0]:
print("Type a whole number from -9999 to 9999.")
return
t = plain(input("b (-9999 to 9999, not 0)> "))
if t == "":
print("Cancelled.")
return
b = number(t, 4)
if not b[0] or b[1] == 0:
print("Type a whole number from -9999 to 9999, not 0.")
return
x = a[1]
y = b[1]
q1 = width.floor_div(x, y)
r1 = width.floor_mod(x, y)
q2 = width.trunc_div(x, y)
r2 = width.trunc_mod(x, y)
print(" Python, toward minus infinity: q " + str(q1) + ", r " + str(r1) + "; q * b + r = " + str(q1 * y + r1))
print(" C and Java, toward zero: q " + str(q2) + ", r " + str(r2) + "; q * b + r = " + str(q2 * y + r2))
if q1 == q2:
print("The two agree: the quotient is exact, or a and b have the same sign.")
else:
print("Both keep q * b + r = a and differ by one in q: the signs differ and the division is not exact.")
if y > 0:
print("As an index into " + str(y) + " slots, Python's r is slot " + str(r1) + "; C's is " + str(r2) + ", outside them.")
print("== Fixed-width integers ==")
print("Arithmetic in Python's integers and in a 32-bit int as C and Java have it.")
running = True
while running:
print("")
print("1) hash a text 2) a midpoint 3) factorials 4) divide 5) quit")
choice = plain(input("choice> "))
if choice == "1":
hash_text()
elif choice == "2":
midpoint()
elif choice == "3":
factorials()
elif choice == "4":
divide()
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
width.eml
eml# P150 fixed-width integers - the same arithmetic in Python's integers and
# in a 32-bit int as C and Java have it. As in the corpus case
# fixed-width-overflow, Python never overflows and a fixed-width language
# wraps, quietly, to a plausible number - a hash, a midpoint, a factorial -
# and can wrap to the wrong sign. As in the corpus case
# integer-division-sign, Python's division rounds toward minus infinity and
# C's toward zero, and the remainder follows; the two disagree exactly on
# the negative values that wrap backwards, a negative hash among them. Two's
# complement is arithmetic mod 2^32 with the top half read as negative, so
# it is written with %.
def two31():
return 2147483648
def two32():
return 4294967296
def wrap32(n):
n % two32() => m
if m >= two31():
return m - two32()
return m
def code(c):
# the character code of a letter, digit, space, dot, dash or underscore
"0123456789" => d
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" => up
"abcdefghijklmnopqrstuvwxyz" => low
0 => i
while i < 26:
if i < 10 and d[i] == c:
return 48 + i
if up[i] == c:
return 65 + i
if low[i] == c:
return 97 + i
i + 1 => i
if c == " ":
return 32
if c == "-":
return 45
if c == ".":
return 46
if c == "_":
return 95
return 0 - 1
def hash_steps(s):
# [character, the hash in Python, the hash in 32 bits] after each one:
# h = h * 31 + code, as Java's String.hashCode
0 => h
0 => w
[] => out
for c in s:
h * 31 + code(c) => h
wrap32(w * 31 + code(c)) => w
out + [[c, h, w]] => out
return out
def floor_div(a, b):
# Python's a // b, written without it: the truncated quotient, one less
# when the signs differ and it is not exact
trunc_div(a, b) => q
if q * b != a and (a < 0) != (b < 0):
q - 1 => q
return q
def trunc_div(a, b):
# C's a / b on ints: toward zero; exact for big values too, the float
# quotient corrected step by step
0 => neg
a => x
b => y
if x < 0:
0 - x => x
1 - neg => neg
if y < 0:
0 - y => y
1 - neg => neg
int(x / y) => q
while q * y > x:
q - 1 => q
while (q + 1) * y <= x:
q + 1 => q
if neg == 1:
return 0 - q
return q
def floor_mod(a, b):
return a - floor_div(a, b) * b
def trunc_mod(a, b):
return a - trunc_div(a, b) * b
def midpoints(lo, hi):
# [Python (lo + hi) // 2, 32-bit (lo + hi) / 2, 32-bit lo + (hi - lo) / 2]
return [floor_div(lo + hi, 2), trunc_div(wrap32(lo + hi), 2), wrap32(lo + trunc_div(wrap32(hi - lo), 2))]
def factorials(n):
# [k, k! in Python, k! in 32 bits] for k from 1 to n
1 => f
1 => w
[] => out
1 => k
while k <= n:
f * k => f
wrap32(w * k) => w
out + [[k, f, w]] => out
k + 1 => k
return out
Python projection (width.py)
def two31():
return 2147483648
def two32():
return 4294967296
def wrap32(n):
m = n % two32()
if m >= two31():
return m - two32()
return m
def code(c):
d = "0123456789"
up = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
low = "abcdefghijklmnopqrstuvwxyz"
i = 0
while i < 26:
if i < 10 and d[i] == c:
return 48 + i
if up[i] == c:
return 65 + i
if low[i] == c:
return 97 + i
i = i + 1
if c == " ":
return 32
if c == "-":
return 45
if c == ".":
return 46
if c == "_":
return 95
return 0 - 1
def hash_steps(s):
h = 0
w = 0
out = []
for c in s:
h = h * 31 + code(c)
w = wrap32(w * 31 + code(c))
out = out + [[c, h, w]]
return out
def floor_div(a, b):
q = trunc_div(a, b)
if q * b != a and (a < 0) != (b < 0):
q = q - 1
return q
def trunc_div(a, b):
neg = 0
x = a
y = b
if x < 0:
x = 0 - x
neg = 1 - neg
if y < 0:
y = 0 - y
neg = 1 - neg
q = int(x / y)
while q * y > x:
q = q - 1
while (q + 1) * y <= x:
q = q + 1
if neg == 1:
return 0 - q
return q
def floor_mod(a, b):
return a - floor_div(a, b) * b
def trunc_mod(a, b):
return a - trunc_div(a, b) * b
def midpoints(lo, hi):
return [floor_div(lo + hi, 2), trunc_div(wrap32(lo + hi), 2), wrap32(lo + trunc_div(wrap32(hi - lo), 2))]
def factorials(n):
f = 1
w = 1
out = []
k = 1
while k <= n:
f = f * k
w = wrap32(w * k)
out = out + [[k, f, w]]
k = k + 1
return out