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



#2

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.


#3

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


#4

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

#5

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.


#6

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.

#7

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.
#8

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.


#9

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?


#10

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

Jeff


#11

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.

#12

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


#13

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

#14

Yes, it is a bug. Good find.

#15

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

#16

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


#17

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


#18

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


#19

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


#20

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.

#21

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime graphing bug BruceH 1 433 11-19-2013, 08:14 AM
Last Post: Joe Horn
  HP Prime - another cosmetic bug BruceH 3 539 11-12-2013, 02:18 PM
Last Post: Ken Shaw
  HP Prime: Edit integer in RPN mode plivesey 15 1,310 10-18-2013, 04:34 PM
Last Post: kris223
  HP Prime Bug bluesun08 19 1,612 10-14-2013, 10:48 PM
Last Post: Han
  HP Prime bug in EDITMAT Han 7 874 09-27-2013, 10:15 AM
Last Post: Han
  Prime Edit Integer kris223 8 758 09-24-2013, 06:43 PM
Last Post: kris223
  HP's thinking behind the 20b/30b? John Ioannidis 3 495 09-07-2013, 10:21 AM
Last Post: Tim Wessman
  [HP 39Gii] - Bug report Jean-Michel 1 420 08-28-2013, 10:53 AM
Last Post: Tim Wessman
  Is the HP-35S bug free? Matt Agajanian 22 1,782 07-01-2013, 04:03 PM
Last Post: Andrés C. Rodríguez (Argentina)
  20b, 30b not in HP's web store Eric Smith 3 492 02-08-2013, 11:52 AM
Last Post: Walter B

Forum Jump: