Exact Short Products From Truncated Multipliers

03/25/2023

∙

by   Daniel Lemire, et al.

∙

0

∙

share

We sometimes need to compute the most significant digits of the product of small integers with a multiplier requiring much storage: e.g., a large integer (e.g., 5^100) or an irrational number (π). We only need to access the most significant digits of the multiplier-as long as the integers are sufficiently small. We provide an efficient algorithm to compute the range of integers given a truncated multiplier and a desired number of digits.