chfft 0.3.4

Fastest Fourier Transform library implemented with pure Rust.
Documentation 
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! Chalharu's Fastest Fourier Transform.
//!
//! # Licensing
//! This Source Code is subject to the terms of the Mozilla Public License
//! version 2.0 (the "License"). You can obtain a copy of the License at
//! http://mozilla.org/MPL/2.0/ .

#[derive(Debug)]
pub(crate) struct Factor {
    pub(crate) value: usize,
    pub(crate) count: usize,
}

struct FactorIterator {
    value: usize,
    prime: usize,
}

impl Iterator for FactorIterator {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        loop {
            match self.prime {
                4 => {
                    if self.value.trailing_zeros() >= 2 {
                        self.value >>= 2;
                        return Some(4);
                    } else {
                        self.prime = 2;
                    }
                }
                2 => {
                    if self.value & 1 == 0 {
                        self.value >>= 1;
                        return Some(2);
                    } else {
                        self.prime = 3;
                    }
                }
                _ => {
                    if self.value >= self.prime * self.prime {
                        if self.value % self.prime == 0 {
                            self.value /= self.prime;
                            return Some(self.prime);
                        } else {
                            self.prime += 2;
                        }
                    } else if self.value > 1 {
                        let v = self.value;
                        self.value = 0;
                        return Some(v);
                    } else {
                        return None;
                    }
                }
            }
        }
    }
}

fn prime_factorization_iter(value: usize) -> FactorIterator {
    FactorIterator { value, prime: 4 }
}

// 素因数分解
pub(crate) fn prime_factorization(value: usize, max: usize) -> Vec<Factor> {
    let mut factors = Vec::<Factor>::new();
    let mut count = 0;
    let mut prime = 0;
    let mut fac4count = 0;
    for p in prime_factorization_iter(value) {
        if p > max {
            return Vec::<Factor>::new();
        }
        if prime != p {
            if count > 0 {
                if prime == 4 {
                    fac4count = count;
                } else {
                    if prime > 4 && fac4count != 0 {
                        factors.push(Factor {
                            value: 4,
                            count: fac4count,
                        });
                        fac4count = 0;
                    }
                    factors.push(Factor {
                        value: prime,
                        count,
                    });
                }
            }
            count = 1;
            prime = p;
        } else {
            count += 1;
        }
    }
    if count > 0 {
        factors.push(Factor {
            value: prime,
            count,
        });
    }
    if fac4count != 0 {
        factors.push(Factor {
            value: 4,
            count: fac4count,
        });
    }
    factors
}