c++ - Cache multiplication operation -

i have raise many numbers in base 50 @ power x (x anywhere between 1 , 300). numbers stored bignums.

my question is: because multiply lots of times 2 bignums digit digit (base 50) faster cache multiplications?

so, every time multiply a[] b[] have a[i]*b[j] many times a[i] , b[j] base 50 numbers.

i thinking instead of doing a[i]*b[j] each time, wouldn't faster create matrix beforehand: prod[50][50], prod[i][j] = i*j. have prod[a[i]][b[j]].

is reading memory faster doing multiplication?

quick example if question not clear:

instead of:

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

is faster:

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

?

short answer: yes, likely.

long answer: depends. faster calculate multiplication in cache fetch large number memory if it's not in cache.

you need implement caching , benchmark against "no cache" see get.

bear in mind powers can calculated more efficiently multiplying, e.g, if want y = x⁵, instead of calculating y = x * x * x * x * x, can calculate x2 = x * x;, y = x2 * x2 * x;, 4 multiplications instead of five. if have x³⁰⁰, make substantial savings using same scheme several times on (calculating x4 , x16 etc).