Jump to content

Zeckendorf arithmetic

From Rosetta Code
Task
Zeckendorf arithmetic
You are encouraged to solve this task according to the task description, using any language you may know.

This task is a total immersion zeckendorf task; using decimal numbers will attract serious disapprobation.

The task is to implement addition, subtraction, multiplication, and division using Zeckendorf number representation. Optionally provide decrement, increment and comparitive operation functions.

Addition

Like binary 1 + 1 = 10, note carry 1 left. There the similarity ends. 10 + 10 = 101, note carry 1 left and 1 right. 100 + 100 = 1001, note carry 1 left and 2 right, this is the general case.

Occurrences of 11 must be changed to 100. Occurrences of 111 may be changed from the right by replacing 11 with 100, or from the left converting 111 to 100 + 100;

Subtraction

10 - 1 = 1. The general rule is borrow 1 right carry 1 left. eg:

  abcde
  10100 -
   1000
  _____
    100  borrow 1 from a leaves 100
  + 100  add the carry
  _____
   1001

A larger example:

  abcdef
  100100 -
    1000
  ______
  1*0100 borrow 1 from b
   + 100 add the carry
  ______
  1*1001

Sadly we borrowed 1 from b which didn't have it to lend. So now b borrows from a:

    1001
  + 1000 add the carry
    ____
   10100
Multiplication

Here you teach your computer its zeckendorf tables. eg. 101 * 1001:

  a = 1 * 101 = 101
  b = 10 * 101 = a + a = 10000
  c = 100 * 101 = b + a = 10101
  d = 1000 * 101 = c + b = 101010

  1001 = d + a therefore 101 * 1001 =
 
  101010
   + 101
  ______
 1000100
Division

Lets try 1000101 divided by 101, so we can use the same table used for multiplication.

  1000101 -
   101010 subtract d (1000 * 101)
  _______
     1000 -
      101 b and c are too large to subtract, so subtract a
     ____
        1 so 1000101 divided by 101 is d + a (1001) remainder 1

Efficient algorithms for Zeckendorf arithmetic is interesting. The sections on addition and subtraction are particularly relevant for this task.

11l

Translation of: Python
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)
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

C

Translation of: D
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

int inv(int a) {
    return a ^ -1;
}

struct Zeckendorf {
    int dVal, dLen;
};

void a(struct Zeckendorf *self, int n) {
    void b(struct Zeckendorf *, int); // forward declare

    int i = n;
    while (true) {
        if (self->dLen < i) self->dLen = i;
        int j = (self->dVal >> (i * 2)) & 3;
        switch (j) {
        case 0:
        case 1:
            return;
        case 2:
            if (((self->dVal >> ((i + 1) * 2)) & 1) != 1) return;
            self->dVal += 1 << (i * 2 + 1);
            return;
        case 3:
            self->dVal = self->dVal & inv(3 << (i * 2));
            b(self, (i + 1) * 2);
            break;
        default:
            break;
        }
        i++;
    }
}

void b(struct Zeckendorf *self, int pos) {
    void increment(struct Zeckendorf *); // forward declare

    if (pos == 0) {
        increment(self);
        return;
    }
    if (((self->dVal >> pos) & 1) == 0) {
        self->dVal += 1 << pos;
        a(self, pos / 2);
        if (pos > 1) a(self, pos / 2 - 1);
    } else {
        self->dVal = self->dVal & inv(1 << pos);
        b(self, pos + 1);
        b(self, pos - (pos > 1 ? 2 : 1));
    }
}

void c(struct Zeckendorf *self, int pos) {
    if (((self->dVal >> pos) & 1) == 1) {
        self->dVal = self->dVal & inv(1 << pos);
        return;
    }
    c(self, pos + 1);
    if (pos > 0) {
        b(self, pos - 1);
    } else {
        increment(self);
    }
}

struct Zeckendorf makeZeckendorf(char *x) {
    struct Zeckendorf z = { 0, 0 };
    int i = strlen(x) - 1;
    int q = 1;

    z.dLen = i / 2;
    while (i >= 0) {
        z.dVal += (x[i] - '0') * q;
        q *= 2;
        i--;
    }

    return z;
}

void increment(struct Zeckendorf *self) {
    self->dVal++;
    a(self, 0);
}

void addAssign(struct Zeckendorf *self, struct Zeckendorf rhs) {
    int gn;
    for (gn = 0; gn < (rhs.dLen + 1) * 2; gn++) {
        if (((rhs.dVal >> gn) & 1) == 1) {
            b(self, gn);
        }
    }
}

void subAssign(struct Zeckendorf *self, struct Zeckendorf rhs) {
    int gn;
    for (gn = 0; gn < (rhs.dLen + 1) * 2; gn++) {
        if (((rhs.dVal >> gn) & 1) == 1) {
            c(self, gn);
        }
    }
    while ((((self->dVal >> self->dLen * 2) & 3) == 0) || (self->dLen == 0)) {
        self->dLen--;
    }
}

void mulAssign(struct Zeckendorf *self, struct Zeckendorf rhs) {
    struct Zeckendorf na = rhs;
    struct Zeckendorf nb = rhs;
    struct Zeckendorf nr = makeZeckendorf("0");
    struct Zeckendorf nt;
    int i;

    for (i = 0; i < (self->dLen + 1) * 2; i++) {
        if (((self->dVal >> i) & 1) > 0) addAssign(&nr, nb);
        nt = nb;
        addAssign(&nb, na);
        na = nt;
    }

    *self = nr;
}

void printZeckendorf(struct Zeckendorf z) {
    static const char *const dig[3] = { "00", "01", "10" };
    static const char *const dig1[3] = { "", "1", "10" };

    if (z.dVal == 0) {
        printf("0");
        return;
    } else {
        int idx = (z.dVal >> (z.dLen * 2)) & 3;
        int i;

        printf(dig1[idx]);
        for (i = z.dLen - 1; i >= 0; i--) {
            idx = (z.dVal >> (i * 2)) & 3;
            printf(dig[idx]);
        }
    }
}

int main() {
    struct Zeckendorf g;

    printf("Addition:\n");
    g = makeZeckendorf("10");
    addAssign(&g, makeZeckendorf("10"));
    printZeckendorf(g);
    printf("\n");
    addAssign(&g, makeZeckendorf("10"));
    printZeckendorf(g);
    printf("\n");
    addAssign(&g, makeZeckendorf("1001"));
    printZeckendorf(g);
    printf("\n");
    addAssign(&g, makeZeckendorf("1000"));
    printZeckendorf(g);
    printf("\n");
    addAssign(&g, makeZeckendorf("10101"));
    printZeckendorf(g);
    printf("\n\n");

    printf("Subtraction:\n");
    g = makeZeckendorf("1000");
    subAssign(&g, makeZeckendorf("101"));
    printZeckendorf(g);
    printf("\n");
    g = makeZeckendorf("10101010");
    subAssign(&g, makeZeckendorf("1010101"));
    printZeckendorf(g);
    printf("\n\n");

    printf("Multiplication:\n");
    g = makeZeckendorf("1001");
    mulAssign(&g, makeZeckendorf("101"));
    printZeckendorf(g);
    printf("\n");
    g = makeZeckendorf("101010");
    addAssign(&g, makeZeckendorf("101"));
    printZeckendorf(g);
    printf("\n");

    return 0;
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

C#

Translation of: Java
using System;
using System.Text;

namespace ZeckendorfArithmetic {
    class Zeckendorf : IComparable<Zeckendorf> {
        private static readonly string[] dig = { "00", "01", "10" };
        private static readonly string[] dig1 = { "", "1", "10" };

        private int dVal = 0;
        private int dLen = 0;

        public Zeckendorf() : this("0") {
            // empty
        }

        public Zeckendorf(string x) {
            int q = 1;
            int i = x.Length - 1;
            dLen = i / 2;
            while (i >= 0) {
                dVal += (x[i] - '0') * q;
                q *= 2;
                i--;
            }
        }

        private void A(int n) {
            int i = n;
            while (true) {
                if (dLen < i) dLen = i;
                int 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:
                        int temp = 3 << (i * 2);
                        temp ^= -1;
                        dVal = dVal & temp;
                        B((i + 1) * 2);
                        break;
                }
                i++;
            }
        }

        private void B(int pos) {
            if (pos == 0) {
                Inc();
                return;
            }
            if (((dVal >> pos) & 1) == 0) {
                dVal += 1 << pos;
                A(pos / 2);
                if (pos > 1) A(pos / 2 - 1);
            }
            else {
                int temp = 1 << pos;
                temp ^= -1;
                dVal = dVal & temp;
                B(pos + 1);
                B(pos - (pos > 1 ? 2 : 1));
            }
        }

        private void C(int pos) {
            if (((dVal >> pos) & 1) == 1) {
                int temp = 1 << pos;
                temp ^= -1;
                dVal = dVal & temp;
                return;
            }
            C(pos + 1);
            if (pos > 0) {
                B(pos - 1);
            }
            else {
                Inc();
            }
        }

        public Zeckendorf Inc() {
            dVal++;
            A(0);
            return this;
        }

        public Zeckendorf Copy() {
            Zeckendorf z = new Zeckendorf {
                dVal = dVal,
                dLen = dLen
            };
            return z;
        }

        public void PlusAssign(Zeckendorf other) {
            for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
                if (((other.dVal >> gn) & 1) == 1) {
                    B(gn);
                }
            }
        }

        public void MinusAssign(Zeckendorf other) {
            for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
                if (((other.dVal >> gn) & 1) == 1) {
                    C(gn);
                }
            }
            while ((((dVal >> dLen * 2) & 3) == 0) || (dLen == 0)) {
                dLen--;
            }
        }

        public void TimesAssign(Zeckendorf other) {
            Zeckendorf na = other.Copy();
            Zeckendorf nb = other.Copy();
            Zeckendorf nt;
            Zeckendorf nr = new Zeckendorf();
            for (int i = 0; i < (dLen + 1) * 2; i++) {
                if (((dVal >> i) & 1) > 0) {
                    nr.PlusAssign(nb);
                }
                nt = nb.Copy();
                nb.PlusAssign(na);
                na = nt.Copy();
            }
            dVal = nr.dVal;
            dLen = nr.dLen;
        }

        public int CompareTo(Zeckendorf other) {
            return dVal.CompareTo(other.dVal);
        }

        public override string ToString() {
            if (dVal == 0) {
                return "0";
            }

            int idx = (dVal >> (dLen * 2)) & 3;
            StringBuilder sb = new StringBuilder(dig1[idx]);
            for (int i = dLen - 1; i >= 0; i--) {
                idx = (dVal >> (i * 2)) & 3;
                sb.Append(dig[idx]);
            }
            return sb.ToString();
        }
    }

    class Program {
        static void Main(string[] args) {
            Console.WriteLine("Addition:");
            Zeckendorf g = new Zeckendorf("10");
            g.PlusAssign(new Zeckendorf("10"));
            Console.WriteLine(g);
            g.PlusAssign(new Zeckendorf("10"));
            Console.WriteLine(g);
            g.PlusAssign(new Zeckendorf("1001"));
            Console.WriteLine(g);
            g.PlusAssign(new Zeckendorf("1000"));
            Console.WriteLine(g);
            g.PlusAssign(new Zeckendorf("10101"));
            Console.WriteLine(g);
            Console.WriteLine();

            Console.WriteLine("Subtraction:");
            g = new Zeckendorf("1000");
            g.MinusAssign(new Zeckendorf("101"));
            Console.WriteLine(g);
            g = new Zeckendorf("10101010");
            g.MinusAssign(new Zeckendorf("1010101"));
            Console.WriteLine(g);
            Console.WriteLine();

            Console.WriteLine("Multiplication:");
            g = new Zeckendorf("1001");
            g.TimesAssign(new Zeckendorf("101"));
            Console.WriteLine(g);
            g = new Zeckendorf("101010");
            g.PlusAssign(new Zeckendorf("101"));
            Console.WriteLine(g);
        }
    }
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

C++

Works with: C++11
// For a class N which implements Zeckendorf numbers:
// I define an increment operation ++()
// I define a comparison operation <=(other N)
// I define an addition operation +=(other N)
// I define a subtraction operation -=(other N)
// Nigel Galloway October 28th., 2012
#include <iostream>
enum class zd {N00,N01,N10,N11};
class N {
private:
  int dVal = 0, dLen;
  void _a(int i) {
    for (;; i++) {
      if (dLen < i) dLen = i;
      switch ((zd)((dVal >> (i*2)) & 3)) {
        case zd::N00: case zd::N01: return;
        case zd::N10: if (((dVal >> ((i+1)*2)) & 1) != 1) return;
                      dVal += (1 << (i*2+1)); return;
        case zd::N11: dVal &= ~(3 << (i*2)); _b((i+1)*2);
  }}}
  void _b(int pos) {
    if (pos == 0) {++*this; 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;
    return;
  }
public:
  N(char const* x = "0") {
    int i = 0, q = 1;
    for (; x[i] > 0; i++);
    for (dLen = --i/2; i >= 0; i--) {dVal+=(x[i]-48)*q; q*=2;
  }}
  const N& operator++() {dVal += 1; _a(0); return *this;}
  const N& operator+=(const N& other) {
    for (int GN = 0; GN < (other.dLen + 1) * 2; GN++) if ((other.dVal >> GN) & 1 == 1) _b(GN);
    return *this;
  }
  const N& operator-=(const N& other) {
    for (int GN = 0; GN < (other.dLen + 1) * 2; GN++) if ((other.dVal >> GN) & 1 == 1) _c(GN);
    for (;((dVal >> dLen*2) & 3) == 0 or dLen == 0; dLen--);
    return *this;
  }
  const N& operator*=(const N& other) {
    N Na = other, Nb = other, Nt, Nr;
    for (int i = 0; i <= (dLen + 1) * 2; i++) {
      if (((dVal >> i) & 1) > 0) Nr += Nb;
      Nt = Nb; Nb += Na; Na = Nt;
    }
    return *this = Nr;
  }
  const bool operator<=(const N& other) const {return dVal <= other.dVal;}
  friend std::ostream& operator<<(std::ostream&, const N&);
};
N operator "" N(char const* x) {return N(x);}
std::ostream &operator<<(std::ostream &os, const N &G) {
  const static std::string dig[] {"00","01","10"}, dig1[] {"","1","10"};
  if (G.dVal == 0) return os << "0";
  os << dig1[(G.dVal >> (G.dLen*2)) & 3];
  for (int i = G.dLen-1; i >= 0; i--) os << dig[(G.dVal >> (i*2)) & 3];
  return os;
}

Testing

The following tests addtition:

int main(void) {
  N G;
  G = 10N;
  G += 10N;
  std::cout << G << std::endl;
  G += 10N;
  std::cout << G << std::endl;
  G += 1001N;
  std::cout << G << std::endl;
  G += 1000N;
  std::cout << G << std::endl;
  G += 10101N;
  std::cout << G << std::endl;
  return 0;
}
Output:
101
1001
10101
100101
1010000

The following tests subtraction:

int main(void) {
  N G;
  G = 1000N;
  G -= 101N;
  std::cout << G << std::endl;
  G = 10101010N;
  G -= 1010101N;
  std::cout << G << std::endl;
  return 0;
}
Output:
1
1000000

The following tests multiplication:

int main(void) {
  N G = 1001N;
  G *= 101N;
  std::cout << G << std::endl;

  G = 101010N;
  G += 101N;
  std::cout << G << std::endl;
  return 0;
}
Output:
1000100
1000100

D

Translation of: Kotlin
import std.stdio;

int inv(int a) {
    return a ^ -1;
}

class Zeckendorf {
    private int dVal;
    private int dLen;

