Skip to main content
Became Hot Network Question
Added a little more explanation
Source Link
pacmaninbw
  • 26.2k
  • 13
  • 47
  • 114

Following the instructions fromThis is a follow up question to my thisStudies on Square Roots post,. I'm posting otheradditional code for solving for square root similar to the other, but with more code to benchmark.

Following the instructions from this post, I'm posting other code for square root similar to the other, but with more code to benchmark.

This is a follow up question to my Studies on Square Roots post. I'm posting additional code for solving for square root similar to the other, but with more code to benchmark.

Source Link
user284928
user284928

More Square Root

Following the instructions from this post, I'm posting other code for square root similar to the other, but with more code to benchmark.

#include <iomanip>
#include <cmath>
#include <chrono>
#include <limits>
#include <vector>
#include <random>
#include <algorithm>
#include <numeric>
#include <iostream>

// Constants
const int NUM_EXECUTIONS = 1000000;
const double precision = 1e-12; // Adjusted precision
bool showNewtonIteration = true;
bool showAnothersIteration = true;

struct IterationData {
    double number;
    double sqrtResult;
    int iterations;
};

// Optimized Newton's method for finding the square root
double newtonSqrt(double number, double precision, int& iterations, bool showIteration) {
    if (number == 0) return 0;
    double guess = number * 0.5; // Starting guess
    double nextGuess;
    iterations = 0;

    while (true) {
        nextGuess = 0.5 * (guess + number / guess);
        if (std::fabs(nextGuess - guess) < precision) {
            break;
        }
        iterations++;
        if (showIteration && showNewtonIteration) {
            std::cout << "Newton's method - ";
            std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << nextGuess << " and more...";
            if (std::fabs(nextGuess - guess) < precision) {
                std::cout << " reached desired precision";
            }
            std::cout << std::endl;
        }

        guess = nextGuess;
    }
    return nextGuess;
}

// Iterative another's method with dynamic initial approximation
double anothersMethod(double number, double precision, int& iterations, bool showIteration) {
    double f = number * 0.5; // Using the initial approximation
    double prev_f = 0;
    iterations = 0;

    while (true) {
        // Check if the value converges within the given precision
        if (std::fabs(f - prev_f) < precision) {
            break;
        }
        
        iterations++;
        if (showIteration && showAnothersIteration) {
            std::cout << "Another's method - ";
            std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << f << " and more...";
            if (std::fabs(f - prev_f) < precision) {
                std::cout << " reached desired precision";
            }
            std::cout << std::endl;
        }
        prev_f = f;
        // New formula to improve the estimate
        f = f - (f * f - number) / (f + number / f);
    }
    return f;
}

// Union to manipulate double as an integer (bit manipulation)
union {
    double value;
    uint64_t bits;
} db;

// Initial approximation using bit manipulation
double initialSqrtEstimate(double x) {
    db.value = x;

    // Bit manipulation to get a rough estimate of the square root
    db.bits = (db.bits & 0x800FFFFFFFFFFFFFULL) | (((db.bits & 0x7FF0000000000000ULL) >> 1) + 0x1FF0000000000000ULL);

    return db.value;
}

// Function to calculate the reciprocal using bit manipulation and Newton-Raphson method
double reciprocal(double x) {
    db.value = x;

    // Initialize an estimate of the reciprocal of x using bit manipulation
    db.bits = 0x7FDDAC7200000000 - db.bits;

    // Refine the estimate using the Newton-Raphson method
    double y = db.value;
    for (int i = 0; i < 2; i++) {
        y = y * (2.0 - x * y); // Newton-Raphson iteration for reciprocal
    }

    return y;
}

// Another iterative method with dynamic initial approximation
double anothersMethod2(double number, double precision, int& iterations, bool showIteration) {
    if (number == 0) return 0;
    initialSqrtEstimate(number);
    int p = int(number) >> 1;
    double guess = 0;
    double nextGuess = db.value + (number / (1 << p));;
    iterations = 0;
    while (true) {
        iterations++;
        if (showIteration && showAnothersIteration) {
            std::cout << "Another's method 2 - ";
            std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << nextGuess << " and more...";
            if (std::fabs(nextGuess - guess) < precision) {
                std::cout << " reached desired precision";
                std::cout << std::endl;
                break;
            }
            std::cout << std::endl;
        }
        if (std::fabs(nextGuess - guess) < precision) {
            break;
        }
        guess = nextGuess;
        nextGuess = 0.5 * (guess + number / guess);
    }
    return guess;
}

