Now that I've had some time to kick it around, this is actually a great example. My Python program solves the sample problem in 1 second. In Perl, using Math::BigInt with the default backend, it takes 10 seconds. With the GMP backend, 5 seconds. With Math::GMP, 1 second, same as Python. By resorting to vile trickery, I was able to get the Perl to run in 0.5 seconds with no modules at all. Here's the kicker, though: the Python program runs in 0.1 second under PyPy (basically JIT compiled Python). | [reply] |

Talking about JIT, maybe try benchmarking a JS version too. :)
Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!
}
| [reply] |

| [reply] |

| [reply] |

Well, I hate to post a complete solution to one of their problems, so I've changed it around. The question is, given the first 10 outputs of this pseudo-random number generator:
`for (1..10) {
$s = ($s*0x5deece66d + 0xb) % 2**48;
say(($s>>17)%1000);
}
`
Find the initial value of the seed $s, which is a randomly-chosen number less than 2**17. Here are the comparisons of a brute-force search using several different modules:
` s/iter BigInt BigIntGMP GMP Perl
BigInt 25.0 -- -42% -94% -100%
BigIntGMP 14.4 73% -- -90% -99%
GMP 1.47 1605% 885% -- -93%
Perl 0.110 22701% 13070% 1238% --
`
I'm running perl 5.24.1 on an aging MacBook. I could make the Perl faster, but it would require a 64-bit perl build. You could probably get good performance with Math::Int64, but I'll leave that as an exercise for the reader. Python is running in time comparable to the pure-Perl, and PyPy smokes them all at under a millisecond. Full code is below. You don't need to tell me that my benchmarking methodology is bad.
| [reply] [d/l] [select] |

Oh look, it's basically the same problem I solved in my old node, Predict Random Numbers. Fifteen years ago. Back then, there wasn't so much information available online, so I actually had to get on my bike and ride to the Stanford math department library to find that algorithm.
That problem involves 48-bit numbers, which really aren't all that big. Maybe try something in the Number Theory category.
Update: Haha, we didn't have youtube back then either.
| [reply] |

| [reply] |

Comment onRe^5: solve cubic equations (Java)DownloadCode