Hello list: I apologize if this is already a very well known issue, but i've found that the "fact" (factorial) function does not seem to work properly in the "expr" external when called with an argument greater than 12. I attached a patch in which i've made my own abstraction (which I cannot tell it is done in the most efficient way, but matches the result of any calculator) to show the discrepancy. Am I doing something wrong?
Oscar Pablo Di Liscia
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-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...
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...
hopefully you can open an issue on github please https://github.com/pure-data/pure-data/issues
Em qui., 17 de set. de 2020 às 18:12, oscar pablo di liscia < odiliscia@gmail.com> escreveu:
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...
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> https://lists.puredata.info/listinfo/pd-list
Thanks, so i will do. I just wanted to be sure before. ;)
El jueves, 17 de septiembre de 2020, Alexandre Torres Porres < porres@gmail.com> escribió:
hopefully you can open an issue on github please https://github.com/ pure-data/pure-data/issues
Em qui., 17 de set. de 2020 às 18:12, oscar pablo di liscia < odiliscia@gmail.com> escreveu:
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-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
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> https://lists.puredata.info/ listinfo/pd-list
-
Albert Rafetseder -
Alexandre Torres Porres -
oscar pablo di liscia