// Another iterative method using initial approximation and multiplication-only formula
double anothersMethod3(double number, double precision, int& iterations, bool showIteration) {
    double f = initialSqrtEstimate(number); // Using the initial approximation
    double prev_f = 0;
    iterations = 0;

    while (true) {
        iterations++;
        if (showIteration && showAnothersIteration) {
            std::cout << "Another's method 3 - ";
            std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << f << " and more...";
            if (std::fabs(f - prev_f) < precision) {
                std::cout << " reached desired precision";
            }
            std::cout << std::endl;
        }

        // Check if the value converges within the given precision
        if (std::fabs(f - prev_f) < precision) {
            break;
        }

        prev_f = f;
        f = 0.5 * (f + number * reciprocal(f)); // Use multiplication for refinement
        
    }
    return f;
}

union {
    float value;
    uint32_t bits;
} db2;

// Function to calculate the inverse square root using Carmack's method
float inverseSqrt(float x) {
    db2.value = x;
    db2.bits = 0x5f3759df - (db2.bits >> 1); // Initial approximation using magic number
    return db2.value;
}

// Function to calculate the square root using the inverse square root
float carmacksMethod(float number, float precision, int& iterations, bool showIteration) {
    if (number == 0) return 0;
    float invSqrt = inverseSqrt(number); // Get the inverse square root
    float sqrt = 1 / invSqrt; // Calculate the square root by taking the reciprocal of the inverse
    iterations = 1;

    if (showIteration) {
        std::cout << "Carmack's method - ";
        std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << sqrt << " and more...";
        std::cout << " reached desired precision";
        std::cout << std::endl;
    }
    return sqrt;
}

// Carmack's Method with a mix of inverse square root and refinement
float carmacksMethod2(float number, float precision, int& iterations, bool showIteration) {
    if (number == 0) return 0;
    float invSqrt = inverseSqrt(number); // Get the inverse square root
    float sqrt = 1 / invSqrt; // Calculate the square root by taking the reciprocal of the inverse
    float prev_sqrt = 0;
    iterations = 0;

    while (true) {
        iterations++;
        if (showIteration) {
            std::cout << "Carmack's method 2 - ";
            std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << sqrt << " and more...";
            if (std::fabs(sqrt - prev_sqrt) < precision) {
                std::cout << " reached desired precision";
            }
            std::cout << std::endl;
        }
        if (std::fabs(sqrt - prev_sqrt) < precision) {
            break;
        }
        prev_sqrt = sqrt;
        sqrt = 0.5 * (sqrt + number / sqrt);
    }
    return sqrt;
}

// Function to calculate the error
double calculateError(double root, double number) {
    double square = root * root;
    return std::fabs(square - number);
}

