2
$\begingroup$

I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this already exists / does it have a name?

I put comments in the code that explain the whole idea. But I will TL;DR here: TL;DR - Algorithm to compute square (power of 2) of a given number N recursively, given the property that (N+1)^2 == N^2 + 2N + 1,

and that the "forward" delta of (N+1)^2 - N^2 == N^2 + 2N + 1 - N^2 == 2N + 1,

and if we replace N with N-1, we get the "backward" delta of 2N - 1.

To be clearer: Forward delta of (N)=3 to (N+1) == 2N+1, or 7 And the Backward delta of (N)=3 to (N-1) == 2N-1, or 5

Square(3) -> Square(4) [ForwardDelta]: This means that if I have Square(3) and want Square(4), we do Square(3) + ForwardDelta(3) == (9 + 7) == 16 -> Square(4)

Square(3) -> Square(2) [BackwardDelta]: This means that if I have Square(3) and want Square(2), we do Square(3) - BackwardDelta(3) == (9 - 5) == 4 -> Square(2)

I have the code on github: https://github.com/CobraCoral/recursive_square

And also posting here if you feel too lazy to click :)

#!/usr/bin/env python3
"""Computes square number of N recursively, without multiplication.

Problem: We want to know N^2 without doing N*N.

Axiom 1: Square of 0 is 0 (zero product property).
Axiom 2: Square of 1 is 1. (as 1 is the identity for multiplication).
Axiom 3: Square of -1 is 1. (as negative multiplied by negative is positive).
Axiom 4: Square of (N+1) = N^2 + 2N + 1 (the quadratic polynomial formula).

Knowing from Quadratic Formula that (N+1)^2 = N^2 + 2N + 1,
let's call X=N+1 and Y=N. We have then:
    X^2 = Y^2 + 2Y + 1

Another way to see it is by looking at the delta of two consecutive square numbers:
(N+1)^2 - N^2 = N^2 +2N +1 - N^2 => 2N + 1

So 2N + 1 is the arithmetic series of odd numbers.

The deltas of each number follow an this progression of +2 always,
starting at 1 for 1 square.

So the arithmetic progression is:
          N:    1  2  3  4  5   6   7   8   9  10
Progression:    1, 3, 5, 7, 9, 11, 13, 15, 17, 19
Therefore, for a given number N, the progression is (2*N)-1,
or in other words, 2*(N-1) + 1.
(i.e. 1 + 2+2+...+2 n-1 times).

So we see that for each number N, its power of 2 will be the power of two
of the previous number, plus a constant (always a factor of 2).

And the square of each number is always the progression, plus the previous
number squared, recursively as follows:
    Progression(N) = Progression(N-1) + 2 => (N*2-1)
         Square(N) = Progression(N) + Square(N-1), for every N.
NOTE: As we will be using recursion and we want to avoid multiplications, we will assume N>=1.


N                Prog    Square  Result
.
.
-2          =      -5,  (-5 + 9)  {  4}
-1          =      -3,  (-3 + 4)  {  1}
0           =      -1,  (-1 + 1)  {  0}
1           =       1,  ( 1 + 0)  {  1}
2           =       3,  ( 3 + 1)  {  4}  -> 3 is previous Prog (1) + 2
3           =       5,  ( 5 + 4)  {  9}  -> 5 is previous Prog (3) + 2
4           =       7,  ( 7 + 9)  { 16}  -> 7 is prev. Prog (5) + 2
5           =       9,  ( 9 + 16) { 25}  -> and so on...
6           =      11,  (11 + 25) { 36}
7           =      13,  (13 + 36) { 49}
8           =      15,  (15 + 49) { 64}
9           =      17,  (17 + 64) { 81}
10          =      19,  (19 + 81) {100}
.
.
.
etc

In this script we have a few methods to compute the above, as follows:
1) How to compute square numbers of a number, with recursion and the properties
   of the square numbers of the previous number
   (i.e. we compute N**2 by computing (N-1)**2)
2) Using recursion with memoization
3) Using tail recursion, with memoization
4) And using function decorators to decorate the non-memoized tail recursion,
with memoization.
"""
import functools


