Threaded Mode | Linear Mode

***drdebcol*** · (This post was last modified: 01-09-2010 12:59 AM by drdebcol.)

There are loads of tasks that you need to do with exponentation. More about exponentation you have here :
http://en.wikipedia.org/wiki/Exponentation
I was working with Turbo Pascal for Windows that has no "math" library (Free Pascal has it). But what if you don't have "math" lib in Pascal or "math.h" in C or C++ and you need to calculate a^n. Well i was trying to find alternatives. If you have two positive integer numbers and you need to calculate a^n, well that is easy. First to say it mathematically :
[Image: 32161_exponentation1.jpg]

If there are two positive integers (including zero) and you do exponentation on them you will get and integer that is in set of positive integer numbers.
Okay now let's see special cases. What if your number is is zero (a=0) and you need to calculate 0^n, than you need to return zero. So 0^n=0 and n>0. Now another case. What if your exponent is zero (n=0), well than you need to return 1. Mathematically :
[Image: 32162_exponentation2.jpg]

And proof :
[Image: 32164_exponentation3.jpg]

And now special extra case, which you probably know is if you have exponent and number equal to zero (a=0 and n=0). For this case mathematical explanation above is not right. That is extra case. The best way is that your algorithm return one in this case. But if you want to go further into problem you have it here :
http://en.wikipedia.org/wiki/Exponentati...zero_power
That would be mathematical explanation and now it is easy to write code for that. I will post Pascal and C or C++ functions for this. In C or C++ i used unsigned int for this because it is the nearest to set of positive numbers.
Pascal power function :

Code:

function power(a,n:integer):integer;

var

  i,p:integer;

begin

  if (a=0)  and (n=0) then

    power:=1

  else

  if (a=0) and (n>0) then

    power:=0

  else

    if (n=0)  and (a>0) then

      power:=1

    else

      begin

        p:=1;

        for i:=1 to n do

          p:=p*a;

        power:=p; 

      end;

C or C++ power function :

Code:

unsigned int power(unsigned int a,unsigned int n) 

{

  if (a==0 && n==0)

    return 1;

  else

  if (a==0 && n>0)

    return 0;

  else

    if (n==0 && a>0)

      return 1;

    else

     { 

       unsigned int i,p;

       p=1;

       for (i=1;i<=n;i++) 

           p*=a;

       return p;

     }

}

But as you can see this way is slow. You have to do loads of operations. That's why recursion is solution. So here is the recursive algorithm for this.
Code in Pascal :

Code:

function sqr(n:integer):integer;

begin

  sqr:=n*n;

end;

function power(a,n:integer):integer;

begin

  if n=0 then

    power:=1

  else

    if n mod 2 = 0 then

      power:=sqr(power(a,n div 2))

    else

      power:=a*(power(a,n-1));

end;

Code in C or C++ :

Code:

unsigned int sqr(unsigned int n) 

{ 

  return n*n; 

}

unsigned int power(unsigned int a,unsigned int n) 

{

 if (n==0)

   return 1;

  else 

   if (n%2 == 0)

     return sqr(power(a,n/2));

   else

     return a*(power(a,n-1));

}

As you can see i made it totally independent of libraries because i made sqr() function which returns n^2.
Okay all of that was because of integer numbers exponentation. Now if we want to make real power() function which will work with real numbers and calculate for example (3.5^-1.5) Than we need to use more complex formula.
The good thing is that there is very structured formula for that :
[Image: 32168_exponentation4.jpg]

Okay now let's explain it. Basically you have exp() function inside which does not anything different than algorithm here :
http://www.pro9ramming.com/exponent-of-m...t-792.html
So exp() function returns exponent of mathematical constant e. If it is exp(1) it will return e^1=e which equals :

Code:

2.71828 18284 59045 23536 . . .

And ln() function is natural logarithm. More about it you have here :
http://en.wikipedia.org/wiki/Natural_logarithm
ln() function is basically exp()^(-1), because :

Code:

exp(ln(n))=n;

And now here is the proof of this formula :
[Image: 32188_exponentation5.jpg]

That is everything you need to know about this. Now let's pass to making an ultimate power function.
So power recursive function in Pascal with errors when you enter something that function can not calculate is :

Code:

function power(a,n:real):real;

begin

  if n=0 then

    power:=1

  else

    if a= 0 then

      power:=0

    else

     if abs(n*ln(abs(a)))>87.498 then

       runerror(205)

     else

       if a>0 then

         power:=exp(n*ln(a))

       else

        if (a<0) and (frac(n)=0) then

          if odd(round(n)) then

            power:=-power(-a,n)

      else

            power:= power(-a,n)

       else

             runerror(207); 

    end;

You can use this function in Pascal. When you use it in C++ don't forget that log() function in C++ is ln() function in Pascal. ln() is as i said with "e", base of natural algorithm, and mathematically log is with base 10. So Pascal is more mathematically correct and C++ is C++, what should i say about this LOL. More about logarithms you have here :
http://en.wikipedia.org/wiki/Logarithms
That would be everything about this subject of exponentation.
I like when it is mathematically explained.
Hope that you will use this function !

codecaine · 01-10-2010, 04:11 AM

Nice work that pretty much covers what the power function does under the hood.

***drdebcol*** · 01-10-2010, 07:12 AM

(01-10-2010 04:11 AM)codecaine Wrote: Nice work that pretty much covers what the power function does under the hood.

Yeah like you say "under the hood", well i just wanted to explain everything. People must know what they use !

Alireza_M · 01-10-2010, 11:04 PM

good and short algorithms for those,can you make your own symbol for for example exponentation?I mean can you declare your own sighn,2^3(=8)?can you declare the sign-^- for your function so that when you use ^ pascal knows that?as same as + - x / ... ?

***drdebcol*** · 01-10-2010, 11:13 PM

I think that is not possible. You need to use function. But it is easy with the function too !

Alphablend · 01-11-2010, 09:24 PM

Nice code Bro. Cool

***drdebcol*** · 01-12-2010, 07:40 PM

(01-11-2010 09:24 PM)Alphablend Wrote: Nice code Bro.

THX