% 2002-3-21
\input amstex
\documentstyle{amsppt}
\define\centreline#1{\centerline{#1}}  % de=Americanization
\define\ruler{\par\medskip\centreline{\underbar{\qquad\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}}\par\bigskip}
\define\point{\raise0.7ex\hbox{.}}
\define\etc{{\it et\ cetera\/}}   
\define\today{\number\year--\number\month--\number\day}
\TagsOnRight
\refstyle{C}
\topmatter
\title Russian Peasant Multiplication \\ and Egyptian Division \\
in Zeckendorf Arithmetic \endtitle
\rightheadtext{Russian Peasant Multiplication and Egyptian Division}
\author Garry J. Tee \endauthor
\affil Department of Mathematics, University of Auckland \\
University of Auckland, New Zealand \endaffil
\address Department of Mathematics, University of Auckland, \newline
\qquad Private Bag 92019, Auckland, New Zealand \endaddress
\email  tee{\@}math.auckland.ac.nz \endemail
\subjclass 11B39, 03H15  \endsubjclass
\endtopmatter
\document
\head 1 \quad Introduction \endhead
       Edouard Zeckendorf (1901--1983) was a Belgian amateur mathematician
(\cite{10}, p.144). He invented \cite{13} the representation of natural numbers
as sums of distinct and non--consecutive Fibonacci numbers, and he shewed that
each natural number has unique representation if $ F_2 $ is used to represent 1,
rather than $ F_1 $ (which also equals 1). Each natural number can be represented
as a Zeckendorf numeral which can be encoded as a stream of bits with index
starting at 2, e.g. $ 27 = F_3 + F_5 + F_8 $ can be encoded (with index
increasing to the right) as 0101001\  . In data transmission the most significant
1 can be followed by 1 (since 11 never occurs within a Zeckendorf numeral) to
indicate the end of a number, so that 27 would get transmitted as the
self-limiting bit-string 01010011\ . This variable--length representation of
natural numbers has been investigated as a potential method for compression of
data in transmission  \cite{1}\cite{6}.\par
          In Zeckendorf arithmetic, addition by 1 is more complicated than in binary arithmetic,
as was explained by Graham, Knuth \& Patashnik (\cite{8}, pp. 282--283). Addition,
subtraction and multiplication were discussed by Freitag \& Phillips \cite{7}; and Peter
Fenwick has recently given the first treatment of all 4 basic arithmetic operations in
Zeckendorf arithmetic \cite{5}, which he has tested with computer programs. Fenwick
comments that ``this arithmetic is unlikely to remain more than a curiosity'' \cite{5},
since it is much more complex than standard binary arithmetic and the Zeckendorf numerals
are bulkier than standard binary numerals. \par
   Another set of algorithms for Zeckendorf arithmetic has been implemented by the author, as
a set of procedures in Lightspeed Pascal. These Pascal procedures, with a set of programs
for testing them, are available from the author by e-mail request sent to 
tee{\@}math.auckland.ac.nz \ . \par
\head 2 \quad Ordering Zeckendorf Numerals \endhead
    To test $ x=y $, just check whether all corresponding Zeckendorf coefficients in $ x $ and
$ y $ are equal. To test $ x>0 $, just check whether the bit--stream contains any 1.\par
		     To add 1 to a Zeckendorf numeral (\cite{8}, pp. 282--283), if its
bit--stream starts with 0 then convert that to 1 (with $ F_2=1$); but if it starts
with 10 then convert that to 01 (with $F_3=2 $). If the 1 which has been inserted
is followed by 10, then that 110 must be standardized to 001 (by the 3--term
recurrence relation for Fibonacci numbers); and that standardization must be
repeated if necessary, i.e. any bit--sequence $ 11010\dots10100 $ (starting at
any positive index) must be converted to $ 00000\dots00010 $\ . The
representation of any standard Zeckendorf numeral is unique. Thus, adding 1 to a
$ k $--digit Zeckendorf numeral can require O($ k $) elementary operations (of
counting and Boolean operations). That is similar to adding 1 in $ k
$--bit binary arithmetic, where the carry can propagate through up to $ k-1 $ consecutive unit bits.
\par
	     If a Zeckendorf numeral $ \mu $ has its most significant 1 at index $ i $ then that is
