Perl: the Markov chain saw  
PerlMonks 
comment on 
( #3333=superdoc: print w/replies, xml )  Need Help?? 
Here's my take on it. Highlights: use Eratosthenes' sieve to determine a factor or primality for integers up to the max required; work out when an additional numerator or denominator kicks in (@switch), and pass over the numbers in reverse order, so each need be visited only once; build up two BigInts for numerator and denominator and just switch to BigFloats to divide the two at the end. The single division at the end takes over 2/3 of the total time, so I'd expect using GMP or Pari for the maths would cut it greatly:
Things that made negligible difference: dropping accuracy to 40 (!); initialising my $bii = Math::BigInt>new($i) before the multiply loops; the $r>bsstr call. I noticed that the numerator consists of 855 prime factors comprising 755 distinct primes; the denominator has 2308 of which 2306 are distinct. No surprise, then, that bpow() isn't a win. Here's the code:
Hugo In reply to Re^2: Algorithm for cancelling common factors between two lists of multiplicands
by hv

