So I decided to dig deeper. Basically the standard crand() is not that good. So instead I searched for the fastest Mersenne Twister there is. I downloaded the latest code and compiled it in the fastest way for my architecture.
And after all that trouble we got the performance down to 18 seconds. Still slower that Julia‘s 16 seconds.
$ time ./eulerfast
Euler : 2.71824
Probably, we could do a bit better with more tweaks, and probably exceed Julia‘s performance with some effort. But at that point, I got tired of pushing this further. The thing I love about Julia is how well it is engineered and hassle free. It is quite phenomenal the performance you get out of it, with so little effort. And for basic technical computing things, like random number generation, you don’t have to dig hard for a better library. The “batteries included” choices in the Julia‘s standard library are pretty good.
it is quite nice though that you can rely on the quality of Base for numerics.
$ time ./a.out
Euler : 2.71829
For the curios, I am using this version of Julia
Julia Version 0.6.3-pre.0
Commit 93168a6 (2017-12-18 07:11 UTC)
OS: Linux (x86_64-linux-gnu)
CPU: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
LLVM: libLLVM-3.9.1 (ORCJIT, haswell)
Now one should not put too much emphasis on such micro benchmarks. However, I found this a very curious examples when a high level language like Julia could be twice as fast a c. The Julia language authors must be doing some amazing mojo.
I came across a neat math puzzle involving counting the number of unique combinations in a hypothetical lock where digit order does not count. Before you continue, please watch at least the first minute of following video:
The rest of the video describes two related approaches for carrying out the counting. Often when I run into complex counting problems, I like to do a sanity check using brute force computation to make sure I have not missed anything. Julia is fantastic choice for doing such computation. It has C like speed, and with an expressiveness that rivals many other high level languages.
Without further ado, here is the Julia code I used to verify my solution the problem.
d=digits(i,10,n)# The digits on an integer in an array with padding
ds=d |>sort|>join# putting the digits in a string after sorting
println("The number of unique digits is $(length(pat_lookup))")
In line 2 we create a dictionary that we will be using to check if the number fits a previously seen pattern. The loop starting in line 3, examines all possible ordered combinations. The digits function in line 4 takes any integer and generate an array of its constituent digits. We generate the unique digit string in line 5 using pipes, by first sorting the integer array of digits and then combining them in a string. In line 6 we check if the pattern of digits was seen before and make use of quick short short-circuit evaluation to avoid an if-then statement.