Re: Help w/ Code Optimization

Hi ;-).

Let me throw around my math skills... Recalling some binary math I figured that 10^2 (10 to the power of 2) may be simplified into this:
10^2 = 10x10 = 10x(2x2x2+2).

Notice all the 2's there? Here's where the left shift operator '<<' comes in handy (and it's pretty fast by the way).

So, every multiplication by 2 could be replaced by a left shift by one (in binary it's equivalent to multiplying by 2 ;) like this:

10^2 = 10<<3 + 10<<1; (by the way, this is may not be 
written as 10<<4! :)
[download]

So, I've replaced 10x10 by a few left shift operators. The key here is to determine how many left shifts will have to be performed for given power. Say, if you were to raise 10 to the power of 3, you'd look down at this:

10x10x10.

From this you'll also note that 10x10 is really (10<<3 + 10<<1) therefore, each 'x10' could be replaced accordingly.

Hopefully I've given you some food for thought ;-). I"ll try to look for a few ways to guess the left shift number for you. Evidently, it depends on the number being multiplied. My thinking is that left shift should work faster than multiplication, althought, folks who've developed Perl might have taken that into consideration... ;-))

"There is no system but GNU, and Linux is one of its kernels." -- Confession of Faith

Comment on Re: Help w/ Code Optimization Select or Download Code

Replies are listed 'Best First'.
Re: Re: Help w/ Code Optimization by John M. Dlugosz (Monsignor) on Dec 27, 2001 at 02:08 UTC
Once upon a time, that was a good idea for PC's. On a 80486, where shift took 1 clock and multiply took up to 40, it was still faster sometimes. Note I said "up to" because it stops early, and essentially does this same thing internally--one addition for each '1' bit, using a barrel shifter that skips the zeros. But with Pentium and later, the multiply is just as fast as anything else, and breaking it up into multiple steps makes it slower, by far. —John	[reply]
Re: Re: Help w/ Code Optimization by sifukurt (Hermit) on Dec 26, 2001 at 23:10 UTC
I like this idea a lot. My only problem, though, is that the exponent won't always be an integer. As a very simple example, sticking with left shift operator idea, would there be a relatively easy way to do 10**(1/3)? I still get a little confused with the whole `<<` thing. ___________________ Kurt	[reply] [d/l]