News for hackers. Stuff that matters.
Re:Munchausen Numbers and How to Find Them by reikonomusha on Wednesday September 21, 2016 @05:23PM (#12552387)
> Here’s the program written in Python. I used it to find every Munchausen number less than 500,000,000. After thirty minutes or so of intense computation, it turns out that the only Munchausen numbers are 1 and 3435.

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:

    > (time (find-munchausen 3000000000))
    Computing all Munchausen numbers below three billion.
    Evaluation took:
      57.087 seconds of real time
      57.059879 seconds of total run time (56.840355 user, 0.219524 system)
      99.95% CPU
      159,836,797,604 processor cycles
      401,488 bytes consed
      
    (0 1 3435 438579088)
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.

    ; 8E2:       4C8B05A7FFFFFF   MOV R8, [RIP-89]                ; #(0 1 4 27 ...)
    ; 8E9:       488BD9           MOV RBX, RCX
    ; 8EC:       0F1F4000         NOP
    ; 8F0: L0:   48BA9A99999999999919 MOV RDX, 1844674407370955162
    ; 8FA:       488BC3           MOV RAX, RBX
    ; 8FD:       48F7E2           MUL RAX, RDX
    ; 900:       488BFA           MOV RDI, RDX
    ; 903:       4883E7FE         AND RDI, -2
    ; 907:       B814000000       MOV EAX, 20
    ; 90C:       488BF7           MOV RSI, RDI
    ; 90F:       48D1FE           SAR RSI, 1
    ; 912:       480FAFF0         IMUL RSI, RAX
    ; 916:       4829F3           SUB RBX, RSI
    ; 919:       488BF3           MOV RSI, RBX
    ; 91C:       488BDF           MOV RBX, RDI
    ; 91F:       498B44B001       MOV RAX, [R8+RSI*4+1]
    ; 924:       4839C8           CMP RAX, RCX
    ; 927:       7E0E             JLE L2
    ; 929:       B917001020       MOV ECX, 537919511
    ; 92E: L1:   488BD1           MOV RDX, RCX
    ; 931:       488BE5           MOV RSP, RBP
    ; 934:       F8               CLC
    ; 935:       5D               POP RBP
    ; 936:       C3               RET
    ; 937: L2:   4829C1           SUB RCX, RAX
    ; 93A:       4885DB           TEST RBX, RBX
    ; 93D:       75B1             JNE L0
    ; 93F:       4885C9           TEST RCX, RCX
    ; 942:       B917001020       MOV ECX, 537919511
    ; 947:       41BB4F001020     MOV R11D, 537919567             ; T
    ; 94D:       490F44CB         CMOVEQ RCX, R11
    ; 951:       EBDB             JMP L1
[0] https://bitbucket.org/tarballs_are_good/lisp-random/raw/mast...
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.