143 lines
3 KiB
Text
143 lines
3 KiB
Text
T Zeckendorf
|
||
Int dLen
|
||
dVal = 0
|
||
|
||
F (x = ‘0’)
|
||
V q = 1
|
||
V i = x.len - 1
|
||
.dLen = i I/ 2
|
||
L i >= 0
|
||
.dVal = .dVal + (x[i].code - ‘0’.code) * q
|
||
q = q * 2
|
||
i = i - 1
|
||
|
||
F a(n)
|
||
V i = n
|
||
L
|
||
I .dLen < i
|
||
.dLen = i
|
||
V j = (.dVal >> (i * 2)) [&] 3
|
||
I j == 0 | j == 1
|
||
R
|
||
I j == 2
|
||
I (.dVal >> ((i + 1) * 2) [&] 1) != 1
|
||
R
|
||
.dVal = .dVal + (1 << (i * 2 + 1))
|
||
R
|
||
I j == 3
|
||
V temp = 3 << (i * 2)
|
||
temp = temp (+) -1
|
||
.dVal = .dVal [&] temp
|
||
.b((i + 1) * 2)
|
||
i = i + 1
|
||
|
||
F b(pos)
|
||
I pos == 0
|
||
.inc()
|
||
R
|
||
I (.dVal >> pos) [&] 1 == 0
|
||
.dVal = .dVal + (1 << pos)
|
||
.a(Int(pos / 2))
|
||
I pos > 1
|
||
.a(Int(pos / 2) - 1)
|
||
E
|
||
V temp = 1 << pos
|
||
temp = temp (+) -1
|
||
.dVal = .dVal [&] temp
|
||
.b(pos + 1)
|
||
.b(pos - (I pos > 1 {2} E 1))
|
||
|
||
F c(pos)
|
||
I (.dVal >> pos) [&] 1 == 1
|
||
V temp = 1 << pos
|
||
temp = temp (+) -1
|
||
.dVal = .dVal [&] temp
|
||
R
|
||
.c(pos + 1)
|
||
I pos > 0
|
||
.b(pos - 1)
|
||
E
|
||
.inc()
|
||
|
||
F inc() -> Void
|
||
.dVal = .dVal + 1
|
||
.a(0)
|
||
|
||
F +(rhs)
|
||
V copy = (.)
|
||
V rhs_dVal = rhs.dVal
|
||
V limit = (rhs.dLen + 1) * 2
|
||
L(gn) 0 .< limit
|
||
I ((rhs_dVal >> gn) [&] 1) == 1
|
||
copy.b(gn)
|
||
R copy
|
||
|
||
F -(rhs)
|
||
V copy = (.)
|
||
V rhs_dVal = rhs.dVal
|
||
V limit = (rhs.dLen + 1) * 2
|
||
L(gn) 0 .< limit
|
||
I (rhs_dVal >> gn) [&] 1 == 1
|
||
copy.c(gn)
|
||
L (((copy.dVal >> ((copy.dLen * 2) [&] 31)) [&] 3) == 0) | (copy.dLen == 0)
|
||
copy.dLen = copy.dLen - 1
|
||
R copy
|
||
|
||
F *(rhs)
|
||
V na = copy(rhs)
|
||
V nb = copy(rhs)
|
||
V nr = Zeckendorf()
|
||
V dVal = .dVal
|
||
L(i) 0 .< (.dLen + 1) * 2
|
||
I ((dVal >> i) [&] 1) > 0
|
||
nr = nr + nb
|
||
V nt = copy(nb)
|
||
nb = nb + na
|
||
na = copy(nt)
|
||
R nr
|
||
|
||
F String()
|
||
V dig = [‘00’, ‘01’, ‘10’]
|
||
V dig1 = [‘’, ‘1’, ‘10’]
|
||
|
||
I .dVal == 0
|
||
R ‘0’
|
||
V idx = (.dVal >> ((.dLen * 2) [&] 31)) [&] 3
|
||
String sb = dig1[idx]
|
||
V i = .dLen - 1
|
||
L i >= 0
|
||
idx = (.dVal >> (i * 2)) [&] 3
|
||
sb ‘’= dig[idx]
|
||
i = i - 1
|
||
R sb
|
||
|
||
print(‘Addition:’)
|
||
V g = Zeckendorf(‘10’)
|
||
g = g + Zeckendorf(‘10’)
|
||
print(g)
|
||
g = g + Zeckendorf(‘10’)
|
||
print(g)
|
||
g = g + Zeckendorf(‘1001’)
|
||
print(g)
|
||
g = g + Zeckendorf(‘1000’)
|
||
print(g)
|
||
g = g + Zeckendorf(‘10101’)
|
||
print(g)
|
||
print()
|
||
|
||
print(‘Subtraction:’)
|
||
g = Zeckendorf(‘1000’)
|
||
g = g - Zeckendorf(‘101’)
|
||
print(g)
|
||
g = Zeckendorf(‘10101010’)
|
||
g = g - Zeckendorf(‘1010101’)
|
||
print(g)
|
||
print()
|
||
|
||
print(‘Multiplication:’)
|
||
g = Zeckendorf(‘1001’)
|
||
g = g * Zeckendorf(‘101’)
|
||
print(g)
|
||
g = Zeckendorf(‘101010’)
|
||
g = g + Zeckendorf(‘101’)
|
||
print(g)
|