1

For a math routine I need a lookup table of exponent "n" of 251 for all integers 0 < n < 65536. Furthermore, the result are to be trimmed to modulo 216, i.e., stored in a 16-bit variable. In other words,

uint16_t result[65536];
void calculate_exponent_lookup_table(void)
{
  for (uint16_t  i = 0 ; i < 65536 ; i++)
      result[i] = pow(251, i) % 65536;
}

But due to resource limitations, I don't have space to separately calculate and store the "result" array statically, nor the computation power to calculate the higher order exponents by repeated multiplication in the given time duration, at run-time.

So, I came across this link about Binary Exponentiation.

Using the above algorithm, I need to pre-calculate and store 16 exponents of 251 i.e 2511 to 25116. I just need to do 16 multiplications, i.e. log 65536, at maximum to obtain any exponent, during runtime, which is doable.

But since the results are going to be stored modulo 216, can I still optimize this and save some computation?

HungryFoolish
  • 542
  • 1
  • 9
  • 27
  • Did you mean that doing one multiplication per itation (ie the previous result, times 251) works out too slow in the end? Or that it's too slow to recalculate from scratch every time? – harold Nov 11 '20 at 07:45
  • @harold, I meant, If I don't store the exponents in a look-up table (due to memory constraints), I'll need to calculate a particular exponent at run-time during look-up by repeated multiplication. Please note, I need these exponent result quite often in the math routine. – HungryFoolish Nov 11 '20 at 07:50
  • Does this answer your question? [Calculating pow(a,b) mod n](https://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – phuclv Nov 11 '20 at 07:57
  • @RishavAmbasta change the loop to `result[i] = result[i - 1]*251 % 65536;` and it'll run much faster. You don't need to recalculate the low powers every time – phuclv Nov 11 '20 at 08:00
  • 1
    You need exponents in range [0, 15] rather than [1, 16]. – Giovanni Cerretani Nov 11 '20 at 08:02

1 Answers1

0

Yes, you can do modulo at any stage as many times you want. However, your problem is not with that but with overflowing when using the pow func. The intermediate results before the modulo are too big.

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • correct. But, just doing modulo at every stage will not save me any computation right ? – HungryFoolish Nov 11 '20 at 07:54
  • 1
    using `pow` here is actually wrong and much slower because the OP just wants the modulo of the power (called modpow in many languages and pow with 3 arguments in python) – phuclv Nov 11 '20 at 07:59
  • @RishavAmbasta It's not a matter of speed but of correctness. Speed is meaningless if the computation is incorrect – SomeWittyUsername Nov 11 '20 at 09:56