By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,804 Members | 1,659 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,804 IT Pros & Developers. It's quick & easy.

Fastest way to mulitply by 7

P: 34
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
Jun 8 '07 #1
Share this Question
Share on Google+
9 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
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.
Jun 8 '07 #2

Savage
Expert 100+
P: 1,764
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
Jun 8 '07 #3

Expert 10K+
P: 11,448
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
Jun 8 '07 #4

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

Suyash
Jun 8 '07 #5

weaknessforcats
Expert Mod 5K+
P: 9,197
What is GZ,isn't that supposed to be 4GHz?
Silent H. :)
Jun 8 '07 #6

Expert 10K+
P: 11,448
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
Jun 8 '07 #7

AdrianH
Expert 100+
P: 1,251
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
Jun 8 '07 #8

Expert 10K+
P: 11,448
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
Jun 9 '07 #9

AdrianH
Expert 100+
P: 1,251
Cool, good to know.


Adrian
Jun 9 '07 #10

Post your reply

Sign in to post your reply or Sign up for a free account.