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

use crate::FieldElement;
use std::prelude::v1::*;

#[derive(Clone, PartialEq, Eq)]
#[cfg_attr(feature = "std", derive(Debug))]
pub struct GeometricSeries {
    current: FieldElement,
    step:    FieldElement,
    length:  usize,
}

impl GeometricSeries {
    pub fn at(&self, index: usize) -> FieldElement {
        &self.current * self.step.pow(index)
    }

    /// Transform the series
    pub fn step_by(mut self, step: usize) -> Self {
        assert!(step > 0);
        self.step = self.step.pow(step);
        self.length /= step;
        self
    }
}

impl Iterator for GeometricSeries {
    type Item = FieldElement;

    fn next(&mut self) -> Option<Self::Item> {
        if self.length == 0 {
            None
        } else {
            // OPT: Make clone free and return reference.
            let item = self.current.clone();
            self.current *= &self.step;
            self.length -= 1;
            Some(item)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.length, Some(self.length))
    }
}

// TODO: Implement multiplication for GeometricSeries x GeometricSeries and
// GeometricSeries x FieldElement.

pub fn geometric_series(base: &FieldElement, step: &FieldElement) -> GeometricSeries {
    GeometricSeries {
        current: base.clone(),
        step:    step.clone(),
        length:  usize::max_value(),
    }
}

pub fn root_series(order: usize) -> GeometricSeries {
    let root = FieldElement::root(order).expect("No root found of given order.");
    GeometricSeries {
        current: FieldElement::ONE,
        step:    root,
        length:  order,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use zkp_macros_decl::field_element;
    use zkp_u256::U256;

    #[test]
    fn geometric_series_test() {
        let base =
            field_element!("0142c45e5d743d10eae7ebb70f1526c65de7dbcdb65b322b6ddc36a812591e8f");
        let step =
            field_element!("00000000000000000000000000000000000000000000000f00dbabe0cafebabe");

        let mut domain = geometric_series(&base, &step);
        assert_eq!(domain.next(), Some(base.clone()));
        assert_eq!(domain.next(), Some(&base * &step));
        assert_eq!(domain.next(), Some(&base * &step * &step));
        assert_eq!(domain.next(), Some(&base * &step * &step * &step));
    }
}