Tetration

#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <vector>
#include <unordered_map>

#ifdef __has_include
#   if __has_include(<boost/multiprecision/cpp_int.hpp>)
#   define BOOST_AVAILABLE
#   include <boost/multiprecision/cpp_int.hpp>
    using cpp_int = boost::multiprecision::cpp_int;
#   endif
#endif

#include <emmintrin.h>

#define PRECISION 7

class Multiplier {
public:
    // Using SSE2 instructions:
    static std::string multiply_SSE2(const std::string& num1, const std::string& num2) {
        size_t n1 = num1.size();
        size_t n2 = num2.size();

        // Check if either input is empty
        if (n1 == 0 || n2 == 0)
            return "0";

        // Allocate memory to store the result
        std::vector<int> result(n1 + n2, 0);

        int i = static_cast<int>(n1) - 1;
        do {
            int carry = 0;
            int num1_digit = num1[i] - '0';

            int j = static_cast<int>(n2) - 1;
            do {
                // int num2_digit = num2[j] - '0';
                //
                // // Multiply using SIMD (SSE2) intrinsic
                // __m128i num1_simd = _mm_set1_epi32(num1_digit);
                // __m128i num2_simd = _mm_set1_epi32(num2_digit);
                // __m128i product = _mm_mul_epu32(num1_simd, num2_simd);
                //
                // // Accumulate the product into the result
                // int index = i + j + 1;
                // __m128i result_simd = _mm_loadu_si128((__m128i*) & result[index]);
                // result_simd = _mm_add_epi32(result_simd, product);
                // _mm_storeu_si128((__m128i*) & result[index], result_simd);
                //
                // carry = _mm_extract_epi32(result_simd, 1);

                int num2_digit = num2[j] - '0';

                __m128i num1_simd = _mm_cvtsi32_si128(num1_digit);
                __m128i num2_simd = _mm_cvtsi32_si128(num2_digit);
                __m128i product = _mm_mul_epu32(num1_simd, num2_simd);

                int index = i + j + 1;
                __m128i result_simd = _mm_loadu_si128((__m128i*) & result[index]);
                result_simd = _mm_add_epi64(result_simd, product);
                _mm_storeu_si128((__m128i*) & result[index], result_simd);

                carry = static_cast<int>(_mm_extract_epi64(result_simd, 1));
            } while (--j >= 0);

            // if (carry > 0)
            //     result[i] += carry;

            carry > 0 ? result[i] += carry : false;

        } while (--i >= 0);

        // Handle any remaining carry and convert the result to a string
        std::string s;
        int carry = 0;
        auto it = result.rbegin();
        do {
            int sum = *it + carry;
            *it = sum % 10;
            carry = sum / 10;
            s += char(*it + '0');
            ++it;
        } while (it != result.rend());

        // Handle any remaining carry
        while (carry) {
            int digit = carry % 10;
            carry /= 10;
            s += char(digit + '0');
        }

        // Remove leading zeros
        size_t nonZeroPos = s.find_first_not_of('0');
        return (nonZeroPos != std::string::npos) ? s.substr(nonZeroPos) : "0";
    }

    static std::string multiply(const std::string& num1, const std::string& num2) {
        size_t n1 = num1.size();
        size_t n2 = num2.size();

        // Check if either input is empty
        if (n1 == 0 || n2 == 0)
            return "0";

        std::vector<int> result(n1 + n2, 0);

        int i = static_cast<int>(n1) - 1;
        do {
            int carry = 0;
            int num1_digit = num1[i] - '0';

            int j = static_cast<int>(n2) - 1;
            do {
                int num2_digit = num2[j] - '0';
                int sum = num1_digit * num2_digit + result[i + j + 1] + carry;
                carry = sum / 10;
                result[i + j + 1] = sum % 10;
            } while (--j >= 0);

            if (carry > 0)
                result[i] += carry;
        } while (--i >= 0);

        std::string s = "";
        for (int i : result)
            s += std::to_string(i);

        // Remove leading zeros
        size_t nonZeroPos = s.find_first_not_of('0');
        return (nonZeroPos != std::string::npos) ? s.substr(nonZeroPos) : "0";
    }

#ifdef BOOST_AVAILABLE
    static cpp_int multiply(cpp_int a, cpp_int b) {
        return a * b;
    }
#endif
};

class PowerCalculator {
private:
    static std::unordered_map<int, std::string> memo;

public:
    static std::string power(const std::string& base, int exponent) {
        switch (exponent) {
        case 0:
            return "1";
        default:
            if (memo.find(exponent) != memo.end()) {
                return memo[exponent];
            }

            std::string halfPower = power(base, exponent / 2);
            std::string result = Multiplier::multiply(halfPower, halfPower);

            if (exponent % 2 == 1)
                result = Multiplier::multiply(result, base);

            memo[exponent] = result;
            return result;
        }
    }

