clock-curve-math 1.1.3

#!/usr/bin/env python3
"""
Simplified FFT/NTT Implementation for Large Integer Multiplication

This module provides working implementations of FFT and NTT for polynomial multiplication.
"""

import math
import cmath  # Use Python's cmath instead of SageMath for complex numbers


class FFTNTTSimple:
    """Simplified FFT/NTT implementation for polynomial multiplication."""

    def __init__(self):
        """Initialize with default parameters."""
        pass

    def cooley_tukey_fft(self, coeffs, inverse=False):
        """
        Cooley-Tukey Fast Fourier Transform.

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

        Returns:
            FFT result
        """
        n = len(coeffs)
        if n <= 1:
            return coeffs

        # Check if power of 2
        if n & (n - 1) != 0:
            # Pad to next power of 2
            next_power = 1 << (n - 1).bit_length()
            coeffs = coeffs + [0] * (next_power - n)
            n = next_power

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

        # Cooley-Tukey iterative algorithm
        size = 2
        while size <= n:
            half_size = size // 2
            angle = (2 if inverse else -2) * math.pi * 1j / size

            for i in range(0, n, size):
                w = 1 + 0j  # Complex 1
                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 *= cmath.exp(angle)

            size *= 2

        if inverse:
            result = [x / n for x in result]

        return result

    def polynomial_multiply_fft(self, a_coeffs, b_coeffs):
        """
        Multiply polynomials using FFT.

        Args:
            a_coeffs, b_coeffs: Coefficient lists

        Returns:
            Product polynomial coefficients
        """
        n = 1
        while n < len(a_coeffs) + len(b_coeffs) - 1:
            n *= 2

        # Pad coefficients
        a_padded = a_coeffs + [0] * (n - len(a_coeffs))
        b_padded = b_coeffs + [0] * (n - len(b_coeffs))

        # Convert to Python complex
        a_complex = [complex(float(x), 0.0) for x in a_padded]
        b_complex = [complex(float(x), 0.0) for x in b_padded]

        # FFT
        a_fft = self.cooley_tukey_fft(a_complex)
        b_fft = self.cooley_tukey_fft(b_complex)

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

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

        # Extract real parts and round
        result = []
        for x in c_complex:
            # Convert to Python complex first, then get real part
            if hasattr(x, 'real_part'):
                real_val = float(x.real_part())
            elif hasattr(x, 'real'):
                real_val = float(x.real)
            else:
                real_val = float(x)

            rounded = round(real_val)
            if abs(real_val - rounded) > 0.1:  # More lenient precision check
                print(f"Warning: large precision issue at {real_val}")
            result.append(int(rounded))

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

        return result

    def big_int_to_coeffs(self, n, base=10):
        """
        Convert big integer to coefficient list.

        Args:
            n: Integer to convert
            base: Base for digits

        Returns:
            List of coefficients
        """
        if n == 0:
            return [0]

        coeffs = []
        while n > 0:
            coeffs.append(int(n % base))
            n //= base
        return coeffs

    def coeffs_to_big_int(self, coeffs, base=10):
        """
        Convert coefficient list back to big integer.

        Args:
            coeffs: List of coefficients
            base: Base for digits

        Returns:
            Reconstructed integer
        """
        result = 0
        for i, coeff in enumerate(coeffs):
            result += coeff * (base ** i)
        return result

    def multiply_big_ints_fft(self, a, b, base=10):
        """
        Multiply two big integers using FFT.

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

        Returns:
            Product a * b
        """
        a_coeffs = self.big_int_to_coeffs(a, base)
        b_coeffs = self.big_int_to_coeffs(b, base)

        product_coeffs = self.polynomial_multiply_fft(a_coeffs, b_coeffs)

        return self.coeffs_to_big_int(product_coeffs, base)


def test_basic():
    """Basic functionality test."""
    print("Testing basic FFT/NTT functionality...")

    mult = FFTNTTSimple()

    # Test polynomial multiplication
    print("\nTesting polynomial multiplication:")
    a = [1, 2, 3]  # 1 + 2x + 3x^2
    b = [4, 5]     # 4 + 5x
    # Product should be: 4 + 13x + 22x^2 + 15x^3

    result = mult.polynomial_multiply_fft(a, b)
    expected = [4, 13, 22, 15]

    print(f"a = {a}")
    print(f"b = {b}")
    print(f"Result: {result}")
    print(f"Expected: {expected}")
    print(f"Correct: {result == expected}")

    # Test big integer multiplication
    print("\nTesting big integer multiplication:")
    test_cases = [
        (0, 0),
        (1, 1),
        (12, 34),
        (123, 456),
    ]

    for x, y in test_cases:
        expected = x * y
        result = mult.multiply_big_ints_fft(x, y)
        correct = (result == expected)
        print(f"{x} * {y} = {result} (expected {expected}) {'✓' if correct else '✗'}")


if __name__ == "__main__":
    test_basic()