def memoization_decorator(func):
    """Add simple memoization to a function."""
    @functools.wraps(func)
    def wrapper_decorator(*args, **kwargs):
        number = args[0]
        if number in memoization_decorator.dictionary.keys():
            return memoization_decorator.dictionary[number]
        # print("recursive square : memoized", number)
        square = func(*args, **kwargs)
        memoization_decorator.dictionary[number] = square
        return square
    return wrapper_decorator


memoization_decorator.dictionary = {1: (1, 1)}


@memoization_decorator
def recursive_square(number):
    """Compute the square of N as described by the recursive algorithm."""
    if number < 1:
        print("ERROR: N must be >= 1")
        return (None, None)
    if number == 1:
        return (1, 1)
    n_minus1_prog, n_minus1_square = recursive_square(number - 1)
    n_prog = n_minus1_prog + 2
    n_square = n_prog+n_minus1_square
    result = (n_prog, n_square)
    # print("recursive", number, result)
    return result

@memoization_decorator
def recursive_square_tail(number):
    """Compute tail recursive square of N."""
    # print("recursive square tail", number)
    def recursive_square_tail_full(number, prog, square):
        if number < 1:
            print("ERROR: N must be >= 1")
            return (None, None)
        # print(".... full", number, prog, square)
        if number == 1:
            return (prog, square)
        result = recursive_square_tail_full(number - 1,
                                            prog + 2,
                                            prog + square + 2)
        # print("     tail", number, result)
        return result
    return recursive_square_tail_full(number, 1, 1)


if __name__ == "__main__":
    def doit(forward=True):
        """Compute recursion and tail recursion, and prints results."""
        if forward:
            range_is = range(1,51)
        else:
            range_is = range(50, 0, -1)
        for num in range_is:
            recur = recursive_square(num)
            tail = recursive_square_tail(num)
            fmt_short = 'n^2({:^5}) = {:>5}  ... ({:^5})'
            fmt_long = '%s       ....     %s' % (fmt_short, fmt_short)
            if recur != tail:
                print(fmt_long.format(num, recur[1], recur[0],
                                      num, tail[1], tail[0]))
            else:
                print(fmt_short.format(num, recur[1], recur[0]))
    doit()
    doit(False)
    doit()
    doit(False)

```
$\endgroup$

2 Answers 2

2
$\begingroup$

This can be called an incremental algorithm, as it computes $n^2$ in terms of $(n-1)^2$. This is not efficient as it takes a number of operations proportional to $n$.

Honestly, I don't like much the idea of memoization because it consumes a lot of space and is of no use when you square a single number. Memoization seems to be "trendy" but should be used sparingly.

A non-recursive version is

N2= 0
for I= 0 TO N-1
  N2= N2 + I + I + 1

A faster solution can be built around the relations

  • $(2n)^2=4n^2=(n^2+n^2)+(n^2+n^2)$,
  • $(2n+1)^2=4n^2+4n+1=(n^2+n^2)+(n^2+n^2)+(n+n)+(n+n)+1$.

Now the idea is to write $n$ as a binary number and to rebuild it from left to right while computing the corresponding squares.

E.g. $11=1011_b$ and $1_b=1\to1$, $10_b=2\to1+1+1+1=4$, $101_b=5\to4+4+4+4+2+2+2+2+1=25$, $1011_b=11\to25+25+25+25+5+5+5+5+1=121$.

This time, the number of operations is proportional to the number of bits, which can be significantly smaller.

$\endgroup$
0
$\begingroup$

Your algorithm (even though I believe that you've worked out yourself) seems to have been built upon already well known facts

  1. Sum of first $n$ odd numbers always equals $n^2$
  2. The difference of $n^2$ and $(n+1)^2$ is the sum $n+(n+1)$ see more explanation here
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.