445,804 Members | 1,659 Online
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
9 Replies

 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

 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

 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

 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

 Expert 100+ P: 1,251 Cool, good to know. Adrian Jun 9 '07 #10