serious stuff
www.cubbi.com
personal
programming
fibonacci numbers
algorithms
benchmarks
forth examples
postscript examples
muf examples
joy examples
j examples
scheme examples
hope examples
ocaml examples
haskell examples
prolog examples
c++ examples
java examples
assembly language examples
fortran examples
c examples
sh examples
awk examples
perl examples
tcl examples
asmix
hacker test
resume
science
martial arts
fun stuff
www.cubbi.org
|
C
Date: 1972 (Standards: ANSI X3.159-1989, ISO/IEC 9899:1990, ISO/IEC 9899:1999)
Type: Imperative low-level language
Usage: Everything written for UNIX-based operating systems, and the majority of system and application software everywhere. This language also influenced the majority of languages after it, most notably C++ and Java.
ALGORITHM 1A: NAIVE BINARY RECURSION |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
int64_t fib(int n) {
return n<2 ? n : fib(n-1) + fib(n-2);
}
int64_t f(int n) {
if(n<0)
return n%2 ? fib(-n) : -fib(-n);
else
return fib(n);
}
void f_print(int n) {
printf("%dth Fibonacci number is %" PRId64 "\n",n,f(n));
}
int main(int argc, char** argv) {
if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
printf("Usage: f1a <n>\n");
else
f_print(atoi(argv[1]));
}
|
ALGORITHM 1B: CACHED BINARY RECURSION / MEMOIZATION |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
void free_mpzp(mpz_t* mp) {
mpz_clear(*mp);
free(mp);
}
mpz_t* fib_m(int n, mpz_t** m) {
if(m[n]) return m[n];
mpz_t *r=malloc(sizeof(mpz_t));
if(n<2) {
mpz_init_set_si(*r, n);
} else {
mpz_init(*r);
mpz_t* f1 = fib_m(n-1, m);
mpz_t* f2 = fib_m(n-2, m);
mpz_add(*r, *f1, *f2);
}
m[n]=r;
return r;
}
mpz_t* fib(int n) {
mpz_t** m = calloc(n+1,sizeof(mpz_t*));
mpz_t* r = fib_m(n, m);
for(int i=0; i<n; i++)
if(m[i]) free_mpzp(m[i]);
free(m);
return r;
}
mpz_t* f(int n) {
if(n>=0) return fib(n);
mpz_t* f = fib(-n);
if(n%2) return f;
mpz_t* ng = malloc(sizeof(mpz_t));
mpz_init(*ng);
mpz_neg(*ng, *f);
free_mpzp(f);
return ng;
}
void f_print(int n) {
mpz_t* f_n = f(n);
char* result = mpz_get_str(NULL, 10, *f_n);
printf("%dth Fibonacci number is %s\n", n, result);
free_mpzp(f_n);
free(result);
}
int main(int argc, char** argv) {
if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
printf("Usage: f1b <n>\n");
return 1;
} else {
f_print(atoi(argv[1]));
return 0;
}
}
|
ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST |
#include <stdio.h>
#include <stdlib.h>
struct FL {
unsigned int f;
struct FL* next;
};
struct FL* fl_init(void) {
struct FL* fl_h;
fl_h = (struct FL*)calloc(1,sizeof(struct FL));
fl_h->next = (struct FL*)calloc(1,sizeof(struct FL));
fl_h->f = fl_h->next->f = 1;
return fl_h;
}
unsigned int fl_get(struct FL* fl_h, int n)
{
int i;
struct FL* fl;
fl=fl_h;
for(i=0; (fl->next!=NULL) && (i<n); i++, fl=fl->next);
for(; i<n; i++, fl=fl->next) {
fl->next=(struct FL*)calloc(1,sizeof(struct FL));
fl->next->f=fl_get(fl_h,i-1)+fl_get(fl_h,i);
}
return fl->f;
}
void f_print(int n) {
struct FL* fl;
fl=fl_init();
printf("%dth Fibonacci number is %lu\n",n,fl_get(fl,n));
}
int main(void) {
f_print(46);
return 0;
}
|
ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATORS |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
void free_mpzp(mpz_t* mp) {
mpz_clear(*mp);
free(mp);
}
mpz_t* fib_rec(mpz_t* x1, mpz_t* x2, int n) {
mpz_add(*x1,*x1,*x2);
mpz_swap(*x1,*x2);
if(n<2) {
free_mpzp(x1);
return x2;
} else
return fib_rec(x1, x2, n-1);
}
mpz_t* fib(int n) {
mpz_t* x1 = malloc(sizeof(mpz_t));
mpz_init_set_si(*x1, 0);
if(!n) return x1;
mpz_t* x2 = malloc(sizeof(mpz_t));
mpz_init_set_si(*x2, 1);
return fib_rec(x1, x2, n-1);
}
mpz_t* f(int n) {
if(n>=0) return fib(n);
mpz_t* f = fib(-n);
if(n%2) return f;
mpz_t* ng = malloc(sizeof(mpz_t));
mpz_init(*ng);
mpz_neg(*ng, *f);
free_mpzp(f);
return ng;
}
void f_print(int n) {
mpz_t* f_n = f(n);
char* result = mpz_get_str(NULL, 10, *f_n);
printf("%dth Fibonacci number is %s\n", n, result);
free_mpzp(f_n);
free(result);
}
int main(int argc, char** argv) {
if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
printf("Usage: f2b <n>\n");
return 1;
} else {
f_print(atoi(argv[1]));
return 0;
}
}
|
ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
void free_mpzp(mpz_t* mp) {
mpz_clear(*mp);
free(mp);
}
mpz_t* fib(int n) {
mpz_t* x1 = malloc(sizeof(mpz_t));
mpz_init_set_si(*x1, 0);
if(!n) return x1;
mpz_t* x2 = malloc(sizeof(mpz_t));
mpz_init_set_si(*x2, 1);
for(int i=1; i<n; i++) {
mpz_add(*x1,*x1,*x2);
mpz_swap(*x1,*x2);
}
free_mpzp(x1);
return x2;
}
mpz_t* f(int n) {
if(n>=0) return fib(n);
mpz_t* f = fib(-n);
if(n%2) return f;
mpz_t* ng = malloc(sizeof(mpz_t));
mpz_init(*ng);
mpz_neg(*ng, *f);
free_mpzp(f);
return ng;
}
void f_print(int n) {
mpz_t* f_n = f(n);
char* result = mpz_get_str(NULL, 10, *f_n);
printf("%dth Fibonacci number is %s\n", n, result);
free_mpzp(f_n);
free(result);
}
int main(int argc, char** argv) {
if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
printf("Usage: f2c <n>\n");
return 1;
} else {
f_print(atoi(argv[1]));
return 0;
}
}
|
ALGORITHM 3A: MATRIX EQUATION |
#include <stdio.h>
struct M2x2 { unsigned int a[2][2]; };
struct M2x2 m_mult(struct M2x2 M1, struct M2x2 M2) {
int i,j,k;
struct M2x2 R;
for(i=0; i<2; i++)
for(j=0; j<2; j++) {
R.a[i][j]=0;
for(k=0; k<2; k++)
R.a[i][j]+=M1.a[i][k]*M2.a[k][j];
}
return R;
}
struct M2x2 m_copy(struct M2x2 s) {
struct M2x2 d;
int i,j;
for(i=0; i<2; i++)
for(j=0; j<2; j++)
d.a[i][j]=s.a[i][j];
return d;
}
struct M2x2 m_pow(struct M2x2 a, int n) {
struct M2x2 b;
b=m_copy(a);
if(n>1) {
a=m_pow(a,n/2);
a=m_mult(a,a);
if(n%2) a=m_mult(a,b);
}
return a;
}
unsigned int f(int n) {
struct M2x2 a;
unsigned int r;
a.a[0][0]=a.a[0][1]=a.a[1][0]=1; a.a[1][1]=0;
a=m_pow(a,n);
r=a.a[0][0];
return r;
}
void f_print(int n) {
printf("%dth Fibonacci number is %lu\n",n,f(n));
}
int main(void) {
f_print(46);
return 0;
}
|
ALGORITHM 3B: FAST RECURSION |
#include <stdio.h>
void l(unsigned int* n1, unsigned int* n2, int n) {
unsigned int k1,k2;
if(n<=1) { *n1=1; *n2=1; return; }
if(n==2) { *n1=2; *n2=1; return; }
if(n%2) {
l(&k1,&k2,(n-1)/2);
*n1 = k1*(k1+k2) + k1*k2;
*n2 = k1*k1 + k2*k2;
} else {
l(&k1,&k2,(n/2)-1);
*n1 = (k1+k2)*(k1+k2) + k1*k1;
*n2 = (k1+k2)*k1 + k1*k2;
}
}
unsigned int f(int n) {
unsigned int n1, n2;
l(&n1,&n2,n);
return n1;
}
void f_print(int n) {
printf("%dth Fibonacci number is %lu\n",n,f(n));
}
int main(void) {
f_print(46);
return 0;
}
|
ALGORITHM 3C: BINET'S FORMULA |
#include <stdio.h>
#include <math.h>
unsigned int f(int n) {
if (n<2) return 1;
double phi = (1+sqrt(5))/2;
return (pow(phi, n+1) - pow(1-phi, n+1)) / sqrt(5);
}
void f_print(int n) {
printf("%dth Fibonacci number is %lu\n",n,f(n));
}
int main(void) {
f_print(46);
return 0;
}
|
|