OJ Board

Posted: **Sun May 14, 2006 9:15 pm**

Hi ! I am having troubles in doing an implementation of a very common problem.
I have a matrix A and I want to get the matrix A^n. As far as I know the best way to do this is to make something like:
A^(n/2)*A^(n/2) if n mod 2==0
A^(n-1)*A if n mod 2 !=0
I get the idea of the recursive algorithm, but I don't know how to make an implementation of this, where to save the temporary results and some other little things that appears when I am trying to coding.
I get from the web this example:

^n
| 0 1 | = | fn-2 fn-1 |
| 1 1 | = | fn-1 fn |

means that the matrix [0 1]^n is equal to the matrix where fn = the
nth fibonacci number : [1 1]
I don't understand why this code make the implementation to get the nth fibonacci using the method explained above

Divide_Conquer_Fib(n) {
i = h = 1;
j = k = 0;
while (n > 0) {
if (n%2 == 1) { // if n is odd
t = j*h;
j = i*h + j*k + t;
i = i*k + t;
}
t = h*h;
h = 2*k*h + t;
k = k*k + t;
n = (int) n/2;
}
return j;
}

well, if someone can help me, I would appreciate very much
thanks!
bye

Posted: **Tue May 16, 2006 5:37 pm**

Hi!

Here's my code. Hope it helps!

Code: Select all

int odd(long x) {
   return ((x & 0x0001)!= 0);
}

void matrix_multiply(long aiMatrix1[][2], long aiMatrix2[][2], long aiResult[][2]) {
   long aiTemp[2][2];

   aiTemp[0][0]= aiMatrix1[0][0]*aiMatrix2[0][0] + aiMatrix1[0][1]*aiMatrix2[1][0];
   aiTemp[0][1]= aiMatrix1[0][0]*aiMatrix2[0][1] + aiMatrix1[0][1]*aiMatrix2[1][1];
   aiTemp[1][0]= aiMatrix1[1][0]*aiMatrix2[0][0] + aiMatrix1[1][1]*aiMatrix2[1][0];
   aiTemp[1][1]= aiMatrix1[1][0]*aiMatrix2[0][1] + aiMatrix1[1][1]*aiMatrix2[1][1];
   memcpy(aiResult, aiTemp, sizeof(aiTemp));
}

long fibonacci(long iNum) {
   long iTemp1, iTemp2;
   long aiResult[2][2]= {{1, 1}, {1, 0}};
   long aiMatrix[2][2]= {{1, 1}, {1, 0}};

   while (iNum> 0) {
      if (odd(iNum))
         matrix_multiply(aiResult,aiMatrix, aiResult);
      matrix_multiply(aiMatrix,aiMatrix, aiMatrix);
      iNum>>= 1;
   }
   return(aiResult[1][1]);
}

Posted: **Wed May 17, 2006 7:42 am**

First, try to understand this problem,

compute a^n with order log(n)

Code: Select all

int pow(int a,int n)
{
if (!n)return 1;
int t=pow(a,n/2);
return n%2?a*t*t:t*t;
}

Posted: **Sat May 20, 2006 1:19 am**

thanks for your help!
I made the problem of compute a^n with order log(n)...but I think it's easier.

OJ Board

help with divide & conquer problem

help with divide & conquer problem