On the use of Montgomery multiplication in the computation of binary BBP-type formulas for mathematical constants

In this paper, we propose a method of using Montgomery multiplication in the computation of binary Bailey–Borwein–Plouffe (BBP)-type formulas for mathematical constants. The most time-consuming part of the computation of a BBP-type formula is modular exponentiation. It is known that modular exponentiation can be performed efficiently using binary modular exponentiation and Montgomery multiplication. When computing a Montgomery multiplication in binary, the modulus of the modular exponentiation must be an odd number. However, if the denominator of the fraction in a binary BBP-type formula, excluding the power of the base, is an even number, then the modulus of the modular exponentiation is also an even number, so Montgomery multiplication cannot be used directly. The proposed method makes it possible to use Montgomery multiplication for binary BBP-type formulas even in such a case.