Archived

This topic is now archived and is closed to further replies.

Vanukoff

In general, which is faster?

Recommended Posts

Vanukoff    122
Assuming I have two integers, a and b, and a is much larger than b (a > b). Is it quicker (in code) to multiply a*b or b*a? int a = 424242; int b = 11; int c = a*b; // ? int c = b*a; // ? I thought I read somewhere that order can make a speed difference. Does it?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
If it makes a difference, it''s virtually zero. Floating point numbers can be a different story, though.

Share this post


Link to post
Share on other sites
Dactylos    122
Even if it did make a noticable difference (which I strongly doubt), then you still wouldn''t know which order the compiler decided to multiply them. Most compilers can perform "mathematical optimizations". Since the compiler ''knows'' that a*b is the same as b*a mathematically, then it might decide to flip the order of the multiplicands in order to simplify register allocation or whatever....

(This would not be the case if operator * is overloaded for the types of ''a'' and ''b'', since "a.operator * (b)" is not necessarily the same as "b.operator * (a)").

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
To my understanding mul operations take the same number of cycles regardless of the numbers being used.

You might try making the smaller number a short or char though. But i think multiplication is done with two numbers of the same bit so it would probably convert the numbers to the type with a large bit which would be undesirable. The best way to get more preformance out of a mul operation is todo it with 16 or 8 bit (instead of 32 bit ints) numbers or not do it at all which is even faster.

Share this post


Link to post
Share on other sites
gmcbay    130
In your specific example, each of those will take exactly the same time because the compiler (assuming it was made within the last 8 years or so) is going to optimize the multiply away and just put the result in c.

And the short answer is that time taken to do a multiply may change due to the size of the type (int, short, long), but its not going to change because of the size of the values within a certain type (with certain exceptions where if you multiply by certain constants the compiler may optimize the operation).


Share this post


Link to post
Share on other sites
DekuTree64    1168
An article I read said the first one''s faster, but I did a little test (using ASM, so I knew exactly what was happening) and the second one seemed to be a tiny bit faster. I was doing 3 * 0x7fffffff (1 less than a DWORD can hold) 20,000,000 times per frame though, and the frame rate was the same, except it''d occasionally go up or down 1 frame, and switching them seemed to make it a little less frequent. Not enough to worry about though, and my frame counter probably isn''t too accurate anyway^^



-Deku-chan

DK Art (my site, which has little programming-related stuff on it, but you should go anyway^_^)

Share this post


Link to post
Share on other sites
gph-gw    122
quote:
Original post by Anonymous Poster
To my understanding mul operations take the same number of cycles regardless of the numbers being used.

You might try making the smaller number a short or char though. But i think multiplication is done with two numbers of the same bit so it would probably convert the numbers to the type with a large bit which would be undesirable. The best way to get more preformance out of a mul operation is todo it with 16 or 8 bit (instead of 32 bit ints) numbers or not do it at all which is even faster.



To my understanding I thought 16 and 8 bit numbers were slower than 32 bit numbers, because of the alignment issue on x86 processors. They do save memory, however. If you had a huge structure like 1,000,000 of them then it might be logical to use shorts and MMX instructions, where bit size seems not to matter.

Share this post


Link to post
Share on other sites
GayleSaver    122
First, make sure that you''re not optimizing without a purpose. Can the code run at acceptable speed without caring about this performance issue? I''ve seen people make this optimization blunder too many times, and when it catches up to them, they realize that their competitor produced a satisfactorily-running, full-featured program, while they produced an optimized cookie which is next to impossible to read, much less modify.

Second, if you really care about operation order that much, start an __asm block and do it yourself.

Share this post


Link to post
Share on other sites
Ruval    122
According to Andre la Mothe the smaller value should be the
multiplier (right hand value) because the multiplication finishes
as soon as all significant bits of the multiplier have been
processed.

Whether that''s still true on Pentium III I don''t know.

Share this post


Link to post
Share on other sites
Sandman    2210
Frankly, stuff like that isnt worth optimising. If it makes any difference in speed at all (unlikely) it isnt going to be significant, so just dont bother worrying about it.

Share this post


Link to post
Share on other sites
Mithrandir    607
They will both take the same amount of time.

The way a computer multiplies two numbers is using a set process which takes a constant time, no matter what numbers are used.

A multiplication in circuitry is broken down to a sequence of shifts and additions.


take, for example, 14 x 21

  
14 = 1110b
21 = 10101b

10101
x 1110
-------
10101
10101
10101
------------
100100110


in this example, we shortened the multiplication by doing it by hand and placing the number with the fewest digits on the bottom, reducing the number of additions that need to be made.

However, a computer cannot work like this. It needs a more circuit oriented algorithm to perform the multiplication.

Note that any n-bit number multiplied by another n-bit number will result in a maxium of a 2n-bit number. (ie: 2 8-bit numbers multiplied can result in a maximum of 16 bits. indeed, 255*255 = 65025, which is a 16 bit number.)

So, for a computer to multiply two word''s together (assuming that the word size is the same as the register size), it needs to have 4 registers: multiplicant, mutliplier, and 2 registers to store the product.

The algorithm is as follows:
  
store 0 into C register // counting register

clear A register // first half of result (higher)

clear B register // second half of result (lower)

while( C < bits ) // bits is the word size

if( multiplier & 1 == 1 )
add multiplicand into A register
shift multiplier register down 1 bit
shift A register down 1 bit, pushing last bit into B register (also shifting it down 1 bit)
increment C
end while


lets assume we are working with 4 bit words here, to make it simple. I will manually multiply 7x13, to get an 8 bit number.

  
1101->multiplier
0111->multiplicand
0->A
0->B
0->C

loop1:
1101&1 = 1, so add 0111 to A
A = 0111
shift multiplier down 1 bit
shift AB down one bit
multiplier = 0110
A = 0011
B = 1000

loop2:
0110&1 = 0, do nothing
shift multiplier down 1 bit
shift AB down one bit
multiplier = 0011
A = 0001
B = 1100

loop3:
0011&1 = 1, add 0111 to A
A = 1000
shift multiplier down 1 bit
shift AB down one bit
multiplier = 0001
A = 0100
B = 0110

loop4:
0001&1 = 1, add 0111 to A
A =1011
shift multiplier down 1 bit
shift AB down one bit
multiplier = 0000
A = 0101
B = 1011

Final result = 01011011
7 * 13 = 91
01011011 = 91


ta-da!

in short, any N-bit multiplication will require N shifts and N additions, no matter what the multiplier or multiplicand are.

Share this post


Link to post
Share on other sites