➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author rhettinger
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, rhettinger, serhiy.storchaka, tim.peters
Date 2022-01-12.08:20:15
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1641975616.2.0.910449572212.issue37295@roundup.psfhosted.org>
In-reply-to
Content 
Ran some timings on the pure python version with and without the precomputed diagonal:  [C(n, k) for k in range(n+1)]

          New Code        Baseline
         ---------       --------- 
n=85      156 usec        160 usec
n=137     632 usec       1.82 msec
n=156    1.01 msec       4.01 msec
n=183    1.58 msec       7.06 msec
n=212    2.29 msec       10.4 msec
n=251    7.07 msec       15.6 msec
n=311    19.6 msec       25.5 msec
n=1001    314 msec        471 msec

As expected, the best improvement comes in the range of the precomputed combinations:  C(129, 20) through C(250, 20).

To get a better idea of where the benefit is coming from, here is a trace from the recursive part of the new code:

>>> C(240, 112)
C(240, 112) = C(240, 20) * C(220, 92) // C(112, 20)
C(220, 92) = C(220, 20) * C(200, 72) // C(92, 20)
C(200, 72) = C(200, 20) * C(180, 52) // C(72, 20)
C(180, 52) = C(180, 20) * C(160, 32) // C(52, 20)
C(160, 32) = C(160, 20) * C(140, 12) // C(32, 20)
C(140, 12) = C(140, 6) * C(134, 6) // C(12, 6)
C(140, 6) = C(140, 3) * C(137, 3) // C(6, 3)
C(140, 3) = C(140, 1) * C(139, 2) // C(3, 1)
C(139, 2) = C(139, 1) * C(138, 1) // C(2, 1)
C(137, 3) = C(137, 1) * C(136, 2) // C(3, 1)
C(136, 2) = C(136, 1) * C(135, 1) // C(2, 1)
C(134, 6) = C(134, 3) * C(131, 3) // C(6, 3)
C(134, 3) = C(134, 1) * C(133, 2) // C(3, 1)
C(133, 2) = C(133, 1) * C(132, 1) // C(2, 1)
C(131, 3) = C(131, 1) * C(130, 2) // C(3, 1)
C(130, 2) = C(130, 1) * C(129, 1) // C(2, 1)
53425668586973006090333976236624193248148570813984466591034254245235155


Here is a trace for the old code without the precomputed diagonal:

