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.

About these ads

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. 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)))))
    
  5. Mitchell said

    Nobody’s done it this way yet…

    (defun square (n)
      (apply '+ (make-list n n)))
    
  6. Andrew said

    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)

  7. pip1984 said

    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;
     }
    
  8. def square_no_add(n, ctr=0):
        if n == ctr:
            return 0
        else:
            return n + square_no_add(n, ctr + 1)
    
  9. Matthew said

    And in forth:

    : sqr.add ( n — n*n )
    dup 1 > if dup dup 1 do over + loop swap drop then ;

  10. 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)
    
  11. 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))
    
  12. x0j0c said
    _start:
    	mov	ecx, 5	; the number to square
    	xor	ebx, ebx
    	mov	eax, ecx
    .sum:
    	add	ebx, eax
    	loop	.sum
    
    	;; ebx now contains the square
    	mov	eax, 1
    	int	0x80
    
  13. 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)))))
    
  14. XtremePrime said

    [Java]

    private int squared(int n){
    int result = 0;
    for(int i = 0; i < n; ++i){
    result += n;
    }
    return result;
    }

  15. spainmc said

    JavaScript


    function OddSquare(n) {
    var result = 0;
    for (var i = 0; i < n; i++) {
    result += n;
    }
    return result;
    }

    http://jsfiddle.net/jpkmt/

  16. #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)))
    
    
  17. Eitan said

    Java
    int square(int n){
    int sum = n;
    for(int i = 1; i < n; i++){
    sum += n;
    }
    return sum;
    }

  18. 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;
    }
    
  19. 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.

  20. skuba713 said

    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()
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: