Re: how to specify power of number

On 18 Apr 2008 at 14:05, Yanb wrote:
Antoninus Twink <nospam@xxxxxxxxxxxxxx> wrote:
For general integer powers, a simple square-and-multiply algorithm is
a good bet, e.g.

unsigned long long power(unsigned a, unsigned b)
{
unsigned long long r, bit, pow;
for(bit=r=1, pow=a; bit<=b; bit<<=1, pow *= pow)
if(b & bit)
r*=pow;
return r;
}

The hardest part is checking for overflow - left as an exercise for
the reader...


Thank you both. I must admit, that the code Is almost a mystery for me :-)

Well, it's overkill for exponents small enough not to overflow a
unit64_t, but the idea is this: naively, to raise a to the power b takes
b integer multiplies (a*a*...*a, b times). But actually, you can do this
using more like log(b) multiplies by repeatedly squaring to compute a^2,
a^4, a^8, ... and then multiplying those terms corresponding to
exponents of 2 that occur in the binary expansion of b. For example, if
b=7, then a^7 = a^(1+2+4) = a * a^2 * a^4.

.

Relevant Pages

  • Re: .net 2003 vs vc6 performance
    ... Turned off overflow checks ... Your VB.NET code is doing 64-bit multiplies. ... optimizations. ... Made a COM in VC++ which is executing following code: ...
    (microsoft.public.dotnet.framework.performance)
  • [PATCH 2/7] s390: overflow in sched_clock.
    ... method multiplies first and then shifts the value to make the result ... with 1000 will overflow shortly after 52 days. ... by the scheduler for time stamp deltas, ... two time stamps the scheduler will get confused. ...
    (Linux-Kernel)
  • Re: arm9e: how do I invert sign of a halfword?
    ... Positive leftshifts that overflow are ... However multiplies of positive and negative numbers ... If you don't pay attention, you will sooner or later have to pay. ...
    (comp.arch.embedded)