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 \sum_{i=1}^{n} i = \frac {n(n+1)}{2}. By distributing the multiplication through the addition and rearranging terms, this becomes n^2 = \left( 2 \sum_{i=1}^{n} i \right) - n. 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.

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 616 other followers

%d bloggers like this: