Zeckendorf arithmetic: Difference between revisions
m
→{{header|11l}}: Void
SqrtNegInf (talk | contribs) m (→{{header|Julia}}: Fix link: Perl 6 --> Raku) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
(27 intermediate revisions by 14 users not shown) | |||
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}}
<syntaxhighlight 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() -> 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)</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
=={{header|C}}==
{{trans|D}}
<
#include <stdio.h>
#include <string.h>
Line 260 ⟶ 425:
return 0;
}</
{{out}}
<pre>Addition:
Line 279 ⟶ 444:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Text;
Line 467 ⟶ 632:
}
}
}</
{{out}}
<pre>Addition:
Line 486 ⟶ 651:
=={{header|C++}}==
{{works with|C++11}}
<
// I define an increment operation ++()
// I define a comparison operation <=(other N)
Line 558 ⟶ 723:
return os;
}
</syntaxhighlight>
===Testing===
The following tests addtition:
<
N G;
G = 10N;
Line 575 ⟶ 740:
std::cout << G << std::endl;
return 0;
}</
{{out}}
<pre>
Line 585 ⟶ 750:
</pre>
The following tests subtraction:
<
N G;
G = 1000N;
Line 594 ⟶ 759:
std::cout << G << std::endl;
return 0;
}</
{{out}}
<pre>
Line 601 ⟶ 766:
</pre>
The following tests multiplication:
<
int main(void) {
N G = 1001N;
Line 611 ⟶ 776:
std::cout << G << std::endl;
return 0;
}</
{{out}}
<pre>
Line 620 ⟶ 785:
=={{header|D}}==
{{trans|Kotlin}}
<
int inv(int a) {
Line 791 ⟶ 956:
g += "101".Z;
writeln(g);
}</
{{out}}
<pre>Addition:
Line 807 ⟶ 972:
1000100
1000100</pre>
=={{header|Dart}}==
{{trans|Kotlin}}
<syntaxhighlight lang="Dart">
class Zeckendorf {
int dVal = 0;
int dLen = 0;
Zeckendorf(String x) {
var q = 1;
var i = x.length - 1;
dLen = i ~/ 2;
while (i >= 0) {
dVal += (x[i].codeUnitAt(0) - '0'.codeUnitAt(0)) * q;
q *= 2;
i--;
}
}
void a(int n) {
var i = n;
while (true) {
if (dLen < i) dLen = i;
var j = (dVal >> (i * 2)) & 3;
switch (j) {
case 0:
case 1:
return;
case 2:
if (((dVal >> ((i + 1) * 2)) & 1) != 1) return;
dVal += 1 << (i * 2 + 1);
return;
case 3:
dVal &= ~(3 << (i * 2));
b((i + 1) * 2);
break;
}
i++;
}
}
void b(int pos) {
if (pos == 0) {
this.increment();
return;
}
if (((dVal >> pos) & 1) == 0) {
dVal += 1 << pos;
a(pos ~/ 2);
if (pos > 1) a(pos ~/ 2 - 1);
} else {
dVal &= ~(1 << pos);
b(pos + 1);
b(pos - (pos > 1 ? 2 : 1));
}
}
void c(int pos) {
if (((dVal >> pos) & 1) == 1) {
dVal &= ~(1 << pos);
return;
}
c(pos + 1);
if (pos > 0)
b(pos - 1);
else
this.increment();
}
Zeckendorf increment() {
dVal += 1;
a(0);
return this;
}
void operator + (Zeckendorf other) {
for (var gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) b(gn);
}
}
void operator - (Zeckendorf other) {
for (var gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) c(gn);
}
while (dLen > 0 && (((dVal >> dLen * 2) & 3) == 0)) dLen--;
}
void operator * (Zeckendorf other) {
var na = other.copy();
var nb = other.copy();
Zeckendorf nt;
var nr = Zeckendorf("0");
for (var i = 0; i <= (dLen + 1) * 2; i++) {
if (((dVal >> i) & 1) > 0) nr + nb;
nt = nb.copy();
nb + na;
na = nt.copy();
}
dVal = nr.dVal;
dLen = nr.dLen;
}
int compareTo(Zeckendorf other) {
return dVal.compareTo(other.dVal);
}
@override
String toString() {
if (dVal == 0) return "0";
var sb = StringBuffer(dig1[(dVal >> (dLen * 2)) & 3]);
for (var i = dLen - 1; i >= 0; i--) {
sb.write(dig[(dVal >> (i * 2)) & 3]);
}
return sb.toString();
}
Zeckendorf copy() {
var z = Zeckendorf("0");
z.dVal = dVal;
z.dLen = dLen;
return z;
}
static final List<String> dig = ["00", "01", "10"];
static final List<String> dig1 = ["", "1", "10"];
}
void main() {
print("Addition:");
var g = Zeckendorf("10");
g + Zeckendorf("10");
print(g);
g + Zeckendorf("10");
print(g);
g + Zeckendorf("1001");
print(g);
g + Zeckendorf("1000");
print(g);
g + Zeckendorf("10101");
print(g);
print("\nSubtraction:");
g = Zeckendorf("1000");
g - Zeckendorf("101");
print(g);
g = Zeckendorf("10101010");
g - Zeckendorf("1010101");
print(g);
print("\nMultiplication:");
g = Zeckendorf("1001");
g * Zeckendorf("101");
print(g);
g = Zeckendorf("101010");
g + Zeckendorf("101");
print(g);
}
</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
=={{header|Elena}}==
{{trans|C++}}
ELENA
<
const dig = new string[]{"00","01","10"};
Line 858 ⟶ 1,202:
};
int v := (dVal $shr (i * 2))
v =>
0 { ^ self }
1 { ^ self }
2 {
ifnot ((dVal $shr ((i + 1) * 2)).allMask
{
^ self
Line 874 ⟶ 1,218:
3 {
int tmp := 3 $shl (i * 2);
tmp := tmp.
dVal := dVal
self.b((i+1)*2)
Line 894 ⟶ 1,238:
if (pos == 0) { ^ self.inc() };
ifnot((dVal $shr pos).allMask
{
dVal += (1 $shl pos);
Line 902 ⟶ 1,246:
else
{
dVal := dVal
self.b(pos + 1);
int arg := pos - ((pos > 1) ? 2 : 1);
Line 911 ⟶ 1,255:
private c(int pos)
{
if ((dVal $shr pos).allMask
{
int tmp := 1 $shl pos;
tmp := tmp.
dVal := dVal
^ self
Line 938 ⟶ 1,282:
int mLen := 0;
n.readContent(ref
m.readContent(ref mVal, ref mLen);
dLen := l;
for(int GN := 0; GN < (mLen + 1) * 2; GN += 1)
{
if ((mVal $shr GN).allMask
{
self.b(GN)
Line 955 ⟶ 1,302:
int mLen := 0;
n.readContent(ref
m.readContent(ref mVal, ref mLen);
dLen := l;
for(int GN := 0; GN < (mLen + 1) * 2; GN += 1)
{
if ((mVal $shr GN).allMask
{
self.c(GN)
Line 966 ⟶ 1,316:
};
while (((dVal $shr (dLen*2))
{
dLen -= 1
Line 974 ⟶ 1,324:
internal constructor product(ZeckendorfNumber n, ZeckendorfNumber m)
{
n.readContent(ref
dVal := v;
dLen := l;
ZeckendorfNumber Na := m;
Line 981 ⟶ 1,334:
ZeckendorfNumber Nt := 0n;
for(int i := 0
{
if (((dVal $shr i)
{
Nr += Nb
Line 992 ⟶ 1,345:
};
Nr.readContent(ref
dVal := v;
dLen := l;
}
Line 1,006 ⟶ 1,362:
{ ^ "0" };
string s := dig1[(dVal $shr (dLen * 2))
int i := dLen - 1;
while (i >= 0)
{
s := s + dig[(dVal $shr (i * 2))
i-=1
Line 1,059 ⟶ 1,415:
n += 101n;
console.printLine(n)
}</
{{out}}
<pre>
Line 1,078 ⟶ 1,434:
=={{header|Go}}==
{{trans|Kotlin}}
<
import (
Line 1,261 ⟶ 1,617:
g.PlusAssign(NewZeck("101"))
fmt.Println(g)
}</
{{out}}
Line 1,280 ⟶ 1,636:
1000100
</pre>
=={{header|Haskell}}==
We make Zeckendorf numbers first class citizens implementing instances of <code>Eq</code>, <code>Ord</code>, <code>Num</code>, <code>Enum</code>, <code>Real</code> and <code>Integral</code> classes. So everything that could be done with integral numbers is applicable with Zeckendorf numbers.
Addition and subtraction are done using cellular automata. Conversion from integers, multiplication and division are implemented via generalized Fibonacci series (Zeckendorf tables).
<syntaxhighlight lang="haskell">{-# LANGUAGE LambdaCase #-}
import Data.List (find, mapAccumL)
import Control.Arrow (first, second)
-- Generalized Fibonacci series defined for any Num instance, and for Zeckendorf numbers as well.
-- Used to build Zeckendorf tables.
fibs :: Num a => a -> a -> [a]
fibs a b = res
where
res = a : b : zipWith (+) res (tail res)
data Fib = Fib { sign :: Int, digits :: [Int]}
-- smart constructor
mkFib s ds =
case dropWhile (==0) ds of
[] -> 0
ds -> Fib s (reverse ds)
-- Textual representation
instance Show Fib where
show (Fib s ds) = sig s ++ foldMap show (reverse ds)
where sig = \case { -1 -> "-"; s -> "" }
-- Equivalence relation
instance Eq Fib where
Fib sa a == Fib sb b = sa == sb && a == b
-- Order relation
instance Ord Fib where
a `compare` b =
sign a `compare` sign b <>
case find (/= 0) $ alignWith (-) (digits a) (digits b) of
Nothing -> EQ
Just 1 -> if sign a > 0 then GT else LT
Just (-1) -> if sign a > 0 then LT else GT
-- Arithmetic
instance Num Fib where
negate (Fib s ds) = Fib (negate s) ds
abs (Fib s ds) = Fib 1 ds
signum (Fib s _) = fromIntegral s
fromInteger n =
case compare n 0 of
LT -> negate $ fromInteger (- n)
EQ -> Fib 0 [0]
GT -> Fib 1 . reverse . fst $ divModFib n 1
0 + a = a
a + 0 = a
a + b =
case (sign a, sign b) of
( 1, 1) -> res
(-1, 1) -> b - (-a)
( 1,-1) -> a - (-b)
(-1,-1) -> - ((- a) + (- b))
where
res = mkFib 1 . process $ 0:0:c
c = alignWith (+) (digits a) (digits b)
-- use cellular automata
process =
runRight 3 r2 . runLeftR 3 r2 . runRightR 4 r1
0 - a = -a
a - 0 = a
a - b =
case (sign a, sign b) of
( 1, 1) -> res
(-1, 1) -> - ((-a) + b)
( 1,-1) -> a + (-b)
(-1,-1) -> - ((-a) - (-b))
where
res = case find (/= 0) c of
Just 1 -> mkFib 1 . process $ c
Just (-1) -> - (b - a)
Nothing -> 0
c = alignWith (-) (digits a) (digits b)
-- use cellular automata
process =
runRight 3 r2 . runLeftR 3 r2 . runRightR 4 r1 . runRight 3 r3
0 * a = 0
a * 0 = 0
1 * a = a
a * 1 = a
a * b =
case (sign a, sign b) of
(1, 1) -> res
(-1, 1) -> - ((-a) * b)
( 1,-1) -> - (a * (-b))
(-1,-1) -> ((-a) * (-b))
where
-- use Zeckendorf table
table = fibs a (a + a)
res = sum $ onlyOnes $ zip (digits b) table
onlyOnes = map snd . filter ((==1) . fst)
-- Enumeration
instance Enum Fib where
toEnum = fromInteger . fromIntegral
fromEnum = fromIntegral . toInteger
instance Real Fib where
toRational = fromInteger . toInteger
-- Integral division
instance Integral Fib where
toInteger (Fib s ds) = signum (fromIntegral s) * res
where
res = sum (zipWith (*) (fibs 1 2) (fromIntegral <$> ds))
quotRem 0 _ = (0, 0)
quotRem a 0 = error "divide by zero"
quotRem a b = case (sign a, sign b) of
(1, 1) -> first (mkFib 1) $ divModFib a b
(-1, 1) -> second negate . first negate $ quotRem (-a) b
( 1,-1) -> first negate $ quotRem a (-b)
(-1,-1) -> second negate $ quotRem (-a) (-b)
------------------------------------------------------------
-- helper funtions
-- general division using Zeckendorf table
divModFib :: (Ord a, Num c, Num a) => a -> a -> ([c], a)
divModFib a b = (q, r)
where
(r, q) = mapAccumL f a $ reverse $ takeWhile (<= a) table
table = fibs b (b+b)
f n x = if n < x then (n, 0) else (n - x, 1)
-- application of rewriting rules
-- runs window from left to right
runRight n f = go
where
go [] = []
go lst = let (w, r) = splitAt n lst
(h: t) = f w
in h : go (t ++ r)
-- runs window from left to right and reverses the result
runRightR n f = go []
where
go res [] = res
go res lst = let (w, r) = splitAt n lst
(h: t) = f w
in go (h : res) (t ++ r)
-- runs reversed window and reverses the result
runLeftR n f = runRightR n (reverse . f . reverse)
-- rewriting rules from [C. Ahlbach et. all]
r1 = \case [0,3,0] -> [1,1,1]
[0,2,0] -> [1,0,1]
[0,1,2] -> [1,0,1]
[0,2,1] -> [1,1,0]
[x,0,2] -> [x,1,0]
[x,0,3] -> [x,1,1]
[0,1,2,0] -> [1,0,1,0]
[0,2,0,x] -> [1,0,0,x+1]
[0,3,0,x] -> [1,1,0,x+1]
[0,2,1,x] -> [1,1,0,x ]
[0,1,2,x] -> [1,0,1,x ]
l -> l
r2 = \case [0,1,1] -> [1,0,0]
l -> l
r3 = \case [1,-1] -> [0,1]
[2,-1] -> [1,1]
[1, 0, 0] -> [0,1,1]
[1,-1, 0] -> [0,0,1]
[1,-1, 1] -> [0,0,2]
[1, 0,-1] -> [0,1,0]
[2, 0, 0] -> [1,1,1]
[2,-1, 0] -> [1,0,1]
[2,-1, 1] -> [1,0,2]
[2, 0,-1] -> [1,1,0]
l -> l
alignWith :: (Int -> Int -> a) -> [Int] -> [Int] -> [a]
alignWith f a b = go [] a b
where
go res as [] = ((`f` 0) <$> reverse as) ++ res
go res [] bs = ((0 `f`) <$> reverse bs) ++ res
go res (a:as) (b:bs) = go (f a b : res) as bs</syntaxhighlight>
<pre>λ> 15 :: Fib
100010
λ> 153 :: Fib
10000010001
λ> [1..13] :: [Fib]
[1,10,100,101,1000,1001,1010,10000,10001,10010,10100,10101,100000]
λ> 15 + 47 :: Fib
100001010
λ> toInteger it
62
λ> 15 - 47 :: Fib
-1010100
λ> toInteger it
-32
λ> 15 * 47 :: Fib
10001000001001
λ> toInteger it
705
λ> 47 `div` 15 :: Fib
100
λ> 47 `mod` 15 :: Fib
10</pre>
=={{header|J}}==
Loosely based on the [[#Perl|perl]] implementation:<syntaxhighlight lang="j">zform=: {{ 10 |."1@(#.inv) y }} :. (10#.|."1) NB. use decimal numbers for representation
zinc=: {{ carry ({.,2}.])carry 1,y }}
zdec=: {{ (|.k$0 1),y }.~k=. 1+y i.1 }}
zadd=: {{ x while. 1 e. y do. x=. zinc x [ y=. zdec y end. }}
zsub=: {{ x while. 1 e. y do. x=. zdec x [ y=. zdec y end. }} NB. intended for unsigned arithmetic
zmul=: {{ t=. 0 0 while. 1 e. y do. t=. t zadd x [ y=. zdec y end. }}
zdiv=: {{ t=. 0 0 while. x zge y do. t=. zinc t [ x=. x zsub y end. }} NB. discards remainder
carry=: {{
s=. 0
for_b. y do.
if. (1+b) = s=. s-_1^b do. y=. (-.b) (b_index-0,b)} y end.
end.
if. 2=s do. y,1 else. y end.
}}
zge=: {{ cmp=. x -/@,: y while. (#cmp)*0={:cmp do. cmp=. }:cmp end. 0<:{:cmp }}</syntaxhighlight>
For example, we use the decimal number 10100 to represent 11 in base 10, and 1010 would represent 7. We convert these numbers to an internal zeckendorf representation and add them, then convert the result back to decimal 101000 which represents 18 in base 10.
Task examples:<syntaxhighlight lang="j"> 1 zadd&.zform 1
10
10 zadd&.zform 10
101
10100 zadd&.zform 1010
101000
10100 zsub&.zform 1010
101
10100 zmul&.zform 100101
10010010001
10100 zdiv&.zform 1010
1
10100 zdiv&.zform 1000
10
100001000001 zdiv&.zform 100010
100101
100001000001 zdiv&.zform 100101
100010</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|9}}
<
public class Zeckendorf implements Comparable<Zeckendorf> {
Line 1,469 ⟶ 2,089:
System.out.println(g);
}
}</
{{out}}
<pre>Addition:
Line 1,488 ⟶ 2,108:
=={{header|Julia}}==
Influenced by the format of the Tcl and Raku versions, but added other functionality.
<
const z0 = "0"
Line 1,660 ⟶ 2,280:
zeckendorftest()
</
Addition:
101
Line 1,683 ⟶ 2,303:
=={{header|Kotlin}}==
{{trans|C++}}
<
class Zeckendorf(x: String = "0") : Comparable<Zeckendorf> {
Line 1,838 ⟶ 2,458:
g += "101".Z
println(g)
}</
{{out}}
Line 1,858 ⟶ 2,478:
</pre>
=={{header|
{{trans|Go}}
<syntaxhighlight lang="nim">type Zeckendorf = object
dVal: Natural
dLen: Natural
const
Dig = ["00", "01", "10"]
Dig1 = ["", "1", "10"]
# Forward references.
func inc(z: var Zeckendorf)
func a(z: var Zeckendorf; n: Natural) =
var i = n
while true:
if z.dLen < i: z.dLen = i
let j = z.dVal shr (i * 2) and 3
case j
of 0, 1:
return
of 2:
if
of 3:
z.dVal = z.dVal and not (3 shl (i * 2))
z.b((i + 1) * 2)
else:
assert(false)
inc i
func b(z: var Zeckendorf; pos: Natural) =
if pos == 0:
inc z
return
if (z.dVal shr pos and 1) == 0:
z.dVal += 1 shl pos
z.a(pos div 2)
if pos > 1: z.a(pos div 2 - 1)
else:
z.dVal = z.dVal and
z.b(pos + 1)
z.b(pos - (if pos >
func c(z: var Zeckendorf; pos: Natural) =
if (z.dVal shr pos and 1) == 1:
return
z.c(pos + 1)
if pos > 0:
else:
func initZeckendorf(s = "0"): Zeckendorf =
var q = 1
var i = s.high
result.dLen = i div 2
while i >= 0:
result.dVal += (ord(s[i]) - ord('0')) * q
q *= 2
dec i
func inc(z: var Zeckendorf) =
inc z.dVal
z.a(0)
func `+=`(z1: var Zeckendorf; z2: Zeckendorf) =
for gn in 0 .. (2 * z2.dLen + 1):
if (z2.dVal shr gn and 1) == 1:
z1.b(gn)
func `-=`(z1: var Zeckendorf; z2: Zeckendorf) =
for gn in 0 .. (2 * z2.dLen + 1):
if (z2.dVal shr gn and 1) == 1:
z1.c(gn)
while z1.dLen > 0 and (z1.dVal shr (z1.dLen * 2) and 3) == 0:
dec z1.dLen
func `*=`(z1: var Zeckendorf; z2: Zeckendorf) =
var na, nb = z2
var nr: Zeckendorf
for i in 0 .. (z1.dLen + 1) * 2:
if (z1.dVal shr i and 1) > 0: nr += nb
let nt = nb
nb += na
na = nt
z1 = nr
func`$`(z: var Zeckendorf): string =
if z.dVal == 0: return "0"
result.add Dig1[z.dVal shr (z.dLen * 2) and 3]
for i in countdown(z.dLen - 1, 0):
result.add Dig[z.dVal shr (i * 2) and 3]
when isMainModule:
var g: Zeckendorf
echo "Addition:"
g = initZeckendorf("10")
g += initZeckendorf("10")
echo g
g += initZeckendorf("10")
echo g
g += initZeckendorf("1001")
echo g
g += initZeckendorf("1000")
echo g
g += initZeckendorf("10101")
echo g
echo "\nSubtraction:"
g = initZeckendorf("1000")
g -= initZeckendorf("101")
echo g
g = initZeckendorf("10101010")
g -= initZeckendorf("1010101")
echo g
echo "\nMultiplication:"
g = initZeckendorf("1001")
g *= initZeckendorf("101")
echo g
g = initZeckendorf("101010")
g += initZeckendorf("101")
echo g</syntaxhighlight>
{{out}}
<pre>Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">use v5.36;
package Zeckendorf;
use overload qw("" zstring + zadd - zsub ++ zinc -- zdec * zmul / zdiv ge zge);
sub new ($class, $value) {
bless \$value, ref $class || $class;
}
sub zinc ($self, $, $) {
local $_ = $$self;
s/0$/1/ or s/(?:^|0)1$/10/;
1 while s/(?:^|0)11/100/;
$$self = $self->new( s/^0+\B//r )
}
sub zdec ($self, $, $) {
local $_ = $$self;
1 while s/100(?=0*$)/011/;
s/1$/0/ || s/10$/01/;
$$self = $self->new( s/^0+\B//r )
}
sub zadd ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
$x++, $y-- while $$y;
$x
}
sub zsub ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
$x--, $y-- while $$y;
$x
}
sub zmul ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
my $product = Zeckendorf->new(0);
$product = $product + $x, $y-- while $y;
$product
}
sub zdiv ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
my $quotient = Zeckendorf->new(0);
$quotient++, $x = $x - $y while $x ge $y;
$quotient
}
sub zge ($self, $other, $) {
my $l; $l = length $$other if length $other > ($l = length $$self);
0 x ($l - length $$self) . $$self ge 0 x ($l - length $$other) . $$other;
}
sub asdecimal ($self) {
my($aa, $bb, $n) = (1, 1, 0);
for ( reverse split '', $$self ) {
$n += $bb * $_;
($aa, $bb) = ($bb, $aa + $bb);
}
$n
}
sub fromdecimal ($self, $value) {
my $z = $self->new(0);
$z++ for 1 .. $value;
$z
}
sub zstring { ${ shift() } }
package main;
for ( split /\n/, <<END ) # test cases
1 + 1
10 + 10
10100 + 1010
10100 - 1010
10100 * 1010
100010 * 100101
10100 / 1010
101000 / 1000
100001000001 / 100010
100001000001 / 100101
END
{
my ($left, $op, $right) = split;
my ($x, $y) = map Zeckendorf->new($_), $left, $right;
my $answer =
$op eq '+' ? $x + $y :
$op eq '-' ? $x - $y :
$op eq '*' ? $x * $y :
$op eq '/' ? $x / $y :
die "bad op <$op>";
printf "%12s %s %-9s => %12s in Zeckendorf\n", $x, $op, $y, $answer;
printf "%12d %s %-9d => %12d in decimal\n\n",
$x->asdecimal, $op, $y->asdecimal, $answer->asdecimal;
}</syntaxhighlight>
{{out}}
<pre> 1 + 1 => 10 in Zeckendorf
1 + 1 => 2 in decimal
10 + 10 => 101 in Zeckendorf
2 + 2 => 4 in decimal
10100 + 1010 => 101000 in Zeckendorf
11 + 7 => 18 in decimal
10100 - 1010 => 101 in Zeckendorf
11 - 7 => 4 in decimal
10100 * 1010 => 101000001 in Zeckendorf
11 * 7 => 77 in decimal
100010 * 100101 => 100001000001 in Zeckendorf
15 * 17 => 255 in decimal
10100 / 1010 => 1 in Zeckendorf
11 / 7 => 1 in decimal
101000 / 1000 => 100 in Zeckendorf
18 / 5 => 3 in decimal
100001000001 / 100010 => 100101 in Zeckendorf
255 / 15 => 17 in decimal
100001000001 / 100101 => 100010 in Zeckendorf
255 / 17 => 15 in decimal</pre>
=={{header|Phix}}==
Uses a binary representation of Zeckendorf numbers, eg decimal 11 is stored as 0b10100, ie meaning 8+3, but actually 20 in decimal.<br>
As such, they can be directly compared using the standard comparison operators, and printed quite trivially just by using the %b format.<br>
They are however (and not all that surprisingly) pulled apart into individual bits for addition/subtraction, etc.<br>
Does not handle negative numbers or anything >139583862445 (-ve probably doable but messy, >1.4e12 requires a total rewrite, probably using string representation).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">fib</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zeckendorf</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Same as [[Zeckendorf_number_representation#Phix]]</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[$]<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">fib</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">c</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">*</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Convert Zeckendorf number(s) to decimal</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">z</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bit</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">bit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bit</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">fib</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">dec</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">to_bits</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Simplified copy of int_to_bits(), but in reverse order,
-- and +ve only but (also only) as many bits as needed, and
-- ensures there are *two* trailing 0 (most significant)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- sanity/avoid infinite loop</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">bits</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (since eg 101+101 -> 10000)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">bits</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">to_bits2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Apply to_bits() to a and b, and pad to the same length</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sa</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">to_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">to_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">diff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">)-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">sa</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span> <span style="color: #000000;">sb</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">to_int</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">bits</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Copy of bits_to_int(), but in reverse order (lsb last)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">val</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">val</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">val</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%b"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">was</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">wth</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- helper for cleanup, validates replacements </span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">de</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">was</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">..</span><span style="color: #000000;">de</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">was</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">was</span><span style="color: #0000FF;">)!=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wth</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">..</span><span style="color: #000000;">de</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wth</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zcleanup</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (shared by zadd and zsub)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- first stage, left to right, {020x -> 100x', 030x -> 110x', 021x->110x, 012x->101x}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- first stage cleanup</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 030 -> 111</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 020 -> 101</span>
<span style="color: #008080;">else</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 0120 -> 1010</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 03 -> 11</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 02 -> 10</span>
<span style="color: #008080;">else</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 012 -> 101</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- second stage, pass 1, right to left, 011 -> 100</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- second stage, pass 2, left to right, 011 -> 100</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]={</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">to_int</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">to_bits2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">zcleanup</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zinc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">to_bits2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sb</span><span style="color: #0000FF;">))</span>
<span style="color: #000080;font-style:italic;">-- (/not/ combined with the first pass of the add routine!)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s3</span><span style="color: #0000FF;">={</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- copied from PicoLisp: {1,-1} -> {0,1} and {2,-1} -> {1,1}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">={</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- sanity check</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">zcleanup</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zdec</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mult</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)}</span> <span style="color: #000080;font-style:italic;">-- (as per task desc)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">bits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">bits</span><span style="color: #0000FF;"><</span><span style="color: #000000;">b</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">mult</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">bit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">b</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bit</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mult</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">bits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">mult</span><span style="color: #0000FF;">[$]<</span><span style="color: #000000;">a</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">mult</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mult</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mult</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">a</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (a is the remainder)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">zi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zeckendorf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zi</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d: %7b (%d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">zres</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">):</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" rem "</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">dres</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)?</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"%d rem %d"</span><span style="color: #0000FF;">),</span><span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">aka</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"aka %d %s %d = %s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">),</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">decimal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">),</span><span style="color: #000000;">dres</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zres</span><span style="color: #0000FF;">=</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" *** ERROR ***!!"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s %s %s = %s, %s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">),</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zstr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">),</span><span style="color: #000000;">zres</span><span style="color: #0000FF;">,</span><span style="color: #000000;">aka</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ok</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b0</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b0</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10000"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1001"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1000100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1000101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1000101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1001 rem 1"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1001"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"100101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1010000"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10101010</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10101010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1000000"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1000100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101010</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1000100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101000"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101000</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100010</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100101</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"100001000001"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100001000001</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b100001000001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101010001 rem 0"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101000101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101000101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b101001</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101010000010101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101010000010101</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b101010000010101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1001010001001 rem 10"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100010010100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100010010100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"100000000010101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100010010100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100010010100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10010001000010"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10000</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1001000001</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10100010010100"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1010001010000001001</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100000000100000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b1010001010000001001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b100000000100000</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10001 rem 10100001010101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zadd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101000"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zsub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"101000001"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"1 rem 101"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b10100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1010</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"10100 rem 0"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,186 ⟶ 3,106:
=={{header|PicoLisp}}==
<syntaxhighlight lang="text">(seed (in "/dev/urandom" (rd 8)))
(de unpad (Lst)
Line 2,318 ⟶ 3,238:
(test (numz (- X 1)) (decz (numz X))) ) )
(bye)</
=={{header|Python}}==
<
class Zeckendorf:
Line 2,464 ⟶ 3,384:
g = Zeckendorf("101010")
g = g + Zeckendorf("101")
print g</
{{out}}
<pre>Addition:
Line 2,480 ⟶ 3,400:
1000100
1000100</pre>
=={{header|Quackery}}==
Unsigned (non-negative) Zeckendorf arithmetic.
Implements the required functions; addition, subtraction, multiplication and division, the optional decrement, increment and comparative functions, and additionally double and modulus, since they come for free with addition and division respectively.
The algorithms are of my own devising, without reference to the description in the task or existing research, so are potentially novel, but probably not.
I really should have taken notes as I was going along, so here is the hand-wavy explanation:
Mostly Zeckendorf numbers are represented bitwise to benefit from the inherent parallelism of bitwise logic, but occasionally as nests (the Quackery name for dynamic arrays) of 0s and 1s for ease of coding.
The word <code>canonise</code> puts a Zecekendorf number in canonical form; no two adjacent bits are set to 1, runs of 0s are allowed. The converse operation, <code>defrock</code> puts a number as far from canonical form as possible; no two adjacent bits are set to 0, runs of 1s are allowed. Despite their similarities they are coded quite differently as there was a long gap between coding one and then the other and as noted above, I didn't take notes.
Addition works by isolating the bits in both arguments that are set to 1, removing them from both and then bitwise xoring them together and canonising. After this the isolated bits are doubled and these two numbers (the xored number and the isolated bits number) are added. This is repeated until the xored number is 0. Doubling is achieved by shifting the number an appropriate distance left and right and adding the left shifted and right shifted numbers. <code>zadd</code> and <code>zdouble</code> are mutually recursive.
<code>2blit</code> separates the lowest two bits from a Zeckedorf number so that <code>zdouble</code> can treat them as a special case.
Multiplication is basically the Russian Peasant algorithm with the twist that instead of doubling we start with two instances of one of the multiplicands and repeatedly add them Fibonacci style.
Subtraction is implemented as ''difference'' (i.e. abs(a-b) as this is an unsigned implementation.) The process is to reduce both numbers in value until the smaller one equals zero. Continuing the naming theme established by <code>canonise</code> and <code>defrock</code>, the word that removes the bits that are set to 1 in both arguments is called <code>exorcise</code>. The appropriate sequence of exorcisms and defrockings will reduce the smaller argument to zero much of the time.
However, numbers which alternate 1s and 0s (e.g. ...01010101...) are immune to both canonisation and defrocking. When this occurs we add the smaller number to the larger number and double the smaller number and repeat the exorisms and defrockings. Extensive testing leads me to believe with a very high degree of confidence this is sufficient, but I have not proved it in a mathematical sense.
Division is basic binary long division with a twist; instead of multiplying the divisor by 2 until it's large enough, use it to make a fibonacci style sequence, except starting with a couple of copies of the divisor rather than 1s.
The while-again loop computes a nest of all the fibonacci multiples up to the dividend, the witheach loop tries subracting each one from largest to smallest and builds up the result accordingly. The remainder (modulus) comes for free as what is left at the end of all the subtractions.
To demonstrate that these words correctly implement Zeckendorf arithmetic, I have used them to implement Euclid's algorithm for Greatest Common Denominator, and used that to implement Largest Common Multiple. We repeatedly give <code>zlcm</code> two random numbers up to one quintillion (converted to Zeckendorf notation) and print the result (converted back to decimal), next to the same computation made using the conventional representation. <code>zgcd</code> and <code>zlcm</code> exercise the multiplication, division and modulus routines repeatedly, and those exercise the addition, subtraction and comparison routines.
<code>bin</code> is an extension to the Quackery compiler to allow it to understand numbers in binary notation (and hence also Zeckendorf notation).
<code>gcd</code> and <code>lcm</code> are defined at [[Least common multiple#Quackery]], and <code>n->z</code> and <code>z->n</code> are defined at [[Zeckendorf number representation#Quackery]].
<syntaxhighlight lang="Quackery"> [ nextword
dup $ "" = if
[ $ '"bin" needs to be followed by a string.'
message put bail ]
dup
2 base put
$->n
base release
not if
[ drop
$ " is not a binary number."
join message put
bail ]
nip
swap dip join ] builds bin ( [ $ --> [ $ )
[ ^ not ] is zeq ( z z --> b )
[ zeq not ] is zne ( z z --> b )
[ false unrot
[ 2dup zne while
rot drop
dup 1 & unrot
1 >> dip [ 1 >> ]
again ]
2drop ] is zlt ( z z --> b )
[ swap zlt ] is zgt ( z z --> b )
[ zlt not ] is zge ( z z --> b )
[ zgt not ] is zle ( z z --> b )
[ dup 1 << & 0 zeq ] is canonical ( z --> b )
[ [] swap
[ dup 1 & rot join
swap 1 >>
dup not until ]
drop ] is bits ( z --> [ )
[ dup canonical if done
0 0 rot bits
witheach
[ |
[ table
[ 1 << 0 ]
[ 1 << 1 | bin 10 ]
[ 1 << 0 ]
[ 1 >> 1 |
bin 10 << 0 ] ]
do ]
drop again ] is canonise ( z --> z )
[ dup bin -100
& swap bin 11 & ] is 2blit ( z --> z z )
[ 2blit bit | canonise ] is zinc ( z --> z )
[ dup 0 zeq if
[ $ "Cannot zdec zero."
fail ]
1
[ 2dup & if done
1 << again ]
tuck ^
swap 1 <<
[ bin 10 >>
tuck | swap
dup 0 zeq until ]
drop ] is zdec ( z --> z )
forward is zadd ( z --> z )
[ dup 2blit
[ table
0 bin 10 bin 101 ]
unrot bin 10 >>
swap 1 <<
rot | zadd ] is zdouble ( z --> z )
[ 2dup ^ canonise
unrot &
dup 0 zeq iff
drop done
zdouble again ] resolves zadd ( z z --> z )
[ tuck take zadd swap put ] is ztally ( z s --> )
[ 0 temp put
dip dup
[ dup while
dup 1 & if
[ over temp ztally ]
dip [ tuck zadd ]
1 >> again ]
drop 2drop temp take ] is zmult ( z z --> z )
[ 2dup & ~ tuck & dip & ] is exorcise ( z z --> z z )
[ dup
[ 0 ' [ 0 0 0 ] rot 1
[ 2dup > while
1 << again ]
1 <<
[ dup while
2swap 2over & 0 !=
dip
[ dup
' [ 1 0 0 ]
= if
[ drop
' [ 0 1 1 ] ] ]
join
behead
rot 1 << | swap
2swap 1 >> again ]
2drop
witheach
[ dip [ 1 << ] | ]
dup bin 111 &
bin 100 zeq if
[ bin -1000 &
bin 11 | ] ]
2dup zeq iff drop done
nip again ] is defrock ( z --> z )
[ 2dup zlt if swap
dup 0 zeq iff drop done
[ exorcise dup while
dip defrock
exorcise dup while
dup dip zadd
zdouble
again ]
drop canonise ] is zdiff ( z z --> z )
[ dup 0 zeq if
[ $ "Z-division by zero."
fail ]
0 unrot swap
temp put
dup nested
[ dup 0 peek
tuck dip rot zadd
temp share
over zge while
swap join
again ]
drop nip
temp take
swap witheach
[ rot 1 << unrot
2dup zge iff
[ zdiff
dip [ 1 | ] ]
else drop ] ] is zdivmod ( z z --> z z )
[ zdivmod drop ] is zdiv ( z z --> z )
[ zdivmod nip ] is zmod ( z z --> z )
[ [ dup while
tuck zmod again ]
drop ] is zgcd ( z z --> z )
[ 2dup and iff
[ 2dup zgcd
zdiv zmult ]
else and ] is zlcm ( z z --> z )
10 times
[ 10 15 ** random
10 15 ** random
2dup lcm echo cr
n->z dip n->z
zlcm z->n echo cr cr ]</syntaxhighlight>
{{out}}
<pre>25624571429859946191396654570
25624571429859946191396654570
24702413608219494319878326100
24702413608219494319878326100
177592191573881063687998734000
177592191573881063687998734000
28221788451919578670971892845
28221788451919578670971892845
99008448632249766843573255321
99008448632249766843573255321
312648960463735816244223692220
312648960463735816244223692220
146093274904252809568841733264
146093274904252809568841733264
169485448104022309641359784180
169485448104022309641359784180
593337022246602746222083444716
593337022246602746222083444716
50904418052185753625716614402
50904418052185753625716614402
</pre>
=={{header|Racket}}==
This implementation only handles natural (non-negative numbers). The algorithms for addition and subtraction use the techniques explained in the paper "Efficient algorithms for Zeckendorf arithmetic" (http://arxiv.org/pdf/1207.4497.pdf).
<
(define sqrt5 (sqrt 5))
Line 2,679 ⟶ 3,845:
(example '/ zeck-quotient 9876 1000)
(example '% zeck-remainder 9876 1000)
</syntaxhighlight>
{{output}}
Line 2,692 ⟶ 3,858:
=={{header|Raku}}==
(formerly Perl 6)
This is a somewhat limited implementation of Zeckendorf arithmetic operators. They only handle positive integer values. There are no actual calculations, everything is done with string manipulations, so it doesn't matter what glyphs you use for 1 and 0.
Implemented arithmetic operators:
Comparison operators:
<syntaxhighlight lang="raku"
my $z0 = '0'; # glyph to use for a '0'
sub zorder($a) { ($z0 lt $z1) ?? $a !! $a.trans([$z0, $z1] => [$z1, $z0]) }
######## Zeckendorf comparison operators #########
# less than
sub infix:<ltz>($a, $b) { $a.&zorder lt $b.&zorder }
# greater than
sub infix:<gtz>($a, $b) { $a.&zorder gt $b.&zorder }
# equal
sub infix:<eqz>($a, $b) { $a eq $b }
# not equal
sub infix:<nez>($a, $b) { $a ne $b }
######## Operators for Zeckendorf arithmetic ########
Line 2,747 ⟶ 3,913:
# addition
sub infix:<+z>($a is copy, $b is copy) { $a++z; $a++z while $b--z nez $z0; $a }
# subtraction
sub infix:<-z>($a is copy, $b is copy) { $a--z; $a--z while $b--z nez $z0; $a }
# multiplication
sub infix:<
return $z0 if $a eqz $z0 or $b eqz $z0;
return $a if $b eqz $z1;
Line 2,765 ⟶ 3,931:
} until $d eqz $b;
$c
}
# division (really more of a div mod)
Line 2,780 ⟶ 3,946:
$c ~= " remainder $a" if $a nez $z0;
$c
}
###################### Testing ######################
# helper sub to translate constants into the particular glyphs you used
sub z($a) { $a.trans([<1 0>] => [$z1, $z0]) }
say "Using the glyph '$z1' for 1 and '$z0' for 0\n";
Line 2,799 ⟶ 3,965:
printf $fmt, "$zeck -z {z('100')}", $zeck -z= z('100'), '# subtraction';
printf $fmt, "$zeck
printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';
Line 2,805 ⟶ 3,971:
printf( $fmt, "$zeck--z", $zeck--z, '# decrement' ) for 1 .. 5;
printf $fmt, "$zeck
printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';</
'''Testing Output'''
Line 2,825 ⟶ 3,991:
10100 +z 1010 = 101000 # addition
101000 -z 100 = 100010 # subtraction
100010
100001000001 /z 100 = 101010001 # division
101010001--z = 101010000 # decrement
Line 2,832 ⟶ 3,998:
101001001--z = 101001000 # decrement
101001000--z = 101000101 # decrement
101000101
101010000010101 /z 100 = 1001010001001 remainder 10 # division</pre>
Using alternate glyphs:
<pre>
Using the glyph 'X' for 1 and 'O' for 0
Line 2,850 ⟶ 4,016:
XOXOO +z XOXO = XOXOOO # addition
XOXOOO -z XOO = XOOOXO # subtraction
XOOOXO
XOOOOXOOOOOX /z XOO = XOXOXOOOX # division
XOXOXOOOX--z = XOXOXOOOO # decrement
Line 2,857 ⟶ 4,023:
XOXOOXOOX--z = XOXOOXOOO # decrement
XOXOOXOOO--z = XOXOOOXOX # decrement
XOXOOOXOX
XOXOXOOOOOXOXOX /z XOO = XOOXOXOOOXOOX remainder XO # division</pre>
=={{header|Rust}}==
{{trans|C#}}
<syntaxhighlight lang="Rust">
struct Zeckendorf {
d_val: i32,
d_len: i32,
}
impl Zeckendorf {
fn new(x: &str) -> Zeckendorf {
let mut d_val = 0;
let mut q = 1;
let mut i = x.len() as i32 - 1;
let d_len = i / 2;
while i >= 0 {
d_val += (x.chars().nth(i as usize).unwrap() as i32 - '0' as i32) * q;
q *= 2;
i -= 1;
}
Zeckendorf { d_val, d_len }
}
fn a(&mut self, n: i32) {
let mut i = n;
loop {
if self.d_len < i {
self.d_len = i;
}
let j = (self.d_val >> (i * 2)) & 3;
match j {
0 | 1 => return,
2 => {
if ((self.d_val >> ((i + 1) * 2)) & 1) != 1 {
return;
}
self.d_val += 1 << (i * 2 + 1);
return;
}
3 => {
let temp = 3 << (i * 2);
let temp = !temp;
self.d_val &= temp;
self.b((i + 1) * 2);
}
_ => (),
}
i += 1;
}
}
fn b(&mut self, pos: i32) {
if pos == 0 {
self.inc();
return;
}
if ((self.d_val >> pos) & 1) == 0 {
self.d_val += 1 << pos;
self.a(pos / 2);
if pos > 1 {
self.a(pos / 2 - 1);
}
} else {
let temp = 1 << pos;
let temp = !temp;
self.d_val &= temp;
self.b(pos + 1);
self.b(pos - if pos > 1 { 2 } else { 1 });
}
}
fn c(&mut self, pos: i32) {
if ((self.d_val >> pos) & 1) == 1 {
let temp = 1 << pos;
let temp = !temp;
self.d_val &= temp;
return;
}
self.c(pos + 1);
if pos > 0 {
self.b(pos - 1);
} else {
self.inc();
}
}
fn inc(&mut self) -> &mut Self {
self.d_val += 1;
self.a(0);
self
}
fn copy(&self) -> Zeckendorf {
Zeckendorf {
d_val: self.d_val,
d_len: self.d_len,
}
}
fn plus_assign(&mut self, other: &Zeckendorf) {
for gn in 0..(other.d_len + 1) * 2 {
if ((other.d_val >> gn) & 1) == 1 {
self.b(gn);
}
}
}
fn minus_assign(&mut self, other: &Zeckendorf) {
for gn in 0..(other.d_len + 1) * 2 {
if ((other.d_val >> gn) & 1) == 1 {
self.c(gn);
}
}
while (((self.d_val >> self.d_len * 2) & 3) == 0) || (self.d_len == 0) {
self.d_len -= 1;
}
}
fn times_assign(&mut self, other: &Zeckendorf) {
let mut na = other.copy();
let mut nb = other.copy();
let mut nt;
let mut nr = Zeckendorf::new("0");
for i in 0..(self.d_len + 1) * 2 {
if ((self.d_val >> i) & 1) > 0 {
nr.plus_assign(&nb);
}
nt = nb.copy();
nb.plus_assign(&na);
na = nt.copy(); // `na` is now mutable, so this reassignment is allowed
}
self.d_val = nr.d_val;
self.d_len = nr.d_len;
}
fn to_string(&self) -> String {
if self.d_val == 0 {
return "0".to_string();
}
let dig = ["00", "01", "10"];
let dig1 = ["", "1", "10"];
let idx = (self.d_val >> (self.d_len * 2)) & 3;
let mut sb = String::from(dig1[idx as usize]);
for i in (0..self.d_len).rev() {
let idx = (self.d_val >> (i * 2)) & 3;
sb.push_str(dig[idx as usize]);
}
sb
}
}
fn main() {
println!("Addition:");
let mut g = Zeckendorf::new("10");
g.plus_assign(&Zeckendorf::new("10"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("10"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("1001"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("1000"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("10101"));
println!("{}", g.to_string());
println!();
println!("Subtraction:");
g = Zeckendorf::new("1000");
g.minus_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
g = Zeckendorf::new("10101010");
g.minus_assign(&Zeckendorf::new("1010101"));
println!("{}", g.to_string());
println!();
println!("Multiplication:");
g = Zeckendorf::new("1001");
g.times_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
g = Zeckendorf::new("101010");
g.plus_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
}
</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
=={{header|Scala}}==
{{works with|Scala|2.13.1}}
The addition is an implementation of an algorithm suggested in http[:]//arxiv.org/pdf/1207.4497.pdf: Efficient Algorithms for Zeckendorf Arithmetic.
<syntaxhighlight lang="scala">
import scala.collection.mutable.ListBuffer
Line 3,195 ⟶ 4,564:
}
</syntaxhighlight>
Output:
<pre style="height: 30ex; overflow: scroll">101Z(i:4) + 10100Z(i:11) = 100010Z(i:15)
Line 3,235 ⟶ 4,604:
=={{header|Tcl}}==
{{trans|
<
# Want to use alternate symbols? Change these
variable zero "0"
Line 3,310 ⟶ 4,679:
namespace export \[a-y\]*
namespace ensemble create
}</
Demonstrating:
<
puts [zeckendorf sub "10100" "1010"]
puts [zeckendorf mul "10100" "1010"]
puts [zeckendorf div "10100" "1010"]
puts [zeckendorf div [zeckendorf mul "10100" "1010"] "1010"]</
{{out}}
<pre>
Line 3,328 ⟶ 4,697:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 3,525 ⟶ 4,894:
End Sub
End Module</
{{out}}
<pre>Addition:
Line 3,541 ⟶ 4,910:
1000100
1000100</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">import strings
const (
dig = ["00", "01", "10"]
dig1 = ["", "1", "10"]
)
struct Zeckendorf {
mut:
d_val int
d_len int
}
fn new_zeck(xx string) Zeckendorf {
mut z := Zeckendorf{}
mut x := xx
if x == "" {
x = "0"
}
mut q := 1
mut i := x.len - 1
z.d_len = i / 2
for ; i >= 0; i-- {
z.d_val += int(x[i]-'0'[0]) * q
q *= 2
}
return z
}
fn (mut z Zeckendorf) a(ii int) {
mut i:=ii
for ; ; i++ {
if z.d_len < i {
z.d_len = i
}
j := (z.d_val >> u32(i*2)) & 3
if j in [0, 1] {
return
} else if j==2 {
if ((z.d_val >> (u32(i+1) * 2)) & 1) != 1 {
return
}
z.d_val += 1 << u32(i*2+1)
return
} else {// 3
z.d_val &= ~(3 << u32(i*2))
z.b((i + 1) * 2)
}
}
}
fn (mut z Zeckendorf) b(p int) {
mut pos := p
if pos == 0 {
z.inc()
return
}
if ((z.d_val >> u32(pos)) & 1) == 0 {
z.d_val += 1 << u32(pos)
z.a(pos / 2)
if pos > 1 {
z.a(pos/2 - 1)
}
} else {
z.d_val &= ~(1 << u32(pos))
z.b(pos + 1)
mut temp := 1
if pos > 1 {
temp = 2
}
z.b(pos - temp)
}
}
fn (mut z Zeckendorf) c(p int) {
mut pos := p
if ((z.d_val >> u32(pos)) & 1) == 1 {
z.d_val &= ~(1 << u32(pos))
return
}
z.c(pos + 1)
if pos > 0 {
z.b(pos - 1)
} else {
z.inc()
}
}
fn (mut z Zeckendorf) inc() {
z.d_val++
z.a(0)
}
fn (mut z1 Zeckendorf) plus_assign(z2 Zeckendorf) {
for gn := 0; gn < (z2.d_len+1)*2; gn++ {
if ((z2.d_val >> u32(gn)) & 1) == 1 {
z1.b(gn)
}
}
}
fn (mut z1 Zeckendorf) minus_assign(z2 Zeckendorf) {
for gn := 0; gn < (z2.d_len+1)*2; gn++ {
if ((z2.d_val >> u32(gn)) & 1) == 1 {
z1.c(gn)
}
}
for z1.d_len > 0 && ((z1.d_val>>u32(z1.d_len*2))&3) == 0 {
z1.d_len--
}
}
fn (mut z1 Zeckendorf) times_assign(z2 Zeckendorf) {
mut na := z2.copy()
mut nb := z2.copy()
mut nr := Zeckendorf{}
for i := 0; i <= (z1.d_len+1)*2; i++ {
if ((z1.d_val >> u32(i)) & 1) > 0 {
nr.plus_assign(nb)
}
nt := nb.copy()
nb.plus_assign(na)
na = nt.copy()
}
z1.d_val = nr.d_val
z1.d_len = nr.d_len
}
fn (z Zeckendorf) copy() Zeckendorf {
return Zeckendorf{z.d_val, z.d_len}
}
fn (z1 Zeckendorf) compare(z2 Zeckendorf) int {
if z1.d_val < z2.d_val {
return -1
} else if z1.d_val > z2.d_val {
return 1
} else {
return 0
}
}
fn (z Zeckendorf) str() string {
if z.d_val == 0 {
return "0"
}
mut sb := strings.new_builder(128)
sb.write_string(dig1[(z.d_val>>u32(z.d_len*2))&3])
for i := z.d_len - 1; i >= 0; i-- {
sb.write_string(dig[(z.d_val>>u32(i*2))&3])
}
return sb.str()
}
fn main() {
println("Addition:")
mut g := new_zeck("10")
g.plus_assign(new_zeck("10"))
println(g)
g.plus_assign(new_zeck("10"))
println(g)
g.plus_assign(new_zeck("1001"))
println(g)
g.plus_assign(new_zeck("1000"))
println(g)
g.plus_assign(new_zeck("10101"))
println(g)
println("\nSubtraction:")
g = new_zeck("1000")
g.minus_assign(new_zeck("101"))
println(g)
g = new_zeck("10101010")
g.minus_assign(new_zeck("1010101"))
println(g)
println("\nMultiplication:")
g = new_zeck("1001")
g.times_assign(new_zeck("101"))
println(g)
g = new_zeck("101010")
g.plus_assign(new_zeck("101"))
println(g)
}</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-trait}}
<syntaxhighlight lang="wren">import "./trait" for Comparable
class Zeckendorf is Comparable {
static dig { ["00", "01", "10"] }
static dig1 { ["", "1", "10"] }
construct new(x) {
var q = 1
var i = x.count - 1
_dLen = (i / 2).floor
_dVal = 0
while (i >= 0) {
_dVal = _dVal + (x[i].bytes[0] - 48) * q
q = q * 2
i = i - 1
}
}
dLen { _dLen }
dVal { _dVal }
dLen=(v) { _dLen = v }
dVal=(v) { _dVal = v }
a(n) {
var i = n
while (true) {
if (_dLen < i) _dLen = i
var j = (_dVal >> (i * 2)) & 3
if (j == 0 || j == 1) return
if (j == 2) {
if (((_dVal >> ((i + 1) * 2)) & 1) != 1) return
_dVal = _dVal + (1 << (i * 2 + 1))
return
}
if (j == 3) {
_dVal = _dVal & ~(3 << (i * 2))
b((i + 1) * 2)
}
i = i + 1
}
}
b(pos) {
if (pos == 0) {
var thiz = this
thiz.inc
return
}
if (((_dVal >> pos) & 1) == 0) {
_dVal = _dVal + (1 << pos)
a((pos / 2).floor)
if (pos > 1) a((pos / 2).floor - 1)
} else {
_dVal = _dVal & ~(1 << pos)
b(pos + 1)
b(pos - ((pos > 1) ? 2 : 1))
}
}
c(pos) {
if (((_dVal >> pos) & 1) == 1) {
_dVal = _dVal & ~(1 << pos)
return
}
c(pos + 1)
if (pos > 0) {
b(pos - 1)
} else {
var thiz = this
thiz.inc
}
}
inc {
_dVal = _dVal + 1
a(0)
return this
}
plusAssign(other) {
for (gn in 0...(other.dLen + 1) * 2) {
if (((other.dVal >> gn) & 1) == 1) b(gn)
}
}
minusAssign(other) {
for (gn in 0...(other.dLen + 1) * 2) {
if (((other.dVal >> gn) & 1) == 1) c(gn)
}
while ((((_dVal >> _dLen * 2) & 3) == 0) || (_dLen == 0)) _dLen = _dLen - 1
}
timesAssign(other) {
var na = other.copy()
var nb = other.copy()
var nr = Zeckendorf.new("0")
for (i in 0..(_dLen + 1) * 2) {
if (((_dVal >> i) & 1) > 0) nr.plusAssign(nb)
var nt = nb.copy()
nb.plusAssign(na)
na = nt.copy()
}
_dVal = nr.dVal
_dLen = nr.dLen
}
compare(other) { (_dVal - other.dVal).sign }
toString {
if (_dVal == 0) return "0"
var sb = Zeckendorf.dig1[(_dVal >> (_dLen * 2)) & 3]
if (_dLen > 0) {
for (i in _dLen - 1..0) {
sb = sb + Zeckendorf.dig[(_dVal >> (i * 2)) & 3]
}
}
return sb
}
copy() {
var z = Zeckendorf.new("0")
z.dVal = _dVal
z.dLen = _dLen
return z
}
}
var Z = Zeckendorf // type alias
System.print("Addition:")
var g = Z.new("10")
g.plusAssign(Z.new("10"))
System.print(g)
g.plusAssign(Z.new("10"))
System.print(g)
g.plusAssign(Z.new("1001"))
System.print(g)
g.plusAssign(Z.new("1000"))
System.print(g)
g.plusAssign(Z.new("10101"))
System.print(g)
System.print("\nSubtraction:")
g = Z.new("1000")
g.minusAssign(Z.new("101"))
System.print(g)
g = Z.new("10101010")
g.minusAssign(Z.new("1010101"))
System.print(g)
System.print("\nMultiplication:")
g = Z.new("1001")
g.timesAssign(Z.new("101"))
System.print(g)
g = Z.new("101010")
g.plusAssign(Z.new("101"))
System.print(g)</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100
</pre>
{{omit from|Brlcad}}
|