## An Odd Way To Square

### February 26, 2013

I’m not sure where this comes from; it could be an interview question, or some kind of programming puzzle:

Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.

Your task is to write the squaring function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 26 Responses to “An Odd Way To Square”

1. ts said
```square 0 = 0
square n = (square (n-1)) + n + (n-1)
```
2. […] today’s Programming Praxis exercise, our goal is to implement an algorithm to square a number using only […]

3. Hm, something went wrong in posting. Let’s try that again:

```import Data.Bits
import Data.List

square :: Integer -> Integer
square n = sum \$ genericReplicate n n

square2 :: Integer -> Integer
square2 n = sum [a | (i,a) <- unfoldr (\(i,p,a) -> if p <= n then
Just ((i,a), (i+1,p+p,a+a)) else Nothing) (0,1,n), testBit n i]
```
4. […] Question is from here. […]

5. Janne said

Isn’t it slightly cleaner to just add n directly? The time complexity remains the same.

```(define (sq2 n)
(let loop ((x n) (s 0))
(if (zero? x ) s
(loop (- x 1) (+ s n)))))
```
6. Mitchell said

Nobody’s done it this way yet…

```(defun square (n)
(apply '+ (make-list n n)))
```
7. […] Pages: 1 2 […]

8. Andrew said

Python

``` def poor_square(n): l = [n for i in range(n)] return sum(l)```

``` n = 12 print poor_square(n) ```

9. pip1984 said

```unsigned int sqr(unsigned int n) {
unsigned int sum = 0, x = n;
for (int i = 0; x; x >>= 1, i++)
if (x & 1) sum += n << i;
return sum;
}
```
10. ```def square_no_add(n, ctr=0):
if n == ctr:
return 0
else:
return n + square_no_add(n, ctr + 1)
```
11. Matthew said

And in forth:

: sqr.add ( n — n*n )
dup 1 > if dup dup 1 do over + loop swap drop then ;

12. cosmin said

An O(log(N)) algorithm exploiting the binary representation of N. Assuming that N=2^k(1) + 2^k(2) + … + 2^k(t) the algorithm will add: N*2^k(1), N*2^k(2), … ,N*2^k(t)

```def square(n, x, p, q):
s = square(n, x, p + p, q + q) if p + p <= n else 0
if p <= x < p + p:
x -= p
s += q
return s

n = 16
print square(n, [n], 1, n)
```
13. Mike said

Python 3.3

based on the formula (n+1)**2 = n**2 + 2*n + 1

```from itertools import accumulate, count, islice

def square(n):
return next(islice(accumulate(n+n+1 for n in count()), n-1, n))
```
14. x0j0c said
```_start:
mov	ecx, 5	; the number to square
xor	ebx, ebx
mov	eax, ecx
.sum:
loop	.sum

;; ebx now contains the square
mov	eax, 1
int	0x80
```
15. Jamie Hope said

Here’s another O(n) one based on the fact that n*n is the sum of all odd integers less than 2n:

```(define (square n)
(let loop ((i (+ n n -1)) (s 0))
(if (= i -1) s (loop (- i 2) (+ s i)))))
```
16. XtremePrime said

[Java]

private int squared(int n){
int result = 0;
for(int i = 0; i < n; ++i){
result += n;
}
return result;
}

17. spainmc said

JavaScript

``` function OddSquare(n) { var result = 0; for (var i = 0; i < n; i++) { result += n; } return result; } ```
http://jsfiddle.net/jpkmt/

18. ```#Python program to
#find square of number
# without using multiplication

def num_square(num):
count = 0
result = 0

while count < num:
result = result + num
count+=1
return result

n = input("Enter the number whose square has to be calculated:>")

print(num_square(int(n)))

```
19. Eitan said

Java
int square(int n){
int sum = n;
for(int i = 1; i < n; i++){
sum += n;
}
return sum;
}

20. brooknovak said

Binary arithmetic yielding O(1):

```public static uint Multiply(uint n1, uint n2) {
uint res = 0;
for (; n2 > 0; n2 >>= 1, n1 <<= 1) {
if ((n2 & 1) == 1)
res += n1;
}
return res;
}
```
21. brooknovak said

Woops the binary arithmetic isnt really o(1), its dependent on position of the MSB that equals 1 of the unsigned int (n2). Worst case would be 32 iterations.
To improve on this you could swap n1 with n2 if n1 < n2.

22. skuba713 said

```def main():