[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