## An Odd Way To Square

### February 26, 2013

This is easy if you think about it the right way. Gauss’ formula for the sum of the first n integers is $\sum_{i=1}^{n} i = \frac {n(n+1)}{2}$. By distributing the multiplication through the addition and rearranging terms, this becomes $n^2 = \left( 2 \sum_{i=1}^{n} i \right) - n$. So add up the integers to n, add the sum to itself, and subtract n:

(define (square n)   (let loop ((x n)) (s 0))     (if (zero? x) (+ s s (- n))       (loop (- x 1) (+ s x)))))

Another version of the program adds two copies of i and subtracts 1 each time through the loop, distributing the work through the loop:

(define (square n)   (if (zero? n) 0     (+ (square (- n 1)) n n -1)))

If we allow doubling and halving, which are simpler operations than general multiplication, division or exponentiation, we can use the peasant algorithm to perform the squaring:

(define (square n)   (let loop ((x n) (y n) (s 0))     (cond ((zero? x) s)           ((odd? x) (loop (quotient x 2) (* y 2) (+ p y)))           (else (loop (quotient x 2) (* y 2) p)))))

The first two versions of the function take time O(n), the third version is O(log n). You can see all of these functions in action at http://programmingpraxis.codepad.org/Oz8Rt3EA.

Pages: 1 2

### 25 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[0] < p + p:
x[0] -= 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():