The tutor follows up his earlier post about an algorithm for exponentiation.

In my Aug 28 post I brought up exponentiation and a straightforward algorithm that uses a loop. However, there is a less straightforward, yet more efficient, algorithm for it:

#!/usr/bin/perl
$orbase=ARGV[0];#reads original base as a param. from function call

$orexp=ARGV[1];#the original exponent

$exp=$orexp;

$base=$orbase;#this program changes the exponent and base

$res=1;#this variable will become the result
while($exp>0){
if($exp%2==1){#checks if the exponent is odd

$res*=$base;

}
$exp=int($exp/2);#for example: int(11/2)=5
if($exp>0){

$base*=$base;

}
}#end while loop

print “$orbase to the exponent of $orexp is $res\n\n”;

Let’s assume this file is named exp.txt. To call it and ask it to evalute 2¹⁰, one would type at the command prompt

perl exp.txt 2 10

This algorithm is more efficient than the looping one because it can square the base, then halve the number of times it needs to be multiplied by itself. Furthermore, it can separate the expression into even and odd segments, then tackle the even one(s) as just described.

I’ll be talking more about the details of this algorithm in future posts:)

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Addison-Wesley: Toronto,
1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math/comp sci: another algorithm for exponentiation

The tutor follows up his earlier post about an algorithm for exponentiation.

Leave a Reply Cancel reply