[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';Thread Previous | Thread Next