Multiplying our way out of division
4 days ago
- #compiler-optimizations
- #binary-to-decimal
- #low-level-programming
- The article discusses optimizing a 'binary to decimal' routine, focusing on converting numbers to their ASCII representation.
- A simple method involves using modulo and division to extract digits, then adjusting for ASCII values.
- The compiler optimizes division by a constant (like 10) into multiplication and bit shifting, avoiding expensive division operations.
- Magic numbers (e.g., 0xcccccccd) and shifts (e.g., right by 35) are used to approximate division by 10 efficiently.
- The article highlights clever compiler optimizations, including loop unrolling and remainder calculation tricks.
- Additional optimizations involve log(10) calculations and lookup tables for faster digit extraction.
- The post is part of a series on compiler optimizations, written by Matt Godbolt and reviewed by LLMs and humans.