Zeckendorf arithmetic
Zeckendorf number representation 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.
This task is a total immersion zeckendorf task, using decimal numbers will attract serious disapprobation.
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.
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 Sadley 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