unchanged by adding 1, unless $ \mu+1 = F_{i+1} $, in which case the index increases by 1. Every
natural number $ \lambda>\mu $ can be produced from $ \mu $ by repeated additions by 1, in each
of which the highest index either remains constant or else increases by 1. Hence, the highest index
for $ \lambda $ is greater than or equal to the highest index for $ \mu $. Therefore $ \mu <\lambda $
if and only if, in their Zeckendorf representations with coefficients 0 or 1,
$$   \lambda \ = \ \sum_{i\ge 2} Y_iF_i, \qquad \mu \ = \ \sum_{i\ge 2} Z_iF_i,  \tag1$$
 $ Y_i = Z_i $ for all $ i>h$ for some $ h \ge 2 $, but $Y_h=1 $ and $ Z_h=0 $. Thus,
a simple program can be written for a {\bf Boolean function} less (x,y) which yields {\bf true}
if $ x<y $ but otherwise yields {\bf false}, doing a single downward scan through the bit--streams of
Zeckendorf coefficients for $ x $ and  $ y $.  From that function, other simple functions can be
written to test $ x>y,\ x\ge y $ and  $ x\le y$: \par
\qquad\qquad  greater:= less(y,x), \qquad ge:= {\bf not} less(x,y), \qquad le:= ge(y,x). 
\head 3 \quad Addition and Subtraction \endhead 
\subhead 3.1 Addition   \endsubhead
       In the Pascal procedure for addition, for each digit 1 at index $ i $ in $ y $ add $ F_i $
into $ x $. When a digit 0 (at index $ i $ in $ x $) gets 1 added into it, if that new 1 is
followed by 10 then standardization must be applied from index $ i $ upwards; but otherwise, if the
new bit--stream from index $ i-1 $ is 110, then standardization must be applied from index $ i-1 $
upwards. If 1 gets added to 1 at index $ i $, then $ 2F_i $ must be replaced by $ F_{i+1} + F_{i-2}
$. To add in $ F_{i+1} - 2F_i $, the bit--stream 010 from index $ i-1 $ must be converted to
001, and if that is followed by 1 then standardization must be applied from index $ i+1 $,
costing O($ k $) elementary operations. And to add in $ F_{i-2} $, then this process must
be applied recursively, with O($ k $) stages. Thus, even increasing a single Zeckendorf
coefficient by 1 costs O($ k^2 $) elementary operations; and hence adding a pair of $ k
$--digit Zeckendorf numerals by the Pascal procedure costs O($ k^3 $) elementary operations! \par
\subhead  3.2 Subtraction  \endsubhead
			Zeckendorf subtraction by 1 is very simple. Consider $ \mu = F_a + F_b + \dots
 + F_z $, where the subscripts are in strictly increasing order. If $ a=2 $ then just 
delete $ F_2 $. With $ a>2 $ then $ \mu-1 = (F_a-1) + F_b + \dots + F_z $. From the 
3--term recurrence formula, \par
  $$ \multline  F_a \ = \ F_{a-2} + F_{a-1} \ = \ F_{a-4} + F_{a-3} + F_{a-1} \ = 
  \ F_{a-6} + F_{a-5} + F_{a-3} + F_{a-1} \\
= \ \dots\  = \ \left\{\matrix F_2 + F_3 \ \text{(for even $ a $)} \\
 F_1 + F_2\ \text{(for odd $ a $)} \endmatrix\right\}
+\dots + F_{a-7} + F_{a-5} + F_{a-3} + F_{a-1}\ ; \endmultline  \tag2$$ 
and hence \par
  $$ F_a-1 \ = \ \left\{\matrix F_3+F_5 \ \text{(for even $ a $)} \\
 F_2+F_4\ \text{(for odd $ a $)} \endmatrix\right\}
+\dots + F_{a-7} + F_{a-5} + F_{a-3} + F_{a-1} \ . \tag3$$ 
This produces $ \mu -1 $ in standard Zeckendorf form, with no consecutive Fibonacci
numbers. \par
    Consider the subtraction of Zeckendorf numerals $ x-y $, where $ x \ge
