[PD] weird behavior of factorial in expr

[Alexandre Torres Porres]

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 at 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 at 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 `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
>>
> _______________________________________________
> Pd-list at lists.iem.at mailing list
> UNSUBSCRIBE and account-management ->
> https://lists.puredata.info/listinfo/pd-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20200917/f8c2afb8/attachment-0001.html>