Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$?
We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) or else on the same order.
I am trying to find possibilities for precomputation and/or parallelism.
For example, if two of the $B_{i}$'s are "near" each other, we can do:
$$AB_{0} = AB_{0}$$ $$T = A(B_{1} - B_{0})$$ $$AB_{1} = T + AB_{0}$$
We still have two multiplications, but since $B_{1}$ and $B_{0}$ are close, one of the multiplications is smaller than it would be otherwise, though I'm not sure whether that is useful in practice. If any pair of $B_{i}$'s differ by $2^{k}$, then we have an obvious reduction. But this is rare and hard to identify.
Absent any other ideas for parallelism, we look at precomputation.
If we were using a digital circuit, we could omit (on average) half the partial products (i.e. those for which the corresponding bit in $A$ is $0$) and pack the adders to avoid them.
In software this might analog to a fixed sequence of binary shifts & adds. Using FFT multiplication, we could precompute $A$'s polynomial and FFT. But given the huge overhead of FFT multiplication this might only succeed in cutting down the overhead rather than reaping an advantage (?)
Any ideas or pointers (even far-fetched) would be appreciated. Are there any general strategies for algorithm optimization besides parallelism and precomputation? I'm trying to think outside the proverbial box.
Though only inspirationally-related, I was intrigued by Daniel Bernstein's parallel algorithm for finding the smooth parts of a large set of integers.
Related question: Number Theoretic Transform (NTT) to speed up multiplications
If anyone thinks this question belongs on StackOverflow, let me know.