Monday, 22 September 2008

mmmm

The golden ratio, represented by the Greek letter, φ (phi), is equal to (sqrt(5)+1)/2. This number makes a very interesting base because of this special property:

φ2 = φ + 1, which means 100φ = 011φ and 0200φ = 1001φ. These two rules can be applied in either direction against any sequence of consecutive digits in a base-φ number to put it in "standard form", which means no digits other than 0 or 1, and no two 1's in a row. In addition, the repeating decimal 0.101010... is equal to 1.

100φ = 011φ

This relation can be applied anywhere in a base-φ number to handle most "carries" when adding. So, for example,

111.111
+111.111
--------
222.222

is the result after doing the addition, but the "2" digits in the result aren't considered "normal form", so they must be reorganized into zeros and ones by "carrying" the digits to the left. Unlike integer base arithmetic, in which digits need to be carried only to the next column, in base-φ, we have to carry two non-zero digits two places to the left using the identity 100φ = 011φ. Here's how that looks:

111.111
+111.111
--------
222.222, and then process the "carries" this way:
222.311
223.201
232.101
321.101
1211.101
10111.101

0200φ = 1001φ

Does this always work? No, we have a problem if we encounter an "02" pattern. One way to handle it is to carry one digit to the left, and one digit two places to the right, so 02.00 becomes 10.01. Then we might have another problem if the "rightbound carry" lands on a digit that's already one, because we might have to carry a digit two more places to the right. Here's an example where this comes up:

10100
+10101
--------
20201, and then process the "carries" this way:
21002
21010.01
110010.01

No comments: