Zeckendorf arithmetic: Difference between revisions
No edit summary |
m (→{{header|C++}}) |
||
Line 69: | Line 69: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{works with|C++11}} |
|||
<lang cpp>// For a class N which implements Zeckendorf numbers: |
<lang cpp>// For a class N which implements Zeckendorf numbers: |
||
// I define an increment operation ++() |
// I define an increment operation ++() |
Revision as of 18:13, 7 April 2013
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++
<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
- 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>############### Some helper routines ################
- Zeckendorf orders-of-magnitude: infinite lazy list
my @oom := 1, 2, *+* ... *;
- Check to see if it is a valid Zeckendorf number
sub is_zec ($a) { so( $a >= 0 and $a !~~ /<-[01]>/ and $a !~~ /11/ ) }
- Get the index of the largest order of magnetude smaller than the number
sub zindex ($a where $a >= 1) {
my $i; map { $i = $_-1 and last if @oom[$_] > $a }, 1..*; $i
}
- Convert Zeckendorf radix to decimal radix if valid
multi sub z2d ($a where $a.&is_zec) { [+] ($a.comb.reverse Z* @oom) } multi sub z2d ($a) { fail "$a is not a valid Zeckendorf number" }
- Convert decimal radix to Zeckendorf radix
sub d2z ($a where $a >= 0) {
return $a if $a <= 1; my $b = $a; my $z; map { $z ~= ($b div @oom[$_]); $b mod= @oom[$_] }, ( 0 .. zindex($a) ).reverse; $z
}
- Operators for Zeckendorf arithmetic ########
- addition
sub infix:<+z>($a, $b) { d2z(z2d($a) + z2d($b)) };
- subtraction
sub infix:<-z>($a, $b) { d2z(z2d($a) - z2d($b)) };
- multiplication
sub infix:<*z>($a, $b) { d2z(z2d($a) * z2d($b)) };
- division (really more of a div mod)
sub infix:</z>($a, $b) {
my $d = d2z(z2d($a) div z2d($b)); my $r = d2z(z2d($a) mod z2d($b)); $d ~= " remainder $r" if $r; $d
};
- post increment
sub postfix:<++z>($a is rw) { $a = d2z(z2d($a) + 1) };
- post decrement
sub postfix:<--z>($a is rw) { $a = d2z(z2d($a) - 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.&z2d", $zeck.=&z2d, '# conversion';
printf $fmt, "$zeck.&d2z", $zeck.=&d2z, '# conversion';
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 = 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.&z2d = 1520 # conversion 1520.&d2z = 101010000010101 # conversion 101010000010101 /z 100 = 1001010001001 remainder 10 # division