Re: [Bug-apl] Binomial function with extended exact result range beyond that of primitive function

[Juergen Sauermann]

Hi,
I have revised the algorithm for binomials. It should now return 
integers where possible. SVN 432.

/// Jürgen


On 08/07/2014 08:00 AM, Frederick H. Pitts wrote:
Elias,

        Juergen informed me that he had changed how monadic ! is calculated in
in a reply with the above subject line. I assumed he made the change in
an effort to increase the range of exact results produced by dyadic !
before the latter reverts to producing floating point numbers that are
limited to 15-decimal digit accuracy(4 digits less than the 64-bit
integer is capable of producing).

        So "No" my issue is not with monadic ! with integers arguments per se.
My issue is that for increasing integer arguments dyadic ! starts
producing floating point results long before the limit imposed by a
signed 64-bit integer is reached.  This situation results from a literal
implementation of the binomial formula n!/(k!(n-k)!).  At n=21, GnuAPL
starts representing the value of n! as a floating point number and when
n=66, n! is so large that the 15 decimal digit precision is insufficient
for the calculation of an exact integer result of dyadic !.  The BINOM
defined function gets around the limitation by canceling prime factors
between numerator and denominator before evaluating the factorials.

        BTW, for integer arguments monadic ! can produce a answer for n = 0 to
n = 170.  At n = 171 GnuAPL reports a DOMAIN ERROR because the result is
greater than the upper limit of double precision numbers.  Also note
that monadic ! only produces exact integer results for n = 0 to n = 20.
Above n = 20, the results no longer fit in a 64-bit signed integer.  I
have no desire to memoize a bunch of floating point numbers that are not
suited for the task at hand, calculating exact binomial coefficients
over a large a range as the 64-bit signed integer will allow.

Regards,

Fred


On Thu, 2014-08-07 at 11:36 +0800, Elias Mårtenson wrote:
Frederick,


Is you issue with monadic ! for integer arguments only? If so, since
the are only 70 or so valid inputs to this function, the results can
be precalculated and the implementation can simple dereference the
result from an array.


For fractional parameters to monadic !, the result of the Gamma
function has to be computed which of course is much more expensive.


Regards,
Elias


On 7 August 2014 11:15, Frederick H. Pitts <fred.pi...@comcast.net>
wrote:
         Hello Juergen,
         
                 I reran timing tests comparing the defined BINOM
         function with the
         dyadic ! function after upgrading to SVN rev. 422. I saw no
         difference
         in the BINOM and dyadic ! results and maybe a factor of 2
         slowdown in
         the dyadic ! which I attributed to the change in how monadic !
         is
         calculated.  I was hoping to see the dyadic ! produce exact
         integer
         results up to the 9200000000000000000 upper limit on 64-bit
         GnuAPL
         integers after the change. :-(.
         
                 Is the change to monadic ! actually in SVN rev. 422?
          Your email does
         not say.
         
                 If the change is there, then the 15-digit precision of
         double precision
         numbers (even if the 15 digits are exact) simply isn't enough
         precision
         to exactly calculate the binomial ! if the right argument to
         the latter
         is 37 or greater.  BINOM gives exact results for right
         arguments up to
         66 with a result that approaches the upper limit of 64-bit
         integers.
         
                 I'm reporting this only to let you know that the
         change to monadic !
         did not impact the dyadic !, if in fact the change is in SVN,
         other than
         to slow it down.
         
         Regards,
         
         
         
         
         On Wed, 2014-08-06 at 17:29 +0200, Juergen Sauermann wrote:
         
         > Hi Fred,
         >
         > I did a small rework of the monadic ! function. It should
         now be
         > exact (well, as exact as ×/⍳N is) for integer arguments up
         to 170
         > (i.e. the max integer before DOMAIN ERROR is thrown),
         >
         > Before it was calling tgamma() of libm.
         >
         > There are still many cases where GNU APL calls libm
         functions
         > and replacing them all by more exact versions would be
         rather tedious.
         > There are often speed-precision trade-offs involved.
         Normally the
         > precision of libm functions is good enough. Let's fix issues
         on a
         > case-by-case basis when we find them.
         >
         > /// Jürgen
         >
         >
         > On 08/06/2014 03:06 AM, Frederick H. Pitts wrote:
         >
         > > Gentle people,
         > >
         > >     Please find attached binom.apl.tgz.  It contains the
         source for BINOM,
         > > a defined function does what the primitive dyadic !
         function does but
         > > produces exact results over a larger range.
         > >
         > >         BINOM produces 1) the same results as ! over the
         range where !
         > > produces exact integers, 2) exact integer results in range
         above that
         > > produced by the ! but below the 9200000000000000000 upper
         limit of GNU
         > > 64-bit integers and 3) floating point results that match
         those of !
         > > above the 64-bit integer upper limit.
         > >
         > >     In the interest of full disclosure:
         > > 1) The code is slow; 100 times slower than the primitive
         dyadic !.  But
         > > then BINOM is interpreted while ! is compiled in to the
         interpreter.
         > > 2) The code was presented in 1996 on comp.lang.apl by Jim
         Weigang and
         > > others.
         > >
         > > Enjoy,
         > >
         > > Fred
         > > Retired Chemical Engineer
         >