(Free42) not a bug  COMB

07132020, 11:36 AM
Post: #1




(Free42) not a bug  COMB
.. but an easy fix for a tiny 'problem'.
COMB obviously computes the result as n/1*(n1)/2*(n2)/3...*(np)/p But it will give an Out of Range error for eg C(20408,10204) while the result is 1.47e6141, well within range. That can easily be fixed computing COMB as 1E5*n/1*(n1)/2*(n2)/3...*(np)/p*1E5 This will allow up to COMB(20420,10210), and 10210 is the largest value p for which C(n,p) doesn't overflow but C(n,p)*p does (the last value in the chain calculation before the final division by p), so 1E5 is sufficiently small. 1E4 is not ;) Cheers, Werner 

07132020, 12:03 PM
Post: #2




RE: (Free42) not a bug  COMB
This looks like it would only address the specific example. Other cases would still overflow.
The 34S uses logΓ with a forced rounding to integer: \( ^nC_r = e^{logΓ(n)  logΓ(r)  logΓ(n  r)} \) This risks cancellation of digits by subtraction. Pauli 

07132020, 12:10 PM
Post: #3




RE: (Free42) not a bug  COMB
We can shift the argument: \( \binom{n}{r} = {n \over nr}\; \binom{n1}{r} \)
→ C(20408, 10204) = 2 × C(20407, 10204) 

07132020, 12:22 PM
Post: #4




RE: (Free42) not a bug  COMB
(07132020 12:03 PM)Paul Dale Wrote: This looks like it would only address the specific example. Other cases would still overflow. No, it doesn't. As long as the final result is less than 1e6145, it will return it  otherwise it overflows, as it should. There are hundreds of cases like this for which the current COMB overflows. It's nitpicking, perhaps  but to simulate an HP, you have to pay attention to detail :) Werner 

07132020, 12:28 PM
Post: #5




RE: (Free42) not a bug  COMB  
07132020, 12:58 PM
(This post was last modified: 07132020 12:59 PM by Thomas Okken.)
Post: #6




RE: (Free42) not a bug  COMB
That looks like a good fix. I'll apply it in the next release.
Unless any more serious bugs turn up, the next release won't be very soon. I think I'll hold off until Free42+ is ready, so I can release it and a regular Free42 update at the same time. (It won't actually be called Free42+ but I'll just use that as the working title. Work begins this week...) 

07132020, 01:16 PM
(This post was last modified: 07132020 01:17 PM by Werner.)
Post: #7




RE: (Free42) not a bug  COMB
(07132020 12:22 PM)Werner Wrote: There are hundreds of cases like this for which the current COMB overflows. It's nitpicking, perhaps  but to simulate an HP, you have to pay attention to detail :)Not so nitpicking, take COMB(n,p) with p= 1229, just an example. The builtin COMB can compute C(n,1229) up till n=45116057, returning Out of Range for larger n. My RPN routine (in another thread) goes up to n=45377959. Quite a difference. Thanks for the fix, Thomas, and of course it isn't urgent. Cheers, Werner 

07142020, 03:38 AM
Post: #8




RE: (Free42) not a bug  COMB
I'm coding the fix so that it starts the product with 1/s instead of 1, and then multiplies by s at the end, where s is 10^(1+floor(log10(p))), or 2^(1+floor(log2(p))) in the binary version. That fixes all the cases mentioned in this thread.
https://github.com/thomasokken/free42/co...487ac559e6 

07142020, 06:57 AM
Post: #9




RE: (Free42) not a bug  COMB
(07142020 03:38 AM)Thomas Okken Wrote: I'm coding the fix so that it starts the product with 1/s instead of 1, and then multiplies by s at the end, where s is 10^(1+floor(log10(p))), or 2^(1+floor(log2(p))) in the binary version. That fixes all the cases mentioned in this thread. For Free42 Decimal, the largest value of C(n,p)*p that overflows while C(n,p) does not is for n=20421,p=10167, and that is also the only case that requires the constant s to be 1E5 i.o. 1E4. 1E5 will thus work for all cases in Free42 Decimal. Likewise, s=2^10 will work for all cases in Free42 Binary. Anything larger will also work, of course. Cheers, Werner 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)