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 
(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.
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 […]