[PD] weird behavior of factorial in expr
Albert Rafetseder
albert.rafetseder+pd at univie.ac.at
Thu Sep 17 09:24:51 CEST 2020
Hi Oscar,
> the "fact" (factorial) function does not seem to work properly in the
> "expr" external when called with an argument greater than 12.
the problem in [expr fact(...)] looks like an integer overflow. See [1]
for conceptual details, TL;DR: Factorials produce huge numbers very
quickly, but the implementation of `fact` reserves too little space to
store the result's digits [2], and thus truncates the result, producing
garbage:
[expr fact(12)] is 4.79002e+08, just about right
[expr fact(13)] is 1.93205e+09, clearly *not* the above times 13
[expr fact(14)] is 1.27895e+09, even smaller than the previous result
(...)
[expr fact(17)] is a negative number altogether
I can't comment on the efficiency your implementation as I'm not too
well versed in Pd. I'd speculate it won't suffer [expr fact]'s numerical
problems since AFAIK, patches use floats as the default number format,
basically allowing for larger numbers to be stored.
The usual suggestion for avoiding numerical problems with factorials is
to re-think what the numbers are used for -- Taylor series?
combinatorials of n-choose-k kind? something else? -- and use an
appropriate alternative such as:
* Stirling's approximation [3]
* the Gamma function [4]
* binomial coefficient without factorials [5]
Cheers,
Albert.
[1] https://en.wikipedia.org/wiki/Integer_overflow
[2]
https://github.com/pure-data/pure-data/blob/2af4b5d/src/x_vexp_fun.c#L913-L928
[3] https://en.wikipedia.org/wiki/Stirling%27s_approximation
[4] https://en.wikipedia.org/wiki/Gamma_function
[5]
https://en.wikipedia.org/wiki/Binomial_coefficient#Binomial_coefficient_in_programming_languages
More information about the Pd-list
mailing list