c - Issue finding last digits of the nth term in the Fibonacci sequence -

i wrote code determine nth fibonacci number using nice blog post given in accepted answer question: finding out nth fibonacci number large 'n'. doing way of practising more difficult recursion problem given on projecteuler not relevant. method relies on changing problem small linear algebra problem of form

fn = t^n f1

where f1 = (1 1)^t , fn contains nth , (n-1)th fibonacci number. term t^n can determined in o(log n) time. implemented succesfully , seems work fine. when perform matrix exponentiation use %10000 last 4 digits only, seems work (i checked against large fibonacci numbers). however, wanted try more last digits increasing number 10000. doesn't seem work however. no longer correct answer. here code

#include<stdio.h> #include<math.h> #include<stdlib.h>  const unsigned long m = 10000;  unsigned long int * matprod(unsigned long int * a, unsigned long int * b){   unsigned long int * c;   c = malloc(4*sizeof(unsigned long int));   c[0] = ((a[0]*b[0]%m) + (a[1]*b[2]%m)) % m;   c[1] = ((a[0]*b[1]%m) + (a[1]*b[3]%m)) % m;   c[2] = ((a[2]*b[0]%m) + (a[3]*b[2]%m)) % m;   c[3] = ((a[2]*b[1]%m) + (a[3]*b[3]%m)) % m;   return c; }  unsigned long int * matexp(unsigned long int *a, unsigned long int n){   if (n==1){     return a;   }   if (n%2==0){     return matexp(matprod(a,a),n/2);   }   return matprod(a,matexp(a,n-1)); }  unsigned long int findfib(unsigned long int n){   unsigned long int a[4] = {0, 1, 1, 1};   unsigned long int * c;   c = malloc(4*sizeof(unsigned long int));   c = matexp(a,n-2);   return (c[2]+c[3]); }  main(){   unsigned long int n = 300;   printf("%ld\n",findfib(n)); } 

there several issues there regards proper coding conventions , things can improved. thought changing long int might solve problem not seem trick. problem increasing m instance 1000000 not give me more digits instead gives me nonsense. mistake making?

p.s. sorry poor math formatting, used math.stackexchange.

the issue running on system long 32-bits in size, believe case windows. can check compiling , running printf("%d\n", sizeof(long)) should output 4.

since m=1000000=10^6, product of 2 numbers smaller m can go 10^12, overflow issues when computing matrix entries since unsigned long can hold @ 2^32-1 or 4 * 10^9.

to fix using unsigned long long type instead of unsigned long. or better yet, uint64_t, guaranteed 64-bits in platforms (and require #include <stdint.h>). should make code work m sqrt(2^64)~10^9. if need bigger you'll need use big integer library.