y $, with $ k $ digits in $ x $. For each digit 1 at index $ i $ in $ y $, we need to subtract $
F_i $ from $ x $.  When a digit 1 (at index $ i $ in the current  value of $ x $) gets
1 subtracted from it then that digit in $ x $ is replaced by 0\ . But if the digit at index $ i $ of
$ x $ is 0 and 1 is to be subtracted from it, then scan the bit-stream from index $ i+1 $ upwards,
to find the 1 with least index $ h>i $. As in (2),
$$ F_h \ = \ F_{h-2j} + F_{h-2j+1} + F_{h-2j+3} + \dots  + F_{h-3} + F_{h-1}.   \tag4$$ 
Hence, when $ h-i $ is even then 
$$ F_h-F_i \ = \ F_{i+1} + F_{i+3} + \dots  + F_{h-5} + F_{h-3} + F_{h-1},    \tag5$$ 
but if $ h-i $ is odd then
$$ F_h-F_i \ = \ F_{i-1} + F_{i+2} + \dots  + F_{h-5} + F_{h-3} + F_{h-1}.    \tag6$$ \par
	         Thus, in subtracting $ F_i $ from $ x $, if $ h-i $ is even then it can be done by (5) at
the cost of O($ k $) elementary operations. But if $ h-i $ is odd then it can be done by (6),
which also adds in $ F_{i-1} $, at a cost O($ k^2 $). \par
    Hence, subtracting a pair of $ k $--digit Zeckendorf numerals by the Pascal procedure costs O($
k^3 $) elementary operations. \par 
 \head  4 \quad  Russian Peasant Multiplication   \endhead
      Before the Russian Revolution in 1917, some visitors to Russia were surprised to
find that many illiterate Russian peasants were able to multiply quite large numbers
mentally. The following algorithm (in Pascal) computes $ z = xn $, where $ n $ is any non-negative
integer and $ x $ is any number.\par\smallskip
\qquad\ {\bf if} odd(n) {\bf then}  s:= x {\bf else} s:= 0; \quad n:= n
{\bf div} 2;\par
 \qquad {\bf while} n$ > $0 {\bf do} \par
 \qquad {\bf begin} x:= x+x;\quad {\bf if} odd(n) {\bf then} s:= s + x; 
\quad n:= n {\bf div} 2 \par
\qquad {\bf end};  \quad z:= sum\  .\par  \smallskip\noindent
	  This algorithm can be interpreted as generating successively the digits in the
base--2 representation of $ n $. After $ k $ executions of either
if--statement ($ k = 0,1,2,\dots$) the current value of $ x $ is $ 2^k $ times its
initial value, and the current value of $ n $ is the quotient when the initial value
has been divided by $ 2^k $. That current value of $ n $ is odd, if and only if  $
2^k $ has coefficient 1 in the binary expansion of the initial value of $ n $; and
hence the sum is to be increased by the current value of $ x $ if and only if the
{\bf Boolean} function odd(n) yields {\bf true}. The number of additions into $ s $ is 
less than or equal to the number of doublings of $ x $, which is $ \lfloor
\log_2n \rfloor $. \par
	          This Russian Peasant Multiplication algorithm is independent of any written
numerals, and it is independent of the base (if any) which might be used in the spoken
numerals. The user needs only to be able to decide whether $ n $ is odd (and whether
$ n=0 $), to halve $ n $ (discarding remainder 1 when $ n $ is odd), and to add $
x $ into a number.\par
      Less systematic versions of Russian Peasant Multiplication (without halving) were
used in Ancient Egypt for multiplication and division (\cite{4}, pp. 14--20). In Ancient
India, powers $ x^n $ were computed by an algorithm very similar to Russian Peasant
Multiplication (\cite{3}, p.76), with addition being replaced by multiplication and the
initial value 0 being replaced by 1. The RSA cryptographic algorithm requires
efficient computation of $ x^n $ {\bf mod} $ m $ for very large integers $x,\ n,\ m$. That
has been done \cite{11} by a version of the Ancient Indian method, using the
operation of multiplication ({\bf mod} $m$). More generally, the number $ x $ and
the operator + can be replaced by elements of any monoid with associative
operator $ \otimes $, with 0 being replaced by the neutral element for $ \otimes
$, to apply $ \otimes $  ($n-1$ times) to $ x
$ (\cite{9}, p.399). For example, $ x $ could be a polynomial whose coefficients are
scalars or are square matrices (integer, real, complex or quaternion), and $ \otimes $
could be the operation of multiplication of polynomials, to compute the $ n $th power of
the polynomial $ x $.\par
	            If $ x $ and $ n $ are represented in binary notation, then Russian Peasant
Multiplication is closely similar to the standard algorithm for multiplication in binary
arithmetic. In binary arithmetic the doublings of $ x $ are done by shifting all binary digits up
one place, and the binary digits of $ n $ are operated on directly. \par	    
 
 \subhead  4.1 Multiplication in Zeckendorf Arithmetic  \endsubhead \par
    The existing algorithms for Zeckendorf multiplication \cite{7} involve
