## Posts Tagged ‘**Maths**’

## Evaluation of Powers

This is a very interesting problem with a lots of history. Anyways we will not wonder into it. We shall see how fast can we calculate *x*^{n}, given x and n where n is a positive integer. The brute force method would be to run a loop from 2 to n and calculate in n-1 steps. We will discuss three methods to do it quickly.

**Binary Method**

This the most common method used in programs today. It is also called the Dynamic Programming method. Here is an C++ implementation :

int binary(int x,int n) { if (n==1) return x; if (n%2==0) { int t=binary(x,n/2); return t*t; } else return x*binary(x,n-1); }

But does this method give the minimum number of multiplications. The answer is **NO**.

The smallest counterexample is n=15. The binary method takes six multiplications but the best method can do it in five multiplications. We can calculate y = *x*^{3} in two multiplications and *x*^{15} = *y*^{5} in three more, needing only five multiplications in total.

**Factor Method**

Let n=pq where p is smallest prime factor of n. We can calculate n by first calculating p and then raising this quantity to q-th power. If n is prime we calculate *x*^{n-1} and multiply by x. For example to calculate *x*^{55}, we first calculate y = *x*^{5} = *x*^{4}x = *( x^{2})*

^{2}x; then we form

*y*

^{11}=

*y*

^{10}y =

*(*

*y*^{2})^{5}y. The whole process takes eight multiplications.

But does this method give the minimum number of multiplications. The answer is

**NO**.

The smallest counterexample is n=33. The factor method takes seven multiplications but the best method(binary method) can do it in six multiplications.

**The “Power Tree Method”**

Lets first see the power tree.

Figure above shows the first few levels of the “power tree.” The (k + 1)-st level of this tree is defined as follows, assuming that the first k levels have been constructed: Take each node n of the lath level, from left to right in turn, and attach below it the nodes

n + 1, n + *a*_{1}, n + *a*_{2}, . . . , n + *a*_{k-1} = 2n

(in this order), where 1, *a*_{1}, *a*_{2}, . . . , *a*_{2} is the path from the root of the tree to n;but discard any node that duplicates a number that has already appeared in the tree. The C++ implementation of the above can be :

/** LINKU[j], LINKR[j] for 0 <= j <= 2^r; point upwards and to the right, respectively, if j is a number in the tree **/ int LINKU[2050]={0},k=0,LINKR[2050]={0},q,s,nm,m,i,n; LINKR[0]=1; LINKR[1]=0; //11 being number of level while (k < 11) { n=LINKR[0];m=0; do { q=0,s=n; do { if (LINKU[n+s]==0) { if (q==0) nm=n+s; LINKR[n+s]=q; LINKU[n+s]=n; q=n+s; } s=LINKU[s]; }while (s!=0); if (q!=0) { LINKR[m]=q; m=nm; } n=LINKR[n]; }while (n!=0); LINKR[m]=0; k=k+1; }

But does this method give the minimum number of multiplications. The answer is **NO**.

The smallest counterexample is n=77.Other examples are 154 and 233.

**Some Analysis**

- The first case for which the power tree is superior to both the binary method and the factor method is 23.
- The first case for which the factor method beats the power tree method is 19879 = 103*193. Such cases are rare, only 6 for n<
*10*.^{5} - Power tree never gives more multiplications for the computation of
*x*^{n}than the binary method.

If You are not interested in Maths stop reading here.

Let l(n) denote the minimum number of multiplications for a given number n.

λ(n) = floor(lg n), where floor(x) is the largest integer not greater than x.

v(n) = number of 1s in the binary representation of n.

They follow the following recurrence relations :

λ(1)=0, λ(2n) = λ(2n+1) = λ(n) + 1;

v(1)=1, v(2n)=v(n), v(2n+1) = v(n)+1.

The binary method requires λ(n) + v(n) – 1 steps.

So we have following theorems

- l(n)<= λ(n) + v(n) -1.
- l(n)>= ceiling(lg n), where ceiling(x) is the smallest integer not less than x.
- l(
*2*^{A}) = A. - l(
*2*^{A}+*2*^{B}) = A+1 if A>B. - l(
*2*^{A}+*2*^{B}+*2*^{C}) = A+2 if A>B>C.

**Conjecture**

- l(2n) = l(n) +1; It fails since l(191) = l(382) = 11.
- The smallest four values for which l(2n) = l(n) are n = 191,701,743,1111.

**Conclusion**

The table of l(n) may be prepared for 2<=n<=1000 by using the formula l(n) = min(l(n-1)+1 , *l*_{n}) – *δ*_{n},

where *l*_{n} = ∞ if n is prime, otherwise *l*_{n} = l(p)+l(n/p) if p is the smallest prime dividing n; and *δ*_{n} = 1 for n in Table below and 0 otherwise.

23 | 163 | 229 | 319 | 371 | 413 | 453 | 553 | 599 | 645 | 707 | 741 | 813 | 849 | 903 |

43 | 165 | 233 | 323 | 373 | 419 | 455 | 557 | 611 | 659 | 709 | 749 | 825 | 863 | 905 |

59 | 179 | 281 | 347 | 377 | 421 | 457 | 561 | 619 | 667 | 711 | 759 | 835 | 869 | 923 |

77 | 203 | 283 | 349 | 381 | 423 | 479 | 569 | 623 | 669 | 713 | 779 | 837 | 887 | 941 |

83 | 211 | 293 | 355 | 382 | 429 | 503 | 571 | 631 | 677 | 715 | 787 | 839 | 893 | 947 |

107 | 213 | 311 | 359 | 395 | 437 | 509 | 573 | 637 | 683 | 717 | 803 | 841 | 899 | 955 |

