# MATH 3600 - HW18

## Your name: _____________________________

Date: ________________

## The Powers that Be.

We want to find a fast way to calculate $x^n$, and we can do this by exploiting the binary representation of $n$. First recall the following information about hardware integers and their binary representation. A hardware integer (type int) consists of 64 bits. The first bit is the sign bit and the remaining bits define the value of the integer.  The easiest way to describe the integer is with hexadecimal notation, where each hexadecimal digit (0, 1, . . . , F) specifies the precise pattern for 4 bits.

 decimal binary hex 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F

Now consider, for example, the calculation of $x^{13}$.

In binary, $13=1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0$.  Consequently we can write

$x^{13} = x^{1\cdot 2^3 +1\cdot 2^2 +0\cdot 2^1+1\cdot 2^0} = (x^8)^1 \cdot (x^4)^{1} \cdot (x^2)^{0} \cdot x^{1}\cdot x^{0}$

$x^{13} = ((x^4)^2)^1 \cdot ((x^2)^2)^1 \cdot (x^2)^0 \cdot x^{1}\cdot 1$

For a slightly different example, consider the calculation of $x^{10}$.

In binary, $10=1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+0\cdot 2^0$.  Consequently we can write

$x^{10} = x^{1\cdot 2^3 +0\cdot 2^2 +1\cdot 2^1+0\cdot 2^0} = (x^8)^1 \cdot (x^4)^{0} \cdot (x^2)^{1} \cdot (x^1)^{0}\cdot x^{0}$

$x^{10} = ((x^4)^2)^1 \cdot ((x^2)^2)^0 \cdot (x^2)^1 \cdot x^{0}\cdot 1$

Hopefully the underlying pattern for the algorithm is beginning to shine through. We start with two terms $y=1$ and $x_s=x$.  Then we examine the rightmost bit, $b$, of the exponent. Then we calculate
$y = x_s^b*y$   and  $x_s = x_s^2$

Of course $b$ can only be 0 or 1, so the first equation can be implemented by saying, "if $b$ is 1, then multiply $y$ by $x_s$, and if not, don't change $y$".  In either case, always update $x_s$ to get the base for the next binary digit.

The following function, pow(x,n) uses this algorithm to calculate $x^n$.

def pow(x,n): y = 1 xs = x while 0 < n: if n%2==1: y *= xs xs *= xs n = n//2 return y
pow(2,0);pow(2,1);pow(2,3);pow(2,13);pow(3,2);pow(2,100);pow(3,10)

The number of multiplications is bounded by $2 \left\lfloor {1+ \log _2 (n)} \right\rfloor$.  The following version of the code counts the number of multiples and compares them with this formula.

def pow2(x,n): y = 1 xs = x count = 0 while 0 < n: if n%2==1: y *= xs count += 1 xs *= xs count += 1 n = n//2 return (y,count)
for n in range(32): y,count = pow2(2,n) if n==0: print n,'\t',y,'\t\t',count elif n<20: print n,'\t',y,'\t\t',count,'\t', 2*floor(1+log(n,2)) else: print n,'\t',y,'\t',count,'\t', 2*floor(1+log(n,2)) print pow2(2,1000), 2*floor(1+log(1000,2))

If the numbers don't get too large, then we could calculate $x$ raised to the google power with only 666 multiplications. Of course making sure the numbers don't get too large may be a serious problem. That is one message that came through loud and clear with the Lehmer iteration in Project 2.

# The worst case number of multiplies to calculate x^google google = 10^100 2*floor(1+log(google,2))

## Given integers $x$ and $q$, we usually define $x$ mod $q$ as the remainder of $x$ divided by $q$.  Another approach would be to think of representing $x$ base $q$, then $x$ mod $q$ is simply the rightmost "digit" in this representation.  This should make it intuitively clear that if $x$ and $y$ are integers, then $x+y$ mod $q$ and ($x$ mod $q$ + $y$ mod $q$) mod $q$ are the same.  Similarly,  $x \cdot y$ mod $q$ and (($x$ mod $q$)$\cdot$($y$ mod $q$)) mod $q$ are the same.

