search

ingonyama-zk / icicle

a GPU Library for Zero-Knowledge Acceleration
MIT License
303 stars 88 forks source link

[QA] Can you give a paper about mixed-radix ntt algorithm? #543

Open qiji2023 opened 1 month ago

qiji2023 commented 1 month ago

Description

I want to learn the mixed-radix ntt algorithm, but there are not comments in the code, I can understand radix-2, but the mixed-radix is very complex, I can't understand the code. Could you give me a paper about mixed-radix ntt algorithm? or add some comments in the code. Thanks very much

jeremyfelder commented 1 month ago

@qiji2023 We have some documentation here: https://dev.ingonyama.com/icicle/primitives/ntt#mixed-radix. If you want something a bit more thorough, we can write something up in the near future.

qiji2023 commented 1 month ago

@jeremyfelder I have some questions， could you give me some questions？

  1. Can you explain fast twiddle? I can't understand your codes and your codes don't have any comments!!!!
  2. Can you explain digit reverse? I can't understand your codes and your codes don't have any comments!!!! Thanks! I have to say a word, your codes are very ugly, maybe you don't want users to make sense.
yshekel commented 1 month ago

I understand your concern about the lack of comments and clarity in the code. We will be adding detailed comments to explain the logic and purpose, making the code more readable and easier to understand.

About you questions:

  1. It is a way to store the twiddles in GPU memory in an efficient layout for reading during compute. The downside of it is that we have to duplicate values and store them more than once. So essentially a tradeoff between performance and memory.
  2. it's a generalization of bit-reverse that we have in radix2 implementation. In mixed radix, we split the logN bits to digits with 4,5 or 6 bits each, in contrast to 1b in the radix2.