Fibonacci with matrixes and recursive powers

m[][]=AlgoritmiMatrici.identita(2);-->it generates the 2x2 identity matrix

AlgoritmiMatrici.prodotto(m,m);-->is the result of the multiplication between m and m

This code should calculate the umteenth number of Fabionacci series, but it alwyas returns 1.

Can anyone help me?

Code :

public static int matrice1(int n)
{
int m[][]=AlgoritmiMatrici.identita(2);
potenzamatrice(m, n-1);
return m[0][0];
}
public static void potenzamatrice(int[][] m, int n)
{
if(n>1)
{
potenzamatrice(m, n/2);
m=AlgoritmiMatrici.prodotto(m,m);
}
if(n%2==1)
{
int a[][]={{1,1},{1,0}};
m=AlgoritmiMatrici.prodotto(m,a);
}
}

Re: Fibonacci with matrixes and recursive powers

Hey Enrico,

Can you please post what your **prodotto **method does? Seems like your multi dimensional integer array is getting filled after the call to prodotto method i.e AlgoritmiMatrici.prodotto(m,m);.

From the code, seems like what you are returning is the 1st element of your 1st array [return m[0][0];]. So may be there is a possibility that your prodotto method is populating the values in such a way that it always happens to be ''1" at the first element.

I hope you are getting me.

Goldest

Re: Fibonacci with matrixes and recursive powers

Here you are.

It returns a matrix which is the multiplication between two matrixes

Code :

public static int [][] prodotto(int t1[][],int t2[][]) {
//it is possible only if t1[0].length = t2.length
int n = t1.length;
int m = t2[0].length;
int prod[][] = new int [n][m];
for (int i=0 ; i<n; i++)
for (int k=0; k<m ; k++){
int s=0;
for (int r=0;r<t1[0].length;r++)
s=s+t1[i][r]*t2[r][k];
prod[i][k]=s;
}//end for
return prod;
}//fine prodotto

Re: Fibonacci with matrixes and recursive powers

The array passed to one of the functions is being recreated and the caller expects the change to take effect on the passed object, which does not happen in java. Take the following as an example:

Code java:

public static void main(String[] args){
int[] m = new int[10];
for ( int i = 0; i < 10; i++ ){
m[i] = -1;
}
test(m);
System.out.println(m[0]);
}
public static void test(int[] m){
int v[] = new int[10];
for ( int i = 0; i < m.length; i++ ){
v[i] = 1;
}
m = v;
}

Will print -1

Re: Fibonacci with matrixes and recursive powers

Ok.

I tried to return the value of the matrix after the product, but the result is always the same...