Page 2 of 2

### Re: Code optimization techniques

Posted: Thu Jan 10, 2019 6:45 am
Final Report on my goal of an automated Stack History for Fibonacci by Memoization,
the complication for me being Memoization's use of a "lookup" table or cache, and
I wish to first thank MHealy and v6ph1 without whose generous insight
I'd still be struggling late into the night(s)...

Outputting only the incoming lookup[] table rows for/and
the calls of fib(n) generates the following and
suggests the Recursion "Tree" on the right:

```								    Recursion "Tree"
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]		    ***************

fib(5) called with above lookup[]:					(first call downward v) v 5
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with above lookup[]:							v 4
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with above lookup[]:						v 3 (last call upward ^)
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with above lookup[]:					v 2 ^
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with above lookup[]:				v 1 ^
lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(0) called with above lookup[]:			  0 ^
lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with above lookup[]:
lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]

fib(2) called with above lookup[]:
lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
(v)
fib(3) called with above lookup[]:
(v)
Fibonacci(5) = 5```

Which looks (humorously) straight-forward enough, however,
outputting more lookup[] table states proves
the Stack History not so obvious:

Expand

Fortunately for me v6ph1 kindly provided the following
(stark) Stack History, with still more annotations than
I am showing (and indeed with fewer steps than
I found for the simplest Fibonacci by Recursion:
17 vs 31 steps for fib(5)):

```	   fib: 5
fib: 5  	4
fib: 5  	4  	3
fib: 5  	4  	3  	2
fib: 5  	4  	3  	2  	1  		<-- lookup set to 1
fib: 5  	4  	3  	2
fib: 5  	4  	3  	2  		0	<-- lookup set to 0
fib: 5  	4  	3  	2  			<-- lookup set to 1 via fib(1)+fib(0)
fib: 5  	4  	3
fib: 5  	4  	3  		1*		<-- lookup = 1*
fib: 5  	4  	3  				<-- lookup set to 2 via fib(2)+fib(1)
fib: 5  	4
fib: 5  	4  		2*			<-- lookup = 1*
fib: 5  	4  					<-- lookup set to 3 via fib(3)+fib(2)
fib: 5
fib: 5  		3*				<-- lookup = 2*
fib: 5  						<-- lookup set to 5 via fib(4)+fib(3) and
returned as Fibonacci(5) = 5
* = lookup[n] already in lookup[]```

Using only the easily listed sequential calls to the fib function:
int fibCall[] = {5, 4, 3, 2, 1, 0, 1, 2, 3}; (and
not using the also easily output lookup table)
my code (last, below) replicates the above:

```   fib: [5, 0, 0, 0, 0, 0]
fib: [5, 4, 0, 0, 0, 0]
fib: [5, 4, 3, 0, 0, 0]
fib: [5, 4, 3, 2, 0, 0]
fib: [5, 4, 3, 2, 1, 0] <-- lookup set to 1
fib: [5, 4, 3, 2, 0, 0]
fib: [5, 4, 3, 2, 0, 0] <-- lookup set to 0
fib: [5, 4, 3, 2, 0, 0] <-- lookup set to 1 via fib(1)+fib(0)
fib: [5, 4, 3, 0, 0, 0]
fib: [5, 4, 3, 0, 1, 0] <-- lookup = 1*
fib: [5, 4, 3, 0, 0, 0] <-- lookup set to 2 via fib(2)+fib(1)
fib: [5, 4, 0, 0, 0, 0]
fib: [5, 4, 0, 2, 0, 0] <-- lookup = 1*
fib: [5, 4, 0, 0, 0, 0] <-- lookup set to 3 via fib(3)+fib(2)
fib: [5, 0, 0, 0, 0, 0]
fib: [5, 0, 3, 0, 0, 0] <-- lookup = 2*
fib: [5, 0, 0, 0, 0, 0] <-- lookup set to 5 via fib(4)+fib(3)
and returned as Fibonacci(5) = 5

* = lookup[n] already in lookup[]
RunTime = 0.0 Secs```

BOTTOM LINE: I understand Stacks better now but computing the nth Fibonacci term by
Memoization hardly shows the advantage of Memoization... In this case,
following the progression of the lookup[] cache, Memoization is a...
Hell of a way to mimic Fibonacci-by-Iteration, which
computes Fibonacci(5) in 4 steps, and has
none of the cripplings of recursion...

