# COME ON CODE ON

A blog about programming and more programming.

## 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 xn, 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 = x3 in two multiplications and x15 = y5 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 xn-1 and multiply by x. For example to calculate x55, we first calculate y = x5 = x4x = (x2)2x; then we form y11 = y10y = (y2)5y. 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.

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 + a1, n + a2, . . . , n + ak-1 = 2n
(in this order), where 1, a1, a2, . . . , a2 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
**/
//11 being number of level
while (k < 11)
{
do
{
q=0,s=n;
do
{
{
if (q==0)
nm=n+s;
q=n+s;
}
}while (s!=0);
if (q!=0)
{
m=nm;
}
}while (n!=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<105.
• Power tree never gives more multiplications for the computation of xn 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(2A) = A.
• l(2A + 2B) = A+1 if A>B.
• l(2A + 2B + 2C) = 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 , ln) – δn,
where ln = ∞ if n is prime, otherwise ln = 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)

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

Written by fR0DDY

March 2, 2009 at 3:54 PM

Posted in Maths, Programming

Tagged with , , , , , ,