8 ms·

Fast Factorial Algorithms

56 points by nill0 5mo ago

smokel 5mo ago
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/ https://projecteuler.net/ [2] https://oeis.org/A000142/a000142.pdf https://oeis.org/A000142/a000142.pdf
- mjevans 5mo ago
  My approach to the first 100 Euler eventually involved a bitmap of possible primes (only odd numbers, there's only one even prime) which was initially seeded by a 'magic number' set representing the lowest primes and would grow up to a target number of cached small / really fast primes. Then the algorithms I understand less kick in. Most of those involve some form of modo math to wrap the number space based on one or more origami like folds and use well known and test algorithms which were previously exhaustively proven to cover the entire 32 bit number-space when utilized in a composite fashion.
- nyankosensei 5mo ago
  The OP includes a link to an English excerpt written by the author of the "Swing, divide and conquer the factorial" manuscript: http://www.luschny.de/math/factorial/SwingIntro.pdf http://www.luschny.de/math/factorial/SwingIntro.pdf
  - deleted 5mo ago
    [deleted]
dvh 5mo ago
No Stirling formula?
- Aardwolf 5mo ago
  That one is an approximation rather than returning all millions of exact big integer digits though (the approximation is more useful for real life statistics etc..., but doesn't look like what this article is targeting)
- dj_axl 5mo ago
  No mention of any of these! https://www.sciencedirect.com/science/article/pii/S0893965911001066 https://www.sciencedirect.com/science/article/pii/S089396591...
deleted 5mo ago
[deleted]
zamadatix 5mo ago
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 http://www.luschny.de/math/factorial/approx/SimpleCases.html which contains many advanced options to compare for that.
- imglorp 5mo ago
  I've always wondered if Stirling(n) can be used to arrive quickly in the vicinity of n!, and then use a search of some kind to get to the exact target.
ipeev 5mo ago
A cached map will do best if you actualy need a fast factorial. There are very little entries before the numbers become pointlessly big.
- karmakurtisaani 5mo ago
  Not if you want to calculate modulo some big number. Might still be useful tho.
- deleted 5mo ago
  [deleted]
looneysquash 5mo ago
I wonder if any compiler can rewrite that last one into one of the others.
anthk 5mo ago
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/ 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.
FiatLuxDave 5mo ago
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 https://en.wikipedia.org/wiki/AKS_primality_test). It's operation is sort of like an FFT for canceling out factorials mod N.

56 points by nill0 5mo ago

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/ https://projecteuler.net/ [2] https://oeis.org/A000142/a000142.pdf https://oeis.org/A000142/a000142.pdf

mjevans 5mo ago
My approach to the first 100 Euler eventually involved a bitmap of possible primes (only odd numbers, there's only one even prime) which was initially seeded by a 'magic number' set representing the lowest primes and would grow up to a target number of cached small / really fast primes. Then the algorithms I understand less kick in. Most of those involve some form of modo math to wrap the number space based on one or more origami like folds and use well known and test algorithms which were previously exhaustively proven to cover the entire 32 bit number-space when utilized in a composite fashion.
nyankosensei 5mo ago
The OP includes a link to an English excerpt written by the author of the "Swing, divide and conquer the factorial" manuscript: http://www.luschny.de/math/factorial/SwingIntro.pdf http://www.luschny.de/math/factorial/SwingIntro.pdf
- deleted 5mo ago
  [deleted]

dvh 5mo ago

No Stirling formula?

Aardwolf 5mo ago
That one is an approximation rather than returning all millions of exact big integer digits though (the approximation is more useful for real life statistics etc..., but doesn't look like what this article is targeting)
dj_axl 5mo ago
No mention of any of these! https://www.sciencedirect.com/science/article/pii/S0893965911001066 https://www.sciencedirect.com/science/article/pii/S089396591...

deleted 5mo ago

[deleted]

zamadatix 5mo ago

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 http://www.luschny.de/math/factorial/approx/SimpleCases.html which contains many advanced options to compare for that.

imglorp 5mo ago
I've always wondered if Stirling(n) can be used to arrive quickly in the vicinity of n!, and then use a search of some kind to get to the exact target.

ipeev 5mo ago

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

karmakurtisaani 5mo ago
Not if you want to calculate modulo some big number. Might still be useful tho.
deleted 5mo ago
[deleted]

looneysquash 5mo ago

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

anthk 5mo ago

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/ 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.

FiatLuxDave 5mo ago

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 https://en.wikipedia.org/wiki/AKS_primality_test). It's operation is sort of like an FFT for canceling out factorials mod N.