58 lines
1.3 KiB
Python
58 lines
1.3 KiB
Python
""" https://rosettacode.org/wiki/Knuth%27s_power_tree """
|
|
|
|
from typing import List, Dict
|
|
from mpmath import mp
|
|
|
|
# Set decimal precision for mpmath calculations (like Go example 320 bits)
|
|
mp.dps = 140
|
|
|
|
# Global variables
|
|
p: Dict[int, int] = {1: 0}
|
|
lvl: List[List[int]] = [[1]]
|
|
|
|
|
|
def path(n: int) -> List[int]:
|
|
""" return path to the node with id ''n'' """
|
|
if n == 0:
|
|
return []
|
|
|
|
while n not in p:
|
|
q: List[int] = []
|
|
for x in lvl[0]:
|
|
for y in path(x):
|
|
z = x + y
|
|
if z in p:
|
|
break
|
|
p[z] = x
|
|
q.append(z)
|
|
lvl[0] = q
|
|
|
|
r = path(p[n]) + [n]
|
|
return r
|
|
|
|
|
|
def tree_pow(x: float, n: int) -> mp.mpf:
|
|
""" use power tree to compute x ** n """
|
|
r: Dict[int, mp.mpf] = {0: mp.mpf('1'), 1: mp.mpf(str(x))}
|
|
prev = 0
|
|
for i in path(n):
|
|
r[i] = mp.mpf(r[i - prev] * r[prev])
|
|
prev = i
|
|
return r[n]
|
|
|
|
|
|
def show_pow(x: float, n: int) -> None:
|
|
""" print the power calculation """
|
|
print(f"{n}: {path(n)}")
|
|
y = tree_pow(x, n)
|
|
ans = mp.nstr(y, n=100, strip_zeros=True)[
|
|
:-2] if mp.isint(y) else mp.nstr(y, n=10)
|
|
print(f"{mp.nstr(x)} ^ {n} = {ans}\n")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
for expo in range(18):
|
|
show_pow(2, expo)
|
|
show_pow(1.1, 81)
|
|
show_pow(3.0, 191)
|