Code: Select all

``````import java.util.Arrays;

class GeekFibonacciMemoizationStackLean
{
public static void main(String args [ ])
{
double start = System.currentTimeMillis();

System.out.println();

int n = 5;
int size = n+1;
int fibpntr = 0;
int rowpntr = 0;
int colpntr = 5;
int stkpntr = 0;
int setbak1 = -1;
int setbak2 = -2;

int Stack[] = new int[size];

int fibCall[] = {5, 4, 3, 2, 1, 0, 1, 2, 3};
//0  1  2  3  4  5  6  7  8

int lookup[][] = new int[size];
//---------------------------------------------------------------------------------------------------------

for(int i = 0; i < lookup.length; i++)
{
for(int j = 0; j < size; j++)
{
lookup[i][j] = -1;
}
}
//---------------------------------------------------------------------------------------------------------

for(int i = 0; i < size; i++)
{
if(lookup[i][i] == -1 && fibCall[i] > 1)
{
Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack));

fibpntr += 1;;
stkpntr += 1;
rowpntr += 1;
colpntr = fibCall[fibpntr];
}
}
//---------------------------------------------------------------------------------------------------------

while(lookup[rowpntr][n] == -1)
{
if(lookup[rowpntr][fibCall[fibpntr]] != -1)
{
Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +fibCall[fibpntr]+ "] = " +
lookup[rowpntr][fibCall[fibpntr]]+ "*");

lookup[rowpntr+1] = lookup[rowpntr];

setbak1 = setbak2;
setbak2 = fibpntr;

Stack[stkpntr] = 0;
fibpntr -= 2;				//Alway after "*" case...
colpntr = fibCall[fibpntr];
rowpntr += 1;
stkpntr = fibpntr;
}
//---------------------------------------------------------------------------------------------------------

if(fibCall[fibpntr] <= 1 && lookup[rowpntr][colpntr] == -1)
{
Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +Stack[stkpntr]+ "] set to " +
Stack[stkpntr]);

lookup[rowpntr][colpntr] = fibCall[fibpntr];

setbak1 = setbak2;
setbak2 = fibpntr;

Stack[stkpntr] = 0;
if(fibCall[fibpntr] == 1) fibpntr -= 1;	//Note...
if(fibCall[fibpntr] == 0) fibpntr -= 2;	//Note...
colpntr = fibCall[fibpntr];
stkpntr = fibpntr;
}
//---------------------------------------------------------------------------------------------------------

else
{
if(fibCall[fibpntr] > 1 && !(fibpntr+1 == setbak1 && fibpntr+2 == setbak2))
{

System.out.println("   fib: " +Arrays.toString(Stack));

lookup[rowpntr+1] = lookup[rowpntr];

fibpntr += 2;			//Always after "No comment" case...
stkpntr = fibpntr;
colpntr = fibCall[fibpntr];
rowpntr += 1;
}
//---------------------------------------------------------------------------------------------------------

else
{

if(fibCall[fibpntr] > 1 && (fibpntr+1 == setbak1 && fibpntr+2 == setbak2))
{
int first = lookup[rowpntr][colpntr-1];
int secnd = lookup[rowpntr][colpntr-2];
int sum = first + secnd;

lookup[rowpntr][colpntr] = sum;

setbak1 = setbak2;
setbak2 = fibpntr;

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +fibCall[fibpntr]+ "] set to " +sum+
" via fib(" +(fibCall[fibpntr]-1)+
")+fib(" +(fibCall[fibpntr]-2)+ ")");

lookup[rowpntr+1] = lookup[rowpntr];

Stack[stkpntr] = 0;
if(fibpntr > 0)		//for Final Fibonacci fibpntr = 0...
fibpntr -= 1;		//Always after "set to" case...
stkpntr = fibpntr;
colpntr = fibCall[fibpntr];
rowpntr += 1;
lookup[rowpntr] = lookup[rowpntr-1];
}
}
}
}

System.out.println("                                and returned as Fibonacci(" +n+ ") = " +
lookup[rowpntr][n]);
System.out.println();
System.out.println("                                            * = lookup[n] already in lookup[]");
System.out.println();

double finish = System.currentTimeMillis();

System.out.println("RunTime = " + (finish - start)/1000 + " Secs");
}
}``````