In this paper, we discuss the division in the computation of binary Bailey–Borwein–Plouffe (BBP)-type formulas for mathematical constants. To compute a specific digit of a mathematical constant using a BBP-type formula, we need only calculate the fractional part of the sum of quotients. It is sufficient to perform division and summation for BBP-type formulas in fixed-point arithmetic for only the fractional part. In our previous work, calculation of the fractional part of a 128-bit quotient of a 64-bit dividend divided by a 64-bit divisor was performed in fixed-point arithmetic based on the exact division. We extend this to the case where calculation of the fractional part of an m-word quotient of a one-word dividend divided by a one-word divisor is performed in fixed-point arithmetic. When performing an exact division in binary, the denominator of the fraction must be an odd number. We show that even if the denominator of the fraction is an even number, exact division can be performed using the method of applying Montgomery multiplication to modular exponentiation in binary BBP-type formulas. We also show that rounding the quotient in the computation of binary BBP-type formulas reduces the accumulation of the round-off errors better than truncating the quotient.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Division in the Computation of Binary BBP-Type Formulas for Mathematical Constants

  • Daisuke Takahashi

摘要

In this paper, we discuss the division in the computation of binary Bailey–Borwein–Plouffe (BBP)-type formulas for mathematical constants. To compute a specific digit of a mathematical constant using a BBP-type formula, we need only calculate the fractional part of the sum of quotients. It is sufficient to perform division and summation for BBP-type formulas in fixed-point arithmetic for only the fractional part. In our previous work, calculation of the fractional part of a 128-bit quotient of a 64-bit dividend divided by a 64-bit divisor was performed in fixed-point arithmetic based on the exact division. We extend this to the case where calculation of the fractional part of an m-word quotient of a one-word dividend divided by a one-word divisor is performed in fixed-point arithmetic. When performing an exact division in binary, the denominator of the fraction must be an odd number. We show that even if the denominator of the fraction is an even number, exact division can be performed using the method of applying Montgomery multiplication to modular exponentiation in binary BBP-type formulas. We also show that rounding the quotient in the computation of binary BBP-type formulas reduces the accumulation of the round-off errors better than truncating the quotient.