[Rd] Feature request: ..., binomial ... exact test efficiency improvements

[Chris Chang]

Hi,

In the binomial and Fisher’s 2x2 cases, the exact p-value calculation
remains tractable for N well beyond 1e6.  Ravi's function shows roughly
what I had in mind for binom.test, and the fisher.test two-sided p-value
calculation (as well as other two-sided exact tests based on unimodal
distributions with an efficient cdf+ccdf implementation) would work
essentially the same way.

(In the meantime, I'm drafting https://pypi.org/project/exact-tests/ ,
which uses a "double-double" arithmetic library to mitigate the
log-factorial catastrophic cancellation problem.  It's still a few weeks
away from what I'd consider production quality, but it does already contain
accurate and efficient implementations of binomial and Fisher 2x2 exact
tests allowing N up to ~2^31 in general, and ~2^52 in the one-sided cases.
That is where I will initially try to implement efficient alternatives to
the current fisher.test odds-ratio and confidence-interval calculations.)

--Chris

On Mon, May 18, 2026 at 9:20 AM Martin Maechler <maechler using stat.math.ethz.ch>
wrote:

> >>>>> Chris Chang
> >>>>>     on Sat, 16 May 2026 14:24:19 -0700 writes:
>
> [............................]
>
>     >> The one-sided binom.test() does not have this kind of
>     >> performance problem, but the two-sided test (which can be
>     >> written in a manner similar to qbinom(): instead of
>     >> searching for minimal k satisfying pbinom(k, ...) >= p,
>     >> search for the innermost opposite-tail k satisfying
>     >> dbinom(k) <= dbinom(x)) does.
>     >>
>     >> I can submit a patch with efficient two-sided binomial
>     >> and Fisher's 2x2 exact test implementations if there is
>     >> interest.
>     >>
>     >> --Chris
>
> Dear Chris  (and other readers),
>
> Above, you also mention binom.test(),
> and indeed, when I choose numbers in the order of 1e8,
> I see binom.test() taking quite some time, e.g.,
>
>  > system.time(btL <- binom.test(c(4e8, 1.01e8), p = 0.8, alternative =
> "two.sided"))
>    user  system elapsed
>   8.306   0.837   9.159
>
> and here, the time spent is really during p-value computation itself,
> everything else in binom.test() being very fast, AFAICS.
>
> Here it would be useful if you provide a patch to speed the
> p-value computation, still getting exact p-values, using
> pbinom() only instead of  dbinom(<large_support), ..).
>
> Traditionally, we as R core and any applied statistician would
> say that in such large N cases, simple normal approximations should be
> accurate enough,
> which it would be practically in any case, OTOH, it would still
> be nice to get the exact probabilities / confidence intervals,
> with a faster calulation.
>
> Eventually using a new argument  `exact = N < 1e6`  (for some N)
> and using a normal (or better!) asymptotic approximation for
> exact = FALSE  may make sense here as well...
>
> Thank you for raising the issue!
>
> With best regards,
> Martin
>
> --
> Martin Maechler
> ETH Zurich and  R Core team
>
>
>
>

	[[alternative HTML version deleted]]