Fastest NTT about twenty-first HOT 6 CLOSED

With @Munksgaard's help and by using --release the runtime over the field with prime p=167772161 = 5 * 2^25 + 1 has been brought down from 17 seconds on my Dell XPS to 2 seconds on a data set with 2^20 i64 entries.

I have not yet managed to implement the algorithm from Microsoft Research linked above though.

from twenty-first.

There is something called "bit-reversal" ordering in the Microsoft Research article that I don't know what means.

from twenty-first.

Perhaps this is what they mean? https://en.wikipedia.org/wiki/Bit-reversal_permutation

from twenty-first.

Perhaps this is what they mean? https://en.wikipedia.org/wiki/Bit-reversal_permutation

That makes sense as the input always has length 2^n so such a permutation should be possible. So we need to map the value at index 000->000 and 011->110?

from twenty-first.

Might be what is implemented here: https://github.com/dusk-network/plonk/blob/d3412cec5fa5c2e720f848a6fd8db96d663e92a9/src/fft/domain.rs#L310

from twenty-first.

Closed by 524f54e and associated commits. We should have a pretty fast implementation now and NTT is nowhere near being a bottle-neck for any of our STARKs (Rescue Prime, Brainfuck, or Triton VM), so there's no reason to dwell more on this I think.

from twenty-first.