    private void a(int n) {
        auto i = n;
        while (true) {
            if (dLen < i) dLen = i;
            auto 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 = dVal & (3 << (i * 2)).inv();
                    b((i + 1) * 2);
                    break;
                default:
                    assert(false);
            }
            i++;
        }
    }

    private void b(int pos) {
        if (pos == 0) {
            this++;
            return;
        }
        if (((dVal >> pos) & 1) == 0) {
            dVal += 1 << pos;
            a(pos / 2);
            if (pos > 1) a(pos / 2 - 1);
        } else {
            dVal = dVal & (1 << pos).inv();
            b(pos + 1);
            b(pos - (pos > 1 ? 2 : 1));
        }
    }

    private void c(int pos) {
        if (((dVal >> pos) & 1) == 1) {
            dVal = dVal & (1 << pos).inv();
            return;
        }
        c(pos + 1);
        if (pos > 0) {
            b(pos - 1);
        } else {
            ++this;
        }
    }

    this(string x = "0") {
        int q = 1;
        int i = x.length - 1;
        dLen = i / 2;
        while (i >= 0) {
            dVal += (x[i] - '0') * q;
            q *= 2;
            i--;
        }
    }

    auto opUnary(string op : "++")() {
        dVal += 1;
        a(0);
        return this;
    }

    void opOpAssign(string op : "+")(Zeckendorf rhs) {
        foreach (gn; 0..(rhs.dLen + 1) * 2) {
            if (((rhs.dVal >> gn) & 1) == 1) {
                b(gn);
            }
        }
    }

    void opOpAssign(string op : "-")(Zeckendorf rhs) {
        foreach (gn; 0..(rhs.dLen + 1) * 2) {
            if (((rhs.dVal >> gn) & 1) == 1) {
                c(gn);
            }
        }
        while ((((dVal >> dLen * 2) & 3) == 0) || (dLen == 0)) {
            dLen--;
        }
    }

    void opOpAssign(string op : "*")(Zeckendorf rhs) {
        auto na = rhs.dup;
        auto nb = rhs.dup;
        Zeckendorf nt;
        auto nr = "0".Z;
        foreach (i; 0..(dLen + 1) * 2) {
            if (((dVal >> i) & 1) > 0) nr += nb;
            nt = nb.dup;
            nb += na;
            na = nt.dup;
        }
        dVal = nr.dVal;
        dLen = nr.dLen;
    }

    void toString(scope void delegate(const(char)[]) sink) const {
        if (dVal == 0) {
            sink("0");
            return;
        }
        sink(dig1[(dVal >> (dLen * 2)) & 3]);
        foreach_reverse (i; 0..dLen) {
            sink(dig[(dVal >> (i * 2)) & 3]);
        }
    }

    Zeckendorf dup() {
        auto z = "0".Z;
        z.dVal = dVal;
        z.dLen = dLen;
        return z;
    }

    enum dig = ["00", "01", "10"];
    enum dig1 = ["", "1", "10"];
}

auto Z(string val) {
    return new Zeckendorf(val);
}

void main() {
    writeln("Addition:");
    auto g = "10".Z;
    g += "10".Z;
    writeln(g);
    g += "10".Z;
    writeln(g);
    g += "1001".Z;
    writeln(g);
    g += "1000".Z;
    writeln(g);
    g += "10101".Z;
    writeln(g);
    writeln();

    writeln("Subtraction:");
    g = "1000".Z;
    g -= "101".Z;
    writeln(g);
    g = "10101010".Z;
    g -= "1010101".Z;
    writeln(g);
    writeln();

    writeln("Multiplication:");
    g = "1001".Z;
    g *= "101".Z;
    writeln(g);
    g = "101010".Z;
    g += "101".Z;
    writeln(g);
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Dart

Translation of: Kotlin
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);
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100


Elena

Translation of: C++

ELENA 6.x :

import extensions;

const dig = new string[]{"00","01","10"};
const dig1 = new string[]{"","1","10"};

sealed struct ZeckendorfNumber
{
    int dVal;
    int dLen;
    
    clone()
        = ZeckendorfNumber.newInternal(dVal,dLen);
    
    cast n(string s)
    {
        int i := s.Length - 1;
        int q := 1;
        
        dLen := i / 2;
        dVal := 0;
        
        while (i >= 0)
        {
            dVal += ((intConvertor.convert(s[i]) - 48) * q);
            q *= 2;
            
            i -= 1
        }
    }
    
    internal readContent(ref int val, ref int len)
    {
        val := dVal;
        len := dLen;
    }
    
    private a(int n)
    {
        int i := n;

        while (true)
        {
            if (dLen < i)
            {
                dLen := i
            };
            
            int v := (dVal $shr (i * 2)) & 3;
            v =>    
                0 { ^ self }
                1 { ^ self }
                2 {
                    ifnot ((dVal $shr ((i + 1) * 2)).allMask(1))
                    {
                        ^ self
                    };
                    
                    dVal += (1 $shl (i*2 + 1));
                    
                    ^ self
                }
                3 {
                    int tmp := 3 $shl (i * 2);
                    tmp := tmp.bxor(-1);
                    dVal := dVal & tmp;
                    
                    self.b((i+1)*2)
                };
            
            i += 1
        }
    }
    
    inc()
    {
        dVal += 1;
        self.a(0)
    }
    
    private b(int pos)
    {
        if (pos == 0) { ^ self.inc() };
        
        ifnot((dVal $shr pos).allMask(1))
        {
            dVal += (1 $shl pos);
            self.a(pos / 2);
            if (pos > 1) { self.a((pos / 2) - 1) }
        }
        else
        {
            dVal := dVal & (1 $shl pos).BInverted;
            self.b(pos + 1);
            int arg := pos - ((pos > 1) ? 2 : 1);
            self.b(/*pos - ((pos > 1) ? 2 : 1)*/arg)
        }
    }

    private c(int pos)
    {
        if ((dVal $shr pos).allMask(1))
        {
            int tmp := 1 $shl pos;
            tmp := tmp.bxor(-1);
            
            dVal := dVal & tmp;
            
            ^ self
        };
                                        
        self.c(pos + 1);
        
        if (pos > 0)
        {
            self.b(pos - 1)
        }
        else
        {
            self.inc()
        }            
    }
            
    internal constructor sum(ZeckendorfNumber n, ZeckendorfNumber m)
    {
        int mVal := 0;
        int mLen := 0;
        
        n.readContent(ref int v, ref int l);        
        m.readContent(ref mVal, ref mLen);
        
        dVal := v;
        dLen := l;

        for(int GN := 0; GN < (mLen + 1) * 2; GN += 1)
        {
            if ((mVal $shr GN).allMask(1))
            {
                self.b(GN)
            }
        }
    }
    
    internal constructor difference(ZeckendorfNumber n, ZeckendorfNumber m)
    {
        int mVal := 0;
        int mLen := 0;
        
        n.readContent(ref int v, ref int l);        
        m.readContent(ref mVal, ref mLen);
        
        dVal := v;
        dLen := l;
        
        for(int GN := 0; GN < (mLen + 1) * 2; GN += 1) 
        {
            if ((mVal $shr GN).allMask(1))
            {
                self.c(GN)
            }
        };
        
        while (((dVal $shr (dLen*2)) & 3) == 0 || dLen == 0)
        {
            dLen -= 1
        }
    }
    
    internal constructor product(ZeckendorfNumber n, ZeckendorfNumber m)
    {
        n.readContent(ref int v, ref int l);              
        
        dVal := v;
        dLen := l;
        
        ZeckendorfNumber Na := m;
        ZeckendorfNumber Nb := m;
        ZeckendorfNumber Nr := 0n;
        ZeckendorfNumber Nt := 0n;
        
        for(int i := 0; i < (dLen + 1) * 2; i += 1) 
        {
            if (((dVal $shr i) & 1) > 0)
            {
                Nr += Nb
            };
            Nt := Nb;
            Nb += Na;
            Na := Nt
        };
        
        Nr.readContent(ref v, ref l);
        
        dVal := v;
        dLen := l;
    }
    
    internal constructor newInternal(int v, int l)
    {
        dVal := v;
        dLen := l
    }
    
    string toPrintable()
    {
        if (dVal == 0)
            { ^ "0" };
            
        string s := dig1[(dVal $shr (dLen * 2)) & 3];
        int i := dLen - 1;
        while (i >= 0)
        {
            s := s + dig[(dVal $shr (i * 2)) & 3];
            
            i-=1
        };
        
        ^ s
    }
    
    add(ZeckendorfNumber n)
        = ZeckendorfNumber.sum(self, n);
        
    subtract(ZeckendorfNumber n)
        = ZeckendorfNumber.difference(self, n);
        
    multiply(ZeckendorfNumber n)
        = ZeckendorfNumber.product(self, n);
}

public program()
{
    console.printLine("Addition:");
    var n := 10n;
    
    n += 10n;
    console.printLine(n);
    n += 10n;
    console.printLine(n);
    n += 1001n;
    console.printLine(n);
    n += 1000n;
    console.printLine(n);
    n += 10101n;
    console.printLine(n);
    
    console.printLine("Subtraction:");
    n := 1000n;
    n -= 101n;
    console.printLine(n);
    n := 10101010n;
    n -= 1010101n;
    console.printLine(n);
    
    console.printLine("Multiplication:");
    n := 1001n;
    n *= 101n;
    console.printLine(n);
    n := 101010n;
    n += 101n;
    console.printLine(n)
}
Output:
Addition:
101
1001
10101
100101
1010000
Subtraction:
1
1000000
Multiplication:
1000100
1000100

FreeBASIC

Translation of: Python
Type Zeckendorf
    As Integer dLen
    As Ulongint dVal
    
    Declare Constructor()
    Declare Constructor(x As String)
    Declare Sub a(n As Integer)
    Declare Sub b(Pos As Integer)
    Declare Sub c(Pos As Integer)
    Declare Sub inc()
    Declare Function suma(rhs As Zeckendorf) As Zeckendorf
    Declare Function resta(rhs As Zeckendorf) As Zeckendorf
    Declare Function producto(rhs As Zeckendorf) As Zeckendorf
    Declare Function toString() As String
End Type

Constructor Zeckendorf()
    This.dLen = 0
    This.dVal = 0
End Constructor

Constructor Zeckendorf(x As String)
    Dim As Ulongint q = 1
    Dim As Integer i = Len(x) - 1
    This.dLen = Int(i / 2)
    This.dVal = 0
    While i >= 0
        This.dVal += (Asc(Mid(x, i+1, 1)) - Asc("0")) * q
        q *= 2
        i -= 1
    Wend
End Constructor

Sub Zeckendorf.a(n As Integer)
    Dim As Integer i = n
    Do
        If This.dLen < i Then This.dLen = i
        Dim As Integer j = (This.dVal Shr (i * 2)) And 3
        If j = 0 Or j = 1 Then Exit Sub
        If j = 2 Then
            If ((This.dVal Shr ((i + 1) * 2)) And 1) <> 1 Then Exit Sub
            This.dVal += 1ULL Shl (i * 2 + 1)
            Exit Sub
        End If
        If j = 3 Then
            Dim As Ulongint temp = 3ULL Shl (i * 2)
            temp Xor= &HFFFFFFFFFFFFFFFFULL
            This.dVal And= temp
            This.b((i + 1) * 2)
        End If
        i += 1
    Loop
End Sub

Sub Zeckendorf.b(posic As Integer)
    If posic = 0 Then
        This.inc()
        Exit Sub
    End If
    If ((This.dVal Shr posic) And 1) = 0 Then
        This.dVal += 1ULL Shl posic
        This.a(Int(posic / 2))
        If posic > 1 Then This.a(Int(posic / 2) - 1)
    Else
        Dim As Ulongint temp = 1ULL Shl posic
        temp Xor= &HFFFFFFFFFFFFFFFFULL
        This.dVal And= temp
        This.b(posic + 1)
        This.b(posic - Iif(posic > 1, 2, 1))
    End If
End Sub

