# [Rehovot-pm] Speeding up processing

lsprilus at bioinformatics.weizmann.ac.il lsprilus at bioinformatics.weizmann.ac.il
Mon Oct 28 00:12:16 CST 2002

```Sometimes we can speed up processing by avoiding repeated calculations
or processing already known data. A hash is an excellent data structure for
this purpose. There are also some perl modules to extend this principle,
but let's take a look to a simple solution:

A brief description:
The Fibonacci series is formed by adding the latest two numbers to get
the next one, starting from 0 and 1:

0 1 --the series starts like this.
0+1=1 so the series is now
0 1 1
1+1=2 so the series continues...
0 1 1 2 and the next term is
1+2=3 so we now have
0 1 1 2 3  and it continues as follows ...

n:  0  1  2  3  4  5  6  7  8  9 10 11  12  13  14  15  16 ...
Fib(n):  0  1  1  2  3  5  8 13 21 34 55 89 144 233 377 610 987 ...

How can we generate the Fibonacci series:
There are several formulas to compute this series. We will try a simple
recursive approach in this fiboPlain.pl that will print the values for
the positions 25 to 35 in the Fibonacci series.

#!/usr/local/bin/perl
# plain recursive Fibonacci series, J Prilusky, 2002
\$|=1;

foreach \$position (25 .. 35) {
printf ("%03d %30d\n",\$position,fibo(\$position));
}

sub fibo {
my(\$n) = @_;
return 0 if (\$n == 0);
return 1 if (\$n == 1);
return fibo(\$n-1) + fibo(\$n-2);
}

How this works?:
The fibo subroutine does all the job by calling himself as a tool. Nice example
of recursion.

Can we speed this up?:
A close examination shows that at any step we are computing twice the same
values. We can store known values in a hash, as to avoid repeated calculation
of the same values, in this fiboCache.pl

#!/usr/local/bin/perl
# cached recursive Fibonacci series, J Prilusky, 2002
\$|=1;

foreach \$position (25 .. 35) {
printf ("%03d %30d\n",\$position,fibo(\$position));
}

sub fibo {
my(\$n) = @_;
return 0 if (\$n == 0);
return 1 if (\$n == 1);
\$cache{\$n} = fibo(\$n-1) + fibo(\$n-2) if (!\$cache{\$n}); # <== HERE
return \$cache{\$n};
}

Try them both and see the difference.
The trick is to ONLY compute a value for a given position if we haven't
done it before. For each call of the fibo subroutine, we test to see
has a value, we don't need to compute it again.

The same caching technique can be used on several other situations.

--
Dr Jaime Prilusky                | Jaime.Prilusky at weizmann.ac.il
Weizmann Institute of Science    | fax: 972-8-9344113
76100 Rehovot - Israel           | tel: 972-8-9344959

info URL http://bioinformatics.weizmann.ac.il/jaime_prilusky.html
OCA is at http://bioinformatics.weizmann.ac.il:8500

```