An accurate computation of the hypergeometric distribution function

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An accurate computation of the hypergeometric distribution function

Full text

Pdf (676 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 19 , Issue 1 (March 1993) table of contents

Pages: 33 - 43

Year of Publication: 1993

ISSN:0098-3500

Author

Trong Wu

Southern Illinois Univ., Edwardsville

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 65, Citation Count: 1

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/151271.151274 What is a DOI?

ABSTRACT

The computation of the cumulative hypergeometric distribution function is of interest to many researchers who are working in the computational sciences and related areas. Presented here is a new method for computing this function that applies prime number factorization to the factorials. We also apply cancellation to the numerator and denominator to reduce the computational complexity of the initial, the tail end, or weighted probabilities to achieve maximum accuracy. The new method includes two algorithms, one using recursion and the other using iteration. These two algorithms are machine independent; precision is arbitrary, subject to storage limitation. The development of the algorithms is discussed, and some test results and the comparison of these two algorithms are given. To implement both algorithms, we use the Ada programming language that is an American National Standard Institute standardized language. The language has special features such as exception handling and tasks. Exception handling is used to make programming easier and to prevent overflow or underflow conditions during the execution of the program. Tasks are used to compute the numerator and denominator concurrently, and to maximize the possible number of integer multiplications in the numerator and denominator. All of the computations can be done on currently available machines, and the time consumed by these computations remains reasonably small.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BAILEY, T. A. JR., AND DUBES, R.C. Cluster validity profiles. Pattern Recogn. 15, 2 (1982), 61-83.
	2	John G. P. Barnes, Programming ADA, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	3	DAVIES, O.L. On asymptotic formulae for hypergeometric series. I Hypergeometric series in which the Jhurth term is unity. Biometrika 25 (1933), 25.
	4	HUA, L. K. Introduction to Number Theory, Springer-Verlag, New York, 1982 (English translation).
	5	IEEE Inc. IEEE Standard for Binary Floating-Point Ar~thmetic (ANSI/IEEE std 754-1985), New York, 1985.
	6	IMSL Library. FORTRAN subroutines for mathematics and statistics. In User's Manual. Problem-Solving Software Systems, 1984, MDHYP-1-MDHYP-3.
	7	LI, X., AND DUBES, R. C. The selection of significant dichotomous features. Ill IEEE Proceedings of the 7th International Conference on Pattern Recognition, (Montreal, Aug. 1984), pp. 260-263.
	8	LI, X., AND NI, L. M. A pipeline architecture for computing cumulative hypergeometric distributions. In IEEE Proceedings of the 7th Symposium on Computer Arithmetic (Urbana, Ill., June 1985), pp. 166-172.
	9	LmBERMAN, G. J., AND OWEN, D.B. Tables of the hypergeometric probability distribution. Tech. Rep. 50, Stanford Univ., Applied Mathematics and Statistics Laboratories, 1961.
	10	LING, R. F., AND PRATT, J.W. The accuracy of Peizer approximations to the hypergeometeric distribution, with comparisons to some other approximations. J. Am. Stat. Assoc. 7'9 (Mar. 1984), 49 60.
	11	LUKE, Y. L. The Special Functions and Their Approximations, vols. I and 2, Academic Press, New York, 1969.
	12	Xuedong Luo, A practical sieve algorithm finding prime numbers, Communications of the ACM, v.32 n.3, p.344-346, March 1989 [doi>10.1145/62065.62072]
	13	MOLENAAR W. Approximations to the Poisson, binomial, and hypergeometric distribution functions. Mathematical centre Tracts 31, Amsterdam, 1970.
	14	PEIZER, D. B., AND PRATT, J.W. A normal approximation for binomal, F, Beta, and other common related tail probabilities, I. J. Am. Stat. Assoc. 63 (1968), 1416-1456.
	15	SCHILLING, E.G. Acceptance Sampling in Quality Control. Marcel Dekker, New York, 1982.
	16	STEVENSON, D. A proposed standard for binary floating-point arithmetic. IEEE Computer 14 (1981), 51-62.
	17	George W. Struble, Assembler Language Programming: The IBM System 360, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1975
	18	TEBBE, D. L. A multi-category decision network of dichotomous decision trees. In IEEE Proceedings of the 7th International Conference on Pattern Recognition (Montreal, Aug. 1984), pp. 264 266.
	19	Vax Ada Language Reference Manual. Digital Equipment Corp., Maynard, Mass., Feb. 1985.
	20	WISE, M.E. A quickly convergent expansion for cumulative hypergeometric probabilities, diroet and inverse, t~iometr~}~a 41 (1954), a17-329.