Sub Zeckendorf.c(posic As Integer)
    If ((This.dVal Shr posic) And 1) = 1 Then
        Dim As Ulongint temp = 1ULL Shl posic
        temp Xor= &HFFFFFFFFFFFFFFFFULL
        This.dVal And= temp
        Exit Sub
    End If
    This.c(posic + 1)
    If posic > 0 Then
        This.b(posic - 1)
    Else
        This.inc()
    End If
End Sub

Sub Zeckendorf.inc()
    This.dVal += 1
    This.a(0)
End Sub

Function Zeckendorf.suma(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf copy = This
    Dim As Ulongint rhs_dVal = rhs.dVal
    Dim As Integer limit = (rhs.dLen + 1) * 2
    For gn As Integer = 0 To limit - 1
        If ((rhs_dVal Shr gn) And 1) = 1 Then copy.b(gn)
    Next
    Return copy
End Function

Function Zeckendorf.resta(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf copy = This
    Dim As Ulongint rhs_dVal = rhs.dVal
    Dim As Integer limit = (rhs.dLen + 1) * 2
    For gn As Integer = 0 To limit - 1
        If ((rhs_dVal Shr gn) And 1) = 1 Then copy.c(gn)
    Next
    While (((copy.dVal Shr ((copy.dLen * 2) And 31)) And 3) = 0) Or (copy.dLen = 0)
        copy.dLen -= 1
    Wend
    Return copy
End Function

Function Zeckendorf.producto(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf na = rhs, nb = rhs, nr
    Dim As Ulongint dVal = This.dVal
    For i As Integer = 0 To (This.dLen + 1) * 2 - 1
        If ((dVal Shr i) And 1) > 0 Then nr = nr.suma(nb)
        Dim As Zeckendorf nt = nb
        nb = nb.suma(na)
        na = nt
    Next
    Return nr
End Function

Function Zeckendorf.toString() As String
    Dim As String dig(2) = {"00", "01", "10"}
    Dim As String dig1(2) = {"", "1", "10"}
    
    If This.dVal = 0 Then Return "0"
    Dim As Integer idx = (This.dVal Shr ((This.dLen * 2) And 31)) And 3
    Dim As String sb = dig1(idx)
    For i As Integer = This.dLen - 1 To 0 Step -1
        idx = (This.dVal Shr (i * 2)) And 3
        sb &= dig(idx)
    Next
    Return sb
End Function

' Main
Print "Addition:"
Dim As Zeckendorf g = Zeckendorf("10")
g = g.suma(Zeckendorf("10"))
Print g.toString()
g = g.suma(Zeckendorf("10"))
Print g.toString()
g = g.suma(Zeckendorf("1001"))
Print g.toString()
g = g.suma(Zeckendorf("1000"))
Print g.toString()
g = g.suma(Zeckendorf("10101"))
Print g.toString()
Print

Print "Subtraction:"
g = Zeckendorf("1000")
g = g.resta(Zeckendorf("101"))
Print g.toString()
g = Zeckendorf("10101010")
g = g.resta(Zeckendorf("1010101"))
Print g.toString()
Print

Print "Multiplication:"
g = Zeckendorf("1001")
g = g.producto(Zeckendorf("101"))
Print g.toString()
g = Zeckendorf("101010")
g = g.suma(Zeckendorf("101"))
Print g.toString()

Sleep
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Go

Translation of: Kotlin
package main

import (
    "fmt"
    "strings"
)

var (
    dig  = [3]string{"00", "01", "10"}
    dig1 = [3]string{"", "1", "10"}
)

type Zeckendorf struct{ dVal, dLen int }

func NewZeck(x string) *Zeckendorf {
    z := new(Zeckendorf)
    if x == "" {
        x = "0"
    }
    q := 1
    i := len(x) - 1
    z.dLen = i / 2
    for ; i >= 0; i-- {
        z.dVal += int(x[i]-'0') * q
        q *= 2
    }
    return z
}

func (z *Zeckendorf) a(i int) {
    for ; ; i++ {
        if z.dLen < i {
            z.dLen = i
        }
        j := (z.dVal >> uint(i*2)) & 3
        switch j {
        case 0, 1:
            return
        case 2:
            if ((z.dVal >> (uint(i+1) * 2)) & 1) != 1 {
                return
            }
            z.dVal += 1 << uint(i*2+1)
            return
        case 3:
            z.dVal &= ^(3 << uint(i*2))
            z.b((i + 1) * 2)
        }
    }
}

func (z *Zeckendorf) b(pos int) {
    if pos == 0 {
        z.Inc()
        return
    }
    if ((z.dVal >> uint(pos)) & 1) == 0 {
        z.dVal += 1 << uint(pos)
        z.a(pos / 2)
        if pos > 1 {
            z.a(pos/2 - 1)
        }
    } else {
        z.dVal &= ^(1 << uint(pos))
        z.b(pos + 1)
        temp := 1
        if pos > 1 {
            temp = 2
        }
        z.b(pos - temp)
    }
}

func (z *Zeckendorf) c(pos int) {
    if ((z.dVal >> uint(pos)) & 1) == 1 {
        z.dVal &= ^(1 << uint(pos))
        return
    }
    z.c(pos + 1)
    if pos > 0 {
        z.b(pos - 1)
    } else {
        z.Inc()
    }
}

func (z *Zeckendorf) Inc() {
    z.dVal++
    z.a(0)
}

func (z1 *Zeckendorf) PlusAssign(z2 *Zeckendorf) {
    for gn := 0; gn < (z2.dLen+1)*2; gn++ {
        if ((z2.dVal >> uint(gn)) & 1) == 1 {
            z1.b(gn)
        }
    }
}

func (z1 *Zeckendorf) MinusAssign(z2 *Zeckendorf) {
    for gn := 0; gn < (z2.dLen+1)*2; gn++ {
        if ((z2.dVal >> uint(gn)) & 1) == 1 {
            z1.c(gn)
        }
    }

    for z1.dLen > 0 && ((z1.dVal>>uint(z1.dLen*2))&3) == 0 {
        z1.dLen--
    }
}

func (z1 *Zeckendorf) TimesAssign(z2 *Zeckendorf) {
    na := z2.Copy()
    nb := z2.Copy()
    nr := new(Zeckendorf)
    for i := 0; i <= (z1.dLen+1)*2; i++ {
        if ((z1.dVal >> uint(i)) & 1) > 0 {
            nr.PlusAssign(nb)
        }
        nt := nb.Copy()
        nb.PlusAssign(na)
        na = nt.Copy()
    }
    z1.dVal = nr.dVal
    z1.dLen = nr.dLen
}

func (z *Zeckendorf) Copy() *Zeckendorf {
    return &Zeckendorf{z.dVal, z.dLen}
}

func (z1 *Zeckendorf) Compare(z2 *Zeckendorf) int {
    switch {
    case z1.dVal < z2.dVal:
        return -1
    case z1.dVal > z2.dVal:
        return 1
    default:
        return 0
    }
}

func (z *Zeckendorf) String() string {
    if z.dVal == 0 {
        return "0"
    }
    var sb strings.Builder
    sb.WriteString(dig1[(z.dVal>>uint(z.dLen*2))&3])
    for i := z.dLen - 1; i >= 0; i-- {
        sb.WriteString(dig[(z.dVal>>uint(i*2))&3])
    }
    return sb.String()
}

func main() {
    fmt.Println("Addition:")
    g := NewZeck("10")
    g.PlusAssign(NewZeck("10"))
    fmt.Println(g)
    g.PlusAssign(NewZeck("10"))
    fmt.Println(g)
    g.PlusAssign(NewZeck("1001"))
    fmt.Println(g)
    g.PlusAssign(NewZeck("1000"))
    fmt.Println(g)
    g.PlusAssign(NewZeck("10101"))
    fmt.Println(g)

    fmt.Println("\nSubtraction:")
    g = NewZeck("1000")
    g.MinusAssign(NewZeck("101"))
    fmt.Println(g)
    g = NewZeck("10101010")
    g.MinusAssign(NewZeck("1010101"))
    fmt.Println(g)

    fmt.Println("\nMultiplication:")
    g = NewZeck("1001")
    g.TimesAssign(NewZeck("101"))
    fmt.Println(g)
    g = NewZeck("101010")
    g.PlusAssign(NewZeck("101"))
    fmt.Println(g)
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Haskell

We make Zeckendorf numbers first class citizens implementing instances of Eq, Ord, Num, Enum, Real and Integral 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).

{-# 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
λ> 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

J

Loosely based on the perl implementation:

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 }}

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:

   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

Java

Translation of: Kotlin
Works with: Java version 9
import java.util.List;

public class Zeckendorf implements Comparable<Zeckendorf> {
    private static List<String> dig = List.of("00", "01", "10");
    private static List<String> dig1 = List.of("", "1", "10");

    private String x;
    private int dVal = 0;
    private int dLen = 0;

    public Zeckendorf() {
        this("0");
    }

    public Zeckendorf(String x) {
        this.x = x;

        int q = 1;
        int i = x.length() - 1;
        dLen = i / 2;
        while (i >= 0) {
            dVal += (x.charAt(i) - '0') * q;
            q *= 2;
            i--;
        }
    }

    private void a(int n) {
        int i = n;
        while (true) {
            if (dLen < i) dLen = i;
            int 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:
                    int temp = 3 << (i * 2);
                    temp ^= -1;
                    dVal = dVal & temp;
                    b((i + 1) * 2);
                    break;
            }
            i++;
        }
    }

    private void b(int pos) {
        if (pos == 0) {
            Zeckendorf thiz = this;
            thiz.inc();
            return;
        }
        if (((dVal >> pos) & 1) == 0) {
            dVal += 1 << pos;
            a(pos / 2);
            if (pos > 1) a(pos / 2 - 1);
        } else {
            int temp = 1 << pos;
            temp ^= -1;
            dVal = dVal & temp;
            b(pos + 1);
            b(pos - (pos > 1 ? 2 : 1));
        }
    }

    private void c(int pos) {
        if (((dVal >> pos) & 1) == 1) {
            int temp = 1 << pos;
            temp ^= -1;
            dVal = dVal & temp;
            return;
        }
        c(pos + 1);
        if (pos > 0) {
            b(pos - 1);
        } else {
            Zeckendorf thiz = this;
            thiz.inc();
        }
    }

    public Zeckendorf inc() {
        dVal++;
        a(0);
        return this;
    }

    public void plusAssign(Zeckendorf other) {
        for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
            if (((other.dVal >> gn) & 1) == 1) {
                b(gn);
            }
        }
    }

    public void minusAssign(Zeckendorf other) {
        for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
            if (((other.dVal >> gn) & 1) == 1) {
                c(gn);
            }
        }
        while ((((dVal >> dLen * 2) & 3) == 0) || (dLen == 0)) {
            dLen--;
        }
    }

    public void timesAssign(Zeckendorf other) {
        Zeckendorf na = other.copy();
        Zeckendorf nb = other.copy();
        Zeckendorf nt;
        Zeckendorf nr = new Zeckendorf();
        for (int i = 0; i < (dLen + 1) * 2; i++) {
            if (((dVal >> i) & 1) > 0) {
                nr.plusAssign(nb);
            }
            nt = nb.copy();
            nb.plusAssign(na);
            na = nt.copy();
        }
        dVal = nr.dVal;
        dLen = nr.dLen;
    }

    private Zeckendorf copy() {
        Zeckendorf z = new Zeckendorf();
        z.dVal = dVal;
        z.dLen = dLen;
        return z;
    }

    @Override
    public int compareTo(Zeckendorf other) {
        return ((Integer) dVal).compareTo(other.dVal);
    }

    @Override
    public String toString() {
        if (dVal == 0) {
            return "0";
        }

        int idx = (dVal >> (dLen * 2)) & 3;
        StringBuilder stringBuilder = new StringBuilder(dig1.get(idx));
        for (int i = dLen - 1; i >= 0; i--) {
            idx = (dVal >> (i * 2)) & 3;
            stringBuilder.append(dig.get(idx));
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println("Addition:");
        Zeckendorf g = new Zeckendorf("10");
        g.plusAssign(new Zeckendorf("10"));
        System.out.println(g);
        g.plusAssign(new Zeckendorf("10"));
        System.out.println(g);
        g.plusAssign(new Zeckendorf("1001"));
        System.out.println(g);
        g.plusAssign(new Zeckendorf("1000"));
        System.out.println(g);
        g.plusAssign(new Zeckendorf("10101"));
        System.out.println(g);

        System.out.println("\nSubtraction:");
        g = new Zeckendorf("1000");
        g.minusAssign(new Zeckendorf("101"));
        System.out.println(g);
        g = new Zeckendorf("10101010");
        g.minusAssign(new Zeckendorf("1010101"));
        System.out.println(g);

        System.out.println("\nMultiplication:");
        g = new Zeckendorf("1001");
        g.timesAssign(new Zeckendorf("101"));
        System.out.println(g);
        g = new Zeckendorf("101010");
        g.plusAssign(new Zeckendorf("101"));
        System.out.println(g);
    }
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Julia

Influenced by the format of the Tcl and Raku versions, but added other functionality.

import Base.*, Base.+, Base.-, Base./, Base.show, Base.!=, Base.==, Base.<=, Base.<, Base.>, Base.>=, Base.divrem

const z0 = "0"
const z1 = "1"
const flipordered = (z1 < z0)

mutable struct Z s::String end
Z() = Z(z0)
Z(z::Z) = Z(z.s)

pairlen(x::Z, y::Z) = max(length(x.s), length(y.s))
tolen(x::Z, n::Int) = (s = x.s; while length(s) < n s = z0 * s end; s)

<(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) > tolen(y, l) : tolen(x, l) < tolen(y, l))
>(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) < tolen(y, l) : tolen(x, l) > tolen(y, l))
==(x::Z, y::Z) = (l = pairlen(x, y); tolen(x, l) == tolen(y, l))
<=(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) >= tolen(y, l) : tolen(x, l) <= tolen(y, l))
>=(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) <= tolen(y, l) : tolen(x, l) >= tolen(y, l))
!=(x::Z, y::Z) = (l = pairlen(x, y); tolen(x, l) != tolen(y, l))

