Name: Anonymous 2009-12-04 20:00
how does Prague like my ENTERPRISE LEVEL fibs() implementation?
[size]
#include <stdlib.h>
#include <stdio.h>
#define MATSIZE(n) n * n * sizeof(int)
void mprint(int *mat, int size) {
int i, j;
for(i = 0; i <size; ++i) {
for(j=0; j <size; ++j)
printf("%d ", mat[i * size + j]);
printf("\n");
}
}
int dotp(int *mat1, int row, int *mat2, int col, int size, int mod) {
int ind, prod = 0;
for(ind = 0;ind < size; ind++)
prod = (prod + mat1[row * size + ind] * mat2[ind * size + col]) % mod;
return prod;
}
int *mmul(int *matrix1, int *matrix2, int size, int mod) {
int row, col, *product = malloc(MATSIZE(size));
for(row = 0; row < size; row++)
for(col = 0; col < size; col++)
product[row * size + col] = dotp(matrix1, row, matrix2, col, size, mod);
return product;
}
/*runs in constant time w.r.t. pow*/
int *lpow(int *matrix, int size, int pow, int mod) {
int *val[32], *result, *old, ind, i, j;
val[0] = matrix;
for(ind = 1; ind < 32; ind++)
val[ind] = mmul(val[ind-1], val[ind-1], size, mod);
result = malloc(MATSIZE(size));
for(i=0;i<size;i++) for(j=0;j<size;j++) result[i * size + j] = (i == j);
for(ind = 0; ind < 32; ind++)
if(pow & 1<<ind) {
old = result;
result = mmul(result, val[ind], size, mod);
free(old);
free(val[ind]);
}
else
free(val[ind]);
return result;
}
/*calculates fibs(n) modulo mod*/
int fibs(int n, int mod) {
int *mat1, *prod, ret;
mat1 = malloc(MATSIZE(2));
mat1[0] = mat1[1] = mat1[2] = 1;
mat1[3] = 0;
prod = lpow(mat1, 2, n, mod);
ret = prod[1];
free(prod);
return ret;
}
int main(int anusc, char *anusv[]) {
printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n",
fibs(10, 16384),
fibs(100, 16384),
fibs(1000, 16384),
fibs(10000, 16384),
fibs(100000, 16384),
fibs(1000000, 16384),
fibs(10000000, 16384),
fibs(100000000, 16384)); /*modulus can be increased on 64-bit platforms*/
return 0;
}[/code]
[size]
#include <stdlib.h>
#include <stdio.h>
#define MATSIZE(n) n * n * sizeof(int)
void mprint(int *mat, int size) {
int i, j;
for(i = 0; i <size; ++i) {
for(j=0; j <size; ++j)
printf("%d ", mat[i * size + j]);
printf("\n");
}
}
int dotp(int *mat1, int row, int *mat2, int col, int size, int mod) {
int ind, prod = 0;
for(ind = 0;ind < size; ind++)
prod = (prod + mat1[row * size + ind] * mat2[ind * size + col]) % mod;
return prod;
}
int *mmul(int *matrix1, int *matrix2, int size, int mod) {
int row, col, *product = malloc(MATSIZE(size));
for(row = 0; row < size; row++)
for(col = 0; col < size; col++)
product[row * size + col] = dotp(matrix1, row, matrix2, col, size, mod);
return product;
}
/*runs in constant time w.r.t. pow*/
int *lpow(int *matrix, int size, int pow, int mod) {
int *val[32], *result, *old, ind, i, j;
val[0] = matrix;
for(ind = 1; ind < 32; ind++)
val[ind] = mmul(val[ind-1], val[ind-1], size, mod);
result = malloc(MATSIZE(size));
for(i=0;i<size;i++) for(j=0;j<size;j++) result[i * size + j] = (i == j);
for(ind = 0; ind < 32; ind++)
if(pow & 1<<ind) {
old = result;
result = mmul(result, val[ind], size, mod);
free(old);
free(val[ind]);
}
else
free(val[ind]);
return result;
}
/*calculates fibs(n) modulo mod*/
int fibs(int n, int mod) {
int *mat1, *prod, ret;
mat1 = malloc(MATSIZE(2));
mat1[0] = mat1[1] = mat1[2] = 1;
mat1[3] = 0;
prod = lpow(mat1, 2, n, mod);
ret = prod[1];
free(prod);
return ret;
}
int main(int anusc, char *anusv[]) {
printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n",
fibs(10, 16384),
fibs(100, 16384),
fibs(1000, 16384),
fibs(10000, 16384),
fibs(100000, 16384),
fibs(1000000, 16384),
fibs(10000000, 16384),
fibs(100000000, 16384)); /*modulus can be increased on 64-bit platforms*/
return 0;
}[/code]