intricate operations upon the Zeckendorf coefficients. But Zeckendorf numerals
can be multiplied more  simply by Russian Peasant Multiplication, using the
existing Zeckendorf algorithms (in \cite{5}, or the Pascal procedure) for
addition of $ x $. If the factor $ n $ is represented as a standard {\bf integer}
in Pascal (or in any similar programming language), then all operations on $ n $
can be done by standard {\bf integer} operations. \par
\subsubhead  4.1.1   Parity of Zeckendorf Numerals \endsubsubhead
	In order to determine whether $ n $ is odd, consider the
expansion 
$$  n \ = \ \sum_{i=1}^k Z_iF_i \qquad (Z_i = 0,1),  \tag7$$
for a suitable upper limit $ k $, where $ Z_1=0 $ in a standard Zeckendorf numeral. \par
	      Since $ F_0=0 $ which is even, and both $ F_1 $ and $ F_2 $ equal 1 which
is odd, then it follows by induction on the defining 3--term recurrence relation that $
F_i $ is even if and only if $ i=3h $ for some integer $ h $. Therefore, replacing
each coefficient $ Z_{3h} $ in (1) by 0 would not alter the parity of the
sum of Fibonacci numbers. Thus the parity of $ n $ equals the parity of $ \sum_{h \ge 0} \left(
Z_{3h+1}F_{3h+1} +Z_{3h+2}F_{3h+2} \right) $, where both $ F_{3h+1} $ and $F_{3h+2} $ are odd.
Operating {\bf mod} 2, this becomes
$$ n \ \equiv \ \sum_{h \ge 0} \left( Z_{3h+1} + Z_{3h+2} \right)\quad  \text{\bf mod} \ 2 \ . 
\tag8$$  
For each $ h $,  the term in parentheses will equal 1 if $ Z_{3h+1} \ne Z_{3h+2} $, but
otherwise that sum is even. Thus, the {\bf Boolean} value of odd(n) can be computed as
follows, with the Zeckendorf coefficients represented by a {\bf Boolean} array z. If $ n
$ is zero then odd:= {\bf false}, but for positive $ n $ apply the algorithm:
\par\smallskip
\qquad odd:= {\bf false}; \quad i:= 0; \par
\qquad {\bf repeat}\quad{\bf if} z[i+1]$ <> $z[i+2] {\bf then} odd:= {\bf not} odd;
\quad i:=i+3 \par
\qquad {\bf until} i$ >= $k . \par\noindent
Determining the parity of a $ k $--digit Zeckendorf numeral by this algorithm costs O($ k $)
elementary operations. \par
 \subsubhead 4.1.2 Halving nonstandard Zeckendorf Numerals \endsubsubhead 
										In order to halve $ n $, it is convenient to work with nonstandard
Zeckendorf numerals in which consecutive Fibonacci numbers can appear, so that the
bit--stream can be any pattern of 0 and 1; and also $ F_1 $ is accepted, so that the
index in the bit--stream starts with 1 rather than 2. The algorithm for evaluating
odd(n) works for such nonstandard Zeckendorf numerals, since if $ Z_{3h+1} = Z_{3h+2}=1
$ then $ Z_{3h+1} + Z_{3h+2}=2\ \equiv\  0 $ {\bf mod} 2. During the operation of
the algorithm for halving $ n $, the coefficients $ Z_i $ can take the values 0, 1, 2 or
3; but at the end of the algorithm the coefficients of the new $ n $ are all 0 or 1, so
that the new $ n $ can be represented by the {\bf Boolean} array z. The index for
nonstandard Zeckendorf starts at 1, since otherwise we could get $Z_2=2 $ during the
halving.\par
		       In order to halve $ n $ set $ j $ as the index of the highest 1 in $ n $,
 and construct an array c of {\bf integer} coefficients of Fibonacci numbers:  \par
\quad c[0]:= 0; \qquad {\bf for} i:= 1 {\bf to} j {\bf do if} z[i] then c[i]:= 1 
{\bf else} c[i]:= 0\  .\par\noindent
	    Transform the coefficients c[i] so that each becomes 0 or 2, except that