function tocanonical(z::Z)
    while occursin(z0 * z1 * z1, z.s)
        z.s = replace(z.s, z0 * z1 * z1 => z1 * z0 * z0)
    end
    len = length(z.s)
    if len > 1 && z.s[1:2] == z1 * z1
        z.s = z1 * z0 * z0 * ((len > 2) ? z.s[3:end] : "")
    end
    while (len = length(z.s)) > 1 && string(z.s[1]) == z0
        if len == 2
            if z.s == z0 * z0
                z.s = z0
            elseif z.s == z0 * z1
                z.s = z1
            end
        else
            z.s = z.s[2:end]
        end
    end
    z
end

function inc(z)
    if z.s[end] == z0[1]
        z.s = z.s[1:end-1] * z1[1]
    elseif z.s[end] == z1[1]
        if length(z.s) > 1
            if z.s[end-1:end] == z0 * z1
                z.s = z.s[1:end-2] * z1 * z0
            end
        else
            z.s = z1 * z0
        end
    end
    tocanonical(z)
end

function dec(z)
    if z.s[end] == z1[1]
        z.s = z.s[1:end-1] * z0
    else
        if (m = match(Regex(z1 * z0 * '+' * '$'), z.s)) != nothing
            len = length(m.match)
            if iseven(len)
                z.s = z.s[1:end-len] * (z0 * z1) ^ div(len, 2)
            else
                z.s = z.s[1:end-len] * (z0 * z1) ^ div(len, 2) * z0
            end
        end
    end
    tocanonical(z)    
    z
end

function +(x::Z, y::Z)
    a = Z(x.s)
    b = Z(y.s)
    while b.s != z0
        inc(a)
        dec(b)
    end
    a
end

function -(x::Z, y::Z)
    a = Z(x.s)
    b = Z(y.s)
    while b.s != z0
        dec(a)
        dec(b)
    end
    a
end

function *(x::Z, y::Z)
    if (x.s == z0) || (y.s == z0)
        return Z(z0)
    elseif x.s == z1
        return Z(y.s)
    elseif y.s == z1
        return Z(x.s)
    end
    a = Z(x.s)
    b = Z(z1)
    while b != y
        c = Z(z0)
        while c != x
            inc(a)
            inc(c)
        end
        inc(b)
    end
    a
end

function divrem(x::Z, y::Z)
    if y.s == z0
        throw("Zeckendorf division by 0")
    elseif (y.s == z1) || (x.s == z0)
        return Z(x.s)
    end
    a = Z(x.s)
    b = Z(y.s)
    c = Z(z0)
    while a > b
        a = a - b
        inc(c)
    end
    tocanonical(c), tocanonical(a)
end

function /(x::Z, y::Z)
    a, _ = divrem(x, y)
    a
end

show(io::IO, z::Z) = show(io, parse(BigInt, tocanonical(z).s))

function zeckendorftest()
    a = Z("10")
    b = Z("1001")
    c = Z("1000")
    d = Z("10101")

    println("Addition:")
    x = a
    println(x += a)
    println(x += a)
    println(x += b)
    println(x += c)
    println(x += d)

    println("\nSubtraction:")
    x = Z("1000")
    println(x - Z("101"))
    x = Z("10101010")
    println(x - Z("1010101"))

    println("\nMultiplication:")
    x = Z("1001")
    y = Z("101")
    println(x * y)
    println(Z("101010") * y)

    println("\nDivision:")
    x = Z("1000101")
    y = Z("101")
    println(x / y)
    println(divrem(x, y))
end

zeckendorftest()
Output:

Addition:
101
1001
10101
100101
1010000 

Subtraction:
1
1000000

Multiplication:
1000100
101000101

Division:
1001
(1001, 1)

Kotlin

Translation of: C++
// version 1.1.51

class Zeckendorf(x: String = "0") : Comparable<Zeckendorf> {

    var dVal = 0
    var dLen = 0

    private fun a(n: Int) {
        var i = n
        while (true) {
            if (dLen < i) dLen = i
            val j = (dVal shr (i * 2)) and 3
            when (j) {
                0, 1 -> return

                2 -> {
                    if (((dVal shr ((i + 1) * 2)) and 1) != 1) return
                    dVal += 1 shl (i * 2 + 1)
                    return
                }

                3 -> {
                    dVal = dVal and (3 shl (i * 2)).inv()
                    b((i + 1) * 2)
                }
            }
            i++
        }
    }

    private fun b(pos: Int) {
        if (pos == 0) {
            var thiz = this
            ++thiz
            return
        }
        if (((dVal shr pos) and 1) == 0) {
            dVal += 1 shl pos
            a(pos / 2)
            if (pos > 1) a(pos / 2 - 1)
        }
        else {
            dVal = dVal and (1 shl pos).inv()
            b(pos + 1)
            b(pos - (if (pos > 1) 2 else 1))
        }
    }

    private fun c(pos: Int) {
        if (((dVal shr pos) and 1) == 1) {
            dVal = dVal and (1 shl pos).inv()
            return
        }
        c(pos + 1)
        if (pos > 0) b(pos - 1) else { var thiz = this; ++thiz }
    }

    init {
        var q = 1
        var i = x.length - 1
        dLen = i / 2
        while (i >= 0) {
            dVal += (x[i] - '0').toInt() * q
            q *= 2
            i--
        }
    }

    operator fun inc(): Zeckendorf {
        dVal += 1
        a(0)
        return this
    }

    operator fun plusAssign(other: Zeckendorf) {
        for (gn in 0 until (other.dLen + 1) * 2) {
            if (((other.dVal shr gn) and 1) == 1) b(gn)
        }
    }

    operator fun minusAssign(other: Zeckendorf) {
        for (gn in 0 until (other.dLen + 1) * 2) {
            if (((other.dVal shr gn) and 1) == 1) c(gn)
        }
        while ((((dVal shr dLen * 2) and 3) == 0) || (dLen == 0)) dLen--
    }

    operator fun timesAssign(other: Zeckendorf) {
        var na = other.copy()
        var nb = other.copy()
        var nt: Zeckendorf
        var nr = "0".Z
        for (i in 0..(dLen + 1) * 2) {
            if (((dVal shr i) and 1) > 0) nr += nb
            nt = nb.copy()
            nb += na
            na = nt.copy()
        }
        dVal = nr.dVal
        dLen = nr.dLen
    }

    override operator fun compareTo(other: Zeckendorf) = dVal.compareTo(other.dVal)

    override fun toString(): String {
        if (dVal == 0) return "0"
        val sb = StringBuilder(dig1[(dVal shr (dLen * 2)) and 3])
        for (i in dLen - 1 downTo 0) {
            sb.append(dig[(dVal shr (i * 2)) and 3])
        }
        return sb.toString()
    }

    fun copy(): Zeckendorf {
        val z = "0".Z
        z.dVal = dVal
        z.dLen = dLen
        return z
    }

    companion object {
        val dig = listOf("00", "01", "10")
        val dig1 = listOf("", "1", "10")
    }
}

val String.Z get() = Zeckendorf(this)

fun main(args: Array<String>) {
    println("Addition:")
    var g = "10".Z
    g += "10".Z
    println(g)
    g += "10".Z
    println(g)
    g += "1001".Z
    println(g)
    g += "1000".Z
    println(g)
    g += "10101".Z
    println(g)
    println("\nSubtraction:")
    g = "1000".Z
    g -= "101".Z
    println(g)
    g = "10101010".Z
    g -= "1010101".Z
    println(g)
    println("\nMultiplication:")
    g = "1001".Z
    g *= "101".Z
    println(g)
    g = "101010".Z
    g += "101".Z
    println(g)
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Nim

Translation of: Go
type Zeckendorf = object
  dVal: Natural
  dLen: Natural

const
  Dig = ["00", "01", "10"]
  Dig1 = ["", "1", "10"]

# Forward references.
func b(z: var Zeckendorf; pos: Natural)
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 (z.dVal shr ((i + 1) * 2) and 1) != 1: return
      z.dVal += 1 shl (i * 2 + 1)
      return
    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 not(1 shl pos)
    z.b(pos + 1)
    z.b(pos - (if pos > 1: 2 else: 1))


func c(z: var Zeckendorf; pos: Natural) =
  if (z.dVal shr pos and 1) == 1:
    z.dVal = z.dVal and not(1 shl pos)
    return

  z.c(pos + 1)
  if pos > 0:
    z.b(pos - 1)
  else:
    inc z


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
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

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;
  }
Output:
           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

Phix

Uses a binary representation of Zeckendorf numbers, eg decimal 11 is stored as 0b10100, ie meaning 8+3, but actually 20 in decimal.
As such, they can be directly compared using the standard comparison operators, and printed quite trivially just by using the %b format.
They are however (and not all that surprisingly) pulled apart into individual bits for addition/subtraction, etc.
Does not handle negative numbers or anything >139583862445 (-ve probably doable but messy, >1.4e12 requires a total rewrite, probably using string representation).

with javascript_semantics

sequence fib = {1,1}
 
function zeckendorf(atom n)
-- Same as Zeckendorf_number_representation#Phix
    atom r = 0
    while fib[$]<n do
        fib &= fib[$] + fib[$-1]
    end while
    integer k = length(fib)
    while k>2 and n<fib[k] do
        k -= 1
    end while   
    for i=k to 2 by -1 do
        integer c = n>=fib[i]
        r += r+c
        n -= c*fib[i]
    end for
    return r
end function
 
function decimal(object z)
-- Convert Zeckendorf number(s) to decimal
    if sequence(z) then
        sequence res = repeat(0,length(z))
        for i=1 to length(z) do
            res[i] = decimal(z[i])
        end for
        return res
    end if
    atom dec = 0, bit = 2
    while z do
        if and_bits(z,1) then
            dec += fib[bit]
        end if
        bit += 1
        if bit>length(fib) then
            fib &= fib[$] + fib[$-1]
        end if
        z = floor(z/2)
    end while
    return dec
end function
 
function to_bits(integer x)
-- 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)
    if x<0 then ?9/0 end if     -- sanity/avoid infinite loop
    sequence bits = {}
    while 1 do
        bits &= remainder(x,2)
        if x=0 then exit end if
        x = floor(x/2)
    end while
    bits &= 0 -- (since eg 101+101 -> 10000)
    return bits
end function
 
function to_bits2(integer a,b)
-- Apply to_bits() to a and b, and pad to the same length
    sequence sa = to_bits(a), 
             sb = to_bits(b)
    integer diff = length(sa)-length(sb)
    if diff!=0 then
        if diff<0 then  sa &= repeat(0,-diff)
                  else  sb &= repeat(0,+diff)
        end if
    end if
    return {sa,sb}
end function
 
function to_int(sequence bits)
-- Copy of bits_to_int(), but in reverse order (lsb last)
    atom val = 0, p = 1
    for i=length(bits) to 1 by -1 do
        if bits[i] then
            val += p
        end if
        p += p
    end for
    return val
end function
 
function zstr(object z)
    if sequence(z) then
        sequence res = repeat(0,length(z))
        for i=1 to length(z) do
            res[i] = zstr(z[i])
        end for
        return res
    end if
    return sprintf("%b",z)
end function
 
function rep(sequence res, integer ds, sequence was, wth)
-- helper for cleanup, validates replacements 
    integer de = ds+length(was)-1
    if res[ds..de]!=was then ?9/0 end if
    if length(was)!=length(wth) then ?9/0 end if
    res = deep_copy(res)
    res[ds..de] = wth
    return res
end function
 
function zcleanup(sequence res)
-- (shared by zadd and zsub)
    integer l = length(res)
    res = deep_copy(res)
    -- first stage, left to right, {020x -> 100x', 030x -> 110x', 021x->110x, 012x->101x}
    for i=1 to l-3 do
        sequence s3 = res[i..i+2]
           if s3={0,2,0} then res[i..i+2] = {1,0,0} res[i+3] += 1
        elsif s3={0,3,0} then res[i..i+2] = {1,1,0} res[i+3] += 1
        elsif s3={0,2,1} then res[i..i+2] = {1,1,0}
        elsif s3={0,1,2} then res[i..i+2] = {1,0,1}
        end if
    end for
    -- first stage cleanup
    if l>1 then
        if res[l-1]=3 then      res = rep(res,l-2,{0,3,0},{1,1,1})      -- 030 -> 111
        elsif res[l-1]=2 then
            if res[l-2]=0 then  res = rep(res,l-2,{0,2,0},{1,0,1})      -- 020 -> 101
                          else  res = rep(res,l-3,{0,1,2,0},{1,0,1,0})  -- 0120 -> 1010
            end if
        end if
    end if
    if res[l]=3 then            res = rep(res,l-1,{0,3},{1,1})          -- 03 -> 11
    elsif res[l]=2 then
        if res[l-1]=0 then      res = rep(res,l-1,{0,2},{1,0})          -- 02 -> 10
                      else      res = rep(res,l-2,{0,1,2},{1,0,1})      -- 012 -> 101
        end if
    end if      
    -- second stage, pass 1, right to left, 011 -> 100
    for i=length(res)-2 to 1 by -1 do
        if res[i..i+2]={0,1,1} then res[i..i+2] = {1,0,0} end if
    end for
    -- second stage, pass 2, left to right, 011 -> 100
    for i=1 to length(res)-2 do
        if res[i..i+2]={0,1,1} then res[i..i+2] = {1,0,0} end if
    end for
    return to_int(res)
end function
 
function zadd(integer a, b)
    sequence {sa,sb} = to_bits2(a,b)
    return zcleanup(reverse(sq_add(sa,sb)))
end function
 
function zinc(integer a)
    return zadd(a,0b1)
end function
 
