clock-curve-math 1.1.3

#!/usr/bin/env python3
"""
FFT Implementation for Translation to Rust

This provides a working FFT algorithm that can be directly translated
to Rust for the clock-curve-math library.
"""

import math
import cmath


class FFTForRust:
    """FFT implementation designed for easy translation to Rust."""

    @staticmethod
    def is_power_of_two(n):
        """Check if n is a power of 2."""
        return n > 0 and (n & (n - 1)) == 0

    @staticmethod
    def next_power_of_two(n):
        """Find next power of 2 >= n."""
        if n <= 1:
            return 1
        return 1 << (n - 1).bit_length()

    def cooley_tukey_fft(self, coeffs, inverse=False):
        """
        Cooley-Tukey FFT - designed for easy Rust translation.

        Args:
            coeffs: List of complex coefficients
            inverse: If True, compute inverse FFT

        Returns:
            FFT result as list of complex numbers
        """
        n = len(coeffs)

        # Pad to power of 2
        if not self.is_power_of_two(n):
            next_n = self.next_power_of_two(n)
            coeffs = coeffs + [0.0] * (next_n - n)
            n = next_n

        # Convert to complex numbers
        coeffs = [complex(float(x), 0.0) if isinstance(x, (int, float)) else x for x in coeffs]

        # Bit-reversal permutation
        result = [0j] * n
        for i in range(n):
            j = 0
            bits = int(math.log2(n))
            for k in range(bits):
                if i & (1 << k):
                    j |= 1 << (bits - 1 - k)
            result[j] = coeffs[i]

        # Iterative Cooley-Tukey
        size = 2
        while size <= n:
            half_size = size // 2
            angle_step = (2.0 if inverse else -2.0) * math.pi / size
            wlen = cmath.exp(complex(0, angle_step))

            for i in range(0, n, size):
                w = complex(1, 0)
                for j in range(half_size):
                    u = result[i + j]
                    v = result[i + j + half_size] * w
                    result[i + j] = u + v
                    result[i + j + half_size] = u - v
                    w *= wlen

            size *= 2

        # Scale for inverse
        if inverse:
            scale = 1.0 / n
            result = [x * scale for x in result]

        return result

    def polynomial_multiply(self, a, b):
        """
        Multiply polynomials using FFT.

        Args:
            a, b: Coefficient lists

        Returns:
            Product coefficients
        """
        # Determine FFT size
        n = self.next_power_of_two(len(a) + len(b) - 1)

        # Pad inputs
        a_padded = a + [0] * (n - len(a))
        b_padded = b + [0] * (n - len(b))

        # FFT
        a_fft = self.cooley_tukey_fft(a_padded)
        b_fft = self.cooley_tukey_fft(b_padded)

        # Pointwise multiplication
        c_fft = [x * y for x, y in zip(a_fft, b_fft)]

        # Inverse FFT
        c = self.cooley_tukey_fft(c_fft, inverse=True)

        # Extract real parts and round
        result = []
        for x in c:
            val = round(x.real)
            result.append(val)

        # Remove trailing zeros
        while result and result[-1] == 0:
            result.pop()

        return result

    def big_int_multiply(self, a, b, base=1000000000):  # 10^9
        """
        Multiply big integers using FFT.

        Args:
            a, b: Integers to multiply
            base: Base for digit conversion

        Returns:
            Product as integer
        """
        # Convert to base digits
        def to_digits(n):
            if n == 0:
                return [0]
            digits = []
            while n > 0:
                digits.append(n % base)
                n //= base
            return digits

        a_digits = to_digits(a)
        b_digits = to_digits(b)

        # Multiply as polynomials
        product_digits = self.polynomial_multiply(a_digits, b_digits)

        # Convert back to integer
        result = 0
        for i, digit in enumerate(product_digits):
            result += digit * (base ** i)

        return result


def test_fft():
    """Test the FFT implementation."""
    fft = FFTForRust()

    print("Testing FFT polynomial multiplication...")

    # Test cases
    test_cases = [
        ([1, 2, 3], [4, 5]),           # (1+2x+3x²) * (4+5x) = 4 + 13x + 22x² + 15x³
        ([1], [1]),                     # (1) * (1) = 1
        ([1, 1], [1, -1]),             # (1+x) * (1-x) = 1 - x²
    ]

    for a, b in test_cases:
        result = fft.polynomial_multiply(a, b)
        print(f"  {a} * {b} = {result}")

    print("\nTesting big integer multiplication...")

    big_tests = [
        (0, 0),
        (1, 1),
        (12, 34),
        (123, 456),
        (1000, 2000),
    ]

    for a, b in big_tests:
        expected = a * b
        result = fft.big_int_multiply(a, b)
        correct = (result == expected)
        print(f"  {a} * {b} = {result} {'✓' if correct else '✗'}")
        if not correct:
            print(f"    Expected: {expected}")


def rust_translation_example():
    """Example of how this would be translated to Rust."""
    print("\n" + "="*60)
    print("RUST TRANSLATION EXAMPLE")
    print("="*60)

    rust_code = '''
use std::f64::consts::PI;

pub struct FFTMultiplier {
    // No fields needed for basic implementation
}

impl FFTMultiplier {
    /// Check if n is a power of 2
    fn is_power_of_two(n: usize) -> bool {
        n > 0 && (n & (n - 1)) == 0
    }

    /// Find next power of 2 >= n
    fn next_power_of_two(n: usize) -> usize {
        if n <= 1 { return 1; }
        1 << (n.next_power_of_two().trailing_zeros() as usize)
    }

    /// Cooley-Tukey FFT
    pub fn cooley_tukey_fft(&self, coeffs: &mut Vec<Complex<f64>>, inverse: bool) {
        let n = coeffs.len();

        // Bit-reversal permutation
        let mut j = 0;
        for i in 1..n {
            let mut bit = n >> 1;
            while j & bit != 0 {
                j ^= bit;
                bit >>= 1;
            }
            j ^= bit;

            if i < j {
                coeffs.swap(i, j);
            }
        }

        // Iterative Cooley-Tukey
        let mut size = 2;
        while size <= n {
            let half_size = size / 2;
            let angle_step = if inverse { 2.0 } else { -2.0 } * PI / (size as f64);
            let wlen = Complex::new(angle_step.cos(), angle_step.sin());

            let mut i = 0;
            while i < n {
                let mut w = Complex::new(1.0, 0.0);
                for j in 0..half_size {
                    let u = coeffs[i + j];
                    let v = coeffs[i + j + half_size] * w;
                    coeffs[i + j] = u + v;
                    coeffs[i + j + half_size] = u - v;
                    w *= wlen;
                }
                i += size;
            }

            size *= 2;
        }

        // Scale for inverse
        if inverse {
            let scale = 1.0 / (n as f64);
            for coeff in coeffs.iter_mut() {
                *coeff *= scale;
            }
        }
    }
}
'''

    print("This Python implementation can be directly translated to Rust:")
    print("Key components:")
    print("1. Complex<f64> for complex numbers")
    print("2. Vec<Complex<f64>> for coefficient arrays")
    print("3. Bit-reversal permutation")
    print("4. Iterative Cooley-Tukey algorithm")
    print("5. Proper scaling for inverse transform")
    print("\nSample Rust code structure:")
    print(rust_code)


if __name__ == "__main__":
    test_fft()
    rust_translation_example()