Re: [PATCH] pp.c:pp_pow() -- quit when you're done

[CCs turned into BCCs]
Tels wrote:
[snip]
> (Excuse my indention (sp?), but works better in the mailer)
> 
>         UV bit = 1;
>         while (power != 0)
>           {
>           if (power & bit)
>             {
>             result *= base;
>             /* Only bother to clear the bit if it is set*/
>             power &= ~bit;
>             /* Save the last squaring of base, because this makes trouble */
>             if (power == 0) { break; }
>             }
>           base *= base;
>           bit <<= (UV)1;
>           }
> 
> The additional "if (power == 0)" is only executed if the bit was on, which
> should be seldom enough ;)
> 
> One could use a do { } while ( ... ); loop to skip the first power == 0
> test (since that is likely handled above), but that should be only a
> theoretical gain, since such a comparisation is quite fast compared to the
> rest (unlike with BigInt's) (and we see later what the compiler does for
> us, anyway).
> 
> It is also a question whether a loop without the if would be faster on some
> CPU's with long pipelines:
> 
>         UV bit = 1;
>         while (power != 0)
>           {
>           result *= base * (power & bit);
>           power &= ~bit;
>           if (power == 0) { break; }
>           base *= base;
>           bit <<= (UV)1;
>           }
> 
> While this executes some more instructions for the (power & bit == 0) case,
> it saves one comparisation.

Actually, we no also longer need to check power as part of the loop
condition now, since we check it each time it's decreased:

NV result = 1.0;
NV base = ...;
UV bit = 1;
if( power ) {
   for( ; ; ) {
      if( power & bit ) {
         result *= base;
         /* Does a single 'AND-NOT' instruction exist, or */
         /* will "&= ~" become two seperate instructions? */
         /* power &= ~bit; */
         power ^= bit;
         if( power == 0 ) break;
      }
      base *= base;
      bit <<= 1;
   }
}

PS: Would "result *= (base * (power&bit))" really do the right thing?
I'll admit I haven't tested it, but it feels wrong to me, somehow.

For machines with long pipelines, and which can optomize simple "?:"
expressions into a conditional assignment (which should faster than a
conditional jump):

if( power ) {
   for( ; ; ) {
      NV x = (power & bit) ? base : (NV)1.0;
      result *= x;
      power &= ~bit;
      if( power == 0 ) break;
      base *= base;
      bit <<= 1;
   }
}

[All of my code in this message is untested]

-- 
tr/`4/ /d, print "@{[map --$| ? ucfirst lc : lc, split]},\n" for
pack 'u', pack 'H*', 'ab5cf4021bafd28972030972b00a218eb9720000';

• [PATCH] pp.c:pp_pow() -- quit when you're done by Craig A. Berry
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Tels
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Benjamin Goldberg
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Nicholas Clark
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Philip Newton
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Nicholas Clark
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Jarkko Hietaniemi
• Re: [PATCH] pp.c:pp_pow() -- quit when you're done by Craig A. Berry