Zeckendorf arithmetic: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Perl 6}}: remove / condense some redundant code)
m (→‎{{header|Perl 6}}: a few minor tweaks)
Line 239: Line 239:
if !$a {
if !$a {
$a = 1
$a = 1
} elsif $a == 1 {
} elsif $a ~~ /^10?$/ {
$a = 10
$a ~= 0
} elsif $a == 10 {
$a = 100
} elsif $a ~~ /00$/ {
} elsif $a ~~ /00$/ {
$a ~~ s/00$/01/
$a ~~ s/00$/01/
} elsif $a ~~ /00/ {
} elsif $a ~~ /00/ {
$a = $a.subst( /(00)('1'* %% '0')$/, -> $/ { '01' ~ '0' x ($1.chars) })
$a.=subst( /(00)('1'* %% '0')$/, -> $/ { '01' ~ '0' x $1.chars });
} else {
} else {
$a = 1 ~ '0' x $a.chars
$a = 1 ~ '0' x $a.chars
Line 289: Line 287:
fail "Divide by zero" if $b == 0;
fail "Divide by zero" if $b == 0;
return $a if $b == 1;
return $a if $b == 1;
my $d = 0;
my $c = 0;
repeat {
repeat {
my $c = $b +z 10;
my $d = $b +z 10;
$d++z;
$c++z;
$a--z while $c--z
$a--z while $d--z
} until $a < $b;
} until $a < $b;
$d ~= " remainder $a" if $a;
$c ~= " remainder $a" if $a;
$d
$c
};
};


Revision as of 22:33, 7 April 2013

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.

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

Works with: C++11

<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

Perl 6

This is a somewhat limited implementation of Zeckendorf arithmetic operators. They only handle positive integer values. They could be extended to handle negative and decimal (Zeckendorfimal?) fractions but it is beyond the scope of the task.

Implemented operators for: 

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

Didn't bother to implement Zeckendorf specific comparison operators since standard comparison operators will work just fine.

Note that the arithmetic operators are non mutating. For a mutating operator, add an = sign to the end like any other Perl 6 operator. I.E. 

my $z = 100;    # define a variable; put 100 in it
say $z +z 100;  # non mutating; prints 1001
say $z;         # prints 100; $z didn't change
say $z +z= 100; # mutating; prints 1001
say $z;         # prints 1001

The increment / decrement operators are implemented as mutating operators since they are unary. 

my $z = 100;  # define a variable; put 100 in it
say $z++z;    # mutating; prints 101
say $z;       # prints 101
say $z--z;    # mutating; prints 100
say $z;       # prints 100

<lang perl6>######## Operators for Zeckendorf arithmetic ########

  1. post increment

sub postfix:<++z>($a is rw) { 

   if !$a {
       $a = 1
   } elsif $a ~~ /^10?$/ {
       $a ~= 0
   } elsif $a ~~ /00$/ {
       $a ~~ s/00$/01/
   } elsif $a ~~ /00/ {
       $a.=subst( /(00)('1'* %% '0')$/, -> $/ { '01' ~ '0' x $1.chars });
   } else {
       $a = 1 ~ '0' x $a.chars
   }
   $a

}

  1. post decrement

sub postfix:<--z>($a is rw) { 

   if $a ~~ /1$/ {
       $a ~~ s/1$/0/
   } else {
       $a.=subst(/1(0+)$/, -> $/ {0 ~ '10' x $0.chars div 2 ~ '1' x $0.chars mod 2})
   }
   $a ~~ s/^0+//;
   $a

}

  1. addition

sub infix:<+z>($a is copy, $b is copy) { $a++z while $b--z; $a };

  1. subtraction

sub infix:<-z>($a is copy, $b is copy) { $a--z while $b--z; $a };

  1. multiplication

multi sub infix:<*z>($a, $b) { 

   return 0 if $a == 0 or $b == 0;
   return $a * $b if $a == 1 or $b == 1; 
   my $c = $a;
   my $d = 1;
   repeat { 
        my $e = 0;
        repeat { $c++z; $e++z } until $e == $a;
        $d++z;
   } until $d == $b;
   $c

};

  1. division (really more of a div mod)

sub infix:</z>($a is copy, $b is copy) { 

   return 0 if $a == 0;
   fail "Divide by zero" if $b == 0;
   return $a if $b == 1;
   my $c = 0;
   repeat { 
       my $d = $b +z 10;
       $c++z;
       $a--z while $d--z
   } until $a < $b;
   $c ~= " remainder $a" if $a;
   $c

};


                                            1. Testing ######################

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

my $zeck = 1;

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

printf $fmt, "$zeck +z 1010", $zeck +z= 1010, '# addition';

printf $fmt, "$zeck -z 100", $zeck -z= 100, '# subtraction';

printf $fmt, "$zeck *z 100101", $zeck *z= 100101, '# multiplication';

printf $fmt, "$zeck /z 100", $zeck /z= 100, '# division';

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

printf $fmt, "$zeck *z 101001", $zeck *z= 101001, '# multiplication';

printf $fmt, "$zeck /z 100", $zeck /z= 100, '# division';</lang>

Testing Output 

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          =          100101  # addition
100101 -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
Retrieved from "https://rosettacode.org/wiki/Zeckendorf_arithmetic?oldid=221047"