有限体ライブラリ
2021-04-07 fft, ntt 計測
benchmark_fft
N = 1024 13.031 μs (34 allocations: 34.67 KiB)
N = 2048 17.974 μs (36 allocations: 66.58 KiB)
N = 4096 35.842 μs (36 allocations: 130.58 KiB)
N = 8192 70.616 μs (36 allocations: 258.58 KiB)
N = 16384 141.869 μs (36 allocations: 514.58 KiB)
N = 32768 296.155 μs (36 allocations: 1.00 MiB)
N = 65536 693.166 μs (36 allocations: 2.00 MiB)
benchmark_ifft
N = 1024 14.689 μs (41 allocations: 27.06 KiB)
N = 2048 20.712 μs (42 allocations: 51.02 KiB)
N = 4096 41.356 μs (43 allocations: 98.97 KiB)
N = 8192 81.199 μs (43 allocations: 194.97 KiB)
N = 16384 157.689 μs (43 allocations: 386.97 KiB)
N = 32768 337.053 μs (43 allocations: 770.97 KiB)
N = 65536 684.051 μs (43 allocations: 1.50 MiB)
benchmark_convolution
N = 1024 43.018 μs (110 allocations: 112.53 KiB)
N = 2048 62.187 μs (116 allocations: 216.25 KiB)
N = 4096 123.629 μs (117 allocations: 424.20 KiB)
N = 8192 245.753 μs (117 allocations: 840.20 KiB)
N = 16384 484.672 μs (117 allocations: 1.63 MiB)
N = 32768 1.075 ms (117 allocations: 3.26 MiB)
N = 65536 2.400 ms (117 allocations: 6.51 MiB)
benchmark_nnt
N = 1024 189.488 μs (5115 allocations: 659.50 KiB)
N = 2048 388.828 μs (10235 allocations: 1.34 MiB)
N = 4096 796.156 μs (20476 allocations: 2.77 MiB)
N = 8192 1.629 ms (40962 allocations: 5.72 MiB)
N = 16384 3.323 ms (81934 allocations: 11.81 MiB)
N = 32768 6.882 ms (163878 allocations: 24.38 MiB)
N = 65536 16.030 ms (327766 allocations: 50.25 MiB)
benchmark_intt
N = 1024 559.106 μs (6145 allocations: 716.14 KiB)
N = 2048 1.210 ms (12289 allocations: 1.45 MiB)
N = 4096 2.681 ms (24582 allocations: 2.98 MiB)
N = 8192 5.981 ms (49164 allocations: 6.16 MiB)
N = 16384 13.793 ms (98328 allocations: 12.69 MiB)
N = 32768 30.393 ms (196656 allocations: 26.13 MiB)
N = 65536 66.406 ms (393312 allocations: 53.75 MiB)
benchmark_rns
2 ^ 4 add 49.394 ns (1 allocation: 112 bytes)
2 ^ 4 mul 49.340 ns (1 allocation: 112 bytes)
2 ^ 4 pow 51.570 ns (1 allocation: 112 bytes)
2 ^ 16 add 71.325 ns (1 allocation: 160 bytes)
2 ^ 16 mul 71.209 ns (1 allocation: 160 bytes)
2 ^ 16 pow 75.001 ns (1 allocation: 160 bytes)
2 ^ 64 add 128.588 ns (1 allocation: 288 bytes)
2 ^ 64 mul 129.787 ns (1 allocation: 288 bytes)
2 ^ 64 pow 142.371 ns (1 allocation: 288 bytes)
2 ^ 256 add 307.317 ns (1 allocation: 672 bytes)
2 ^ 256 mul 307.393 ns (1 allocation: 672 bytes)
2 ^ 256 pow 333.329 ns (1 allocation: 672 bytes)
2 ^ 1024 add 893.311 ns (1 allocation: 1.98 KiB)
2 ^ 1024 mul 890.674 ns (1 allocation: 1.98 KiB)
2 ^ 1024 pow 966.611 ns (1 allocation: 1.98 KiB)
2 ^ 4096 add 2.844 μs (1 allocation: 6.06 KiB)
2 ^ 4096 mul 2.855 μs (1 allocation: 6.06 KiB)
2 ^ 4096 pow 3.062 μs (1 allocation: 6.06 KiB)
2 ^ 16384 add 9.399 μs (2 allocations: 20.02 KiB)
2 ^ 16384 mul 9.699 μs (2 allocations: 20.02 KiB)
2 ^ 16384 pow 10.099 μs (2 allocations: 20.02 KiB)
2 ^ 65536 add 32.499 μs (2 allocations: 69.02 KiB)
2 ^ 65536 mul 34.000 μs (2 allocations: 69.02 KiB)
2 ^ 65536 pow 39.200 μs (2 allocations: 69.02 KiB)
2 ^ 262144 add 112.899 μs (2 allocations: 242.77 KiB)
2 ^ 262144 mul 234.800 μs (2 allocations: 242.77 KiB)
2 ^ 262144 pow 251.100 μs (2 allocations: 242.77 KiB)
2 ^ 1048576 add 401.701 μs (2 allocations: 867.08 KiB)
2 ^ 1048576 mul 862.600 μs (2 allocations: 867.08 KiB)
2 ^ 1048576 pow 949.600 μs (2 allocations: 867.08 KiB)- RNS諸演算
- RNSテスト
- RNS係数多項式
- RNS係数多項式環 ✅ 2024-07-17
/ not defined on RNS で div_modが出来ない
FFT
┌──────┬──────────┬─────────┐
│ n │ naive │ fft_cpu │
│ │ [ns] │ [ns] │
├──────┼──────────┼─────────┤
│ 128 │ 16491 │ 39921 │
│ 256 │ 55906 │ 39752 │
│ 512 │ 188752 │ 47709 │
│ 1024 │ 739912 │ 106128 │
│ 2048 │ 2834942 │ 95926 │
│ 4096 │ 11570092 │ 226183 │
└──────┴──────────┴─────────┘