lambdaworks_math/circle/
twiddles.rs

1extern crate alloc;
2use crate::{
3    circle::cosets::Coset,
4    field::{element::FieldElement, fields::mersenne31::field::Mersenne31Field},
5};
6use alloc::vec::Vec;
7
8#[derive(PartialEq)]
9pub enum TwiddlesConfig {
10    Evaluation,
11    Interpolation,
12}
13#[cfg(feature = "alloc")]
14pub fn get_twiddles(
15    domain: Coset,
16    config: TwiddlesConfig,
17) -> Vec<Vec<FieldElement<Mersenne31Field>>> {
18    // We first take the half coset.
19    let half_domain_points = Coset::get_coset_points(&Coset::half_coset(domain.clone()));
20
21    // The first set of twiddles are all the y coordinates of the half coset.
22    let mut twiddles: Vec<Vec<FieldElement<Mersenne31Field>>> = Vec::new();
23    twiddles.push(half_domain_points.iter().map(|p| p.y).collect());
24
25    if domain.log_2_size >= 2 {
26        // The second set of twiddles are the x coordinates of the first half of the half coset.
27        twiddles.push(
28            half_domain_points
29                .iter()
30                .take(half_domain_points.len() / 2)
31                .map(|p| p.x)
32                .collect(),
33        );
34        for _ in 0..(domain.log_2_size - 2) {
35            // The rest of the sets of twiddles are the "square" of the x coordinates of the first half of the previous set.
36            let prev = twiddles.last().unwrap();
37            let cur = prev
38                .iter()
39                .take(prev.len() / 2)
40                .map(|x| x.square().double() - FieldElement::<Mersenne31Field>::one())
41                .collect();
42            twiddles.push(cur);
43        }
44    }
45
46    if config == TwiddlesConfig::Interpolation {
47        // For the interpolation, we need to take the inverse element of each twiddle in the default order.
48        // We can take inverse being sure that the `unwrap` won't panic because the twiddles are coordinates
49        // of elements of the coset (or their squares) so they can't be zero.
50        twiddles.iter_mut().for_each(|x| {
51            FieldElement::<Mersenne31Field>::inplace_batch_inverse(x).unwrap();
52        });
53    } else {
54        // For the evaluation, we need reverse the order of the vector of twiddles.
55        twiddles.reverse();
56    }
57    twiddles
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn evaluation_twiddles_vectors_length_is_correct() {
66        let domain = Coset::new_standard(20);
67        let config = TwiddlesConfig::Evaluation;
68        let twiddles = get_twiddles(domain, config);
69        for i in 0..twiddles.len() - 1 {
70            assert_eq!(2 * twiddles[i].len(), twiddles[i + 1].len())
71        }
72    }
73
74    #[test]
75    fn interpolation_twiddles_vectors_length_is_correct() {
76        let domain = Coset::new_standard(20);
77        let config = TwiddlesConfig::Interpolation;
78        let twiddles = get_twiddles(domain, config);
79        for i in 0..twiddles.len() - 1 {
80            assert_eq!(twiddles[i].len(), 2 * twiddles[i + 1].len())
81        }
82    }
83}
lambdaworks_math/circle/twiddles.rs

lambdaworks_math/circle/
twiddles.rs
