Raymond Hettinger <raymond.hettin...@gmail.com> added the comment: ISTM that the asymptotic benefits of Karatsuba multiplication are mostly lost when each of the factors has to be built-up recursively prior to the multiply. Also, the benefits of Karatsuba only start to appear at around 400-bit numbers. For us, we don't get there until comb(400, 200). Even there, almost all of the multiplications are with smaller values that get no benefit at all from Karatsuba multiplication. IOW, I don't think Karatsuba multiplication has been helping at all. More likely, the improvement came from a reduced number of divisions.
The depth issue is a red herring. The fixed j approach is only used up to n=235.¹ The largest input, comb(235, 117), recurses only five levels C(215,97), C(195,77), C(175,57), C(155,37), C(135,17) before handing off to the j=k//2 algorithm. Five levels of width one is so inexpensive that it isn't worth talking about, especially when considering how many PyLong multiplies and divides are saved.² ¹ Jlim = 235 in the posted comb_pole.py. I've since changed the span of precomputed combinations to C(n, 20) where 87 ≤ n ≤ 250. ² See the trace in the previous post showing a seven-fold reduction in the number of PyLong multiply and divide operations. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue37295> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