    static std::string power_SSE2(const std::string& base, int exponent) {
        switch (exponent) {
        case 0:
            return "1";
        default:
            if (memo.find(exponent) != memo.end()) {
                return memo[exponent];
            }

            std::string halfPower = power_SSE2(base, exponent / 2);
            std::string result = Multiplier::multiply_SSE2(halfPower, halfPower); // Use SSE2-based multiplication

            if (exponent % 2 == 1)
                result = Multiplier::multiply_SSE2(result, base); // Use SSE2-based multiplication

            memo[exponent] = result;
            return result;
        }
    }

#ifdef BOOST_AVAILABLE
    static cpp_int power(cpp_int base, int exponent) {
        switch (exponent) {
        case 0:
            return 1;
        default:
            if (exponent % 2 == 0) {
                cpp_int half_power = power(base, exponent / 2);
                return Multiplier::multiply(half_power, half_power);
            }
            else {
                cpp_int half_power = power(base, (exponent - 1) / 2);
                return Multiplier::multiply(Multiplier::multiply(half_power, half_power), base);
            }
        }
    }
#endif
};

std::unordered_map<int, std::string> PowerCalculator::memo;

class Tetrator {
private:
    Multiplier stringMultiplier;
    PowerCalculator powerCalculator;
    Multiplier sse2Multiplier;  // Use SSE2-based multiplier

public:
    static std::string tetration_SSE2(const std::string& base, int height) {
        switch (height) {
        case 0:
            return "1";
        case 1:
            return base;
        default:
            std::string result = base;

            for (int i = 1; i < height; ++i) {
                // Use SSE2-based multiplication for tetration
                result = PowerCalculator::power_SSE2(base, stoull(result));
            }

            return result;
        }
    }

    static std::string tetration(const std::string& base, int height) {
        switch (height) {
        case 0:
            return "1";
        case 1:
            return base;
        default:
            std::string result = base;

            for (int i = 1; i < height; ++i) {
                result = PowerCalculator::power(base, std::stoull(result));
            }

            return result;
        }
    }

#ifdef BOOST_AVAILABLE
    static cpp_int tetration(cpp_int base, int height) {
        return (height == 0) ? 1 : ((height == 1) ? base : PowerCalculator::power(base, tetration(base, height - 1).convert_to<int>()));
    }
#endif
};

void measureStringBasedPerformance() {
    std::string baseInput;
    int heightInput;

    std::cout << "Enter the base (a positive integer): ";
    std::cin >> baseInput;
    std::cout << "Enter the height (a non-negative integer): ";
    std::cin >> heightInput;

    if (baseInput.empty() || heightInput < 0) {
        std::cerr << "Invalid input. Please enter valid base and height values." << std::endl;
        return;
    }

    auto start = std::chrono::high_resolution_clock::now();
    std::string result = Tetrator::tetration(baseInput, heightInput);
    auto end = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double> duration = end - start;
    std::cout << "String-based tetration time: " << std::fixed << std::setprecision(PRECISION) << duration.count() << " seconds" << std::endl;
    std::cout << "Result: " << result << std::endl;
}

#ifdef BOOST_AVAILABLE
void measureBoostBasedPerformance() {
    cpp_int baseInput;
    int heightInput;

    std::cout << "Enter the base (a positive integer): ";
    std::cin >> baseInput;
    std::cout << "Enter the height (a non-negative integer): ";
    std::cin >> heightInput;

    if (heightInput < 0) {
        std::cerr << "Invalid input. Please enter a valid non-negative height value." << std::endl;
        return;
    }

    auto start = std::chrono::high_resolution_clock::now();
    cpp_int result = Tetrator::tetration(baseInput, heightInput);
    auto end = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double> duration = end - start;
    std::cout << "Boost-based tetration time: " << std::fixed << std::setprecision(PRECISION) << duration.count() << " seconds" << std::endl;
    std::cout << "Result: " << result << std::endl;
}
#endif

void measureSSE2BasedPerformance() {
    std::string baseInput;
    int heightInput;

    std::cout << "Enter the base (a positive integer): ";
    std::cin >> baseInput;
    std::cout << "Enter the height (a non-negative integer): ";
    std::cin >> heightInput;

    if (baseInput.empty() || heightInput < 0) {
        std::cerr << "Invalid input. Please enter valid base and height values." << std::endl;
        return;
    }

    // Convert heightInput to a string and call the SSE2-based tetration function
    auto start = std::chrono::high_resolution_clock::now();
    std::string heightStr = std::to_string(heightInput);
    std::string result = Tetrator::tetration_SSE2(baseInput, stoull(heightStr));  // Call SSE2-based tetration
    auto end = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double> duration = end - start;
    std::cout << "SSE2-based tetration time: " << std::fixed << std::setprecision(PRECISION) << duration.count() << " seconds" << std::endl;
    std::cout << "Result: " << result << std::endl;
}



int main() {
    std::cout << "Measuring performance for tetration..." << std::endl;

    std::cout << "\nPerforming string-based tetration..." << std::endl;
    measureStringBasedPerformance();

    std::cout << "\nPerforming SSE2-based tetration..." << std::endl;
    measureSSE2BasedPerformance();

#ifdef BOOST_AVAILABLE
    std::cout << "\nPerforming Boost-based tetration..." << std::endl;
    measureBoostBasedPerformance();
#else
    std::cout << "\nBoost library not available. Boost-based tetration is disabled." << std::endl;
#endif

    return 0;
}