## Tuesday, February 15, 2011

### Triple test for Square!!!

This is a suggestion from Cleanthis Metaxas who wrote us on his email to check whether Recursive Functions are fast.
First we thing that they are usually slow, but we will check it for a specific problem: finding the square of an integer number.
Before that we have to inform you that recursive function is a useful tool in a programmers arsenal, in order to use dynamic programming for solving complicated problems.

We used 3 different pieces of code to find the fastest: Let's analyse them:
public class StraightTest
{
private static int sqr(int n)
{
return n*n;
}

public static void main(String[] args)
{
System.out.println(sqr(Integer.parseInt(args)));
}
}
------------------------------------------------------------------
This is a fast way of solving the problem and very very simple. It get's the number, multiplies it with itself and returns the result

public class ForTest
{
private static int sqr(int n)
{
int result = 1;
for (int i = 1; i<=2; i++) result *= n; return result; } public static void main(String[] args) { System.out.println(sqr(Integer.parseInt(args))); } } ----------------------------------------------------------- This is a more general way of doing it in the aspect of finding any power of a number. Since we are looking for the square we need to loop only twice. public class RecursiveTest { private static int sqr(int n) { if (n == 0) return 0; else return sqr(n - 1) + 2*(n-1) + 1; } public static void main(String[] args) { System.out.println(sqr(Integer.parseInt(args))); } } And this is the recursive function-> f(0) = 0, f(n+1) = f(n-1) + 2*(n-1) + 1
So it calls repeatedly itself until the whole result is found.
Seems slower than the others.

Out experiment will be done using the following numbers for each one:
0, 5, 100, 1000
But we see for this problem the disadvantage of that recursive function, as well as the for: they cannot return the square of a negative number. But this is totally fixable by using absolute so we skip that.

Let's observe our tests:

Input = 0

StraightTest:
real 0m0.825s
user 0m0.528s
sys 0m0.244s
--------------------------
ForTest:
real 0m0.891s
user 0m0.564s
sys 0m0.228s
--------------------------
real 0m0.911s
user 0m0.560s
sys 0m0.220s

The sys time is that we have to look. Since 0 returns 0 at once, recursive method was the fastest.
However, somebody would expect for to be slower than just a multiplication. But maybe our results are not so accurate because of the println. Let't remove it and try again:

StraightTest:
real 0m0.774s
user 0m0.528s
sys 0m0.212s
--------------------------
ForTest:
real 0m0.766s
user 0m0.552s
sys 0m0.180s
--------------------------
RecursiveTest
real 0m0.782s
user 0m0.576s
sys 0m0.172s

Well, recursive should be faster because it uses the less operations for finding zero. Now let's
check the other numbers too:

input = 5

StraightTest:
real 0m0.776s
user 0m0.572s
sys 0m0.168s
--------------------------
ForTest:
real 0m0.781s
user 0m0.548s
sys 0m0.196s
--------------------------
RecursiveTest
real 0m0.773s
user 0m0.564s
sys 0m0.176s

Let's use a medium number let's say:
input = 100

StraightTest:
real 0m0.773s
user 0m0.576s
sys 0m0.168s
--------------------------
ForTest:
real 0m0.773s
user 0m0.540s
sys 0m0.196s
--------------------------
RecursiveTest
real 0m0.782s
user 0m0.540s
sys 0m0.208s

And use a big number:

input = 1000

StraightTest:
real 0m0.780s
user 0m0.568s
sys 0m0.176s
--------------------------
ForTest:
real 0m0.766s
user 0m0.564s
sys 0m0.168s
--------------------------
RecursiveTest
real 0m0.773s
user 0m0.548s
sys 0m0.196s

So in general all results are pretty close. We can't be sure what is the fastest from those results:
All about computers are hypothesis if we do not know exactly how something works.
Java is a language that has a lot of noise, in the sense that, it interprets its bytecode on its virtual machine. Then garbage collector is also used, we don't know what happens exactly.

In our next experiment we'll use another language, so don't miss our article!

We should thank Cleanthis Metaxas for his idea.

You can also send us your experiments or ideas at: vaslabsco@gmail.com