[A89] Re: Exponents

[Prev][Next][Index][Thread]

[A89] Re: Exponents


> Anyone know how to do exponents in C, such as 5 to the 6th power and such?
> I looked in help, but all the funcitons I found having to do with
exponents
> didn't seem to be just plain exponents.  Am I just missing something or is
> that not possible in C?

C is a very low-level language, and you won't find exponentiation as a
native instruction on most (any?) processors.  However, it's very easy to
write the code to do exponentiation using multiplication.  Here's the most
basic example:

int power(int base, int pow)
{
    short result = 1;
    while (pow > 0)
     {
        result *= base;
        --pow;
     }
    return base;
}

When speed matters, you can get a bit more advanced.  Here's one very simple
optimization to that routine that can speed it up a whole lot:

int power(int base, int pow)
{
    short result = 1;
    while (pow > 0)
     {
        if (pow%2 == 0)        // optimization: if pow is divisible by two,
         {                     //   then b^p = (b^2)^(p/2)
            result *= result;  // result = result^2
            pow >>= 1;         // pow = pow/2;
         }
        else
         {
            result *= base;
            --pow;
         }
     }
    return base;
}

FYI -- you can probably skip this part -- I've borrowed that algorithm from
_The Schemer's Guide_ (different language, same algorithm), although it's
pretty well known.  According to the book, "[this algorithm] that requires
fewer multiplications was reported by the French mathematician Adrien-Marie
Legendre (1753-1833) in his book _Theorie des Nombres_, published in 1798."
Just thought I should give credit where credit is due, and besides, I like
sounding like I know what I'm talking about.  Of course, knowing my luck,
someone will point out an error in my implementation, but I think it's all
right.

    -Scott
Follow-Ups: