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.
Became Hot Network Question
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.
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.
lang-cpp