void showIterations(double number, double& resultNewton, double* resultAnothers, double& resultCarmack, double& resultCarmack2, int& iterationsNewton, int* iterationsAnothers, int& iterationsCarmack, int& iterationsCarmack2) {
    resultNewton = newtonSqrt(number, precision, iterationsNewton, true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Newton's method final result: " << resultNewton << " reached desired precision, Iterations: " << iterationsNewton << "\n\n";

    resultAnothers[0] = anothersMethod(number, precision, iterationsAnothers[0], true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Another's method final result: " << resultAnothers[0] << " reached desired precision, Iterations: " << iterationsAnothers[0] << "\n\n";

    resultAnothers[1] = anothersMethod2(number, precision, iterationsAnothers[1], true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Another's method 2 final result: " << resultAnothers[1] << " reached desired precision, Iterations: " << iterationsAnothers[1] << "\n\n";

    resultAnothers[2] = anothersMethod3(number, precision, iterationsAnothers[2], true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Another's method 3 final result: " << resultAnothers[2] << " reached desired precision, Iterations: " << iterationsAnothers[2] << "\n\n";

    resultCarmack = carmacksMethod(number, precision, iterationsCarmack, true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Carmack's method final result: " << resultCarmack << " reached desired precision, Iterations: " << iterationsCarmack << "\n\n";

    resultCarmack2 = carmacksMethod2(number, precision, iterationsCarmack2, true);
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10)
        << "Carmack's method 2 final result: " << resultCarmack2 << " reached desired precision, Iterations: " << iterationsCarmack2 << "\n\n";
}

void measureTime(double* randomNumbers, std::vector<double>& timesSqrt, std::vector<double>& timesNewton, std::vector<double>* timesAnothers, std::vector<double>& timesCarmack, std::vector<double>& timesCarmack2, std::vector<IterationData>& newtonData, std::vector<IterationData>* anothersData, std::vector<IterationData>& carmackData, std::vector<IterationData>& carmack2Data) {
    // Measuring time for standard sqrt function
    std::cout << "Calculating times...\n";
    auto startSqrt = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        volatile double result = std::sqrt(randomNumbers[i]);
    }
    auto endSqrt = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationSqrt = endSqrt - startSqrt;
    timesSqrt.push_back(durationSqrt.count());

    // Measuring time for Newton's pure method
    auto startNewton = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsNewton = 0;
        double result = newtonSqrt(randomNumbers[i], precision, iterationsNewton, false);
        newtonData.push_back({ randomNumbers[i], result, iterationsNewton });
    }
    auto endNewton = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationNewton = endNewton - startNewton;
    timesNewton.push_back(durationNewton.count());

    // Measuring time for the another's method
    auto startAnothers = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsAnothers = 0;
        double result = anothersMethod(randomNumbers[i], precision, iterationsAnothers, false);
        anothersData[0].push_back({ randomNumbers[i], result, iterationsAnothers });
    }
    auto endAnothers = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationAnothers = endAnothers - startAnothers;
    timesAnothers[0].push_back(durationAnothers.count());

    // Measuring time for the another's method 2
    auto startAnothers2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsAnothers = 0;
        double result = anothersMethod2(randomNumbers[i], precision, iterationsAnothers, false);
        anothersData[1].push_back({ randomNumbers[i], result, iterationsAnothers });
    }
    auto endAnothers2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationAnothers2 = endAnothers2 - startAnothers2;
    timesAnothers[1].push_back(durationAnothers2.count());

    // Measuring time for the another's method 3
    auto startAnothers3 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsAnothers = 0;
        double result = anothersMethod3(randomNumbers[i], precision, iterationsAnothers, false);
        anothersData[2].push_back({ randomNumbers[i], result, iterationsAnothers });
    }
    auto endAnothers3 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationAnothers3 = endAnothers3 - startAnothers3;
    timesAnothers[2].push_back(durationAnothers3.count());

    // Measuring time for Carmack's method
    auto startCarmack = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsCarmack = 0;
        double result = carmacksMethod(randomNumbers[i], precision, iterationsCarmack, false);
        carmackData.push_back({ randomNumbers[i], result, iterationsCarmack });
    }
    auto endCarmack = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationCarmack = endCarmack - startCarmack;
    timesCarmack.push_back(durationCarmack.count());

    // Measuring time for Carmack's method 2
    auto startCarmack2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        int iterationsCarmack2 = 0;
        double result = carmacksMethod2(randomNumbers[i], precision, iterationsCarmack2, false);
        carmack2Data.push_back({ randomNumbers[i], result, iterationsCarmack2 });
    }
    auto endCarmack2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> durationCarmack2 = endCarmack2 - startCarmack2;
    timesCarmack2.push_back(durationCarmack2.count());
}

