Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

ENTERPRISE LEVEL FIBS

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]

Name: Anonymous 2009-12-04 20:01

Whoops, fucked the first [code] tag up.
how does Prague like my ENTERPRISE LEVEL fibs() implementation?

#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;
}

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List