1

I'm trying to rise to the nth power the (2x2) matrix in O(log_2(n)) operations. Matrix is defined as follows:

A= [y1 = 1 y2 = 2] [y3 = 1 y4 = 0]

I think I have some errors in my method of doing it. Any suggestions on how I can perform this operation?

#include <stdio.h>

int fnct(int n)
{
    int y1 = 1, y2 = 1, y3 = 1, y4 = 0; //entries of the A matrix 
    int z1, z2, z3, z4; //entries of the auxiliary matrix

                        // if n==0 return matrix it-self
    if (n == 0)
    {
        y1 = 1;
        y2 = 0;
        y3 = 1;
        y4 = 1;
        return y1, y2, y3, y4;
    }
    // if n mod 2 == 0 set y1,y2,y3,y4 to the fnct(n/2)
    if ((n % 2) == 0)
    {
        y1, y2, y3, y4 = fnct(n / 2);
        z1 = y1 * y2 + y2 * y3;
        z2 = y1 * y2 + y2 * y4;
        z3 = y3 * y1 + y4 * y3;
        z4 = y3 * y2 + y4 * y4;
        return z1, z2, z3, z4;
    }

    else if ((n % 2) == 1)
    {
        y1, y2, y3, y4 = fnct(n / 2);
        z1 = y1 * y1 + y2 * y3;
        z2 = y1 * y2 + y2 * y1;
        z3 = y3 * y1 + y4 * y3;
        z4 = y3 * y2 + y4 * y4;

        y1 = z1 + z3;
        y2 = z2 + z4;
        y3 = z1;
        y4 = z2;
        return z1, z2, z3, z4;
    }

    //return of the end of the function 
    return y1, y2, y3, y4;
}

int main()
{
    int n;
    printf("Enter n\n");
    scanf("%d", &n);
    printf("%d\n", fnct(n));
}
machine_1
  • 4,266
  • 2
  • 21
  • 42
  • 1
    I think you expect the `,` in C to do something different from what it actually does. Please consider reading https://stackoverflow.com/questions/52550/what-does-the-comma-operator-do – Mats May 09 '18 at 11:21
  • Possible duplicate of [Fast Matrix Exponentiation](https://stackoverflow.com/questions/12311869/fast-matrix-exponentiation) – DollarAkshay May 09 '18 at 14:43

0 Answers0