Zeckendorf arithmetic: Difference between revisions

From Rosetta Code
m (moved Zeckendorf arithmatic to Zeckendorf arithmetic: Spelling correction)
(No difference)

Revision as of 14:44, 29 October 2012

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.

Zeckendorf number representation is described Here. It looks like binary. The purpose of this task is to explore why Babbage et al. may have preferred binary to zeckendorf when designing computers. Here I extended the representation task by adding an increment and comparison operator. This task will implement addition; subtraction; multiplication; and division using zeckendorf.

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.

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

Subtraction.

To be completed.

Multiplication.

To be completed.

Division.

To be completed.

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) // Nigel Galloway October 28th., 2012

  1. include <iostream>

class N { private:

   int dVal = 0, dLen;
   void _a(int i) {
       for (;; i++) {
           if (dLen < i) dLen = i;
           switch ((dVal >> (i*2)) & 3) {
           case 0: case 1: return;
           case 2: if (((dVal >> ((i+1)*2)) & 1) != 1) return;
                   dVal &= ~(3 << (i*2)); dVal += 1 << (i+1)*2; return;
           case 3: 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));
   }}

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 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> The the following test:

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

Produces this

Output:
101
1001
10101
100101
1010000