Hello Albert: Many thanks for your kind response and your advice. I want factorial to work on some combinatorial stuff. I just wanted to check if I was doing something wrong with the use of "expr". IMHO, the advantage of "expr" is that I can have "packed" in just one object a complete formula including operator precedences. Best
Oscar Pablo Di Liscia
El jue., 17 sept. 2020 a las 4:24, Albert Rafetseder (< albert.rafetseder+pd@univie.ac.at>) escribió:
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
factreserves 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-L9... [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_p...