CODEWITHSUNDEEP
c++caching
XCS
XCS

Reputation: 28157

Cache multiplication operation

I have to raise many numbers in base 50 at power X (X anywhere between 1 and 300). The numbers are stored as bignums.

My question is: because I will multiply lots of times two bignums digit by digit (base 50) will it be faster to cache this multiplications?

So, every time I multiply a[] with b[] I will have to do a[i]*b[j] many times where a[i] and b[j] are base 50 numbers.

I was thinking instead of actually doing a[i]*b[j] each time, wouldn't it be faster to create a matrix beforehand: prod[50][50], where prod[i][j] = i*j. I will then have something like prod[a[i]][b[j]].

Is reading from memory faster then actually doing the multiplication?

Quick example if my question is not clear:

Instead of:

for(int i=1; i<=100; ++i){
   sum += 50*30;
   sum += 37*20;
}

Is this faster:

for(int i=1; i<=100; ++i){
   sum += prod[50][30];
   sum += prod[37][20];
}

?

Upvotes: 0

Views: 139

Answers (1)

Mats Petersson
Mats Petersson

Reputation: 129434

Short answer: yes, most likely.

Long answer: It depends. It is probably faster to calculate a multiplication in cache than it is to fetch a large number from memory if it's not in cache.

You really need to implement the caching and benchmark it against the "no cache" to see what you get.

Bear in mind also that powers can be calculated more efficiently than just multiplying, e.g, if we want y = x5, instead of calculating y = x * x * x * x * x, we can calculate x2 = x * x;, then y = x2 * x2 * x;, which is only four multiplications instead of five. If you have x300, you could make some substantial savings by using that same scheme several times over (calculating x4 and x16 etc).

Upvotes: 3

Related Questions