-
Notifications
You must be signed in to change notification settings - Fork 26
/
fft_fr_test.go
99 lines (91 loc) · 3.24 KB
/
fft_fr_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package kzg
import (
"testing"
"github.com/protolambda/go-kzg/bls"
)
func TestFFTRoundtrip(t *testing.T) {
fs := NewFFTSettings(4)
data := make([]bls.Fr, fs.MaxWidth, fs.MaxWidth)
for i := uint64(0); i < fs.MaxWidth; i++ {
bls.AsFr(&data[i], i)
}
coeffs, err := fs.FFT(data, false)
if err != nil {
t.Fatal(err)
}
res, err := fs.FFT(coeffs, true)
if err != nil {
t.Fatal(err)
}
for i := range res {
if got, expected := &res[i], &data[i]; !bls.EqualFr(got, expected) {
t.Errorf("difference: %d: got: %s expected: %s", i, bls.FrStr(got), bls.FrStr(expected))
}
}
t.Log("zero", bls.FrStr(&bls.ZERO))
t.Log("zero", bls.FrStr(&bls.ONE))
}
func TestInvFFT(t *testing.T) {
fs := NewFFTSettings(4)
data := make([]bls.Fr, fs.MaxWidth, fs.MaxWidth)
for i := uint64(0); i < fs.MaxWidth; i++ {
bls.AsFr(&data[i], i)
}
debugFrs("input data", data)
res, err := fs.FFT(data, true)
if err != nil {
t.Fatal(err)
}
debugFrs("result", res)
ToFr := func(v string) (out bls.Fr) {
bls.SetFr(&out, v)
return
}
expected := []bls.Fr{
ToFr("26217937587563095239723870254092982918845276250263818911301829349969290592264"),
ToFr("8864682297557565932517422087434646388650579555464978742404310425307854971414"),
ToFr("42397926345479656069499145686287671633657326275595206970800938736622240188372"),
ToFr("20829590431265536861492157516271359172322844207237904580180981500923098586768"),
ToFr("26217937587563095241456442667129809078233411015607690300436955584351971573760"),
ToFr("40905488090558605688319636812215252217941835718478251840326926365086504505065"),
ToFr("42397926345479656066034000860214019314881056744907464192530686267856878225364"),
ToFr("28940579956850634752414611731231234796717032005329840446009750351940536963695"),
ToFr("26217937587563095239723870254092982918845276250263818911301829349969290592256"),
ToFr("23495295218275555727033128776954731040973520495197797376593908347998044220817"),
ToFr("10037948829646534413413739647971946522809495755620173630072972432081702959148"),
ToFr("11530387084567584791128103695970713619748716782049385982276732334852076679447"),
ToFr("26217937587563095237991297841056156759457141484919947522166703115586609610752"),
ToFr("31606284743860653617955582991914606665367708293289733242422677199015482597744"),
ToFr("10037948829646534409948594821898294204033226224932430851802719963316340996140"),
ToFr("43571192877568624546930318420751319449039972945062659080199348274630726213098"),
}
for i := range res {
if got := &res[i]; !bls.EqualFr(got, &expected[i]) {
t.Errorf("difference: %d: got: %s expected: %s", i, bls.FrStr(got), bls.FrStr(&expected[i]))
}
}
}
func TestEvaluatePolyInEvaluationForm(t *testing.T) {
fs := NewFFTSettings(4)
// coeffs
data := make([]bls.Fr, fs.MaxWidth, fs.MaxWidth)
for i := uint64(0); i < fs.MaxWidth; i++ {
data[i] = *bls.RandomFr()
}
// coefficients to eval form
res, err := fs.FFT(data, false)
if err != nil {
t.Fatal(err)
}
for i := 0; i < 100; i++ {
x := bls.RandomFr()
var y1 bls.Fr
bls.EvalPolyAt(&y1, data, x)
var y2 bls.Fr
bls.EvaluatePolyInEvaluationForm(&y2, res, x, fs.ExpandedRootsOfUnity[:fs.MaxWidth], 0)
if !bls.EqualFr(&y1, &y2) {
debugFrs("y", []bls.Fr{y1, y2})
t.Fatal("expected to evaluate to the same value")
}
}
}