c[1] becomes 1 if n is odd. To do that transformation, for i from j down to 2, if 
c[i] is odd then $ F_i $ or $ 3F_i $ occurs in the sum represented by the current
array c. In that case, replace $ F_i $ (once) by  $ F_{i-1} + F_{i-2} $, so that c[i]
gets reduced to 0 or 2 and both c[i-1] and  c[i-2] get increased by 1. Construct the
coefficients for the new value of $ n $ by halving each coefficient c[i] (for i$ >
$1). Do not actually  subtract 1 from c[i] and do not perform any arithmetic division.
Rather, in terms of the {\bf Boolean}  array z: \par
   \qquad\qquad {\bf for} i:= k {\bf downto} 2 {\bf do} z[i]:= c[i]$ > $1 . \par
Halving a $ k $--digit Zeckendorf numeral by this algorithm costs O($ k $) elementary
operations. \par
	  This halving algorithm operates on nonstandard Zeckendorf numerals, and so the
cycle of halvings in Russian Peasant Multiplication can be performed in this
manner, without needing to standardize the output. \par	
      In this manner, all of the operations in Russian Peasant Multiplication on the Zeckendorf
numerals for $ x $ and $ n $ have been implemented in Pascal, in terms of addition of small integers
and {\bf Boolean} operations. \par
 \subhead 4.2 Standardizing nonstandard Zeckendorf Numerals \endsubhead 
    If the nonstandard output of the procedure for halving is to be operated on by other
procedures, then it must be converted to standard Zeckendorf form. That standardization can be
done by a Pascal procedure, which scans the bit--stream with index $ i $ decreasing to 1. Each
time that 11 is encountered at indices $ i $ and $ i+1 $ then it must be standardized from index
$ i $ upward, costing O($ k $) elementary operations, as in \S3.1. After
standardizing down to $ i=1 $, if the bit-stream starts with 10 then that must be replaced by 01
(since $ F_1 = F_2 = 1 $), and if the next bit is 1 then one more standardization must be
applied, from index 2 upwards. Thus, standardization costs O($ k^2 $) elementary
operations.\par 
 \head 5 \quad Ancient Egyptian Division \endhead     
    	For non--negative integer numerator $ n $ and positive integer denominator 
$ d $, the operation of integer division produces the unique quotient $ q $ and
remainder $ r $ such that $ n = qd+r $, with $ q \ge 0 $ and $ 0 \le r < d $. The
existing division algorithm \cite{5} requires intricate operations upon the Zeckendorf
coefficients. But it is simpler to use a systematic version of an ancient Egyptian 
method for division, as in Problem 25 of the Rhind Mathematical Papyrus (\cite{4},
p.16).\par
     Construct (once only) an array $ p $ with $ p_i = 2^i$: set i=0 and $ p_i = 1 $, and
then repeat i:=i+1;\  $ p_i $:= $ p_{i-1}+p_{i-1} $ until $ p_i $ is large enough for your
purposes. That array can then be used in any division of $ n $ by $ d $ by the following
algorithm, which constructs (by repeated addition) an array $ t $ with
$t_i=2^i d$. The quotient $ q $ (initially set at 0) effectively gets each 1 in its binary
representation inserted in decreasing place--value, from the array $ p $.\par\medskip
\qquad  r:= n ; \quad  q:=0; \quad  i:=0; \quad  t[i]:= d; \par 
\qquad {\bf while}  t[i]$ < $r {\bf do begin} i:= i+1; \quad
   t[i]:= t[i-1] + t[i-1];  \qquad \{ t[i] = $ 2^i $d  \} \par
\qquad\qquad\qquad\qquad\quad\ {\bf end}; \qquad\qquad\qquad\qquad\qquad\qquad\qquad 
\{ t[i]$ \ge $r$ > $t[i-1] \} \par
\qquad {\bf repeat \ while} r$ < $t[i] {\bf do} i:= i-1;
\qquad\qquad\qquad\quad \{Now, t[i+1]$ > $r$ \ge $t[i] \} \par
\qquad\quad q:= q+p[i]; \ r:= r-t[i]  
\qquad\qquad\quad  \{Puts q$ _i $=1, in its binary expansion \} \par 
\qquad {\bf until} r$ < $d  \ . \par\medskip\noindent
Then $ q $ is the quotient and $ r $ is the remainder. \par
      If $ n<d $ then $ q=0 $ and $ r=d $. But, for $ n\ge d $, the number of subtractions from 
$ r $ equals the number of additions into $ q $, which is less than or equal to the number of
doublings of $ d $; and that equals $ \lceil \log_2q \rceil $. \par
	         If the numbers are represented in binary notation, then the Egyptian algorithm is
