227 lines
4.8 KiB
Python
227 lines
4.8 KiB
Python
import functools
|
|
import time
|
|
|
|
import sets
|
|
|
|
# The encoding used is something I've seen referred to as Von Neuman indices
|
|
# Basically, an empty set is 0 and {a, b, c} is 2^a + 2^b + 2^c
|
|
# The numbers in the set are also encoded the same way
|
|
# For example:
|
|
# 13 = 2³ + 2² + 2⁰
|
|
# → {3, 2, 0}
|
|
# 3 = 2¹ + 2⁰
|
|
# 2 = 2¹
|
|
# → {{1, 0}, {1}, 0}
|
|
# 1 = 2⁰
|
|
# → {{{0}, 0}, {{0}}, 0}
|
|
# → {{{∅}, ∅}, {{∅}}, ∅}
|
|
|
|
empty = sets.set()
|
|
|
|
def I(x):
|
|
"""Converts a number from set representation to an integer"""
|
|
# Algorith works by recursively calling itself
|
|
# I(∅) = 0
|
|
# I({e₁, e₂, e₃, …}) = 2^I(e₁) + 2^I(e₂) + 2^I(e₃) + …
|
|
# For example:
|
|
# I({{{∅}, ∅}, {{∅}}, ∅})
|
|
# → 2^I({{∅}, ∅}) + 2^I({{∅}}) + 2^I(∅)
|
|
# → 2^(2^I({∅}) + 2^I(∅)) + 2^2^I({∅}) + 2^0
|
|
# → 2^(2^2^I(∅) + 2^0) + 2^2^2^I(∅) + 2^0
|
|
# → 2^(2^2^0 + 2^0) + 2^2^2^0 + 2^0
|
|
# → 2^(2^1 + 1) + 2^2^1 + 1
|
|
# → 2^(2 + 1) + 2^2 + 1
|
|
# → 2^3 + 2^2 + 1
|
|
# → 8 + 4 + 1
|
|
# → 13
|
|
|
|
if I == empty:
|
|
return 0
|
|
else:
|
|
return sum(2**I(i) for i in x)
|
|
|
|
def powers_of_two(x):
|
|
"""Lists the powers of two the number is composed of"""
|
|
assert type(x) == int
|
|
|
|
# Look for a power of two bigger than the one we were given
|
|
power = 0
|
|
number = 1
|
|
while number < x:
|
|
number *= 2
|
|
power += 1
|
|
|
|
# Find all smaller powers of two
|
|
powers = []
|
|
while x > 0:
|
|
if number <= x:
|
|
powers.append(power)
|
|
x -= number
|
|
|
|
number //= 2
|
|
power -= 1
|
|
|
|
return powers
|
|
|
|
def J(x):
|
|
"""Converts an integer into set representation"""
|
|
powers = powers_of_two(x)
|
|
return sets.set(J(i) for i in powers)
|
|
|
|
def lesser(x, y):
|
|
only_x = x.difference(y)
|
|
only_y = y.difference(x)
|
|
|
|
if only_x is empty and only_y is not empty:
|
|
return True
|
|
elif only_y is empty:
|
|
return False
|
|
else:
|
|
x_max_power = functools.reduce(lambda a, b: b if lesser(a,b) else a, only_x)
|
|
y_max_power = functools.reduce(lambda a, b: b if lesser(a,b) else a, only_y)
|
|
return lesser(x_max_power, y_max_power)
|
|
|
|
def lshift(x, y):
|
|
return sets.set(add(i, y) for i in x)
|
|
|
|
def double(x):
|
|
return lshift(x, J(1))
|
|
|
|
def rshift(x, y):
|
|
return sets.set(sub(i, y) for i in x)
|
|
|
|
def add(x, y):
|
|
only_x = x.difference(y)
|
|
only_y = y.difference(x)
|
|
one = only_x.union(only_y)
|
|
both = x.intersection(y)
|
|
|
|
if both is empty:
|
|
return one
|
|
else:
|
|
return add(one, double(both))
|
|
|
|
def sub(x, y):
|
|
assert not lesser(x, y)
|
|
only_x = x.difference(y)
|
|
only_y = y.difference(x)
|
|
|
|
if only_y is empty:
|
|
return only_x
|
|
else:
|
|
return sub(add(only_x, only_y), double(only_y))
|
|
|
|
def mul(x, y):
|
|
total = J(0)
|
|
for power in x:
|
|
total = add(total, lshift(y, power))
|
|
return total
|
|
|
|
def divmod(x, y):
|
|
assert y is not empty
|
|
powers = []
|
|
shift_amount = J(0)
|
|
shifted_divisor = y
|
|
|
|
while lesser(shifted_divisor, x):
|
|
shift_amount = add(shift_amount, J(1))
|
|
shifted_divisor = double(shifted_divisor)
|
|
|
|
remaining_dividend = x
|
|
while True:
|
|
if not lesser(remaining_dividend, shifted_divisor):
|
|
powers.append(shift_amount)
|
|
remaining_dividend = sub(remaining_dividend, shifted_divisor)
|
|
|
|
if shift_amount is empty:
|
|
break
|
|
|
|
shift_amount = sub(shift_amount, J(1))
|
|
shifted_divisor = rshift(shifted_divisor, J(1))
|
|
|
|
return sets.set(powers), remaining_dividend
|
|
|
|
def fibonacci():
|
|
a = J(0)
|
|
b = J(1)
|
|
|
|
yield a
|
|
while True:
|
|
yield b
|
|
a, b = b, add(a, b)
|
|
|
|
def py_fibonacci():
|
|
a = 0
|
|
b = 1
|
|
|
|
yield a
|
|
while True:
|
|
yield b
|
|
a, b = b, a + b
|
|
|
|
def pyset_J(x):
|
|
powers = powers_of_two(x)
|
|
return frozenset(pyset_J(i) for i in powers)
|
|
|
|
def pyset_lesser(x, y):
|
|
only_x = x.difference(y)
|
|
only_y = y.difference(x)
|
|
|
|
if only_x == frozenset() and only_y != frozenset():
|
|
return True
|
|
elif only_y == frozenset():
|
|
return False
|
|
else:
|
|
x_max_power = functools.reduce(lambda a, b: b if pyset_lesser(a,b) else a, only_x)
|
|
y_max_power = functools.reduce(lambda a, b: b if pyset_lesser(a,b) else a, only_y)
|
|
return pyset_lesser(x_max_power, y_max_power)
|
|
|
|
def pyset_lshift(x, y):
|
|
return frozenset(pyset_add(i, y) for i in x)
|
|
|
|
def pyset_double(x):
|
|
return pyset_lshift(x, pyset_J(1))
|
|
|
|
def pyset_add(x, y):
|
|
only_x = x.difference(y)
|
|
only_y = y.difference(x)
|
|
one = only_x.union(only_y)
|
|
both = x.intersection(y)
|
|
|
|
if both == frozenset():
|
|
return one
|
|
else:
|
|
return pyset_add(one, pyset_double(both))
|
|
|
|
def pyset_fibonacci():
|
|
a = pyset_J(0)
|
|
b = pyset_J(1)
|
|
|
|
yield a
|
|
while True:
|
|
yield b
|
|
a, b = b, pyset_add(a, b)
|
|
|
|
if __name__ == '__main__':
|
|
start_time = time.monotonic()
|
|
limit = J(2**128)
|
|
for number in fibonacci():
|
|
if lesser(limit, number):
|
|
break
|
|
#print(I(number), tuple(map(I, number)), str(number))
|
|
print(time.monotonic() - start_time)
|
|
|
|
start_time = time.monotonic()
|
|
limit = pyset_J(2**128)
|
|
for number in pyset_fibonacci():
|
|
if pyset_lesser(limit, number):
|
|
break
|
|
print(time.monotonic() - start_time)
|
|
|
|
start_time = time.monotonic()
|
|
limit = 2**128
|
|
for number in py_fibonacci():
|
|
if limit < number:
|
|
break
|
|
print(time.monotonic() - start_time)
|