Brainbench perl test?
David Cantrell
david at cantrell.org.uk
Wed Sep 5 23:25:56 BST 2012
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
More information about the london.pm
mailing list