closely equivalent to the standard binary arithmetic algorithm for division. In binary
arithmetic the doublings of $ t $ are done by shifting all digits up one place, and each digit 1
in $ q $ gets inserted directly, without needing any table of powers of 2. \par
 \subhead 5.1 Division in Zeckendorf Arithmetic  \endsubhead 
       In Zeckendorf arithmetic, the additions and subtractions involving $ p,\ q,\ r $ and $ t $
can be done by the existing algorithms (in \cite{5}, or the Pascal procedures), and a simple
program (3) can test for $ r<d $. In this manner, the Ancient Egyptian method for division has been
implemented in Pascal. \par
 \head 6 \quad Signed Zeckendorf Arithmetic \endhead
         For negative numbers in Zeckendorf form, Fenwick proposed a form of complementing,
generalized from binary arithmetic with 2s-complement. But that representation of negative numbers
proves to be rather cumbersome \cite{5}. \par
	         Accordingly, it is convenient to generalize the unsigned Zeckendorf numerals
by using sign and magnitude representation. Extend the bit--stream for $ z $ to
start at index 0, with z[0] = {\bf false} for $ z \ge 0 $ but {\bf true} for $
z<0 $, so that signed Zeckendorf zero has all elements {\bf false}, from index 0
up. Nonstandard Zeckendorf numerals use z[1] for $ F_1 $, but z[1] is not used in
unsigned standard Zeckendorf numerals. If $ z $ does have a sign at index 0, the
bit--stream from index 2 up gives $ |z| $ in unsigned Zeckendorf form. \par 
           To add signed Zeckendorf numerals $ a+b = c $, if $ a $ and $ b $ have the same
signs set $ c = |a| + |b| $, then give $ c $ the sign of $ a $. If $ a $ and $ b $ have different
signs; then if $ |a| \ge |b| $ set $ c = |a| - |b| $ and then give $ c $ the sign of $ a $, but
otherwise set $ c = |b| - |a| $ and then give $ c $ the sign of $ b $. To subtract signed
Zeckendorf numerals $ c = a-b $, if $ b=0 $ then $ c = a$, but otherwise reverse the sign of $ b $
and then add $ a + (-b) $. \par
       To multiply signed Zeckendorf numerals $ ab = c $, set $ c =|a| \times |b| $, and then
fix the sign by c[0]:= a[0]$ <> $b[0]. Then, if unsigned $ c=0 $, set the sign as non--negative: 
c[0]:= {\bf false}. Signed division could be handled in a similar manner. \par
 \head 7 \quad Complexity of Zeckendorf Arithmetic \endhead
  For numbers written in any integer base $ \beta>1 $, addition or subtraction of a pair of $ m
$--digit numbers costs O($ m $) elementary operations on digits $ 0,1,\dots,\beta-1 $\ , and the
standard algorithms for multiplication and for division cost O($ m^2$) elementary operations. \par
\subhead7.1  Daniel Bernoulli's formula for Fibonacci numbers \endsubhead
    Daniel Bernoulli the 1st (1700--1782) published in 1732 an important paper in which
(amongst much else) he published (\cite{2}, p.52) the explicit formula for  $ F_x $, as: 
$$     \left[ \left( \frac{1+\sqrt{5}}{2} \right)^x \ - \  \left(
\frac{1-\sqrt{5}}{2} \right)^x \right]:\sqrt{5}\  . \tag9$$
Daniel Bernoulli's formula for the Fibonacci numbers has often been mis--named (e.g. \cite{7}
and \cite{8}, p.285) after Binet, who published it 111 years after Daniel Bernoulli did
\cite{12}. \par
						In terms of the golden ratio $ \gamma = (1+\sqrt{5})/2 \ = \  1{\point}6180340 $, Daniel
Bernoulli's formula can be rewritten as
$$  F_i \ = \ \left(\gamma^i - (1-\gamma)^i\right)/\sqrt{5}. \tag10$$ \par
\subsubhead 7.1.1 Golden Numbers \endsubsubhead
        Denote the Zeckendorf numeral for $ z $ as
$$ z \ = \ \sum_{i=2}^m Z_i F_i \ . \tag11$$
Then
$$ z \ = \  \frac{1}{\sqrt{5}}\sum_{i=2}^m Z_i \left( \gamma^i - (1-\gamma)^i
\right)
  \ = \  \frac{1}{\sqrt{5}}\sum_{i=2}^m Z_i \gamma^i 