Exercise 1:  Complete the following pow3 function so that it modifies the original pow function by performing each multiplication mod $q$.  Then evaluate the subsequent block.

def pow3(x,n,q): # # # # # # # return y
for n in range(32): q = 1000 y = pow3(2,n,q) print n,'\t',y print pow3(2,1000,q)

Exercise 2:  Do these answers correctly represent the last 3 digits of $x^n$ in all 33 cases?  What about the cases $n = 10, 11, 12, 17$?

Rerun the previous block with $q=100,000$.  Is the answer for $n=26$ correct?

Exercise 3:  Calculate the last 50 digits of 2^google.

## Fibonacci Numbers

The recurrence relation for the sequence of Fibonacci numbers is

$f_n = f_{n-1} + f_{n-2}$   with   $f_0 = 1$  and  $f_1=1$.

Exercise 4:  Write a forward recurrence that generates and prints out the first 25 Fibonacci Numbers.  For each Fibonacci number print the number, then a tab, then the number of digits, where

digits =  floor(1+log(fn,10))

# # # # # # # # #

Exercise 5:  Once you are sure that you are correctly calculating the Fibonacci numbers and the number of digits, generate a plot of the number of digits of the first 100 Fibonacci numbers.

# # # # # # # # # #

Exercise 6:  Based on the previous results, estimate the number of digits in the $n$-th Fibonacci number when $n=10^{100}$.  The estimated total number of atoms in the Universe is $10^{80}$.  Would it be possible to print this Fibonacci number or even to store it in a computer?

A Matrix Approach.  The Fibonacci recurrence can be written as a matrix recurrence as follows.  Let ${\bf{F}}$ be a vector in ${\bf{Z}}^2$, and let

${\bf{E}} = \left[ {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \end{array}} \right]$

Then

\left[ {\begin{array}{*{20}c}
{f_2 }  \\
{f_1 }  \\
\end{array}} \right] = {\bf{E}}\,{\bf{F}} \\
\left[ {\begin{array}{*{20}c}
{f_3 }  \\
{f_2 }  \\
\end{array}} \right] = {\bf{E}}\,{\bf{E}}\,{\bf{F}} \\
\left[ {\begin{array}{*{20}c}
{f_{n + 1} }  \\
{f_n }  \\
\end{array}} \right] = {\bf{E}}^n \,{\bf{F}} \\
\end{array}
\

${\bf{F}} = \left[ {\begin{array}{*{20}c} {f_1 } \\ {f_0 } \end{array}} \right]$,    $\left[ {\begin{array}{*{20}c}{f_2 } \\{f_1 }\end{array}} \right] = {\bf{E}}\,{\bf{F}}$

$\left[ {\begin{array}{*{20}c}{f_3 } \\ {f_2 } \end{array}} \right] = {\bf{E}}\,{\bf{E}}\,{\bf{F}}$,    $\left[ {\begin{array}{*{20}c} {f_{n + 1} } \\{f_n } \end{array}} \right] = {\bf{E}}^n \,{\bf{F}}$

Since matrix multiplication is associative, we can use the powering algorithm to calculate ${\bf{E}}^n {\bf{F}}$ for $n = 10^{100}$.  Of course, the previous observations mean that we need to use modular arithmetic to restrict the answer to a relatively few trailing digits.

Exercise 7:   Complete the definition of the Epow(n,q) function which calculates E to the $n$ mod $q$.  Then evaluate the subsequent block.

def Epow(n,q): Y = Matrix([[1,0],[0,1]]) E = Matrix([[1,1],[1,0]]) # # # # # # # # # # # # # return Y
q = 10^5 print Epow(0,q) print Epow(1,q) print Epow(2,q) F = Matrix([[1],[1]]) En = Epow(5,q) print En*F En = Epow(23,q) print En*F

Exercise 8:  Calculate the last 100 digits of the $n$-th Fibonacci number where $n=10^{100}$. You may want to provide some supporting results.  However, whatever you print out, be sure to highlight or clearly indicate the 100 digits that you have decided represent the last 100 digits of the google-th Fibonacci number.

google = 10^100