Month: August 2005

The ridiculous fish blog recently posted an entry about using “random” large integers to calculate π. That post was in the context of getting blog commentators to enter two large integer values as a kind of CAPTCHA to keep out spammers automated commenting bots. The idea of calculating pi using just random sequences of integers was intriguing to me so I set about implementing it in JavaScript. I’ve included the functions used below:

First a fairly simple function that returns a random positive integer:

function randomPositiveInteger()
{
   return Math.round(Math.random() * (Math.pow(2, 31)-1));
}

Next a JavaScript implementation of the binary greatest common denominator algorithm followed by a simple coprime function that takes two positive integers and determines if they are coprime or not (by determining if the gcd is 1):

function gcd(u, v)
{
   var k = 0;
   while ((u & 1) == 0  &&  (v & 1) == 0)
   {
      u >>= 1;
      v >>= 1;
      k++;
   }
   do
   {
      if ((u & 1) == 0)
         u >>= 1;
      else if ((v & 1) == 0)
         v >>= 1;
      else if (u >= v)
         u = (u-v) >> 1;
      else
         v = (v-u) >> 1;
   } while (u > 0);
   return v << k;
}

function isCoprime(a, b)
{
   return gcd(a,b) == 1;
}
	

Finally the function that ties it all together; Note the assignment of properties to the function object so that the function can maintain a history of results without having to store variables outside its scope:

function nextPiEstimate()
{
   /* Initialise the properties used to hold the tallies if required. */
   if (nextPiEstimate.totalCoprimePairs == null)
   {
      nextPiEstimate.totalCoprimePairs = 0;
   }
   if (nextPiEstimate.totalPairs == null)
   {
      nextPiEstimate.totalPairs = 0;
   }

   /* Generate two random integers */
   var a = randomPositiveInteger();
   var b = randomPositiveInteger();
   nextPiEstimate.totalPairs++;

   /* Determine if we are dealing with a coprime pair or not */
   if (isCoprime(a,b))
   {
      nextPiEstimate.totalCoprimePairs++;
   }

   /* Determine the percentage of pairs that were prime and calculate Pi */
   var invertedPercentage = nextPiEstimate.totalPairs / nextPiEstimate.totalCoprimePairs;
   var pi = Math.sqrt(invertedPercentage * 6);

   return pi
}
	

See the code in action