Re:Munchausen Numbers and How to Find Them
by lokedhs on Wednesday September 21, 2016 @11:11PM
(#12554053)
I find it quite remarakable that Python is so popular with maths people, even though it's so horribly slow. I've seen similar differences between SBCL and Python quite often, when I have tried reimplmenting code like that in Common Lisp.
Re:Munchausen Numbers and How to Find Them
by hcarvalhoalves on Thursday September 22, 2016 @02:49AM
(#12554963)
> I find it quite remarakable that Python is so popular with maths people, even though it's so horribly slow.
It's popular because of Numpy/Scipy, then the speed of native loops doesn't matter.
This is an awfully long time to wait for something that is very clearly optimizable. If we are searching for Munchausen numbers, then we are probably going to do so in a brute force way. (We could optimize this with various symmetries, such as digit permutations, but let's ignore this for now.)
If we are going to brute force it, then we are probably not going to exceed 64-bits, which means we can avoid using bignums altogether. Written correctly, this would be extremely fast in C.
With this code [0], on my machine, with only meager optimization effort (not thinking too hard about things other than data types), I can go through 3 billion in less than a minute:
The assembly code for the Munchausen test is relatively tight (though not at all as good as handwritten, of course), which makes evident why we check so quickly. [0] https://bitbucket.org/tarballs_are_good/lisp-random/raw/mast...