ALGORITHM 643: FEXACT: a FORTRAN subroutine for Fisher's exact test on unordered r×c contingency tables

ABSTRACT

The computer code for Mehta and Patel's (1983) network algorithm for Fisher's exact test on unordered r×c contingency tables is provided. The code is written in double precision FORTRAN 77. This code provides the fastest currently available method for executing Fisher's exact test, and is shown to be orders of magnitude superior to any other available algorithm. Many important details of data structures and implementation that have contributed crucially to the success of the network algorithm are recorded here.

REFERENCES

• 1: BAKER, R.J. Exact distributions derived from two-way tables. J. Royal Stat. Soc. Series C, 26, 2 (1977), 199.-206.
• 2: GAIL, M., AND MANTEL, N. Counting the number of contingency tables with fixed margins. J. Am. Stat. Assoc. 72 (1977), 859-862.
• 3: HANCOCK, T.W. Remark on algorithm 434 {G2}. Exact probabilties for rxc contingency tables. Commun. ACM 18, 2 (Feb. 1975), 117-119.
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: D. L. March, Algorithm 434: exact probabilities for R×C contingency tables [G2], Communications of the ACM, v.15 n.11, p.991-992, Nov. 1972 [doi>10.1145/355606.355607]
• 6: MEHTA, C. R., AND PATEL, N.R. A network algorithm for the exact treatment of the 2xk contingency table. Commun. Stat. B9, 6 (1980), 649-664.
• 7: MEHTA, C. R., AND PATEL, N.R. A network algorithm for performing Fisher's exact test in rxc contingency tables. J. Am. Stat. Assoc. 78, 382 (1983), 427-434.
• 8: MEHTA, C. R., PATEL, N. R., AND TSIATIS, A. A. Exact significance testing to establish treatment equivalence with ordered categorical data. Biometrics 40, 3 (1984), 819-825.
• 9: MEHTA, C. R., PATEL, N. R., AND GRAY, R. On computing an exact confidence interval for the common odds ratio in several 2x2 contingency tables. J. Am. Stat. Assoc. 80, 392 (1985), 969-973.
• 10: PAGANO, M., AND HALVORSEN, K. An algorithm for finding the exact significance levels of rXc contingency tables. J. Am. Stat. Assoc. 76 (1981), 931-934.
• 11: VERBEEK, A., AND KROONENBERG, P. A survey of algorithms for exact distributions of test statistics in rxc contingency tables with fixed margins. Comput. Star. Data Anal. 3 (1985), 159-185.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical software; Statistical computing

General Terms:
Algorithms

Keywords:
graph theory, spanning trees