Zeckendorf arithmetic: Difference between revisions
Added 11l
m (→{{header|Phix}}: added syntax colouring the hard way) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 69:
[http://arxiv.org/pdf/1207.4497.pdf Efficient algorithms for Zeckendorf arithmetic] is interesting. The sections on addition and subtraction are particularly relevant for this task.
=={{header|11l}}==
{{trans|Python}}
<lang 11l>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() -> N
.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)</lang>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
=={{header|C}}==
| |||