Exercise idea: Golden ratio base / Phinary

[sshine]

(This exercise idea was proposed by someone following the Haskell track. I tried to push them into submitting a pull request for a new exercise, but instead they proposed one of their own, so I'm keeping their idea here.)

The golden ratio base (base-φ) has some interesting properties. One of them is that even though φ is irrational, all non-negative integers have a unique representation as a terminating (finite) base-φ expansion. If the exercise were to define toPhinary :: Natural -> Phinary (Numeric.Natural), the algorithm to apply might be this one. There are two rules to keep in mind, φ × φ = 1 + φ and 1 / φ = −1 + φ.

---

An example: Representing decimal x = 7 in base-φ:

1. The highest power of φ ≤ 7: φ⁴ = 2 + 3φ ≈ 6.854... ≤ 7.

   (φ⁴ = φ² × φ² = (1 + φ)² = 1 + φ² + 2φ = 1 + (1 + φ) + 2φ = 2 + 3φ)

   The result so far being 10000.0000..._φ

2. Subtracting this from 7, we have 7 - (2 + 3φ) = 5 - 3φ ≈ 0.146...

3. The highest power of φ ≤ 5 - 3φ: φ^-4 = 5 - 3φ ≈ 0.146...

   (φ^-4 = ... = 5 - 3φ)

   The result so far being 10000.0001..._φ

4. Subtracting 5 - 3φ from 5 - 3φ, we have 0, so this is the final representation (confirmed).

---

I'll copy-paste a note from the exercise's benefactor wrt. precision:

As people will probably apply the algorithm given in this section, they can try to use floating point operations for finding the largest suitable power of phi at step 2. This is not good, because it's imprecise. To prevent this, there must be numbers with large enough negative powers in the test set, so that imprecise methods don't work (that's why the type is Integer). These numbers should probably be randomly generated. Then, there is a challenge for creators of the tests: if we generate a large integer, how do we know if it has a large negative power of phi? (It seems to be so; but maybe not always?) On the other hand, if we generate two sequences of zeros and ones (before and after the decimal dot, the latter being large enough), how do we know it's an integer? Then, this additional task can be useful: given a "fractional" part of Phinary, find the smallest "integer" part that makes the result integer. And vice versa, just for fun.

In the inverse function (Phinary -> Maybe Integer), both integer and fractional numbers should be given to prevent the usage of approximate methods.

---

There are quite a lot of other potential exercises within this domain, e.g. defining

• fromPhinary :: Phinary -> Maybe Integer
• normalize :: Phinary -> Phinary
• isNormalized :: Phinary -> Bool

See standard form.

But perhaps toPhinary :: Natural -> Phinary is enough already.