Cache FFT root tables about plonky2 HOT 3 CLOSED

IIRC a row in the root table is just the powers of a generator, so another option would be to compute the powers "just in time", with one mul in each inner loop iteration (continuing as it wraps around). Could the muls potentially be cheaper than memory lookups?

from plonky2.

Interesting idea! It would depend on the size of the problem. For small enough problems the bottleneck is the sheer number of instructions per iteration; in this case recomputing the powers would be slower. For problems that are big enough to be bound by memory bandwidth, it would be faster because the input/output buffer reads/writes would no longer compete with root table reads. I’ll run some experiments to see whether it helps on our problem sizes.

from plonky2.

Done in #261.

from plonky2.