Fastest way to mulitply by 7

[Suyash Upadhyay]

Hello all,

I got the answer that fastest way to multiply by 7 is n<<3 - n, but why?

If the question is to multiply by 8, then n<<3 is considerably better than n*8, because bitwise operation is faster. But when we multiply by 7, we are also subtracting n, it may be more cumbersome than multiplying directly with 7.

please answer,
Suyash

[weaknessforcats]

Consider a 1:

0001

Shift it left 3 and you have

1000

which is 8

so you sutract the number to get

0111

which is 7.

Try it with 2 which is:

00010

Shift it left 3:

10000

which is 16

So you subtract 2

01110

which is 14.

I have to say that with a mult-core 4GZ processsor, this is silly. Multiplying by shifting was popular in 1965 when a really small machine filled your bedroom.

Always nice to know how the bits work, though don't put this in your code.

[Savage]

I have to say that with a mult-core 4GZ processsor, this is silly

What is GZ,isn't that supposed to be 4GHz?

Tick,tick,tick.


Savage

[JosAH]

I have to say that with a mult-core 4GZ processsor, this is silly. Multiplying by shifting was popular in 1965 when a really small machine filled your bedroom.

Always nice to know how the bits work, though don't put this in your code.

First I'd like to say that I don't want computers in my bedroom and second:
there are still applications for that trickery-dickery but they find use in very
small processors that lack a multiplication instruction. (even early SPARCs
multiplied like that and nowadays, say, Atmel RISC processors still like to
do it that way). For the 'when every cycle counts' world a simple multiplcation
is still pure luxury. For 4GHz, multi core or whatever larger processors, trying
to squeeze extra speed out of them using this trickery-dickery is indeed a
silly, useless exercise.

kind regards,

Jos

[Suyash Upadhyay]

Thanx...
But I wanted to ask why this method is better because subtraction bears overhead like multiplication.

Suyash

[weaknessforcats]

What is GZ,isn't that supposed to be 4GHz?

Silent H. :)

[JosAH]

Thanx...
But I wanted to ask why this method is better because subtraction bears overhead like multiplication.

Suyash

As I wrote in my previous reply: suppose there is no multiplication instruction
available; using a couple of shifts and additions or subtractions would be best
or second best. Suppose there *is* a multiplication instruction available then
simply counting cycles determines which of the two variants will be best.

You simply can't say up front which one will be the best way. Nowadays big
micro processors all have a decent fast multiplication instruction available and
on average those will be faster than your alternative, but to be sure: count cycles.

kind regards,

Jos

[AdrianH]

As I wrote in my previous reply: suppose there is no multiplication instruction
available; using a couple of shifts and additions or subtractions would be best
or second best. Suppose there *is* a multiplication instruction available then
simply counting cycles determines which of the two variants will be best.

You simply can't say up front which one will be the best way. Nowadays big
micro processors all have a decent fast multiplication instruction available and
on average those will be faster than your alternative, but to be sure: count cycles.

kind regards,

Jos

A good compiler will do this for you if you set it up to optimise for speed.


Adrian

[JosAH]

A good compiler will do this for you if you set it up to optimise for speed.


Adrian

The problem is far more complicated than people think: try to multiply 7*36
on a one byte (8 bits) processor; performing 8*36-1*36 using simple shifts
causes an overflow (8*36 == 288 which doesn't fit in a byte). Most compilers
try to play it safe so they generate 4*36+2*36+1*36 using shifts and additions.
Interchanging the multiplier and multiplicant woult've done a bit better here:
7*36 == 7*32+7*4 using shifts and additions without causing overflow.

The decision whether or not using compound instructions using two 8 bit
words and go for the 16 bit wide shifts versus using additional additions
differs per processor and can't be easily solved. Some processors, notably
the ARM/7 processor has the capability to shift 12 bit words to the left by 20
positions maximum in one single instruction including both operands.

That allows for every 32 bit word to be generated as long as the '1' bits are
no more than 11 positions apart.

Other processors have special barrel shifters in their ALU that can do other
funky things. The answer to the question 'which bit shift is best?' cannot be
easily answered. Google for 'shift for multiplication' and see the mess ;-)

kind regards,

Jos

[AdrianH]

Cool, good to know.


Adrian