Fast Factorial Algorithms (luschny.de)

I hoped this would help me solve some more Project Euler [1] problems. Unfortunately, the algorithms given are not explained in detail, so the learning experience is somewhat mediocre. Then again, I have ChatGPT to elucidate them for me.

This article [2] has some interesting details on the swinging factorial function n≀, but I can't seem to find the essay that it references: "Swing, divide and conquer the factorial", 2008.

[1] https://projecteuler.net/

[2] https://oeis.org/A000142/a000142.pdf

No Stirling formula?

To all commenting about the Sitrling formula, there is a separate page linked at the end for approximations http://www.luschny.de/math/factorial/approx/SimpleCases.html which contains many advanced options to compare for that.

A cached map will do best if you actualy need a fast factorial. There are very little entries before the numbers become pointlessly big.

I wonder if any compiler can rewrite that last one into one of the others.

Zenlisp:

If it runs fast there, it will run fast everywhere, as integers are made of Lisp conses on purpose, so you can see Lisp built from itself as if they were Peano axioms:

https://www.t3x.org/zsp/

  (require 'nmath)
  (gc)
  (define (fac n)
   (fi '#1  n))
  
  (define  (fi a n)
   (or  
   (and (= n '#0) 1) 
   (and (= n '#1) a)
    (and 
    (fi
     (* a n)
     (- n '#1)
      ))))
  
  
  (fac '#10)
  (fac '#0)

Test:

    -:cat fact.l | ./zl
     zenlisp 2013-11-22 by Nils M Holm
     => :t
     => '(#125434 #5638)
     => 'fac
     => 'fi
     => '#3628800
     => '1

Test with (trace fi) before running (fac 0) and (fac 10)

    zenlisp 2013-11-22 by Nils M Holm
    => :t
    => '(#125434 #5638)
    => 'fac
    => 'fi
    => :t
    + (fi #1 #10)
    + (fi #10 #9)
    + (fi #90 #8)
    + (fi #720 #7)
    + (fi #5040 #6)
    + (fi #30240 #5)
    + (fi #151200 #4)
    + (fi #604800 #3)
    + (fi #1814400 #2)
    + (fi #3628800 #1)
    => '#3628800
    + (fi #1 #0)
    => '1

Here you can see how (fi) works on every iteration.

Integers are not actual integers, but lists.

'#3628800 it's '(3 6 2 8 8 0 0).

Open "nmath.l" to see how are digits implemented. Base.t it's interesting too, as it explains you some functions.

I know it's not technically a fast factorial algorithm, but I'm kinda surprised that there is no mention on the site of the AKS primality test (https://en.wikipedia.org/wiki/AKS_primality_test). It's operation is sort of like an FFT for canceling out factorials mod N.