Potential speedup in `pbbinom` exploiting the symmetry of the distribution

[martinmodrak]

Hi,
due to the sequential nature of the algorithm in pbbinom (which is still wicked fast compared to competition!), it takes long time to evaluate with large q.

A simple improvement would be to take advantage of the symmetry of the distribution, i.e.:

extraDistr::pbbinom(q, size, alpha = alpha, beta = beta) ==
  1 - extraDistr::pbbinom(size - q - 1, size, alpha = beta, beta = alpha)

so we can choose whichever results in lower number of steps and always compute at most size / 2 steps.

A quick benchmark shows predictable speedup for large q:

N <- 100
q <- sample(550:950, size = N)
size <- 1000
alpha <- rexp(N)
beta <- rexp(N)

microbenchmark::microbenchmark(
  extraDistr::pbbinom(q, size, alpha = alpha, beta = beta),
  1 - extraDistr::pbbinom(size - q - 1, size, alpha = beta, beta = alpha),
  check = "equal"
)

# Unit: milliseconds
#                                                                     expr       min      lq      mean   median        uq       max neval
#                 extraDistr::pbbinom(q, size, alpha = alpha, beta = beta) 10.012301 10.4201 10.921302 10.70250 10.853801 18.183300   100
#  1 - extraDistr::pbbinom(size - q - 1, size, alpha = beta, beta = alpha)  4.763001  4.9289  5.197128  5.12875  5.244451  7.730002   100

Happy to provide a pull request if you agree this is worth implementing.

Thanks for all the hard work on the package.

[twolodzko]

Hi,

Thanks for the suggestion. I'm not doing any active development on this package anymore, but if you are willing to make a PR that would also make sure it's backward compatible, feel free to do so, and I'll be happy to merge and release it.

Best,
Tim