/*

Shor's Factoring Algorithm, probability of measurement y,
from equation (3.50),  N. David Mermin, Lecture Notes on Quantum Computation.
http://www.lassp.cornell.edu/mermin/qcomp/chap3.pdf

*/

#include <stdio.h>
#include <math.h>

#define n 8
#define q (1<<n)
#define r 10
#define m (q/r)

int main( void)
{
  int k, y; double p, real, imag, pi = 4*atan(1);

  for( y = 0; y < q; ++y)
  {
    real = imag = 0;
    for( k = 0; k < m; ++k)
    {
      real += cos( 2*pi*k*r*y/q);
      imag += sin( 2*pi*k*r*y/q);
    }

    p = (real*real + imag*imag)/(q*m);

    printf( "%i %g\n", y, p);
  }

  return 0;
}