HP Forums
Bug in HP 20b: nCr with non-integer r - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: Bug in HP 20b: nCr with non-integer r (/thread-149251.html)



Bug in HP 20b: nCr with non-integer r - Thomas Klemm - 03-31-2009

In RPN mode I tried to calculate:

1
INPUT
0.5
nCr

The calculator then hangs with a blinking shift-indicator. The keyboard doesn't respond. Even trying to reset the calculator with the triple keys: [ON/CE] [N] [Amort] doesn't work. I had to press a paperclip through the small hole on the back, after removing the cover.

SW Version 6 24 2008 2 is used.

Is this well known?

Now you tell me I should instead use:

   n!
---------
r! (n-r)!

And funny enough it works.

Edited: 31 Mar 2009, 3:41 p.m.


Re: Bug in HP 20b: nCr with non-integer r - Michael de Estrada - 03-31-2009

nCr is valid only for integer values, so what you were getting was an error indication. OTOH, n! is valid for fractional values in the general case of the Gamma function, so it works. However, the calculation that you did was meaningless, as there is no such thing as the combination of 1 items taken 0.5 at a time. As to why your calculator would not reset, perhaps it became very angry at an attempt to misuse its functions and decided to lock you out. ;>)

Michael


Re: Bug in HP 20b: nCr with non-integer r - Chuck - 03-31-2009

My guess is that the factorial function actually utilizes the gamma function, and nCr has an algorithm that does not utilize gamma.

<Michael got there first>

While working on this, I decided to try it out on the HP-42S. Of course the nCr button with non-integers doesn't work. The factorial function also doesn't work because there is a built in gamma function. Here's a little program I wrote for the HP-42S to do it...

01 LBL "NCR"
02 STO 01
03 Rolldown
04 STO 02
05 1
06 +
07 GAMMA
08 1
09 RCL+ 01
10 GAMMA
11 / "divide"
12 RCL 02
13 RCL- 01
14 1
15 +
16 GAMMA
17 /
18 RTN

Put two numbers on the stack and execute NCR

It's most likely not the shortest such program, but works like a charm on your non-integer problem. But, now the REALLY STRANGE PART....

...in doing a problem like 5 nCr 5 or 5 nCr 0 on the 42S I get for an output

Out of Range
x: 1.0000

However, stepping through the program to trouble shoot it, there is no "Out of Range" warning. And, executing the SAME program using Free42 on my ipod I get no "Out of Range Error". Can someone explain that to me?

CHUCK

Edited: 31 Mar 2009, 4:46 p.m.


Re: Bug in HP 20b: nCr with non-integer r - Paul Dale - 03-31-2009

nCr can easily be extend to majority of the complex plane:

                1
nCr = ----------------------
(n+1) beta(n-r+1, r+1)

Is this sensible? Who knows :-)

- Pauli


Re: Bug in HP 20b: nCr with non-integer r - Nigel J Dowrick - 03-31-2009

I can't explain what you have observed, but your program doesn't give those errors when I run it on my HP-42S! Its serial number is 3127S03683; perhaps yours has a different ROM containing a bug?


Re: Bug in HP 20b: nCr with non-integer r - Thomas Klemm - 03-31-2009

Quote:
so what you were getting was an error indication.

The error indicator for the same entries for nPr is:

ER: oo Result
While for other invalid like r > n values you would get:
ER: Invalid Input
One of the above I could accept as an error indication but not blocking the whole calculator.

Quote:
However, the calculation that you did was meaningless

You are kindly requested to scroll down to "Generalization to real and complex argument" in this article about
Binomial coefficients.

Actually I was just playing around with the calculator and wondered what if I wanted to calculate "Newton's binomial series" for an exponent of 0.5? And then I got it wrong and mixed n and r. So at least for me it makes perfectly sense to calculate say nCr(0.5, 5):

It's the coefficent of x5 in the Taylor series expansion of (1 + x)1/2.

In a way it's exactly the same as you probably would expect if n were an integer. So the interesting thing in math is to give meaning to seemingly meaningless things.




Re: Bug in HP 20b: nCr with non-integer r - Jeff Kearns - 03-31-2009

Nor do I have the problem on my HP42s. I get "1" for each case.

Jeff


Re: Bug in HP 20b: nCr with non-integer r - Chuck - 03-31-2009

Arrrg. I'll reset my 42s and try it again. Must have a flag or mode out of kilter. Thanks.

........later.........


Nope. I did a reset; re-entered the program; and ran 5 5 NCR and still got "Out of Range". Stepping through the program works fine though. Hrmph.

My serial number is: 3313S05685

