# Simple algorithm to get the square of an integer using only addition?

This problem was mentioned in passing in a reading and it piqued my curiosity.

I'm not sure where to start. Any pointers? (perhaps square root was meant?)

• You mean expressing $a^2$ as $a + a + a + \ldots + a$? Oct 23, 2013 at 20:22
• I imagine (hope) that wasn't what was meant. Oct 23, 2013 at 20:36
• There is "exponentiation by squaring" so presumably there is "multiplication by doubling" Oct 23, 2013 at 20:47

An algorithm to do this for integers would be (in pseudo-code):

 input a
b = abs a
s = 0
while b > 0 do
s = s + a
b = b - 1
return s

• It would be easier using a for loop.
– leo
Oct 24, 2013 at 15:29
• In my opinion, a "for var startval endval operation" loop is a higher level and less flexible construction than either a "repeat operation until condition" or a "while condition do operation" Oct 29, 2013 at 20:58

$(n+1)^2 = n^2 + n + n + 1$

recursion rocks:

$f(0)=0,\,f(n+1)=f(n)+n+n+1,\,n\geq0$

• It would be useful to be a bit more specific, though... How about $f(0) = 0, f(n+1) = f(n) + n + n + 1$? Oct 24, 2013 at 16:02
• @JohannesKloos done! In my defense, the author asked for pointers, not solutions :) Oct 24, 2013 at 16:23

If you don't want to use the trivial solution $$n^2=n+n+n+\cdots+n=\sum_{k=1}^n k$$ use that $$n^2=1+3+5+\cdots+(2n-1)=\sum_{k=1}^n (2k-1)$$

You can determine the square of any real number $n$ by adding the square of $(n-1)$, plus $n-1$, plus $n$. The formula is $n^2 = (n-1)^2 + (n-1) + n$ . E.g.

to find the square of $4$, add the square of $3$, plus $3$, plus $4$ or $9+3+4 = 16$ to find the square of $9$, add the square of $8$, plus $8$, plus $9$ or $64+8+9 = 81$

While you could code a nifty recursive function to determine the square of $n-1$, most systems limit levels of recursion so you will encounter an error when you reach the limit, thus limiting the starting number range. Better to use a loop.

Also, if you're nit-picking, this formula uses subtraction and the original problem mentioned using only addition. In that case, add $a-1$ to $n$ and you should be in conformation with the restriction to only use addition.

• Please use MathJax for formatting. Feb 23, 2016 at 18:32

$$a^2= 2((a - 1) + (a - 2) + ... + 1) + a$$

Imagine a square of side 5 units (Going clockwise) Add one side (5), then another (4) on and on...

It will give you this: $$2\times(4 + 3 + 2 + 1) + 5 = 25 = 5^2$$