## 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

nand returnsn-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

[...] 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: