I'm working on a small Python program for myself and I need an algorithm for fast multiplication of a huge array with prime powers (over 660 000 numbers, each is 7 digits). The result number is over 4 millions digits. Currently I'm using math.prod, which calculates it in ~10 minutes. But that's too slow, especially if I want to increase amount of numbers.
I checked some algorithms for faster multiplications, for example the Schönhage–Strassen algorithm and Toom–Cook multiplication, but I didn't understand how they work or how to implement them. I tried some versions that I've found on the internet, but they're not working too well and are even slower. I wonder if someone knows how to multiply these amounts of numbers faster, or could explain how to use some math to do this?
math.prod will accumulate a product one number at a time. You can do better by recursively dividing the list, taking the product of each half, for example, which reduces the size of the intermediate products.
This runs in a few seconds for me:
import math
def recursive_prod(ns, r):
if len(r) <= 10: # arbitrary small base case
return math.prod(ns[i] for i in r)
split_at = len(r) // 2
return recursive_prod(ns, r[:split_at]) * recursive_prod(ns, r[split_at:])
import random
ns = [random.randrange(1_000_000_000) for _ in range(660_000)]
p = recursive_prod(ns, range(len(ns)))