\ - \ \frac{1}{\sqrt{5}}\sum_{i=2}^m Z_i (1-\gamma)^i
 \ = \  \frac{\Gamma(z)}{\sqrt{5}} - \rho(z). \tag12$$ 
Here, $ \Gamma(z) $ is the base--$ \gamma $
number whose coefficients equal the corresponding Zeckendorf coefficients of $ z $, and
$$ \rho(z) \ = \ \frac{1}{\sqrt{5}}\sum_{i=2}^m Z_i (1-\gamma)^i . \tag13$$
The real number $ \Gamma(z)/\sqrt{5} $ could be called the {\it Golden Number} for the positive
integer $ z $. \par
	    For all $ m $--digit Zeckendorf numerals, the maximum modulus of $ \rho(z) $ is 
given by $ z = F_{m+1}-1 $, whose Zeckendorf coefficients are given by (3). 
If $ m $ is even then
$$ \multline \rho\left(F_{m+1}-1 \right) \ = \ \left[ (1-\gamma)^2 +
(1-\gamma)^4 +\dots + (1-\gamma)^m \right]/\sqrt{5} \\
 < \ \frac{(1-\gamma)^2}{\sqrt{5}\left(1 -(1-\gamma)^2\right)}
\ = \ \frac{1-2\gamma+\gamma^2}{\sqrt{5}(2\gamma-\gamma^2)} \ .\endmultline \tag14$$
Since $ \gamma^2 = \gamma + 1 $, this inequality reduces to
$$\multline \rho(z) \ < \ \frac{2-\gamma}{\sqrt{5}(\gamma-1)} 
\ = \ \frac{2\gamma-\gamma^2}{\sqrt{5}(\gamma^2-\gamma)} 
\ = \ \frac{\gamma-1}{\sqrt{5}}  \\  
= \ \frac{\sqrt{5}(\sqrt{5}-1)}{10}  \ = \ \frac{5-\sqrt{5}}{10} \ < \ 0{\point}3 \ .
\endmultline \tag15$$
Similarly, if $ m $ is odd then
$$ \rho\left(F_{m+1}-1 \right) \ = \ \left[
(1-\gamma)^3 + (1-\gamma)^5 +\dots + (1-\gamma)^m \right]/\sqrt{5},         \tag16$$
so that
$$ -\rho(z) \ < \  \frac{(\gamma-1)(1-\gamma)^2}{\sqrt{5}\left(1 -(1-\gamma)^2\right)}
\ = \ \frac{(\gamma-1)\left(5-\sqrt{5}\right)}{10} \ < \ 0{\point}2 \ . \tag17$$   \par
       Hence, every natural number $ z $ equals the Golden Number $ \Gamma(z)/\sqrt{5} $, rounded
to the nearest integer. \par
\subhead 7.2   Comparison of Zeckendorf Arithmetic with binary arithmetic \endsubhead
	   For numbers written in any integer base $ \beta>1 $, the largest $ m $--digit 
number is $ \beta^m -1 $. For numbers written in some other base $ \delta,\ \delta^p =
\beta^m $, where $ p = m(\log\,\beta/\log\,\delta) $. Hence, conversion of an $ m $--digit integer
in base $ \beta $ to base $ \delta $ requires O($ m $) digits in base $ \delta $. Hence, the
Zeckendorf representation of an $ m $--digit number in base $ \beta $ requires approximately
$ m(\log\,\beta/\log\,\gamma) $ digits in Zeckendorf representation. For example, an $ m $--bit
binary number requires approximately  $ \lceil 1{\point}46m \rceil + 2 $ digits in Zeckendorf
representation. \par
	         Conversion of a $ k $--digit Zeckendorf numeral to standard binary form (or
conversely) costs O($ k $) additions or subtractions of binary numbers with O($ k $) bits, or
O($ k^2 $) elementary operations. Hence, if a pair of Zeckendorf numerals were converted to
binary form, then addition or subtraction performed in binary arithmetic would cost O($ k $)
elementary operations, and multiplication or division would cost O($ k^2 $). If the result of the
binary arithmetic were converted to Zeckendorf form, then the cost for each basic arithmetic
operation on Zeckendorf numerals (via binary arithmetic) would be O($ k^2 $) elementary operations.
But the Pascal procedures for addition and subtraction each cost O($ k^3 $) elementary operations.
In Russian Peasant Multiplication the number of additions is O($ k $), and in Egyptian division the
number of additions or subtractions is O($ k $); and hence multiplication or division of $ k
$--digit Zeckendorf numerals costs O($ k^4 $) elementary operations. \par 
  However, arithmetic operations on large binary integers (beyond the domain of arithmetic 
hardware) usually are done by software, which multiplies by a large factor the time required for
elementary operations on the digits. Consequently, the actual ratio of cost of Zeckendorf
addition or subtraction to cost of binary operations might be much smaller than this simple counting
of elementary operations on digits might suggest. \par  
         If algorithms for addition or subtraction of Zeckendorf numerals could be devised
