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.
Programming Praxis 
[…] 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:
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][…] 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
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; }def square_no_add(n, ctr=0): if n == ctr: return 0 else: return n + square_no_add(n, ctr + 1)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
from itertools import accumulate, count, islice def square(n): return next(islice(accumulate(n+n+1 for n in count()), n-1, n))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)))))[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/
#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)))Java
int square(int n){
int sum = n;
for(int i = 1; i < n; i++){
sum += n;
}
return sum;
}
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; }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:
def main(): count = 1 square = 0 number = int(input("Number?")) while count <= number: square = square + number count = count + 1 print("Square of",number,"is",square) main()[…] Find a square of a number. but you can only use addition or subtraction but no multiplication or division Odd way to Square […]