Skip to main content
gamedev.net
🔒 Locked

Square of an Integer algorithm

Started by Nomad010 Oct 20, 2005 at 11:16 AM 6 replies 950+ views
Original Post
Nomad010
Nomad010
This question doesn't primarily deal with a game, however the answer of the question could be used in games and such things. Is it faster to use the computer's natural multiplication algorithm for finding a square of an integer than to use the sum of odd integers to n terms of an arithmetic series. I'm not completely sure how computers naturally work out a square but I am sure that it just multiplies the number by itself. I'm also not sure about which the multiply algorithm, but I am guessing they just add the same number 'n' times. Surely, an alternative way is to add up all the terms of an arithmetic series. For instance, the square of an integer 'n' could be calculated as follows: 

public int getSquare(int n)
{
  int temp = 1;

  for(int i = 1; i < n; i++)
    temp+=i + i + 1

  return temp;
}
as opposed to: 

public int getSquare(int n)
{
  int temp = n;

  for(int i = 1; i < n; i++)
    temp+=n;
}
Hmm. Maybe not. It increases the amount of additions by 2. Is there any better way to square of a number? Even though I have no qualms about the speed of operations, I would like to throw some ideas into the mix about speeding up operations by the computer.
"..."
intransigent-seal
intransigent-seal 
int x;int square_of_x = x*x;

It's more readable, and it will be run far faster than either of your methods. Multiplication (especially integer multiplication) is not a slow operation.

John B
The best thing about the internet is the way people with no experience or qualifications can pretend to be completely superior to other people who have no experience or qualifications.
Sneftel
Sneftel
Quote:
Original post by Nomad010
I'm not completely sure how computers naturally work out a square but I am sure that it just multiplies the number by itself. I'm also not sure about which the multiply algorithm, but I am guessing they just add the same number 'n' times.

Not quite. Even without specialized multiplication circuitry, it's possible to multiply the integers m and n in O(log n) time. Multiplying integers, these days, is a dizzyingly fast operation.

Simian Man
Simian Man
Multiplication is implemented at the Instruction set level. There is actual hardware in the ALU that performs multiply. It does not do it by reppettitive addition. It does it by doing ands and shifts. (I can't recall the exact procedure) Suffice it to say that it takes much less time then what you propose (It always takes the word size (ie 32) iterations - and that's at the harware level). So I'm pretty sure x*x will be the fastest.
Anon Mike
Anon Mike
From what I remember from my college days of cpu design, multiplication of integers in hardware is (was?) done more-or-less essentially the same way humans do multiplication on paper. e.g. you multiply the first term by the lowest significant digit of the second term, then shift everything over and multiply by the next lowest significant digit, etc, and then add everything up. It's easy because you're only ever doing multiplies by zero or one which are of course trivial to do. There's also some optimizations you can do to quickly skip over runs of 0's, etc.

It definitely is *not* the case that they would do (e.g). 1532 * 4902 by doing 1532+1532+1532+1532+... 4900-odd times.

And finally my standard reply to all such perf question - the code to test this out is trivial, you've already written it even, why don't you just plug it in to your compiler and try it rather than relying on other people to guess for you?
-Mike
Nomad010
Nomad010
Actually, I did know that multiplication was done on special circuitry. I don't know why I forgot it. In school, our Add Maths, class project was to build a calculator that could multiply two 3 digit numbers together. We couldn't use any special flip-flops or things like that so we had to use simple gates to acheive this. (And no, we couldn't manufacture our own flip-flops from gates.)

Also, from my design at least, it was evident that you were actually doing quite a few additions of binary digits. I think it was for determining if you needed to carry a '1' bit over to the next bit in the number.

I designed it with the groups of the number(eg: 20,21 etc) in mind and using and gates to multiply two-bits together.

Silly me. Thanks.&#106avascript:;
Show Preview
"..."
ury
ury
Quote:

Is it faster to use the computer's natural multiplication algorithm for finding a square of an integer than to use the sum of odd integers to n terms of an arithmetic series.


In Pentium 4, there's a dedicated slot (slot 0) for performing ALU operation that can perform TWO! ALU operations in one cycle (Be that addition or multiplication). :)
twanvl
twanvl
There are faster algorithms for multiplication then repeated addition (which is O(2^n) for n digit numbers). The simplest is to use shifts, afaik this is also what is implemented in hardware on your processor (the hardware implementation is faster of course).
int getSquare(int n) {  return multiply(a, b);}int multiply(int a, int b) {  int result = 0;  while (a) {    if (a & 1) {      result += b;    }    result >>= 1;    a <<= 1;  }  for(int i = 1; i < n; i++)    temp+=i + i + 1  return temp;}

This can be seen as shifting and adding b for each bit that is set in a:
9 * 11 = 1001 * 1011 a1001    * 1 1001   * 0  b  1001  * 1   1001 * 1----------- + 1100011


There are more complicated algorithms for multiplication, but they are only used when working with very large numbers.

ps. Nomad010, could you please put a line before your signature, it looks like it is part of the post itself.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.