Zeckendorf arithmetic

Zeckendorf arithmetic is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

  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

C++

<lang cpp>// 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

1. 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;

} </lang>

Testing

The following tests addtition: <lang cpp>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;

}</lang>

Output:

101
1001
10101
100101
1010000

The following tests subtraction: <lang cpp>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;

}</lang>

Output:

1
1000000

The following tests multiplication: <lang cpp> int main(void) {

 N G = 1001N;
 G *= 101N;
 std::cout << G << std::endl;

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

}</lang>

Output:

1000100
1000100