## 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 . By distributing the multiplication through the addition and rearranging terms, this becomes . 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

[…] today’s Programming Praxis exercise, our goal is to implement an algorithm to square a number using only […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/26/programming-praxis-an-odd-way-to-square/ for a version with comments):

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

[…] Question is from here. […]

My java solution here.

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

Nobody’s done it this way yet…

[…] Pages: 1 2 […]

Python

http://codepad.org/HKjnImYy

def poor_square(n):

l = [n for i in range(n)]

return sum(l)

n = 12

print poor_square(n)

use shift operator, shift and add, see: http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

And in forth:

: sqr.add ( n — n*n )

dup 1 > if dup dup 1 do over + loop swap drop then ;

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)

Python 3.3

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

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

[Java]

private int squared(int n){

int result = 0;

for(int i = 0; i < n; ++i){

result += n;

}

return result;

}

Haskell

link

JavaScript

function OddSquare(n) {

var result = 0;

for (var i = 0; i < n; i++) {

result += n;

}

return result;

}

http://jsfiddle.net/jpkmt/

Java

int square(int n){

int sum = n;

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

sum += n;

}

return sum;

}

Binary arithmetic yielding O(1):

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.

Easy to follow Python method: