Fibonacci subtraction

As is known the "binary" subtraction is arithmetical operation being more complicated as the "binary" addition. There exist two variants of the "binary" subtraction: (1) the subtraction in the "direct" code; (2) the subtraction based on the application of the special codes numbers (the "inverse" and "supplementary" codes).

The method of the "direct" subtraction is based on the following property of the "binary" numbers:

2n+k - 2n = 2n+k-1 + 2n+k-2 + ... + 2n.(1)

Then we can design the following subtraction table for the classical "binary" number system:

Table 1.
0-0=0
1-1=0
1-0=1
1 0-1=1
1 0 0-1=1 1
1 0 0 0-1=1 1 1

Let's write down the following identity for Fibonacci numbers:

Fn+k - Fn = Fn+k-2 + Fn+k-3 + ... + Fn-1.(2)

We can see that the identity (2) is similar to (1). Then using identity (2) we can design the following Fibonacci subtraction table:

Table 2.
0-0=   0
1-1=   0
1-0=   0 1 1
1 0-1=   0 1
1 0 0-1=   1 1
1 0 0 0-1=1 1 1
    The "direct" Fibonacci subtraction of the multi-digit Fibonacci code combinations A and B is based on the following rules:
  1. The numbers are reduced to the minimal form before the subtraction.
  2. The code combinations reduced to the minimal form are compared by their value and then in accordance with Table 2 the number lesser by its absolute value is subtracted from the bigger one.

It was proved that one may be introduced the notions of the Fibonacci "inverse" and "supplementary" codes; then by usage of these notions the procedure of the Fibonacci subtraction proves to be similar to the "binary" subtraction. And we refer our readers to Stakhov's books "Introduction into Algorithmic Measurement Theory" and "Codes of the Golden Proportion".

Stakhov's book 'Introduction into Algorithmic Measurement Theory' (1977)Stakhov's book 'Codes of the Golden Proportion' (1984)