# Fibonacci with matrixes and recursive powers

• December 27th, 2010, 01:18 PM
Enrico123
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);
}
}

• December 27th, 2010, 01:34 PM
goldest
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
• December 27th, 2010, 01:45 PM
Enrico123
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

• December 27th, 2010, 02:47 PM
copeg
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
• December 28th, 2010, 07:51 AM
Enrico123
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...