[PD] weird behavior of factorial in expr
oscar pablo di liscia
odiliscia at gmail.com
Fri Sep 18 03:12:29 CEST 2020
Thanks, so i will do.
I just wanted to be sure before.
;)
El jueves, 17 de septiembre de 2020, Alexandre Torres Porres <
porres at 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 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
>>
>
--
Oscar Pablo Di Liscia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20200917/cb8390b1/attachment.html>
More information about the Pd-list
mailing list