FFT of 1 element leading estimated negative results

[mmaker]

submitted from Geoffroy Couteau

[mmaker]

The function for estimating fft's is here: https://github.com/mmaker/zkalc/blob/main/frontend/lib/estimates.js#L153

[asn-d6]

Yep, there is something rotten with FFTs on zkalc. Even a 2^20 FFT over curve25519 will return a negative value.

[bufferhe4d]

I think both issues mentioned here are related to the data samples instead of the estimation functions.

For 1 FFT on BLS12-381 on arkworks, there is a 90x difference between the running times for n=2 and n=4 a bit unusual compared to that other libraries. extrapolating for n=1 intercepts the negative point because the slope is too steep.

For the curve25519 the case, the extrapolation goes up first and down to negative later because the value for n=8 is smaller than the value for n = 4:

"fft": {
"range": [
2,
4,
8
],
"results": [
141.1556570246799,
14238.34254577998,
2950.8871964366017
],
"stddev": [
0.4709058022611415,
456.51514683491695,
3.7409763450715916
]
}

[mmaker]

aha, makes sense thanks @bufferhe4d ! do you see a way to solve this when the size is too small? should we keep it flat for values that are smaller than the first sample?

[bufferhe4d]

Yes @mmaker keeping it flat would be the first solution that would come to my mind assuming this only happens for only few operations and libraries.

Also, while trying other approaches, I realizded something about the right extrapolation:

https://github.com/mmaker/zkalc/blob/7900c13668137f2031024e1cc21986a6cb5696fd/frontend/lib/estimates.js#L92C1-L92C38

Shouldn't this line read something like: .map((x, i) => x / Math.log2(xs[i])); ?

It feels counterintuitive that the regression changes based on the query that we make.

[mmaker]

if you don't have examples to extrapolate from, what we do is we take the last few samples and do regression from there. Do you have a better idea to go about it, or am I misunderstanding the question?