FFT

[kmyk]

REP (i, n) REP (j, n) c[i + j] += a[i] * b[j] があったら c = fft(a, b) にするやつ

• [ ] core 言語に新しい組み込み関数 FFT InverseFFT みたいなやつを足す (あるいは Convolution という組み込み関数を足す？) (Jikka.Core.Language.Expr)
  • [ ] それらが $ jikka execute ... で実行できるようにする (Jikka.Core.Execute)
  • [ ] それらが C++ に変換されるようにする (Jikka.CPlusPlus.Convert.FromCore)
  • [ ] 必要なら runtime/include/jikka/convoluion.hpp を足して実装する
  • [ ] それらが C++ で使われていたら自動で #include "jikka/convolution.hpp" とか #include <atcoder/convolution> されるようにする (Jikka.CPlusPlus.Format)
  • [ ] その他必要なもろもろをやる (コンパイルエラーや警告が出なくなれば OK)
• [ ] core 言語に、foldl (fun c i -> foldl (fun c j -> setAt c (i + j) a[i] b[j]) c (range n)) c (range n) やあるいはこれと等価な部分式があれば、それを FFT を使って書き直すような rewrite rule を足す (Jikka.Core.Convert.FFT みたいなのを足して Jikka.Core.Convert の中から呼び出す)

[kmyk]

https://noshi91.hatenablog.com/entry/2020/10/27/175112 の網羅が最終目標です

[kmyk]

@hotman78 さんが手伝ってくれそう。とてもありがたい