149 | 227 | 317 | 367 | 403 | 451 | 551 | 581 | 643 | 691 | 739 | 809 | 845 | 901 | 983 |

Phew!!! That was long.

-fR0D

(notes from TAOCP written by Donald E Knuth)

Links :

http://www.research.att.com/~njas/sequences/a003313.txt

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

## Farey Sequence/Series

**Farey Sequence** of order **N** is the ascending sequnce of all reduced fractions between **0** and **1** that have denominators **<=N. **For example, the Farey Series of order 4 is

^{0}⁄_{1}, ^{1}⁄_{4}, ^{1}⁄_{3}, ^{1}⁄_{2}, ^{2}⁄_{3}, ^{3}⁄_{4}, ^{1}⁄_{1}

This series can be generated using the following recurrence relation

*x*_{0}=0 *y*_{0}=1

*x*_{1}=1 *y*_{1}=N

*x*_{k+2}= floor((*y*_{k}+N)/*y*_{k+1})*x*_{k+1}– *x*_{k}

*y*_{k+2}= floor((*y*_{k}+N)/*y*_{k+1})*y*_{k+1}– *y*_{k}

The C++ Implementation would look something like this :

x1=0,y1=1,x2=1,y2=N; x=1;y=N; printf("%.0lf/%.0lf, %.0lf/%.0lf",x1,y1,x2,y2); while (y!=1.0) { x=floor((y1+N)/(y2))*x2-x1; y=floor((y1+N)/(y2))*y2-y1; printf(", %.0lf/%.0lf",x,y); x1=x2,x2=x,y1=y2,y2=y; } printf("\n");

Note that the number of terms in the Farey Series is given by :

where phi(m) is the Euler Toteint Function.

Did You Know?

77 x 999 = 777 x 99 and

112 x 112 = 12544 and its back order

211 x 211 = 44521

NJOY!!!

-fR0D

## Sum of First n m-th Powers

This is going to be long even without the proof.

The sum of the first n m-th powers is given by the formula :

where S2 is Stirling numbers of the Second Kind :

m\k| 1 2 3 4 5 6

——————————-

1 | 1

2 | 1 1

3 | 1 3 1

4 | 1 7 6 1

5 | 1 15 25 10 1

5 | 1 31 90 65 15 1

given by the recurrence relation :

for m >= 1,

S2(m,0) = 0,

S2(m,1) = 1,

S2(m,k) = 0 for all all k > m,

**S2(m+1,k) = S2(m,k-1) + k*S2(m,k).**

and **f(x,k) = x*(x-1)*(x-2)*…*(x-k+1).**

Let us take two examples :

T(2,n) = S2(2,1)*f(n+1,2)/2 + S2(2,2)*f(n+1,3)/3,

= 1*(n+1)*n/2 + 1*(n+1)*n*(n-1)/3,

= n*(n+1)*(1/2 + [n-1]/3),

= n*(n+1)*(1/2 + n/3 – 1/3),

= n*(n+1)*(2*n+1)/6.

and

T(4,n) = S2(4,1)*f(n+1,2)/2 + S2(4,2)*f(n+1,3)/3 +

S2(4,3)*f(n+1,4)/4 + S2(4,4)*f(n+1,5)/5,

= 1*(n+1)*n/2 + 7*(n+1)*n*(n-1)/3 +

6*(n+1)*n*(n-1)*(n-2)/4 +

1*(n+1)*n*(n-1)*(n-2)*(n-3)/5,

= n*(n+1)*(1/2 + 7*[n-1]/3 + 3*[n-1]*[n-2]/2 +

[n-1]*[n-2]*[n-3]/5),

= n*(n+1)*(1/2 + 7*[n-1]/3 + 3*[n^2-3*n+2]/2 +

[n^3-6*n^2+11*n-6]/5),

= n*(n+1)*(1/2 + 7*n/3 – 7/3 + 3*n^2/2 – 9*n/2 + 3 +

n^3/5 – 6*n^2/5 + 11*n/5 – 6/5),

= n*(n+1)*(n^3/5 + 3*n^2/10 + n/30 – 1/30),

= n*(n+1)*(6*n^3+9*n^2+n-1)/30,

= n*(n+1)*(2*n+1)*(3*n^2+3*n-1)/30.

Try higher powers for yourself.

-fR0D

## Fibonacci Numbers

Fibonacci Numbers are one of the most common sequence in maths and computer science. One of the question is how fast can you calculate Fib(N). The obvious time complexity to calculate this would be O(N) but thanks to late Prof. Edsgar W Dijkstra there exists an O(log N) solution. He gave this two equations :

F(2n-1) = F(n-1)^2 + F(n)^2 F(2n) = ( 2 F(n-1) + F(n) ) F(n)

I have written a program which implements it in time O(log N) but for simplicity reasons the space complexity is O(N). Also the program is capable of calculating the answers only till index 92 which is within the **long long** range. It sure can be implemented for big integers library.

#include

using namespace std;

long long F[93];

long long Fib(int N)

{

if (N==1)

return 1;

if (N==0)

return 0;

else

{

if (F[(N+1)/2-1]==0)

F[(N+1)/2-1]=Fib((N+1)/2-1);

if (F[(N+1)/2]==0)

F[(N+1)/2]=Fib((N+1)/2);

if (N%2==0)

return

((2*F[(N+1)/2-1]+F[(N+1)/2])*F[(N+1)/2]);

else

return

((F[(N+1)/2-1]*F[(N+1)/2-1]+

F[(N+1)/2]*F[(N+1)/2]));

}

}

int main()

{

int N;

while (scanf(“%d”,&N),N>=0&&N<93)
{
printf("%lld\n",Fib(N));
}
}[/sourcecode]
-fR0D