Itérateurs et applications

iterateurs.c

#include<stdio.h>

/*------------------------------------------*/

typedef struct
{
  unsigned long first;
  unsigned long second;
}couple;

/*------------------------------------------*/

typedef struct
{
  unsigned long _11, _12, _21, _22;
}quadruplet;

/*------------------------------------------*/

couple applyF(couple (*f)(couple), int n, couple x)
{
  if (n == 0)
    return x;
  return f(applyF(f, n - 1, x));
}

/*------------------------------------------*/

couple applyFT(couple (*f)(couple), int n, couple x)
{
  if (n == 0)
    return x;
  return applyF(f, n-1, f(x));
}

/*------------------------------------------*/

unsigned long multiplie(unsigned long a, unsigned long b)
{
  couple x = {0, a};
  couple f(couple x)
    {
      couple y = {x.first + x.second, x.second};
      return y;
    }
  return applyFT(f, b, x).first;
}

/*------------------------------------------*/

unsigned long factorielle(unsigned long n)
{
  couple x = {n, 1};
  couple f(couple x)
    {
      couple y = {x.first - 1, x.first*x.second};
      return y;
    }
  return applyFT(f, n, x).second;
}

/*------------------------------------------*/

unsigned long puissance(unsigned long b, unsigned long n)
{
  couple x = {1, b};
  couple f(couple x)
    {
      couple y = {x.first * x.second, x.second};
      return y;
    }
  return applyFT(f, n, x).first;
}

/*------------------------------------------*/

unsigned long fastPuissance(unsigned long b, unsigned long n)
{
  if(n == 0)
    return 1;
  if (n % 2)
      return b * fastPuissance(b*b, n/2);
  return fastPuissance(b*b, n/2);
}

/*------------------------------------------*/

unsigned long applyFD(int (*delta)(int k), 
		      unsigned long (*f)(couple), int n, unsigned long x)  
{
  couple y;
  if (n == 0)
    return x;
  y.first = n;
  y.second = applyFD(delta, f, delta(n), x);
  return f(y);
}

/*------------------------------------------*/

unsigned long slowPuissanceIT(unsigned long b, unsigned long n)
{
  unsigned long f(couple x)
    {
      return  x.second*b;
    }
  int delta(int x)
    {
      return x - 1;
    }
  return applyFD(delta, f, n, 1);
}

/*------------------------------------------*/

unsigned long factorielleIT(unsigned long n)
{
  unsigned long f(couple x)
    {
      return  x.first * x.second;
    }
  int delta(int x)
    {
      return x - 1;
    }
  return applyFD(delta, f, n, 1);
}

/*------------------------------------------*/

unsigned long fastPuissanceIT(unsigned long b, unsigned long n)
{
  unsigned long f(couple x)
    {
      if (x.first % 2)
	return b*x.second*x.second;
      return x.second*x.second;
    }
  int delta(int x)
    {
      return x/2;
    }
  return applyFD(delta, f, n, 1);
}

/*------------------------------------------*/

quadruplet fiboMat()
{
  quadruplet q = {1, 1, 1, 0};
  return q;
}

/*------------------------------------------*/

quadruplet identite()
{
  quadruplet q = {1, 0, 0, 1};
  return q;
}

/*------------------------------------------*/

quadruplet multMat(quadruplet x, quadruplet y)
{
  quadruplet xy;
  xy._11 = x._11*y._11 + x._12*y._21;
  xy._21 = x._21*y._11 + x._22*y._21;
  xy._12 = x._11*y._12 + x._12*y._22;
  xy._22 = x._21*y._12 + x._22*y._22;
  return xy;
}

/*------------------------------------------*/

quadruplet applyFDQ(unsigned long (*delta)(unsigned long), 
		      quadruplet (*f)(unsigned long, quadruplet), 
		      unsigned long n, quadruplet x)   
{
  if (n == 0)
    return x;
  return f(n, applyFDQ(delta, f, delta(n), x));
}

/*------------------------------------------*/

quadruplet matPow(quadruplet x, unsigned long n)
{
  quadruplet f(unsigned long m, quadruplet q)
    {
      quadruplet qPrime = multMat(q, q);
      if (m % 2)
	return multMat(x, qPrime);
      return qPrime;
    }
  unsigned long delta(unsigned long x)
    {
      return x/2;
    }
  return applyFDQ(delta, f, n, identite());  
}

/*------------------------------------------*/

couple multMatVec(quadruplet x, couple y)
{
  couple xy;
  xy.first = x._11*y.first + x._12*y.second;
  xy.second = x._21*y.first + x._22*y.second;
  return xy;
}

/*------------------------------------------*/

unsigned long fastFibonacciIT(unsigned long l)
{
  quadruplet q = fiboMat();
  couple c = {1, 0};
  c = multMatVec(matPow(q, l), c);
  return c.second;
}

/*------------------------------------------*/

int main()
{
  int i;
  for(i = 0 ; i <= 45 ; i++)
    {
      printf("F_%d = %ld\n", i, fastFibonacciIT(i));
    } 
 return 0;
}