Multiplication of one big integer and a long list of integers - fast

Question

This is an example of multiplying a big integer to a list of integers.

3792538124902347509274019274102947 * {2352, 4981, 6492, 3469, 2093, 1049, 5482, 5932, 1923, 7912}

{8920049669770321341812493332690131344,
18890632400138592943693890004306779007,
24621157506866040030206933127476331924,
13156314755286243509671572861863123143,
7937782295420613336910522340697468071,
3978372493022562537228446218533991403,
20790694000714669045840173660632355454,
22497336156920725425013482333978681604,
7293050814187214260333939064099967081,
30006561644227373493376040496702516664}

Note that 3792538124902347509274019274102947 is 34-digit number.
Each element in the list is 4-digit number and there are 10 elements in the list.

To generate the output, we had done

1-digit multiply 1-digit : 34*4*10==1360 times
34~37-digit plus 34~37-digit : 3*10 times (to add four numbers, we plus three times)

Suppose that we have following multiplication table before :

3792538124902347509274019274102947*0==0
3792538124902347509274019274102947*1==3792538124902347509274019274102947
3792538124902347509274019274102947*2==7585076249804695018548038548205894
3792538124902347509274019274102947*3==11377614374707042527822057822308841
3792538124902347509274019274102947*4==15170152499609390037096077096411788
3792538124902347509274019274102947*5==18962690624511737546370096370514735
3792538124902347509274019274102947*6==22755228749414085055644115644617682
3792538124902347509274019274102947*7==26547766874316432564918134918720629
3792538124902347509274019274102947*8==30340304999218780074192154192823576
3792538124902347509274019274102947*9==34132843124121127583466173466926523

Then we need
1-digit multiply 1-digit : 0 times
34~37-digit plus 34~37-digit : 3*10 times

So we save 1360 1-digit multiplications in this case.

But I know there are things to be considered carefully :

1. To use the multiplication table, we have to substitute.
   For example, we have to substitute
   3792538124902347509274019274102947*5 with 18962690624511737546370096370514735.
   Seeking for the multiplication table or substitution itself is also a kind of workload.

2. It is possible that mathematica's built-in feature may already calculated so. I mean mathematica automatically uses optimized method for multiplying a single integer
   and a list of integers.

3. CPU works in base 2. My theory is about base 10.. that difference is a little worrisome.

Q) Do you agree that when multiplying
a fixed very big integer and very long list of integers,
it is good to build multiplication table first?

Answer 1

1. In binary format you would not need a lookup table because one simply decomposes one of the factors into powers of 2. Then multiplying by powers of 2 is just about shifting digits to the left. The actually intense part is the accumulation of the intermediate results.

2. You assume that the integer multiplication is carried out digit per digit on the machine. I don't know about the details, but I m pretty sure that quite a lot concurrency is built into the circuits for integer arithmetic so that the runtime depends only on the register length and not on the actual number of digits of the factors. (Well, if both factors are too large, then maybe the handling of integer overflow may induce a certain extra cost.)

3. With 39 decimal digits the result is too large for a machine integer register (nowadays often 64 bit). That means that the multiplication has to be handled in software. But then again, I doubt that the lookup table would help anything because the most costly part remains: the addition. I guess a good strategy would be to represent the numbers by a couple of 64 bit or 32 bit (unsigned?) integers, use the hardware to accelerate the multiplication of these parts and somehow handle the carry-overs. But instead of rolling out my own multiplication routine for long integers, I'd rather rely on people at Wolfram Research having done a good job.

Answer 2

I expect that Wolfram Research has put more effort into efficiently multiplying big integers than any of us will. It's always going to be quicker to do math with "small" integers (fewer than 64 bits) than large ones. So I suggest reducing the number of big integer operations as much as possible.

To do so, multiply the four-digit integers together until the result is close to 64 bits. In most cases, that will mean multiplying four or five four-digit integers. Given the numbers you listed, here is what I am suggesting:

2352 * 4981 * 6492 * 3469 = 263837589293376
2093 * 1049 * 5482 * 5932 = 71397809887768
1923 * 7912 = 15214776

Then multiply the big integer by 263837589293376, the result of that by 71397809887768, and the result of that by 15214776. This method yields an answer with only three big integer operations. I suspect that you can find two groups of five of the four-digit integers where the product of each group is less than 2**64. Doing so would reduce the number of big integer operations to two.

You could also pull out all the factors of 2 from each of the small integers. Do your multiplications with all the remaining odd numbers and, at the end, multiply by the appropriate power of 2. Multiplying by a power of 2 should be fast because all you're doing is shifting bits but it depends on the internal representation of big integers.