Explores why algorithms with better time complexity don't always perform better in practice. Compares three GCD algorithms (subtraction-based O(n), modulo-based O(log n), and Stein's binary O(log n)) through benchmarks, showing how hardware characteristics like instruction latency, throughput, and IPC can make a theoretically slower algorithm outperform a faster one. Demonstrates that real-world performance depends on both algorithmic efficiency and hardware-friendly implementation choices.
Table of contents
Euclid’s Subtraction-based Algorithm for Computing GCDThe Modulo-based Euclidean Algorithm for GCDBenchmark #1: Huge InputsCost of Integer Add vs Integer Division in HardwareBenchmark #2: Small InputsStein’s Binary Algorithm for GCDBenchmark #3: Comparing All Three AlgorithmsConclusionCode67 Impressions