>>> C(240, 112)
C(240, 112) = C(240, 56) * C(184, 56) // C(112, 56)
C(240, 56) = C(240, 28) * C(212, 28) // C(56, 28)
C(240, 28) = C(240, 14) * C(226, 14) // C(28, 14)
C(240, 14) = C(240, 7) * C(233, 7) // C(14, 7)
C(240, 7) = C(240, 3) * C(237, 4) // C(7, 3)
C(240, 3) = C(240, 1) * C(239, 2) // C(3, 1)
C(239, 2) = C(239, 1) * C(238, 1) // C(2, 1)
C(237, 4) = C(237, 2) * C(235, 2) // C(4, 2)
C(237, 2) = C(237, 1) * C(236, 1) // C(2, 1)
C(235, 2) = C(235, 1) * C(234, 1) // C(2, 1)
C(233, 7) = C(233, 3) * C(230, 4) // C(7, 3)
C(233, 3) = C(233, 1) * C(232, 2) // C(3, 1)
C(232, 2) = C(232, 1) * C(231, 1) // C(2, 1)
C(230, 4) = C(230, 2) * C(228, 2) // C(4, 2)
C(230, 2) = C(230, 1) * C(229, 1) // C(2, 1)
C(228, 2) = C(228, 1) * C(227, 1) // C(2, 1)
C(226, 14) = C(226, 7) * C(219, 7) // C(14, 7)
C(226, 7) = C(226, 3) * C(223, 4) // C(7, 3)
C(226, 3) = C(226, 1) * C(225, 2) // C(3, 1)
C(225, 2) = C(225, 1) * C(224, 1) // C(2, 1)
C(223, 4) = C(223, 2) * C(221, 2) // C(4, 2)
C(223, 2) = C(223, 1) * C(222, 1) // C(2, 1)
C(221, 2) = C(221, 1) * C(220, 1) // C(2, 1)
C(219, 7) = C(219, 3) * C(216, 4) // C(7, 3)
C(219, 3) = C(219, 1) * C(218, 2) // C(3, 1)
C(218, 2) = C(218, 1) * C(217, 1) // C(2, 1)
C(216, 4) = C(216, 2) * C(214, 2) // C(4, 2)
C(216, 2) = C(216, 1) * C(215, 1) // C(2, 1)
C(214, 2) = C(214, 1) * C(213, 1) // C(2, 1)
C(212, 28) = C(212, 14) * C(198, 14) // C(28, 14)
C(212, 14) = C(212, 7) * C(205, 7) // C(14, 7)
C(212, 7) = C(212, 3) * C(209, 4) // C(7, 3)
C(212, 3) = C(212, 1) * C(211, 2) // C(3, 1)
C(211, 2) = C(211, 1) * C(210, 1) // C(2, 1)
C(209, 4) = C(209, 2) * C(207, 2) // C(4, 2)
C(209, 2) = C(209, 1) * C(208, 1) // C(2, 1)
C(207, 2) = C(207, 1) * C(206, 1) // C(2, 1)
C(205, 7) = C(205, 3) * C(202, 4) // C(7, 3)
C(205, 3) = C(205, 1) * C(204, 2) // C(3, 1)
C(204, 2) = C(204, 1) * C(203, 1) // C(2, 1)
C(202, 4) = C(202, 2) * C(200, 2) // C(4, 2)
C(202, 2) = C(202, 1) * C(201, 1) // C(2, 1)
C(200, 2) = C(200, 1) * C(199, 1) // C(2, 1)
C(198, 14) = C(198, 7) * C(191, 7) // C(14, 7)
C(198, 7) = C(198, 3) * C(195, 4) // C(7, 3)
C(198, 3) = C(198, 1) * C(197, 2) // C(3, 1)
C(197, 2) = C(197, 1) * C(196, 1) // C(2, 1)
C(195, 4) = C(195, 2) * C(193, 2) // C(4, 2)
C(195, 2) = C(195, 1) * C(194, 1) // C(2, 1)
C(193, 2) = C(193, 1) * C(192, 1) // C(2, 1)
C(191, 7) = C(191, 3) * C(188, 4) // C(7, 3)
C(191, 3) = C(191, 1) * C(190, 2) // C(3, 1)
C(190, 2) = C(190, 1) * C(189, 1) // C(2, 1)
C(188, 4) = C(188, 2) * C(186, 2) // C(4, 2)
C(188, 2) = C(188, 1) * C(187, 1) // C(2, 1)
C(186, 2) = C(186, 1) * C(185, 1) // C(2, 1)
C(184, 56) = C(184, 28) * C(156, 28) // C(56, 28)
C(184, 28) = C(184, 14) * C(170, 14) // C(28, 14)
C(184, 14) = C(184, 7) * C(177, 7) // C(14, 7)
C(184, 7) = C(184, 3) * C(181, 4) // C(7, 3)
C(184, 3) = C(184, 1) * C(183, 2) // C(3, 1)
C(183, 2) = C(183, 1) * C(182, 1) // C(2, 1)
C(181, 4) = C(181, 2) * C(179, 2) // C(4, 2)
C(181, 2) = C(181, 1) * C(180, 1) // C(2, 1)
C(179, 2) = C(179, 1) * C(178, 1) // C(2, 1)
C(177, 7) = C(177, 3) * C(174, 4) // C(7, 3)
C(177, 3) = C(177, 1) * C(176, 2) // C(3, 1)
C(176, 2) = C(176, 1) * C(175, 1) // C(2, 1)
C(174, 4) = C(174, 2) * C(172, 2) // C(4, 2)
C(174, 2) = C(174, 1) * C(173, 1) // C(2, 1)
C(172, 2) = C(172, 1) * C(171, 1) // C(2, 1)
C(170, 14) = C(170, 7) * C(163, 7) // C(14, 7)
C(170, 7) = C(170, 3) * C(167, 4) // C(7, 3)
C(170, 3) = C(170, 1) * C(169, 2) // C(3, 1)
C(169, 2) = C(169, 1) * C(168, 1) // C(2, 1)
C(167, 4) = C(167, 2) * C(165, 2) // C(4, 2)
C(167, 2) = C(167, 1) * C(166, 1) // C(2, 1)
C(165, 2) = C(165, 1) * C(164, 1) // C(2, 1)
C(163, 7) = C(163, 3) * C(160, 4) // C(7, 3)
C(163, 3) = C(163, 1) * C(162, 2) // C(3, 1)
C(162, 2) = C(162, 1) * C(161, 1) // C(2, 1)
C(160, 4) = C(160, 2) * C(158, 2) // C(4, 2)
C(160, 2) = C(160, 1) * C(159, 1) // C(2, 1)
C(158, 2) = C(158, 1) * C(157, 1) // C(2, 1)
C(156, 28) = C(156, 14) * C(142, 14) // C(28, 14)
C(156, 14) = C(156, 7) * C(149, 7) // C(14, 7)
C(156, 7) = C(156, 3) * C(153, 4) // C(7, 3)
C(156, 3) = C(156, 1) * C(155, 2) // C(3, 1)
C(155, 2) = C(155, 1) * C(154, 1) // C(2, 1)
C(153, 4) = C(153, 2) * C(151, 2) // C(4, 2)
C(153, 2) = C(153, 1) * C(152, 1) // C(2, 1)
C(151, 2) = C(151, 1) * C(150, 1) // C(2, 1)
C(149, 7) = C(149, 3) * C(146, 4) // C(7, 3)
C(149, 3) = C(149, 1) * C(148, 2) // C(3, 1)
C(148, 2) = C(148, 1) * C(147, 1) // C(2, 1)
C(146, 4) = C(146, 2) * C(144, 2) // C(4, 2)
C(146, 2) = C(146, 1) * C(145, 1) // C(2, 1)
C(144, 2) = C(144, 1) * C(143, 1) // C(2, 1)
C(142, 14) = C(142, 7) * C(135, 7) // C(14, 7)
C(142, 7) = C(142, 3) * C(139, 4) // C(7, 3)
C(142, 3) = C(142, 1) * C(141, 2) // C(3, 1)
C(141, 2) = C(141, 1) * C(140, 1) // C(2, 1)
C(139, 4) = C(139, 2) * C(137, 2) // C(4, 2)
C(139, 2) = C(139, 1) * C(138, 1) // C(2, 1)
C(137, 2) = C(137, 1) * C(136, 1) // C(2, 1)
C(135, 7) = C(135, 3) * C(132, 4) // C(7, 3)
C(135, 3) = C(135, 1) * C(134, 2) // C(3, 1)
C(134, 2) = C(134, 1) * C(133, 1) // C(2, 1)
C(132, 4) = C(132, 2) * C(130, 2) // C(4, 2)
C(132, 2) = C(132, 1) * C(131, 1) // C(2, 1)
C(130, 2) = C(130, 1) * C(129, 1) // C(2, 1)
C(112, 56) = C(112, 28) * C(84, 28) // C(56, 28)
C(112, 28) = C(112, 14) * C(98, 14) // C(28, 14)
C(84, 28) = C(84, 14) * C(70, 14) // C(28, 14)
53425668586973006090333976236624193248148570813984466591034254245235155
History
Date User Action Args
2022-01-12 08:20:16rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann
2022-01-12 08:20:16rhettingersetmessageid: <1641975616.2.0.910449572212.issue37295@roundup.psfhosted.org>
2022-01-12 08:20:16rhettingerlinkissue37295 messages
2022-01-12 08:20:15rhettingercreate