Zeckendorf arithmetic: Difference between revisions
m
→{{header|Quackery}}: another typo
m (→{{header|Quackery}}: another typo) |
|||
Line 3,256:
Multiplication is basically the Russian Peasant algorithm with the twist that instead of doubling we start with two instances of one of the multiplicands and repeatedly add them Fibonacci style.
Subtraction is implemented as ''difference'' (i.e. abs(a-b) as this is an unsigned implementation.) The process is to reduce both numbers in value until the smaller one equals zero. Continuing the naming theme established by <code>canonise</code> and <code>defrock</code>, the word that removes the bits that are set to 1 in both arguments is called <code>exorcise</code>. The appropriate sequence of exorcisms and defrockings will reduce the smaller argument to zero much of the time.
However, numbers which alternate 1s and 0s (e.g. ...01010101...) are immune to both canonisation and defrocking). When this occurs we add the smaller number to the larger number and double the smaller number and repeat the exorisms and defrockings. Extensive testing leads me to believe with a very high degree of confidence this is sufficient, but I have not proved it in a mathematical sense.
| |||