void displayAverageTimes(const std::vector<double>& timesSqrt, const std::vector<double>& timesNewton, const std::vector<double>* timesAnothers, const std::vector<double>& timesCarmack, const std::vector<double>& timesCarmack2) {
    double avgSqrt = std::accumulate(timesSqrt.begin(), timesSqrt.end(), 0.0) / timesSqrt.size();
    double avgNewton = std::accumulate(timesNewton.begin(), timesNewton.end(), 0.0) / timesNewton.size();
    double avgAnothers = std::accumulate(timesAnothers[0].begin(), timesAnothers[0].end(), 0.0) / timesAnothers[0].size();
    double avgAnothers2 = std::accumulate(timesAnothers[1].begin(), timesAnothers[1].end(), 0.0) / timesAnothers[1].size();
    double avgAnothers3 = std::accumulate(timesAnothers[2].begin(), timesAnothers[2].end(), 0.0) / timesAnothers[2].size();
    double avgCarmack = std::accumulate(timesCarmack.begin(), timesCarmack.end(), 0.0) / timesCarmack.size();
    double avgCarmack2 = std::accumulate(timesCarmack2.begin(), timesCarmack2.end(), 0.0) / timesCarmack2.size();

    std::cout << "\nAverage Results:\n";
    std::cout << std::scientific << std::setprecision(6); // Ensure values are displayed in scientific notation
    std::cout << "Standard sqrt average time (ms): " << avgSqrt << std::endl;
    std::cout << "Newton's method average time (ms): " << avgNewton << std::endl;
    std::cout << "Another's method average time (ms): " << avgAnothers << std::endl;
    std::cout << "Another's method 2 average time (ms): " << avgAnothers2 << std::endl;
    std::cout << "Another's method 3 average time (ms): " << avgAnothers3 << std::endl;
    std::cout << "Carmack's method average time (ms): " << avgCarmack << std::endl;
    std::cout << "Carmack's method 2 average time (ms): " << avgCarmack2 << std::endl;
}

void calculateAndDisplayErrors(double number, const std::vector<double>& roots) {
    double actualSqrt = std::sqrt(number);
    std::cout << "\nError comparison with actual sqrt(" << number << "): " << std::setprecision(std::numeric_limits<double>::max_digits10) << actualSqrt << "\n";
    for (size_t i = 0; i < roots.size(); ++i) {
        double error = calculateError(roots[i], number);
        std::cout << "Error for root " << i + 1 << " (" << std::scientific << std::setprecision(std::numeric_limits<double>::max_digits10) << roots[i] << "): " << error << "\n";
    }
}

