// Pruebas de la multiplicación: Karatsuba contra la escuela, y contra productos que caben en 64 bits.
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <random>
#include <string>

#include "karatsuba.h"

static Digits random_number(std::size_t n, std::mt19937& rng) {
    Digits a(n);
    for (int& digit : a) {
        digit = static_cast<int>(rng() % 10);
    }
    trim(a);
    return a;
}

static void test_known() {
    long long c = 0;
    assert(to_string(karatsuba(from_string("1234"), from_string("5678"), 3, c)) == "7006652");
    assert(to_string(karatsuba(from_string("0"), from_string("5678"), 3, c)) == "0");
    assert(to_string(karatsuba(from_string("99999"), from_string("99999"), 3, c)) == "9999800001");
    // a + b tiene un dígito más que sus partes.
    assert(to_string(karatsuba(from_string("9999"), from_string("9999"), 3, c)) == "99980001");
    assert(to_string(school_multiply(from_string("1234"), from_string("5678"), c)) == "7006652");
}

static void test_against_64_bits() {
    std::mt19937 rng(1);
    for (int round = 0; round < 3000; round++) {
        std::uint64_t p = rng() % 4000000000u;
        std::uint64_t q = rng() % 4000000000u;
        long long c = 0;
        Digits product = karatsuba(from_string(std::to_string(p)), from_string(std::to_string(q)), 3, c);
        assert(to_string(product) == std::to_string(p * q));
    }
}

static void test_against_school() {
    std::mt19937 rng(2);
    for (int round = 0; round < 400; round++) {
        std::size_t n = 1 + rng() % 300;
        std::size_t m = round % 2 == 0 ? n : 1 + rng() % 300;
        Digits x = random_number(n, rng);
        Digits y = random_number(m, rng);
        if (round % 5 == 0) {
            x.assign(n, 9);  // todos nueves: el peor caso de los acarreos
            y.assign(m, 9);
        }
        long long c = 0;
        Digits expected = school_multiply(x, y, c);
        for (std::size_t threshold : {std::size_t{3}, std::size_t{7}, std::size_t{32}}) {
            assert(karatsuba(x, y, threshold, c) == expected);
        }
    }
}

static void test_counts() {
    std::mt19937 rng(3);
    // La escuela hace exactamente n² productos.
    for (std::size_t n : {std::size_t{5}, std::size_t{64}, std::size_t{500}}) {
        Digits x(n, 7);
        long long c = 0;
        school_multiply(x, x, c);
        assert(c == static_cast<long long>(n * n));
    }
    // Con n = 2^k y sin acarreos que alarguen las sumas, 3^(k-1) hojas de 2 x 2 dígitos: 4·3^(k-1) productos.
    long long c = 0;
    karatsuba(from_string("1111"), from_string("1111"), 3, c);
    assert(c == 4 * 3);
    c = 0;
    karatsuba(from_string("11111111"), from_string("11111111"), 3, c);
    assert(c == 4 * 9);
    // Al duplicar n, el conteo se multiplica por cerca de 3, no por 4.
    long long previous = 0;
    for (std::size_t n = 1024; n <= 8192; n *= 2) {
        Digits x = random_number(n, rng);
        Digits y = random_number(n, rng);
        long long count = 0;
        karatsuba(x, y, 3, count);
        if (previous != 0) {
            double ratio = static_cast<double>(count) / static_cast<double>(previous);
            assert(ratio > 2.8 && ratio < 3.2);
        }
        previous = count;
    }
}

int main() {
    test_known();
    test_against_64_bits();
    test_against_school();
    test_counts();
    std::puts("test_karatsuba: ok");
}