• Announcements

Archived

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

In general, which is faster?

Recommended Posts

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 on other sites
If it makes a difference, it''s virtually zero. Floating point numbers can be a different story, though.

Share on other sites
Don''t think it does...

Share on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 = 1110b21 = 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->multiplier0111->multiplicand0->A0->B0->Cloop1:1101&1 = 1, so add 0111 to AA = 0111shift multiplier down 1 bitshift AB down one bitmultiplier = 0110A = 0011B = 1000loop2:0110&1 = 0, do nothingshift multiplier down 1 bitshift AB down one bitmultiplier = 0011A = 0001B = 1100loop3:0011&1 = 1, add 0111 to AA = 1000shift multiplier down 1 bitshift AB down one bitmultiplier = 0001A = 0100B = 0110loop4:0001&1 = 1, add 0111 to AA =1011shift multiplier down 1 bitshift AB down one bitmultiplier = 0000A = 0101B = 1011Final result = 010110117 * 13 = 9101011011 = 91

ta-da!

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

• Forum Statistics

• Total Topics
627743
• Total Posts
2978894

• 10
• 10
• 21
• 14
• 14