void displaySomeIterations(const std::vector<IterationData>& newtonData, const std::vector<IterationData>* anothersData, const std::vector<IterationData>& carmackData, const std::vector<IterationData>& carmack2Data) {
    std::vector<IterationData> sortedNewtonData = newtonData;
    std::vector<IterationData> sortedAnothersData = anothersData[0];
    std::vector<IterationData> sortedAnothersData1 = anothersData[1];
    std::vector<IterationData> sortedAnothersData2 = anothersData[2];
    std::vector<IterationData> sortedCarmackData = carmackData;
    std::vector<IterationData> sortedCarmack2Data = carmack2Data;

    // Sort the data based on the number of iterations
    std::sort(sortedNewtonData.begin(), sortedNewtonData.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::sort(sortedAnothersData.begin(), sortedAnothersData.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::sort(sortedAnothersData1.begin(), sortedAnothersData1.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::sort(sortedAnothersData2.begin(), sortedAnothersData2.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::sort(sortedCarmackData.begin(), sortedCarmackData.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::sort(sortedCarmack2Data.begin(), sortedCarmack2Data.end(), [](const IterationData& a, const IterationData& b) {
        return a.iterations > b.iterations;
        });

    std::cout << "\nSome random numbers and their iterations for Newton's method:\n";
    for (size_t i = 0; i < 10 && i < sortedNewtonData.size(); ++i) {
        std::cout << "Number: " << sortedNewtonData[i].number
            << ", Iterations: " << sortedNewtonData[i].iterations
            << ", Sqrt: " << sortedNewtonData[i].sqrtResult << "\n";
    }

    std::cout << "\nSome random numbers and their iterations for Another's method:\n";
    for (size_t i = 0; i < 10 && i < sortedAnothersData.size(); ++i) {
        std::cout << "Number: " << sortedAnothersData[0, i].number
            << ", Iterations: " << sortedAnothersData[0, i].iterations
            << ", Sqrt: " << sortedAnothersData[0, i].sqrtResult << "\n";
    }

    std::cout << "\nSome random numbers and their iterations for Another's method 2:\n";
    for (size_t i = 0; i < 10 && i < sortedAnothersData.size(); ++i) {
        std::cout << "Number: " << sortedAnothersData[1, i].number
            << ", Iterations: " << sortedAnothersData[1, i].iterations
            << ", Sqrt: " << sortedAnothersData[1, i].sqrtResult << "\n";
    }

    std::cout << "\nSome random numbers and their iterations for Another's method 3:\n";
    for (size_t i = 0; i < 10 && i < sortedAnothersData.size(); ++i) {
        std::cout << "Number: " << sortedAnothersData[2, i].number
            << ", Iterations: " << sortedAnothersData[2, i].iterations
            << ", Sqrt: " << sortedAnothersData[2, i].sqrtResult << "\n";
    }

    std::cout << "\nSome random numbers and their iterations for Carmack's method:\n";
    for (size_t i = 0; i < 10 && i < sortedCarmackData.size(); ++i) {
        std::cout << "Number: " << sortedCarmackData[i].number
            << ", Iterations: " << sortedCarmackData[i].iterations
            << ", Sqrt: " << sortedCarmackData[i].sqrtResult << "\n";
    }

    std::cout << "\nSome random numbers and their iterations for Carmack's method 2:\n";
    for (size_t i = 0; i < 10 && i < sortedCarmack2Data.size(); ++i) {
        std::cout << "Number: " << sortedCarmack2Data[i].number
            << ", Iterations: " << sortedCarmack2Data[i].iterations
            << ", Sqrt: " << sortedCarmack2Data[i].sqrtResult << "\n";
    }
}

void clearScreen() {
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif
}

int main() {
    double number;

    std::cout << "Enter the number to find the square root: ";
    std::cin >> number;

    // Show iterations for each method with user input
    double resultNewton, resultAnothers[3], resultCarmack, resultCarmack2;
    int iterationsNewton, iterationsAnothers[3], iterationsCarmack, iterationsCarmack2;
    showIterations(number, resultNewton, resultAnothers, resultCarmack, resultCarmack2, iterationsNewton, iterationsAnothers, iterationsCarmack, iterationsCarmack2);

    std::cout << "Press enter to continue . . .";
    std::cin.get();
    std::cin.get();

    std::vector<double> timesSqrt, timesNewton, timesAnothers[3], timesCarmack, timesCarmack2;
    std::vector<IterationData> newtonData, anothersData[3], carmackData, carmack2Data;

    double* randomNumbers = new double[NUM_EXECUTIONS];
    std::mt19937_64 rng;
    std::uniform_real_distribution<double> dist(1.0, 100.0); // Random numbers between 1 and 100

    for (int i = 0; i < NUM_EXECUTIONS; i++) {
        randomNumbers[i] = dist(rng);
    }

    measureTime(randomNumbers, timesSqrt, timesNewton, timesAnothers, timesCarmack, timesCarmack2, newtonData, anothersData, carmackData, carmack2Data);

    delete[] randomNumbers;

    std::cout << "Press enter to continue to error calculations . . .";
    std::cin.get();

    // Display the error calculations
    std::vector<double> roots = { resultNewton, resultAnothers[0], resultAnothers[1], resultAnothers[2], resultCarmack, resultCarmack2 };
    calculateAndDisplayErrors(number, roots);

    std::cout << "Press enter to continue to time measurements . . .";
    std::cin.get();

    // Display the average times
    displayAverageTimes(timesSqrt, timesNewton, timesAnothers, timesCarmack, timesCarmack2);

    std::cout << "Press enter to continue to top iterations display . . .";
    std::cin.get();

    // Display the top iterations
    std::cout << "Some random numbers and their iterations:\n";
    displaySomeIterations(newtonData, anothersData, carmackData, carmack2Data);

    std::cout << "Press enter to exit . . .";
    std::cin.get();

    return 0;
}

Sorry for the duplicate code.