Re: [alexandria-devel] Subfactorial is wrong starting from 11
Here is a correct, linear-time implementation of subfactorial: (defun subfactorial (n) "Subfactorial of the non-negative integer N." (check-type n (integer 0)) (if (zerop n) 1 (do ((x 1 (1+ x)) (a 0 (* x (+ a b))) (b 1 a)) ((= n x) a)))) and the corresponding test (deftest subfactorial.1 (mapcar #'subfactorial (iota 22)) (1 0 1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 2290792932 32071101049 481066515734 7697064251745 130850092279664 2355301661033953 44750731559645106 895014631192902121 18795307255050944540)).
Will this be fixed in the library repository? On Sun, Jan 23, 2011 at 11:07 PM, Mason Smith <masonium@gmail.com> wrote:
Here is a correct, linear-time implementation of subfactorial: (defun subfactorial (n) "Subfactorial of the non-negative integer N." (check-type n (integer 0)) (if (zerop n) 1 (do ((x 1 (1+ x)) (a 0 (* x (+ a b))) (b 1 a)) ((= n x) a)))) and the corresponding test (deftest subfactorial.1 (mapcar #'subfactorial (iota 22)) (1 0 1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 2290792932 32071101049 481066515734 7697064251745 130850092279664 2355301661033953 44750731559645106 895014631192902121 18795307255050944540)).
_______________________________________________ alexandria-devel mailing list alexandria-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel
Will this be fixed in the library repository?
eventually for sure. i personally have starred the mail with the fix, but as i have no clue about subfactorial, i'm waiting for at least an amen from someone else before i push it. a random uninformed doubt: the new version seems to be twice as slow (and more accurate, i know). -- attila Notice your eroding (digital) freedom, and do something about it! PGP: 2FA1 A9DC 9C1E BA25 A59C 963F 5D5F 45C7 DFCD 0A39 OTR XMPP: 8647EEAC EA30FEEF E1B55146 573E52EE 21B1FF06
Two months passed, but subfactorial is still not good in the repository :-( On Sat, Jan 29, 2011 at 5:03 AM, Attila Lendvai <attila.lendvai@gmail.com> wrote:
Will this be fixed in the library repository?
eventually for sure.
i personally have starred the mail with the fix, but as i have no clue about subfactorial, i'm waiting for at least an amen from someone else before i push it.
a random uninformed doubt: the new version seems to be twice as slow (and more accurate, i know).
-- attila
Notice your eroding (digital) freedom, and do something about it! PGP: 2FA1 A9DC 9C1E BA25 A59C 963F 5D5F 45C7 DFCD 0A39 OTR XMPP: 8647EEAC EA30FEEF E1B55146 573E52EE 21B1FF06
On 23 January 2011 23:07, Mason Smith <masonium@gmail.com> wrote:
Here is a correct, linear-time implementation of subfactorial:
Thank you! Sorry about the delay -- merged and pushed. Cheers, -- nikodemus
participants (4)
-
Attila Lendvai -
Mason Smith -
Nikodemus Siivola -
Sergey Dymchenko