Brainbench perl test?

[David Cantrell]

On Wed, Sep 05, 2012 at 09:51:27PM +0100, Gordon Banner wrote:

> Of course, almost all of them would use recursion, and my real interest 
> was in the follow-on discussion "why did you do it that way?", and how 
> long it took them to twig that while factorials are a good illustration 
> of recursion, recursion isn't necessarily a good implementation of 
> factorials.

Nor's a naive iterative method though - it takes no time at all before
you overflow your ints and then (assuming that you're aware of this and use
bigints, instead of just doing a fandango on core^Wvariable) every
single operation after that is on bigints, and so is like trying to suck
molasses through a straw.

I've been working on-and-off on a way to reduce the number of bigint
operations, but I keep running into other expensive functions.  The best
I've come up with so far:
  * requires a function to return the nth prime
  * requires a function to return the number of primes less than n
      these are required to get a list of the factorial's factors. You
      could use a lookup table - but then, why not just have a table of
      factorials
  * is NP-complete if you want to really minimise bigint ops
      the knapsack problem, breaking that list into sub-lists whose
      products are all just under 2^32 (or 2^64, or ...).

And being NP-complete is the least of my problems, because the previous
two functions *don't exist yet* and very clever people have been failing
to find them for, oh, at least 150 years.

Oh, and it's wrong anyway, because it misses some repeated prime factors :-)

But hey, it's something to keep me out of trouble.

-- 
David Cantrell | Hero of the Information Age

Do not be afraid of cooking, as your ingredients will know and misbehave
   -- Fergus Henderson