From [the Readme of secp256k1][1] we can see the following:

Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.

I was wondering why in particular the table used precomputed table of multiples of 16? I would have expected a higher number or a more dynamic approach which includes dynamic caching.

Let me elaborate a little bit:

With multiples of 16 we always need 4 bit computed in the table. meaning we have 256 / 4 = 64 buckets with 16 entries for each bucket.

Let n be the number of bits in a window for which we compute powers of g this would result in the general formula for the amount of precomputed values in our table for n > 1:

256 / n * 2 ^ n

with n = 4 we have 64 * 16 = 1024 entries.

When choosing n = 8 we would have 32 * 256 = 8192 entries. However when actually computing a multiplication we would only need 32 additions instead of 64. creating a speedup of a factor of 2 for 8 times us much memory usage of our lookup table.

With n = 16 we would have 16 * 65536 = 1048576 or 1M * sizeof(point) of main memory to have only 16 point additions when computing a multiplication.

Obviously such a big lookup table requires some time when setting up the library. Even if the table was already precomputed and in binary shipped with the library.

Anyway I was wondering for the particular choice of 4 bits. I would assume that 8 bits was better and probably even taking 16 bit windows seems fairly reasonable. [1]:https://github.com/bitcoin/bitcoin/tree/bccb4d29a8080bf1ecda1fc235415a11d903a680/src/secp256k1

From the Readme of secp256k1 we can see the following:

Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.

I was wondering why in particular the table used precomputed table of multiples of 16? I would have expected a higher number or a more dynamic approach which includes dynamic caching.

Let me elaborate a little bit:

With multiples of 16 we always need 4 bit computed in the table. meaning we have 256 / 4 = 64 buckets with 16 entries for each bucket.

Let n be the number of bits in a window for which we compute powers of g this would result in the general formula for the amount of precomputed values in our table for n > 1:

256 / n * 2 ^ n

with n = 4 we have 64 * 16 = 1024 entries.

When choosing n = 8 we would have 32 * 256 = 8192 entries. However when actually computing a multiplication we would only need 32 additions instead of 64. creating a speedup of a factor of 2 for 8 times us much memory usage of our lookup table.

With n = 16 we would have 16 * 65536 = 1048576 or 1M * sizeof(point) of main memory to have only 16 point additions when computing a multiplication.

Obviously such a big lookup table requires some time when setting up the library. Even if the table was already precomputed and in binary shipped with the library.

Anyway I was wondering for the particular choice of 4 bits. I would assume that 8 bits was better and probably even taking 16 bit windows seems fairly reasonable.