Curious if this happens for anybody else. :(

CHUCK


Edited: 31 Mar 2009, 7:09 p.m.


Re: Bug in HP 20b: nCr with non-integer r - Michael de Estrada - 03-31-2009

The intended purpose of the nCr and nPr functions are to compute combinations and permutations of discrete objects, such that the n and r values must be integers to have any meaning. The calculation of these functions is made using the integer factorial function, which is defined for only non-negative integer values. The fact that this a special case of Gamma, which extends to real numbers or even complex numbers is irrelevant to the intent of the nCr and nPr functions. I have yet to find a calculator with these two functions that permit non-integer values.

As far as your calculator locking up, well of course I was just joking when suggesting that it should do this. Some of my older calcs blink to indicate an error message, and I don't own an HP 20b, so I'm not familiar with its error indications.

Edited: 1 Apr 2009, 10:30 a.m.


Re: Bug in HP 20b: nCr with non-integer r - Gene Wright - 03-31-2009

Yes, it is a bug. Good find.


HP-42S: nCr with non-integer r - Karl Schneider - 04-01-2009

Chuck --

Your program works just fine on my HP-42S models with different ROM's (1989 flat screen 2939Sxxxxx and 1990 recessed-screen 3047Sxxxxx).

One obscure point: The numbered storage registers must be dimensioned to store real-valued numbers, not complex. Taking ABS of a recalled number before GAMMA is a work-around if the recalled value is x + i0 or x / 0.

A related point: There is a minor bug of COMB and PERM in the redesigned (recessed-screen) versions of the HP-42S:

http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv008.cgi?read=17122#17122

-- KS


Re: Bug in HP 20b: nCr with non-integer r - Karl Schneider - 04-01-2009

I think it may have been a bug; there were a few with earlier ROM versions. My HP-20b gives the correct response of "Invalid Input".

-- KS




Re: Bug in HP 20b: nCr with non-integer r - cyrille de Brébisson - 04-01-2009

hello,

1 0.5 nCr should return an Invalid Input error. However, I do seem to recall that early version of the SW had a bug there and were not checking on the inputs.

the calculator does not use the factorial formula because it would lead very rapidly to numbers above the calculator precision and cause lost of precision, instead it uses a loop... as a result, of course, if you have i=0.5 and loop doing i-1 until i=0.... you never end and crashes the calculator :-( unless you have the version that actually tests for it...

cyrille


Re: HP-42S: nCr with non-integer r - Chuck - 04-01-2009

I'm still baffled. When I set flag 24 to ignore "Out of Range" errors I get 0 as a result for 5 nCr 5, and 5 nCr 0. And, setting flag 25 in program (skip error) to pinpoint which step is causing the error, I discovered two different situations.

1) "Out of Range" error occurs on the LAST gamma function for the 5 nCr 5 problem

2) the SECOND gamma causes the error on the 5 nCr 0 problem

The error doesn't occur when I reprogram with the factorial function (but this defeats the non-integer usefulness).

So, clearly there is a bug with GAMMA when executed in a RUNNING program (I don't get the error when stepping through the program.) If not a bug, then I have a very unique calculator.

I'll keep exploring.

CHUCK


Re: Bug in HP 20b: nCr with non-integer r - David Hayden - 04-01-2009

Quote:
nCr is valid only for integer values, so what you were getting was an error indication.

An error indication could be easily cleared so the user could continue to use the calculator. In this case, the calculator froze up completely, so I'd call it a bug.


Re: Bug in HP 20b: nCr with non-integer r - Michael de Estrada - 04-01-2009

Cyrille,

Finally, a logical explanation. What is the actual algorithm that is used here? I know you say it is iterative, but exactly how does it work?

Michael


Re: Bug in HP 20b: nCr with non-integer r - Paul Dale - 04-01-2009

I'd imagine the iterative algorithm used is:

       n    n - 1   n - 2         n - ( k - 1 )
nCk = --- . ----- . ----- . ... . -------------
k k - 1 k - 2 k - ( k - 1 )

I cannot think of a better alternative.

However, I'd use:

nCk = EXP( lngamma(n+1) - lngamma(k+1) - lngamma(n-k+1) )

With a round to nearest integer if the inputs are both integer.

- Pauli


Re: Bug in HP 20b: nCr with non-integer r - cyrille de Brébisson - 04-02-2009

hello

Quote:
I'd imagine the iterative algorithm used is:

       n    n - 1   n - 2         n - ( k - 1 )
nCk = --- . ----- . ----- . ... . -------------
k k - 1 k - 2 k - ( k - 1 )

yep, exactly, and since it gets to maxreal realy fast for inputs that overflow, time is not critical there...

cyrille


Re: Bug in HP 20b: nCr with non-integer r - Michael de Estrada - 04-02-2009

So, are you saying that the loop counter is on the denominator, and that it checks for exactly = 0, rather than <= 0, so it continues looping indefinitely? By my reckoning, the second product will produce 0, so all subsequent products will be 0, such that an overflow condition will never occur, which would then halt the calculator with an overflow error indication.


Re: Bug in HP 20b: nCr with non-integer r - Paul Dale - 04-02-2009

True so long as you also reduce things via:

nCk = nC(n-k), when k>n/2

Otherwise you could be in for a long long wait...

Think 1,000,000 C 999,999


- Pauli