prog

frontpage - thread list - new thread - preferences - ?

LISP Puzzles

137 2020-05-21 11:38

Intuition would indicate and profiling shows that most of the time for R(10^78) >>105 is spent in Layer4.increment >>102.

$ python3 -m cProfile -s time wrapper.py flake.hofs layers "1$(printf "%078d" 0)" | tee temp/profile.txt | less
levels: 5
1000000000000000000000000000000000000000000000000000000000000000000000000000000 -> 500000000000000000000000000000000000000942809041582063365839428238027648024522282176747574937498915190189902751724515553262387695706471431607983773634306949 0x254AAD173EA5E82CB765169D1EFC9860FE05AE7B1E8FB19314D597561CED1F19F448CA74BCDEE10F0F168DAE0F529DA97AADE66B397A970EDCFEA83CA35C68A385 518
         1579011 function calls (1578437 primitive calls) in 5.325 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   143277    4.213    0.000    4.213    0.000 hofs.py:821(increment)
   143296    0.297    0.000    0.297    0.000 hofs.py:794(increment)
        1    0.181    0.181    5.322    5.322 hofs.py:909(work_layers_loop)
   143397    0.151    0.000    0.776    0.000 hofs.py:869(counts)
   143331    0.125    0.000    0.125    0.000 hofs.py:771(increment)

But swapping out Layer4 for a gmpy2 version that converts inputs to mpz, performs all the work in mpz and converts outputs to python ints does not yield the expected speedup.

$ python3 -m cProfile -s time wrapper.py numsci.hofs l4 "1$(printf "%078d" 0)" | tee temp/profile.txt | less
levels: 5
1000000000000000000000000000000000000000000000000000000000000000000000000000000 -> 500000000000000000000000000000000000000942809041582063365839428238027648024522282176747574937498915190189902751724515553262387695706471431607983773634306949 0x254AAD173EA5E82CB765169D1EFC9860FE05AE7B1E8FB19314D597561CED1F19F448CA74BCDEE10F0F168DAE0F529DA97AADE66B397A970EDCFEA83CA35C68A385 518
         2726218 function calls (2725626 primitive calls) in 5.041 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   143277    3.690    0.000    3.832    0.000 hofs.py:24(increment)
   143296    0.301    0.000    0.301    0.000 hofs.py:794(increment)
        1    0.201    0.201    5.026    5.026 hofs.py:909(work_layers_loop)
   143397    0.163    0.000    0.834    0.000 hofs.py:869(counts)
   143331    0.130    0.000    0.130    0.000 hofs.py:771(increment)
  1002940    0.115    0.000    0.115    0.000 {built-in method gmpy2.mpz}

This is despite the fact that the conversion cost at the edges of the method barely registers at 0.115s, and the gmpy2.mpz type is faster than python ints for large numbers.

$ python3 -m timeit -s "x = $(echo 'print ("123456" * 13)' | python3)" "y = x * (x + 1)"
10000000 loops, best of 3: 0.126 usec per loop
$ python3 -m timeit -s 'import gmpy2' -s "x = gmpy2.mpz ($(echo 'print ("123456" * 13)' | python3))" "y = x * (x + 1)"
10000000 loops, best of 3: 0.0702 usec per loop

It seems the gmpy2.mpz advantage isn't nearly as dramatic as I expected. Or there is something else going on that I cannot see yet.

157