function zsub(integer a, b)
    sequence {sa,sb} = to_bits2(a,b)
    sequence res = reverse(sq_sub(sa,sb))
    -- (/not/ combined with the first pass of the add routine!)
    for i=1 to length(res)-2 do
        sequence s3 = res[i..i+2]
           if s3={1, 0, 0} then res[i..i+2] = {0,1,1}
        elsif s3={1,-1, 0} then res[i..i+2] = {0,0,1}
        elsif s3={1,-1, 1} then res[i..i+2] = {0,0,2}
        elsif s3={1, 0,-1} then res[i..i+2] = {0,1,0}
        elsif s3={2, 0, 0} then res[i..i+2] = {1,1,1}
        elsif s3={2,-1, 0} then res[i..i+2] = {1,0,1}
        elsif s3={2,-1, 1} then res[i..i+2] = {1,0,2}
        elsif s3={2, 0,-1} then res[i..i+2] = {1,1,0}
        end if
    end for
    -- copied from PicoLisp: {1,-1} -> {0,1} and {2,-1} -> {1,1}
    for i=1 to length(res)-1 do
        sequence s2 = res[i..i+1]
           if s2={1,-1} then res[i..i+1] = {0,1}
        elsif s2={2,-1} then res[i..i+1] = {1,1}
        end if
    end for
    if find(-1,res) then ?9/0 end if -- sanity check
    return zcleanup(res)
end function
 
function zdec(integer a)
    return zsub(a,0b1)
end function
 
function zmul(integer a, b)
    sequence mult = {a,zadd(a,a)}   -- (as per task desc)
    integer bits = 2
    while bits<b do
        mult = append(mult,zadd(mult[$],mult[$-1]))
        bits *= 2
    end while
    integer res = 0,
            bit = 1
    while b do
        if and_bits(b,1) then
            res = zadd(res,mult[bit])
        end if
        b = floor(b/2)
        bit += 1
    end while
    return res
end function
 
function zdiv(integer a, b)
    sequence mult = {b,zadd(b,b)}
    integer bits = 2
    while mult[$]<a do
        mult = append(mult,zadd(mult[$],mult[$-1]))
        bits *= 2
    end while
    integer res = 0
    for i=length(mult) to 1 by -1 do
        integer mi = mult[i]
        if mi<=a then
            res = zadd(res,bits)
            a = zsub(a,mi)
            if a=0 then exit end if
        end if
        bits = floor(bits/2)
    end for
    return {res,a} -- (a is the remainder)
end function
 
for i=0 to 20 do
    integer zi = zeckendorf(i)
    atom d = decimal(zi)
    printf(1,"%2d: %7b (%d)\n",{i,zi,d})
end for
 
procedure test(atom a, string op, atom b, object res, string expected)
    string zres = iff(atom(res)?zstr(res):join(zstr(res)," rem ")),
           dres = sprintf(iff(atom(res)?"%d":"%d rem %d"),decimal(res)),
           aka = sprintf("aka %d %s %d = %s",{decimal(a),op,decimal(b),dres}),
           ok = iff(zres=expected?"":" *** ERROR ***!!")
    printf(1,"%s %s %s = %s, %s %s\n",{zstr(a),op,zstr(b),zres,aka,ok})
end procedure
 
test(0b0,"+",0b0,zadd(0b0,0b0),"0")
test(0b101,"+",0b101,zadd(0b101,0b101),"10000")
test(0b10100,"-",0b1000,zsub(0b10100,0b1000),"1001")
test(0b100100,"-",0b1000,zsub(0b100100,0b1000),"10100")
test(0b1001,"*",0b101,zmul(0b1001,0b101),"1000100")
test(0b1000101,"/",0b101,zdiv(0b1000101,0b101),"1001 rem 1")
 
test(0b10,"+",0b10,zadd(0b10,0b10),"101")
test(0b101,"+",0b10,zadd(0b101,0b10),"1001")
test(0b1001,"+",0b1001,zadd(0b1001,0b1001),"10101")
test(0b10101,"+",0b1000,zadd(0b10101,0b1000),"100101")
test(0b100101,"+",0b10101,zadd(0b100101,0b10101),"1010000")
test(0b1000,"-",0b101,zsub(0b1000,0b101),"1")
test(0b10101010,"-",0b1010101,zsub(0b10101010,0b1010101),"1000000")
test(0b1001,"*",0b101,zmul(0b1001,0b101),"1000100")
test(0b101010,"+",0b101,zadd(0b101010,0b101),"1000100")
 
test(0b10100,"+",0b1010,zadd(0b10100,0b1010),"101000")
test(0b101000,"-",0b1010,zsub(0b101000,0b1010),"10100")
 
test(0b100010,"*",0b100101,zmul(0b100010,0b100101),"100001000001")
test(0b100001000001,"/",0b100,zdiv(0b100001000001,0b100),"101010001 rem 0")
test(0b101000101,"*",0b101001,zmul(0b101000101,0b101001),"101010000010101")
test(0b101010000010101,"/",0b100,zdiv(0b101010000010101,0b100),"1001010001001 rem 10")
 
test(0b10100010010100,"+",0b1001000001,zadd(0b10100010010100,0b1001000001),"100000000010101")
test(0b10100010010100,"-",0b1001000001,zsub(0b10100010010100,0b1001000001),"10010001000010")
test(0b10000,"*",0b1001000001,zmul(0b10000,0b1001000001),"10100010010100")
test(0b1010001010000001001,"/",0b100000000100000,zdiv(0b1010001010000001001,0b100000000100000),"10001 rem 10100001010101")
 
test(0b10100,"+",0b1010,zadd(0b10100,0b1010),"101000")
test(0b10100,"-",0b1010,zsub(0b10100,0b1010),"101")
test(0b10100,"*",0b1010,zmul(0b10100,0b1010),"101000001")
test(0b10100,"/",0b1010,zdiv(0b10100,0b1010),"1 rem 101")
integer m = zmul(0b10100,0b1010)
test(m,"/",0b1010,zdiv(m,0b1010),"10100 rem 0")
Output:
 0:       0 (0)
 1:       1 (1)
 2:      10 (2)
 3:     100 (3)
 4:     101 (4)
 5:    1000 (5)
 6:    1001 (6)
 7:    1010 (7)
 8:   10000 (8)
 9:   10001 (9)
10:   10010 (10)
11:   10100 (11)
12:   10101 (12)
13:  100000 (13)
14:  100001 (14)
15:  100010 (15)
16:  100100 (16)
17:  100101 (17)
18:  101000 (18)
19:  101001 (19)
20:  101010 (20)
0 + 0 = 0, aka 0 + 0 = 0
101 + 101 = 10000, aka 4 + 4 = 8
10100 - 1000 = 1001, aka 11 - 5 = 6
100100 - 1000 = 10100, aka 16 - 5 = 11
1001 * 101 = 1000100, aka 6 * 4 = 24
1000101 / 101 = 1001 rem 1, aka 25 / 4 = 6 rem 1
10 + 10 = 101, aka 2 + 2 = 4
101 + 10 = 1001, aka 4 + 2 = 6
1001 + 1001 = 10101, aka 6 + 6 = 12
10101 + 1000 = 100101, aka 12 + 5 = 17
100101 + 10101 = 1010000, aka 17 + 12 = 29
1000 - 101 = 1, aka 5 - 4 = 1
10101010 - 1010101 = 1000000, aka 54 - 33 = 21
1001 * 101 = 1000100, aka 6 * 4 = 24
101010 + 101 = 1000100, aka 20 + 4 = 24
10100 + 1010 = 101000, aka 11 + 7 = 18
101000 - 1010 = 10100, aka 18 - 7 = 11
100010 * 100101 = 100001000001, aka 15 * 17 = 255
100001000001 / 100 = 101010001 rem 0, aka 255 / 3 = 85 rem 0
101000101 * 101001 = 101010000010101, aka 80 * 19 = 1520
101010000010101 / 100 = 1001010001001 rem 10, aka 1520 / 3 = 506 rem 2
10100010010100 + 1001000001 = 100000000010101, aka 888 + 111 = 999
10100010010100 - 1001000001 = 10010001000010, aka 888 - 111 = 777
10000 * 1001000001 = 10100010010100, aka 8 * 111 = 888
1010001010000001001 / 100000000100000 = 10001 rem 10100001010101, aka 9876 / 1000 = 9 rem 876
10100 + 1010 = 101000, aka 11 + 7 = 18
10100 - 1010 = 101, aka 11 - 7 = 4
10100 * 1010 = 101000001, aka 11 * 7 = 77
10100 / 1010 = 1 rem 101, aka 11 / 7 = 1 rem 4
101000001 / 1010 = 10100 rem 0, aka 77 / 7 = 11 rem 0

PicoLisp

(seed (in "/dev/urandom" (rd 8)))

