# Recursive Algorithm to compute Square numbers

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)

$$$$


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.

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