[alexandria-devel] Subfactorial is wrong starting from 11

[Mason Smith]

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)).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20110123/7b69ad16/attachment.html>