(de unpad (Lst)
   (while (=0 (car Lst))
      (pop 'Lst) )
   Lst )

(de numz (N)
   (let Fibs (1 1)
      (while (>= N (+ (car Fibs) (cadr Fibs)))
         (push 'Fibs (+ (car Fibs) (cadr Fibs))) )
      (make
         (for I (uniq Fibs)
            (if (> I N)
               (link 0)
               (link 1)
               (dec 'N I) ) ) ) ) )

(de znum (Lst)
   (let Fibs (1 1)
      (do (dec (length Lst))
         (push 'Fibs (+ (car Fibs) (cadr Fibs))) )
      (sum
         '((X Y) (unless (=0 X) Y))
         Lst
         (uniq Fibs) ) ) )
            
(de incz (Lst)
   (addz Lst (1)) )

(de decz (Lst)
   (subz Lst (1)) )
   
(de addz (Lst1 Lst2)
   (let Max (max (length Lst1) (length Lst2))
      (reorg
         (mapcar + (need Max Lst1 0) (need Max Lst2 0)) ) ) )

(de subz (Lst1 Lst2)
   (use (@A @B)
      (let
         (Max (max (length Lst1) (length Lst2))
            Lst (mapcar - (need Max Lst1 0) (need Max Lst2 0)) )
         (loop 
            (while (match '(@A 1 0 0 @B) Lst)
               (setq Lst (append @A (0 1 1) @B)) )
            (while (match '(@A 1 -1 0 @B) Lst)
               (setq Lst (append @A (0 0 1) @B)) )
            (while (match '(@A 1 -1 1 @B) Lst)
               (setq Lst (append @A (0 0 2) @B)) )
            (while (match '(@A 1 0 -1 @B) Lst)
               (setq Lst (append @A (0 1 0) @B)) )
            (while (match '(@A 2 0 0 @B) Lst)
               (setq Lst (append @A (1 1 1) @B)) )
            (while (match '(@A 2 -1 0 @B) Lst)
               (setq Lst (append @A (1 0 1) @B)) )
            (while (match '(@A 2 -1 1 @B) Lst)
               (setq Lst (append @A (1 0 2) @B)) )
            (while (match '(@A 2 0 -1 @B) Lst)
               (setq Lst (append @A (1 1 0) @B)) )
            (while (match '(@A 1 -1) Lst)
               (setq Lst (append @A (0 1))) )
            (while (match '(@A 2 -1) Lst)
               (setq Lst (append @A (1 1))) )
            (NIL (match '(@A -1 @B) Lst)) )
         (reorg (unpad Lst)) ) ) )

(de mulz (Lst1 Lst2)
   (let (Sums (list Lst1) Mulz (0))
      (mapc
         '((X)
            (when (= 1 (car X))
               (setq Mulz (addz (cdr X) Mulz)) ) 
            Mulz )
         (mapcar
            '((X)
               (cons
                  X 
                  (push 'Sums (addz (car Sums) (cadr Sums))) ) )
            (reverse Lst2) ) ) ) ) 
          
(de divz (Lst1 Lst2)
   (let Q 0
      (while (lez Lst2 Lst1)
         (setq Lst1 (subz Lst1 Lst2))
         (setq Q (incz Q)) )
      (list Q (or Lst1 (0))) ) )

(de reorg (Lst)
   (use (@A @B)
      (let Lst (reverse Lst)
         (loop
            (while (match '(@A 1 1 @B) Lst)
               (if @B
                  (inc (nth @B 1))
                  (setq @B (1)) )
               (setq Lst (append @A (0 0) @B) ) )
            (while (match '(@A 2 @B) Lst)
               (inc
                  (if (cdr @A) 
                     (tail 2 @A)
                     @A ) )
               (if @B
                  (inc (nth @B 1))
                  (setq @B (1)) )
               (setq Lst (append @A (0) @B)) )
            (NIL
               (or
                  (match '(@A 1 1 @B) Lst)
                  (match '(@A 2 @B) Lst) ) ) )
         (reverse Lst) ) ) )

(de lez (Lst1 Lst2)
   (let Max (max (length Lst1) (length Lst2))
      (<= (need Max Lst1 0) (need Max Lst2 0)) ) )

(let (X 0 Y 0)
   (do 1024
      (setq X (rand 1 1024))
      (setq Y (rand 1 1024))
      (test (numz (+ X Y)) (addz (numz X) (numz Y)))
      (test (numz (* X Y)) (mulz (numz X) (numz Y)))
      (test (numz (+ X 1)) (incz (numz X))) )

   (do 1024
      (setq X (rand 129 1024))
      (setq Y (rand 1 128))
      (test (numz (- X Y)) (subz (numz X) (numz Y)))
      (test (numz (/ X Y)) (car (divz (numz X) (numz Y))))
      (test (numz (% X Y)) (cadr (divz (numz X) (numz Y))))
      (test (numz (- X 1)) (decz (numz X))) ) )

(bye)

Python

import copy

class Zeckendorf:
    def __init__(self, x='0'):
        q = 1
        i = len(x) - 1
        self.dLen = int(i / 2)
        self.dVal = 0
        while i >= 0:
            self.dVal = self.dVal + (ord(x[i]) - ord('0')) * q
            q = q * 2
            i = i -1

    def a(self, n):
        i = n
        while True:
            if self.dLen < i:
                self.dLen = i
            j = (self.dVal >> (i * 2)) & 3
            if j == 0 or j == 1:
                return
            if j == 2:
                if (self.dVal >> ((i + 1) * 2) & 1) != 1:
                    return
                self.dVal = self.dVal + (1 << (i * 2 + 1))
                return
            if j == 3:
                temp = 3 << (i * 2)
                temp = temp ^ -1
                self.dVal = self.dVal & temp
                self.b((i + 1) * 2)
            i = i + 1

    def b(self, pos):
        if pos == 0:
            self.inc()
            return
        if (self.dVal >> pos) & 1 == 0:
            self.dVal = self.dVal + (1 << pos)
            self.a(int(pos / 2))
            if pos > 1:
                self.a(int(pos / 2) - 1)
        else:
            temp = 1 << pos
            temp = temp ^ -1
            self.dVal = self.dVal & temp
            self.b(pos + 1)
            self.b(pos - (2 if pos > 1 else 1))

    def c(self, pos):
        if (self.dVal >> pos) & 1 == 1:
            temp = 1 << pos
            temp = temp ^ -1
            self.dVal = self.dVal & temp
            return
        self.c(pos + 1)
        if pos > 0:
            self.b(pos - 1)
        else:
            self.inc()

    def inc(self):
        self.dVal = self.dVal + 1
        self.a(0)

    def __add__(self, rhs):
        copy = self
        rhs_dVal = rhs.dVal
        limit = (rhs.dLen + 1) * 2
        for gn in range(0, limit):
            if ((rhs_dVal >> gn) & 1) == 1:
                copy.b(gn)
        return copy

    def __sub__(self, rhs):
        copy = self
        rhs_dVal = rhs.dVal
        limit = (rhs.dLen + 1) * 2
        for gn in range(0, limit):
            if (rhs_dVal >> gn) & 1 == 1:
                copy.c(gn)
        while (((copy.dVal >> ((copy.dLen * 2) & 31)) & 3) == 0) or (copy.dLen == 0):
            copy.dLen = copy.dLen - 1
        return copy

    def __mul__(self, rhs):
        na = copy.deepcopy(rhs)
        nb = copy.deepcopy(rhs)
        nr = Zeckendorf()
        dVal = self.dVal
        for i in range(0, (self.dLen + 1) * 2):
            if ((dVal >> i) & 1) > 0:
                nr = nr + nb
            nt = copy.deepcopy(nb)
            nb = nb + na
            na = copy.deepcopy(nt)
        return nr

    def __str__(self):
        dig = ["00", "01", "10"]
        dig1 = ["", "1", "10"]

        if self.dVal == 0:
            return '0'
        idx = (self.dVal >> ((self.dLen * 2) & 31)) & 3
        sb = dig1[idx]
        i = self.dLen - 1
        while i >= 0:
            idx = (self.dVal >> (i * 2)) & 3
            sb = sb + dig[idx]
            i = i - 1
        return sb

# main
print "Addition:"
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
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

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 canonise puts a Zecekendorf number in canonical form; no two adjacent bits are set to 1, runs of 0s are allowed. The converse operation, defrock 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. zadd and zdouble are mutually recursive.

2blit separates the lowest two bits from a Zeckedorf number so that zdouble 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 canonise and defrock, the word that removes the bits that are set to 1 in both arguments is called exorcise. 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 zlcm 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. zgcd and zlcm exercise the multiplication, division and modulus routines repeatedly, and those exercise the addition, subtraction and comparison routines.

bin is an extension to the Quackery compiler to allow it to understand numbers in binary notation (and hence also Zeckendorf notation).

gcd and lcm are defined at Least common multiple#Quackery, and n->z and z->n are defined at Zeckendorf number representation#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 ]
Output:
25624571429859946191396654570
25624571429859946191396654570

24702413608219494319878326100
24702413608219494319878326100

177592191573881063687998734000
177592191573881063687998734000

28221788451919578670971892845
28221788451919578670971892845

99008448632249766843573255321
99008448632249766843573255321

312648960463735816244223692220
312648960463735816244223692220

146093274904252809568841733264
146093274904252809568841733264

169485448104022309641359784180
169485448104022309641359784180

593337022246602746222083444716
593337022246602746222083444716

50904418052185753625716614402
50904418052185753625716614402

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).

#lang racket (require math)

(define sqrt5 (sqrt 5))
(define phi (* 0.5 (+ 1 sqrt5)))

;; What is the nth fibonnaci number, shifted by 2 so that
;; F(0) = 1, F(1) = 2, ...?
;;
(define (F n)
  (fibonacci (+ n 2)))

;; What is the largest n such that F(n) <= m?
;;
(define (F* m)
  (let ([n (- (inexact->exact (round (/ (log (* m sqrt5)) (log phi)))) 2)])
    (if (<= (F n) m) n (sub1 n))))

(define (zeck->natural z)
  (for/sum ([i (reverse z)]
            [j (in-naturals)])
    (* i (F j))))
            
(define (natural->zeck n)
  (if (zero? n)
      null
      (for/list ([i (in-range (F* n) -1 -1)])
        (let ([f (F i)])
          (cond [(>= n f) (set! n (- n f))
                          1]
                [else 0])))))

; Extend list to the right to a length of len with repeated padding elements
;
(define (pad lst len [padding 0])
  (append lst (make-list (- len (length lst)) padding)))

; Strip padding elements from the left of the list
;
(define (unpad lst [padding 0])
  (cond [(null? lst) lst]
        [(equal? (first lst) padding) (unpad (rest lst) padding)]
        [else lst]))

;; Run a filter function across a window in a list from left to right
;;
(define (left->right width fn)
  (λ (lst)
    (let F ([a lst])
      (if (< (length a) width) 
          a
          (let ([f (fn (take a width))])
            (cons (first f) (F (append (rest f) (drop a width)))))))))

;; Run a function fn across a window in a list from right to left
;;
(define (right->left width fn)
  (λ (lst)
    (let F ([a lst])
      (if (< (length a) width) 
          a
          (let ([f (fn (take-right a width))])
            (append (F (append (drop-right a width) (drop-right f 1)))
                    (list (last f))))))))

;; (a0 a1 a2 ... an) -> (a0 a1 a2 ... (fn ... an))
;;
(define (replace-tail width fn)
  (λ (lst)
    (append (drop-right lst width) (fn (take-right lst width)))))

(define (rule-a lst)
  (match lst
    [(list 0 2 0 x) (list 1 0 0 (add1 x))]
    [(list 0 3 0 x) (list 1 1 0 (add1 x))]
    [(list 0 2 1 x) (list 1 1 0 x)]
    [(list 0 1 2 x) (list 1 0 1 x)]
    [else lst]))

(define (rule-a-tail lst)
  (match lst
    [(list x 0 3 0) (list x 1 1 1)]
    [(list x 0 2 0) (list x 1 0 1)]
    [(list 0 1 2 0) (list 1 0 1 0)]
    [(list x y 0 3) (list x y 1 1)]
    [(list x y 0 2) (list x y 1 0)]
    [(list x 0 1 2) (list x 1 0 0)]
    [else lst]))

(define (rule-b lst)
  (match lst
    [(list 0 1 1) (list 1 0 0)]
    [else lst]))

(define (rule-c lst)
  (match lst
    [(list 1 0 0) (list 0 1 1)]
    [(list 1 -1 0) (list 0 0 1)]
    [(list 1 -1 1) (list 0 0 2)]
    [(list 1 0 -1) (list 0 1 0)]
    [(list 2 0 0) (list 1 1 1)]
    [(list 2 -1 0) (list 1 0 1)]
    [(list 2 -1 1) (list 1 0 2)]
    [(list 2 0 -1) (list 1 1 0)]
    [else lst]))

(define (zeck-combine op y z [f identity])
  (let* ([bits (max (add1 (length y)) (add1 (length z)) 4)]
         [f0 (λ (x) (pad (reverse x) bits))]
         [f1 (left->right 4 rule-a)]
         [f2 (replace-tail 4 rule-a-tail)]
         [f3 (right->left 3 rule-b)]
         [f4 (left->right 3 rule-b)])
    ((compose1 unpad f4 f3 f2 f1 f reverse) (map op (f0 y) (f0 z)))))
 
(define (zeck+ y z)
  (zeck-combine + y z))

(define (zeck- y z)
  (when (zeck< y z) (error (format "~a" `(zeck-: cannot subtract since ,y < ,z))))
  (zeck-combine - y z (left->right 3 rule-c)))

(define (zeck* y z)
  (define (M ry Zn Zn_1 [acc null])
    (if (null? ry) 
        acc
        (M (rest ry) (zeck+ Zn Zn_1) Zn 
           (if (zero? (first ry)) acc (zeck+ acc Zn))))) 
  (cond [(zeck< z y) (zeck* z y)]
        [(null? y) null]               ; 0 * z -> 0
        [else (M (reverse y) z z)]))

(define (zeck-quotient/remainder y z)
  (define (M Zn acc)
    (if (zeck< y Zn) 
        (drop-right acc 1)
        (M (zeck+ Zn (first acc)) (cons Zn acc))))
  (define (D x m [acc null])
    (if (null? m)
        (values (reverse acc) x)
        (let* ([v (first m)]
               [smaller (zeck< v x)]
               [bit (if smaller 1 0)]
               [x_ (if smaller (zeck- x v) x)])
          (D x_ (rest m) (cons bit acc)))))
  (D y (M z (list z))))

(define (zeck-quotient y z)
  (let-values ([(quotient _) (zeck-quotient/remainder y z)])
    quotient))

(define (zeck-remainder y z)
  (let-values ([(_ remainder) (zeck-quotient/remainder y z)])
    remainder))

(define (zeck-add1 z)
  (zeck+ z '(1)))

(define (zeck= y z)
  (equal? (unpad y) (unpad z)))

(define (zeck< y z)
  ; Compare equal-length unpadded zecks
  (define (LT a b)
    (if (null? a) 
        #f
        (let ([a0 (first a)] [b0 (first b)])
          (if (= a0 b0) 
              (LT (rest a) (rest b))
              (= a0 0)))))
        
  (let* ([a (unpad y)] [len-a (length a)]
         [b (unpad z)] [len-b (length b)])
    (cond [(< len-a len-b) #t]
          [(> len-a len-b) #f]
          [else (LT a b)])))

(define (zeck> y z)
  (not (or (zeck= y z) (zeck< y z))))


;; Examples
;;
(define (example op-name op a b)
  (let* ([y (natural->zeck a)]
         [z (natural->zeck b)]
         [x (op y z)]
         [c (zeck->natural x)])
    (printf "~a ~a ~a = ~a ~a ~a = ~a = ~a\n"
            a op-name b y op-name z x c)))

(example '+ zeck+ 888 111)
(example '- zeck- 888 111)
(example '* zeck* 8 111)
(example '/ zeck-quotient 9876 1000)
(example '% zeck-remainder 9876 1000)
Output:
888 + 111 = (1 0 1 0 0 0 1 0 0 1 0 1 0 0) + (1 0 0 1 0 0 0 0 0 1) = (1 0 0 0 0 0 0 0 0 0 1 0 1 0 1) = 999
888 - 111 = (1 0 1 0 0 0 1 0 0 1 0 1 0 0) - (1 0 0 1 0 0 0 0 0 1) = (1 0 0 1 0 0 0 1 0 0 0 0 1 0) = 777
8 * 111 = (1 0 0 0 0) * (1 0 0 1 0 0 0 0 0 1) = (1 0 1 0 0 0 1 0 0 1 0 1 0 0) = 888
9876 / 1000 = (1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1) / (1 0 0 0 0 0 0 0 0 1 0 0 0 0 0) = (1 0 0 0 1) = 9
9876 % 1000 = (1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1) % (1 0 0 0 0 0 0 0 0 1 0 0 0 0 0) = (1 0 1 0 0 0 0 1 0 1 0 1 0 1) = 876

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:

  +z addition 
  -z subtraction
  ×z multiplication
  /z division (more of a divmod really)
 ++z post increment
 --z post decrement

Comparison operators:

 eqz equal 
 nez not equal 
 gtz greater than 
 ltz less than 
my $z1 = '1'; # glyph to use for a '1'
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 ########

# post increment
sub postfix:<++z>($a is rw) {
    $a = ("$z0$z0"~$a).subst(/("$z0$z0")($z1+ %% $z0)?$/,
      -> $/ { "$z0$z1" ~ ($1 ?? $z0 x $1.chars !! '') });
    $a ~~ s/^$z0+//;
    $a
}

# post decrement
sub postfix:<--z>($a is rw) {
    $a.=subst(/$z1($z0*)$/,
      -> $/ {$z0 ~ "$z1$z0" x $0.chars div 2 ~ $z1 x $0.chars mod 2});
    $a ~~ s/^$z0+(.+)$/$0/;
    $a
}

# 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:<×z>($a, $b) { 
    return $z0 if $a eqz $z0 or $b eqz $z0;
    return $a if $b eqz $z1;
    return $b if $a eqz $z1;
    my $c = $a;
    my $d = $z1;
    repeat { 
         my $e = $z0;
         repeat { $c++z; $e++z } until $e eqz $a;
         $d++z;
    } until $d eqz $b;
    $c
}

# division  (really more of a div mod)
sub infix:</z>($a is copy, $b is copy) {
    fail "Divide by zero" if $b eqz $z0;
    return $a if $a eqz $z0 or $b eqz $z1;
    my $c = $z0;
    repeat { 
        my $d = $b +z ($z1 ~ $z0);
        $c++z;
        $a++z;
        $a--z while $d--z nez $z0
    } until $a ltz $b;
    $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";

my $fmt = "%-22s = %15s  %s\n";

my $zeck = $z1;

printf( $fmt, "$zeck++z", $zeck++z, '# increment' ) for 1 .. 10;

printf $fmt, "$zeck +z {z('1010')}", $zeck +z= z('1010'), '# addition';

printf $fmt, "$zeck -z {z('100')}", $zeck -z= z('100'), '# subtraction';

printf $fmt, "$zeck ×z {z('100101')}", $zeck ×z= z('100101'), '# multiplication';

printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';

printf( $fmt, "$zeck--z", $zeck--z, '# decrement' ) for 1 .. 5;

printf $fmt, "$zeck ×z {z('101001')}", $zeck ×z= z('101001'), '# multiplication';

printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';

Testing Output

Using the glyph '1' for 1 and '0' for 0

1++z                   =              10  # increment
10++z                  =             100  # increment
100++z                 =             101  # increment
101++z                 =            1000  # increment
1000++z                =            1001  # increment
1001++z                =            1010  # increment
1010++z                =           10000  # increment
10000++z               =           10001  # increment
10001++z               =           10010  # increment
10010++z               =           10100  # increment
10100 +z 1010          =          101000  # addition
101000 -z 100          =          100010  # subtraction
100010 ×z 100101       =    100001000001  # multiplication
100001000001 /z 100    =       101010001  # division
101010001--z           =       101010000  # decrement
101010000--z           =       101001010  # decrement
101001010--z           =       101001001  # decrement
101001001--z           =       101001000  # decrement
101001000--z           =       101000101  # decrement
101000101 ×z 101001    = 101010000010101  # multiplication
101010000010101 /z 100 = 1001010001001 remainder 10  # division

Using alternate glyphs:

Using the glyph 'X' for 1 and 'O' for 0

X++z                   =              XO  # increment
XO++z                  =             XOO  # increment
XOO++z                 =             XOX  # increment
XOX++z                 =            XOOO  # increment
XOOO++z                =            XOOX  # increment
XOOX++z                =            XOXO  # increment
XOXO++z                =           XOOOO  # increment
XOOOO++z               =           XOOOX  # increment
XOOOX++z               =           XOOXO  # increment
XOOXO++z               =           XOXOO  # increment
XOXOO +z XOXO          =          XOXOOO  # addition
XOXOOO -z XOO          =          XOOOXO  # subtraction
XOOOXO ×z XOOXOX       =    XOOOOXOOOOOX  # multiplication
XOOOOXOOOOOX /z XOO    =       XOXOXOOOX  # division
XOXOXOOOX--z           =       XOXOXOOOO  # decrement
XOXOXOOOO--z           =       XOXOOXOXO  # decrement
XOXOOXOXO--z           =       XOXOOXOOX  # decrement
XOXOOXOOX--z           =       XOXOOXOOO  # decrement
XOXOOXOOO--z           =       XOXOOOXOX  # decrement
XOXOOOXOX ×z XOXOOX    = XOXOXOOOOOXOXOX  # multiplication
XOXOXOOOOOXOXOX /z XOO = XOOXOXOOOXOOX remainder XO  # division

Rust

Translation of: C#
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());
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Scala

Works with: Scala version 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.

import scala.collection.mutable.ListBuffer

object ZeckendorfArithmetic extends App {


  val elapsed: (=> Unit) => Long = f => {
    val s = System.currentTimeMillis

    f

    (System.currentTimeMillis - s) / 1000
  }
  val add: (Z, Z) => Z = (z1, z2) => z1 + z2
  val subtract: (Z, Z) => Z = (z1, z2) => z1 - z2
  val multiply: (Z, Z) => Z = (z1, z2) => z1 * z2
  val divide: (Z, Z) => Option[Z] = (z1, z2) => z1 / z2
  val modulo: (Z, Z) => Option[Z] = (z1, z2) => z1 % z2
  val ops = Map(("+", add), ("-", subtract), ("*", multiply), ("/", divide), ("%", modulo))
  val calcs = List(
    (Z("101"), "+", Z("10100"))
    , (Z("101"), "-", Z("10100"))
    , (Z("101"), "*", Z("10100"))
    , (Z("101"), "/", Z("10100"))
    , (Z("-1010101"), "+", Z("10100"))
    , (Z("-1010101"), "-", Z("10100"))
    , (Z("-1010101"), "*", Z("10100"))
    , (Z("-1010101"), "/", Z("10100"))
    , (Z("1000101010"), "+", Z("10101010"))
    , (Z("1000101010"), "-", Z("10101010"))
    , (Z("1000101010"), "*", Z("10101010"))
    , (Z("1000101010"), "/", Z("10101010"))
    , (Z("10100"), "+", Z("1010"))
    , (Z("100101"), "-", Z("100"))
    , (Z("1010101010101010101"), "+", Z("-1010101010101"))
    , (Z("1010101010101010101"), "-", Z("-1010101010101"))
    , (Z("1010101010101010101"), "*", Z("-1010101010101"))
    , (Z("1010101010101010101"), "/", Z("-1010101010101"))
    , (Z("1010101010101010101"), "%", Z("-1010101010101"))
    , (Z("1010101010101010101"), "+", Z("101010101010101"))
    , (Z("1010101010101010101"), "-", Z("101010101010101"))
    , (Z("1010101010101010101"), "*", Z("101010101010101"))
    , (Z("1010101010101010101"), "/", Z("101010101010101"))
    , (Z("1010101010101010101"), "%", Z("101010101010101"))
    , (Z("10101010101010101010"), "+", Z("1010101010101010"))
    , (Z("10101010101010101010"), "-", Z("1010101010101010"))
    , (Z("10101010101010101010"), "*", Z("1010101010101010"))
    , (Z("10101010101010101010"), "/", Z("1010101010101010"))
    , (Z("10101010101010101010"), "%", Z("1010101010101010"))
    , (Z("1010"), "%", Z("10"))
    , (Z("1010"), "%", Z("-10"))
    , (Z("-1010"), "%", Z("10"))
    , (Z("-1010"), "%", Z("-10"))
    , (Z("100"), "/", Z("0"))
    , (Z("100"), "%", Z("0"))
  )
  val iadd: (BigInt, BigInt) => BigInt = (a, b) => a + b
  val isub: (BigInt, BigInt) => BigInt = (a, b) => a - b

  // just for result checking:

  import Z._

  val imul: (BigInt, BigInt) => BigInt = (a, b) => a * b
  val idiv: (BigInt, BigInt) => Option[BigInt] = (a, b) => if (b == 0) None else Some(a / b)
  val imod: (BigInt, BigInt) => Option[BigInt] = (a, b) => if (b == 0) None else Some(a % b)
  val iops = Map(("+", iadd), ("-", isub), ("*", imul), ("/", idiv), ("%", imod))

  case class Z(var zs: String) {

    import Z._

    require((zs.toSet -- Set('-', '0', '1') == Set()) && (!zs.contains("11")))

    //--- fa(summand1.z,summand2.z) --------------------------
    val fa: (BigInt, BigInt) => BigInt = (z1, z2) => {
      val v = z1.toString.toCharArray.map(_.asDigit).reverse.padTo(5, 0).zipAll(z2.toString.toCharArray.map(_.asDigit).reverse, 0, 0)
      val arr1 = (v.map(p => p._1 + p._2) :+ 0).reverse
      (0 to arr1.length - 4) foreach { i => //stage1
        val a = arr1.slice(i, i + 4).toList
        val b = a.foldRight("")("" + _ + _) dropRight 1
        val a1 = b match {
          case "020" => List(1, 0, 0, a(3) + 1)
          case "030" => List(1, 1, 0, a(3) + 1)
          case "021" => List(1, 1, 0, a(3))
          case "012" => List(1, 0, 1, a(3))
          case _ => a
        }
        0 to 3 foreach { j => arr1(j + i) = a1(j) }
      }
      val arr2 = arr1.foldRight("")("" + _ + _)
        .replace("0120", "1010").replace("030", "111").replace("003", "100").replace("020", "101")
        .replace("003", "100").replace("012", "101").replace("021", "110")
        .replace("02", "10").replace("03", "11")
        .reverse.toArray
      (0 to arr2.length - 3) foreach { i => //stage2, step1
        val a = arr2.slice(i, i + 3).toList
        val b = a.foldRight("")("" + _ + _)
        val a1 = b match {
          case "110" => List('0', '0', '1')
          case _ => a
        }
        0 to 2 foreach { j => arr2(j + i) = a1(j) }
      }
      val arr3 = arr2.foldRight("")("" + _ + _).concat("0").reverse.toArray
      (0 to arr3.length - 3) foreach { i => //stage2, step2
        val a = arr3.slice(i, i + 3).toList
        val b = a.foldRight("")("" + _ + _)
        val a1 = b match {
          case "011" => List('1', '0', '0')
          case _ => a
        }
        0 to 2 foreach { j => arr3(j + i) = a1(j) }
      }
      BigInt(arr3.foldRight("")("" + _ + _))
    }
    //--- fs(minuend.z,subtrahend.z) -------------------------
    val fs: (BigInt, BigInt) => BigInt = (min, sub) => {
      val zmvr = min.toString.toCharArray.map(_.asDigit).reverse
      val zsvr = sub.toString.toCharArray.map(_.asDigit).reverse.padTo(zmvr.length, 0)
      val v = zmvr.zipAll(zsvr, 0, 0).reverse
      val last = v.length - 1
      val zma = zmvr.reverse.toArray

      val zsa = zsvr.reverse.toArray
      for (i <- (0 to last).reverse) {
        val e = zma(i) - zsa(i)
        if (e < 0) {
          zma(i - 1) = zma(i - 1) - 1
          zma(i) = 0
          val part = Z(((i to last).map(zma(_))).foldRight("")("" + _ + _))
          val carry = Z("1".padTo(last - i, "0").foldRight("")("" + _ + _))
          val sum = part + carry

          val sums = sum.z.toString
          (1 to sum.size) foreach { j => zma(last - sum.size + j) = sums(j - 1).asDigit }
          if (zma(i - 1) < 0) {
            for (j <- (0 until i).reverse) {
              if (zma(j) < 0) {
                zma(j - 1) = zma(j - 1) - 1
                zma(j) = 0
                val part = Z(((j to last).map(zma(_))).foldRight("")("" + _ + _))
                val carry = Z("1".padTo(last - j, "0").foldRight("")("" + _ + _))
                val sum = part + carry

                val sums = sum.z.toString
                (1 to sum.size) foreach { k => zma(last - sum.size + k) = sums(k - 1).asDigit }
              }
            }
          }
        }
        else zma(i) = e
        zsa(i) = 0
      }
      BigInt(zma.foldRight("")("" + _ + _))
    }
    //--- fm(multiplicand.z,multplier.z) ---------------------
    val fm: (BigInt, BigInt) => BigInt = (mc, mp) => {
      val mct = mt(Z(mc.toString))
      val mpxi = mp.toString.reverse.toCharArray.map(_.asDigit).zipWithIndex.filter(_._1 != 0).map(_._2)
      mpxi.foldRight(Z("0"))((fi, sum) => sum + mct(fi)).z
    }
    //--- fd(dividend.z,divisor.z) ---------------------------
    val fd: (BigInt, BigInt) => BigInt = (dd, ds) => {
      val dst = dt(Z(dd.toString), Z(ds.toString)).reverse
      var diff = Z(dd.toString)
      val zd = ListBuffer[String]()
      0 until dst.length foreach { i =>
        if (dst(i) > diff) zd += "0" else {
          diff = diff - dst(i)

          zd += "1"
        }
      }
      BigInt(zd.mkString)
    }
    val fasig: (Z, Z) => Int = (z1, z2) => if (z1.z.abs > z2.z.abs) z1.z.signum else z2.z.signum
    val fssig: (Z, Z) => Int = (z1, z2) =>
      if ((z1.z.abs > z2.z.abs && z1.z.signum > 0) || (z1.z.abs < z2.z.abs && z1.z.signum < 0)) 1 else -1
    var z: BigInt = BigInt(zs)

    override def toString: String = "" + z + "Z(i:" + z2i(this) + ")"

    def size: Int = z.abs.toString.length

    def ++ : Z = {
      val za = this + Z("1")

      this.zs = za.zs

      this.z = za.z

      this
    }

    def +(that: Z): Z =
      if (this == Z("0")) that
      else if (that == Z("0")) this
      else if (this.z.signum == that.z.signum) Z((fa(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum).toString)
      else if (this.z.abs == that.z.abs) Z("0")
      else Z((fs(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * fasig(this, that)).toString)

    def -- : Z = {
      val zs = this - Z("1")

      this.zs = zs.zs

      this.z = zs.z

      this
    }

    def -(that: Z): Z =
      if (this == Z("0")) Z((that.z * (-1)).toString)
      else if (that == Z("0")) this
      else if (this.z.signum != that.z.signum) Z((fa(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum).toString)
      else if (this.z.abs == that.z.abs) Z("0")
      else Z((fs(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * fssig(this, that)).toString)

    def %(that: Z): Option[Z] =
      if (that == Z("0")) None
      else if (this == Z("0")) Some(Z("0"))
      else if (that == Z("1")) Some(Z("0"))
      else if (this.z.abs < that.z.abs) Some(this)
      else if (this.z == that.z) Some(Z("0"))
      else this / that match {
        case None => None

        case Some(z) => Some(this - z * that)
      }

    def *(that: Z): Z =
      if (this == Z("0") || that == Z("0")) Z("0")
      else if (this == Z("1")) that
      else if (that == Z("1")) this
      else Z((fm(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum * that.z.signum).toString)

    def /(that: Z): Option[Z] =
      if (that == Z("0")) None
      else if (this == Z("0")) Some(Z("0"))
      else if (that == Z("1")) Some(Z("1"))
      else if (this.z.abs < that.z.abs) Some(Z("0"))
      else if (this.z == that.z) Some(Z("1"))
      else Some(Z((fd(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum * that.z.signum).toString))

    def <(that: Z): Boolean = this.z < that.z

    def <=(that: Z): Boolean = this.z <= that.z

    def >(that: Z): Boolean = this.z > that.z

    def >=(that: Z): Boolean = this.z >= that.z

  }

  object Z {
    // only for comfort and result checking:
    val fibs: LazyList[BigInt] = {
      def series(i: BigInt, j: BigInt): LazyList[BigInt] = i #:: series(j, i + j)

      series(1, 0).tail.tail.tail
    }
    val z2i: Z => BigInt = z => z.z.abs.toString.toCharArray.map(_.asDigit).reverse.zipWithIndex.map { case (v, i) => v * fibs(i) }.foldRight(BigInt(0))(_ + _) * z.z.signum

    var fmts: Map[Z, List[Z]] = Map(Z("0") -> List[Z](Z("0"))) //map of Fibonacci multiples table of divisors

    // get division table (division weight vector)
    def dt(dd: Z, ds: Z): List[Z] = {
      val wv = new ListBuffer[Z]
      wv ++= mt(ds)
      var zs = ds.z.abs.toString
      val upper = dd.z.abs.toString
      while ((zs.length < upper.length)) {
        wv += (wv.toList.last + wv.toList.reverse.tail.head)

        zs = "1" + zs
      }
      wv.toList
    }

    // get multiply table from fmts
    def mt(z: Z): List[Z] = {
      fmts.getOrElse(z, Nil) match {
        case Nil =>
          val e = mwv(z)
          fmts = fmts + (z -> e)
          e
        case l => l
      }
    }

    // multiply weight vector
    def mwv(z: Z): List[Z] = {
      val wv = new ListBuffer[Z]
      wv += z
      wv += (z + z)
      var zs = "11"
      val upper = z.z.abs.toString
      while ((zs.length < upper.length)) {
        wv += (wv.toList.last + wv.toList.reverse.tail.head)

        zs = "1" + zs
      }
      wv.toList
    }
  }

  println("elapsed time: " + elapsed {
    calcs foreach { case (op1, op, op2) => println("" + op1 + " " + op + " " + op2 + " = "
      + {
      (ops(op)) (op1, op2) match {
        case None => None

        case Some(z) => z

        case z => z
      }
      }
      .ensuring { x =>
        (iops(op)) (z2i(op1), z2i(op2)) match {
          case None => None == x

          case Some(i) => i == z2i(x.asInstanceOf[Z])

          case i => i == z2i(x.asInstanceOf[Z])
        }
      })
    }
  } + " sec"
  )

}

Output:

101Z(i:4) + 10100Z(i:11) = 100010Z(i:15)
101Z(i:4) - 10100Z(i:11) = -1010Z(i:-7)
101Z(i:4) * 10100Z(i:11) = 10010010Z(i:44)
101Z(i:4) / 10100Z(i:11) = 0Z(i:0)
-1010101Z(i:-33) + 10100Z(i:11) = -1000001Z(i:-22)
-1010101Z(i:-33) - 10100Z(i:11) = -10010010Z(i:-44)
-1010101Z(i:-33) * 10100Z(i:11) = -101010001010Z(i:-363)
-1010101Z(i:-33) / 10100Z(i:11) = -100Z(i:-3)
1000101010Z(i:109) + 10101010Z(i:54) = 10000101001Z(i:163)
1000101010Z(i:109) - 10101010Z(i:54) = 100000000Z(i:55)
1000101010Z(i:109) * 10101010Z(i:54) = 101000001000101001Z(i:5886)
1000101010Z(i:109) / 10101010Z(i:54) = 10Z(i:2)
10100Z(i:11) + 1010Z(i:7) = 101000Z(i:18)
100101Z(i:17) - 100Z(i:3) = 100001Z(i:14)
1010101010101010101Z(i:10945) + -1010101010101Z(i:-609) = 1010100000000000000Z(i:10336)
1010101010101010101Z(i:10945) - -1010101010101Z(i:-609) = 10000001010101010100Z(i:11554)
1010101010101010101Z(i:10945) * -1010101010101Z(i:-609) = -100010001000001001010010100100001Z(i:-6665505)
1010101010101010101Z(i:10945) / -1010101010101Z(i:-609) = -100101Z(i:-17)
1010101010101010101Z(i:10945) % -1010101010101Z(i:-609) = 1010100100100Z(i:592)
1010101010101010101Z(i:10945) + 101010101010101Z(i:1596) = 10000101010101010100Z(i:12541)
1010101010101010101Z(i:10945) - 101010101010101Z(i:1596) = 1010000000000000000Z(i:9349)
1010101010101010101Z(i:10945) * 101010101010101Z(i:1596) = 10001000100001010001001010001001001Z(i:17468220)
1010101010101010101Z(i:10945) / 101010101010101Z(i:1596) = 1001Z(i:6)
1010101010101010101Z(i:10945) % 101010101010101Z(i:1596) = 101000000001000Z(i:1369)
10101010101010101010Z(i:17710) + 1010101010101010Z(i:2583) = 100001010101010101001Z(i:20293)
10101010101010101010Z(i:17710) - 1010101010101010Z(i:2583) = 10100000000000000000Z(i:15127)
10101010101010101010Z(i:17710) * 1010101010101010Z(i:2583) = 1000100010001000000000001000100010001Z(i:45744930)
10101010101010101010Z(i:17710) / 1010101010101010Z(i:2583) = 1001Z(i:6)
10101010101010101010Z(i:17710) % 1010101010101010Z(i:2583) = 1010000000001000Z(i:2212)
1010Z(i:7) % 10Z(i:2) = 1Z(i:1)
1010Z(i:7) % -10Z(i:-2) = 1Z(i:1)
-1010Z(i:-7) % 10Z(i:2) = -1Z(i:-1)
-1010Z(i:-7) % -10Z(i:-2) = -1Z(i:-1)
100Z(i:3) / 0Z(i:0) = None
100Z(i:3) % 0Z(i:0) = None
elapsed time: 1 sec

Tcl

Translation of: Raku
namespace eval zeckendorf {
    # Want to use alternate symbols? Change these
    variable zero "0"
    variable one "1"

    # Base operations: increment and decrement
    proc zincr var {
	upvar 1 $var a
	namespace upvar [namespace current] zero 0 one 1
	if {![regsub "$0$" $a $1$0 a]} {append a $1}
	while {[regsub "$0$1$1" $a "$1$0$0" a]
		|| [regsub "^$1$1" $a "$1$0$0" a]} {}
	regsub ".$" $a "" a
	return $a
    }
    proc zdecr var {
	upvar 1 $var a
	namespace upvar [namespace current] zero 0 one 1
	regsub "^$0+(.+)$" [subst [regsub "${1}($0*)$" $a "$0\[
		string repeat {$1$0} \[regsub -all .. {\\1} {} x]]\[
		string repeat {$1} \[expr {\$x ne {}}]]"]
	    ] {\1} a
	return $a
    }

    # Exported operations
    proc eq {a b} {
	expr {$a eq $b}
    }
    proc add {a b} {
	variable zero
	while {![eq $b $zero]} {
	    zincr a
	    zdecr b
	}
	return $a
    }
    proc sub {a b} {
	variable zero
	while {![eq $b $zero]} {
	    zdecr a
	    zdecr b
	}
	return $a
    }
    proc mul {a b} {
	variable zero
	variable one
	if {[eq $a $zero] || [eq $b $zero]} {return $zero}
	if {[eq $a $one]} {return $b}
	if {[eq $b $one]} {return $a}
	set c $a
	while {![eq [zdecr b] $zero]} {
	    set c [add $c $a]
	}
	return $c
    }
    proc div {a b} {
	variable zero
	variable one
	if {[eq $b $zero]} {error "div zero"}
	if {[eq $a $zero] || [eq $b $one]} {return $a}
	set r $zero
	while {![eq $a $zero]} {
	    if {![eq $a [add [set a [sub $a $b]] $b]]} break
	    zincr r
	}
	return $r
    }
    # Note that there aren't any ordering operations in this version

    # Assemble into a coherent API
    namespace export \[a-y\]*
    namespace ensemble create
}

Demonstrating:

puts [zeckendorf add "10100" "1010"]
puts [zeckendorf sub "10100" "1010"]
puts [zeckendorf mul "10100" "1010"]
puts [zeckendorf div "10100" "1010"]
puts [zeckendorf div [zeckendorf mul "10100" "1010"] "1010"]
Output:
101000
101
101000001
1
10100

Visual Basic .NET

Translation of: C#
Imports System.Text

Module Module1

    Class Zeckendorf
        Implements IComparable(Of Zeckendorf)

        Private Shared ReadOnly dig As String() = {"00", "01", "10"}
        Private Shared ReadOnly dig1 As String() = {"", "1", "10"}

        Private dVal As Integer = 0
        Private dLen As Integer = 0

        Public Sub New(Optional x As String = "0")
            Dim q = 1
            Dim i = x.Length - 1
            dLen = i \ 2

            Dim z = Asc("0")
            While i >= 0
                Dim a = Asc(x(i))
                dVal += (a - z) * q
                q *= 2
                i -= 1
            End While
        End Sub

        Private Sub A(n As Integer)
            Dim i = n
            While True
                If dLen < i Then
                    dLen = i
                End If
                Dim j = (dVal >> (i * 2)) And 3
                If j = 0 OrElse j = 1 Then
                    Return
                ElseIf j = 2 Then
                    If ((dVal >> ((i + 1) * 2)) And 1) <> 1 Then
                        Return
                    End If
                    dVal += 1 << (i * 2 + 1)
                    Return
                ElseIf j = 3 Then
                    Dim temp = 3 << (i * 2)
                    temp = temp Xor -1
                    dVal = dVal And temp
                    B((i + 1) * 2)
                End If
                i += 1
            End While
        End Sub

        Private Sub B(pos As Integer)
            If pos = 0 Then
                Inc()
                Return
            End If
            If ((dVal >> pos) And 1) = 0 Then
                dVal += 1 << pos
                A(pos \ 2)
                If pos > 1 Then
                    A(pos \ 2 - 1)
                End If
            Else
                Dim temp = 1 << pos
                temp = temp Xor -1
                dVal = dVal And temp
                B(pos + 1)
                B(pos - If(pos > 1, 2, 1))
            End If
        End Sub

        Private Sub C(pos As Integer)
            If ((dVal >> pos) And 1) = 1 Then
                Dim temp = 1 << pos
                temp = temp Xor -1
                dVal = dVal And temp
                Return
            End If
            C(pos + 1)
            If pos > 0 Then
                B(pos - 1)
            Else
                Inc()
            End If
        End Sub

        Public Function Inc() As Zeckendorf
            dVal += 1
            A(0)
            Return Me
        End Function

        Public Function Copy() As Zeckendorf
            Dim z As New Zeckendorf With {
                .dVal = dVal,
                .dLen = dLen
            }
            Return z
        End Function

        Public Sub PlusAssign(other As Zeckendorf)
            Dim gn = 0
            While gn < (other.dLen + 1) * 2
                If ((other.dVal >> gn) And 1) = 1 Then
                    B(gn)
                End If
                gn += 1
            End While
        End Sub

        Public Sub MinusAssign(other As Zeckendorf)
            Dim gn = 0
            While gn < (other.dLen + 1) * 2
                If ((other.dVal >> gn) And 1) = 1 Then
                    C(gn)
                End If
                gn += 1
            End While
            While (((dVal >> dLen * 2) And 3) = 0) OrElse dLen = 0
                dLen -= 1
            End While
        End Sub

        Public Sub TimesAssign(other As Zeckendorf)
            Dim na = other.Copy
            Dim nb = other.Copy
            Dim nt As Zeckendorf
            Dim nr As New Zeckendorf
            Dim i = 0
            While i < (dLen + 1) * 2
                If ((dVal >> i) And 1) > 0 Then
                    nr.PlusAssign(nb)
                End If
                nt = nb.Copy
                nb.PlusAssign(na)
                na = nt.Copy
                i += 1
            End While
            dVal = nr.dVal
            dLen = nr.dLen
        End Sub

        Public Function CompareTo(other As Zeckendorf) As Integer Implements IComparable(Of Zeckendorf).CompareTo
            Return dVal.CompareTo(other.dVal)
        End Function

        Public Overrides Function ToString() As String
            If dVal = 0 Then
                Return "0"
            End If

            Dim idx = (dVal >> (dLen * 2)) And 3
            Dim sb As New StringBuilder(dig1(idx))
            Dim i = dLen - 1
            While i >= 0
                idx = (dVal >> (i * 2)) And 3
                sb.Append(dig(idx))
                i -= 1
            End While
            Return sb.ToString
        End Function
    End Class

    Sub Main()
        Console.WriteLine("Addition:")
        Dim g As New Zeckendorf("10")
        g.PlusAssign(New Zeckendorf("10"))
        Console.WriteLine(g)
        g.PlusAssign(New Zeckendorf("10"))
        Console.WriteLine(g)
        g.PlusAssign(New Zeckendorf("1001"))
        Console.WriteLine(g)
        g.PlusAssign(New Zeckendorf("1000"))
        Console.WriteLine(g)
        g.PlusAssign(New Zeckendorf("10101"))
        Console.WriteLine(g)
        Console.WriteLine()

        Console.WriteLine("Subtraction:")
        g = New Zeckendorf("1000")
        g.MinusAssign(New Zeckendorf("101"))
        Console.WriteLine(g)
        g = New Zeckendorf("10101010")
        g.MinusAssign(New Zeckendorf("1010101"))
        Console.WriteLine(g)
        Console.WriteLine()

        Console.WriteLine("Multiplication:")
        g = New Zeckendorf("1001")
        g.TimesAssign(New Zeckendorf("101"))
        Console.WriteLine(g)
        g = New Zeckendorf("101010")
        g.PlusAssign(New Zeckendorf("101"))
        Console.WriteLine(g)
    End Sub

End Module
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

V (Vlang)

Translation of: Go
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)
}
Output:
Addition:
101
1001
10101
100101
1010000

Subtraction:
1
1000000

Multiplication:
1000100
1000100

Wren

Translation of: Kotlin
Library: Wren-trait
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