with cost of lower order (e.g. O($ k\,\log\,k $) elementary operations) then there would be
no need to consider conversion to and from binary numerals for doing arithmetic on Zeckendorf
numerals.  \par
\ruler
     I wish to thank  Peter Fenwick, for introducing me to the concept of Zeckendorf
arithmetic. \par

\Refs
\ref \key 1 \by  A. Apostolico A. \& A. S. Fraenkel \paper Robust transmission of
unbounded strings using Fibonacci representations \jour IEEE Trans. on
Inf. Th. \vol IT--33 \yr 1987) \pages 238-245 \finalinfo (cited from [5]) \endref 
\ref \key 2 \by Daniel Bernoulli \paper Observationes de seriebus quae
formantur ex additione vel subtraction quacunque terminorum se mutuo consequentium, ubi
praesertim earundem insignis usus pro inveniendis radicum omnium aequationum
algebraicarum ostenditur \jour Commentarii Academiae Scientiarum Imperialis
Petropolitanae \rm t.3 \yr 1732 for 1728 \pages 85--100  \finalinfo Reprinted in: 
{\sl Die Werke von Daniel Bernoulli} Band 2 (edited by David Spieser), 
Birkh{\"a}user Verlag, Basel--Boston--Stuttgart (1982), pp. 49--64 \endref
\ref \key 3 \by Bibhutibhusan Datta \& A. N. Singh \book History of Hindu Mathematics
\vol 1 \publ Motilal Banarsidass \publaddr Lahore \yr 1935 \endref
\ref \key 4 \by John Fauvel \& Jeremy Gray \book The History of Mathematics - a Reader
\publ Macmillan Press \publaddr London \yr 1987 \endref
\ref\key 5 \by Peter Fenwick \paper Zeckendorf integer arithmetic \jour The
Fibonacci Quarterly \toappear \endref
\ref \key 6 \by A. S. Fraenkel \& S. T. Klein \paper Robust universal complete codes for
transmission and compression \jour Discrete Applied Mathematics \vol 64 \yr 1996
\pages 31--55 \finalinfo (cited from [5])\endref
\ref \key 7 \by  H. T. Freitag \& G. M. Phillips \paper On the Zeckendorf form of $
F_{kn}/F_n$ \jour The Fibonacci Quarterly \vol 34, \rm No.5 \yr 1996 \pages 444--446
\endref   
\ref \key 8 \by Ronald L. Graham, Donald E. Knuth \& Oren Patashnik \book Concrete
Mathematics \publ Addison--Wesley \publaddr Reading MA \yr 1989 \endref
\ref \key 9 \by Donald E. Knuth \book The Art of Computer Programming  \vol 2
\publ Addison--Wesley Publishing \publaddr Reading \yr 1969 \endref
\ref \key 10 \by George M. Phillips \book Two Millenia of Mathematics, from
Archimedes to Gauss \publ Springer--Verlag \publaddr New York \yr 2000 \endref
\ref \key 11 \by Garry J. Tee \paper The perfect cryptographic method? \finalinfo
in: {\sl Directions For the Future: Communication. Papers given during the 49th
ANZAAS Congress, University of Auckland January 1979} (ed. by Mari Davis), Trans
Knowledge Associates, Melbourne, 1979, pp. 24--28 \endref
\ref \key 12 \by Garry J. Tee \paper Integer sums of recurring series \jour New
Zealand Journal of Mathematics \vol 22 \yr 1993 \pages 85--100 \endref
\ref \key 13 \by E. Zeckendorf \paper  Repres{\'{e}}ntation des nombres
naturels par une somme de nombres de Fibonacci ou les nombres de Lucas \jour Bull. Soc.
Roy. Sci. Li{\`{e}}ge \vol 41 \yr 1972 \pages 179--182 \endref
\endRefs
\par
\medskip\hfill\today
\enddocument

