In my article “Using Integers to Check a Floating-Point Approximation,” I briefly mentioned “bigcomp,” an optimization strtod() uses to reduce big integer overhead when checking long decimal inputs. bigcomp does a floating-point to decimal conversion — right in the middle of a decimal to floating-point conversion mind you — to generate the decimal expansion of the number halfway between two target floating-point numbers. This decimal expansion is compared to the input decimal string, and the result of the comparison dictates which of the two target numbers is the correctly rounded result.

In this article, I’ll explain how bigcomp works, and when it applies. Also, I’ll talk briefly about its performance; my informal testing shows that, under the default setting, bigcomp actually worsens performance for some inputs.

Continue reading …

For decimal inputs that don’t qualify for fast path conversion, David Gay’s strtod() function does three things: first, it uses IEEE double-precision floating-point arithmetic to calculate an approximation to the correct result; next, it uses arbitrary-precision integer arithmetic (AKA big integers) to check if the approximation is correct; finally, it adjusts the approximation, if necessary. In this article, I’ll explain the second step — how the check of the approximation is done.

Continue reading …

David Gay’s strtod() function does decimal to floating-point conversion using both IEEE double-precision floating-point arithmetic and arbitrary-precision integer arithmetic. For some inputs, a simple IEEE floating-point calculation suffices to produce the correct result; for other inputs, a combination of IEEE arithmetic and arbitrary-precision arithmetic is required. In the latter case, IEEE arithmetic is used to calculate an approximation to the correct result, which is then refined using arbitrary-precision arithmetic. In this article, I’ll describe the approximation calculation, which is based on a form of binary exponentiation.

Continue reading …

Hexadecimal floating-point constants, also known as hexadecimal floating-point literals, are an alternative way to represent floating-point numbers in a computer program. A hexadecimal floating-point constant is shorthand for binary scientific notation, which is an abstract — yet direct — representation of a binary floating-point number. As such, hexadecimal floating-point constants have exact representations in binary floating-point, unlike decimal floating-point constants, which in general do not.

Hexadecimal floating-point constants are useful for two reasons: they bypass decimal to floating-point conversions, which are sometimes done incorrectly, and they bypass floating-point to decimal conversions which, even if done correctly, are often limited to a fixed number of decimal digits. In short, their advantage is that they allow for direct control of floating-point variables, letting you read and write their exact contents.

In this article, I’ll show you what hexadecimal floating-point constants look like, and how to use them in C.

Continue reading …

In my article “Patterns in the Last Digits of the Positive Powers of Five” I showed that the cycles of ending digits of the positive powers of five could be represented with a binary tree:

Binary Tree Showing Nested Ending Digit Patterns of the Positive Powers of Five

The tree layout shows that certain pairs of ending digits are related, and that these pairs differ by five in their starting digits. I will show why this is true.

Continue reading …

In my article “Counting Binary and Hexadecimal Palindromes” I derived formulas for counting binary palindromes and hexadecimal palindromes. For each type of palindrome, I derived two pairs of formulas: one pair to count n-digit palindromes, and one pair to count palindromes of n digits or less.

In this article, I will derive similar formulas to count binary/hexadecimal palindromes — multi-base palindromes I’ve shown to have an algorithmically defined structure.

Continue reading …

To perform arbitrary-precision arithmetic in C and C++ programs on Windows, I use GMP. In particular, I use MPIR, a Windows port of GMP. MPIR is a simple alternative to using GMP under Cygwin or MinGW.

I will show you how to install MPIR in Microsoft Visual C++ as a static, 32-bit library. I will also show you how to install the optional C++ interface — also as a static, 32-bit library. I will provide two example C programs that call the GMP integer and floating-point functions, and two equivalent C++ programs — programs that use the same GMP functions, only indirectly through the C++ interface.

Continue reading …

How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:

• When n is even: 9·10^n/2-1
• When n is odd: 9·10^(n+1)/2-1

How many nonzero, decimal number palindromes are there, consisting of n-digits or less? These two formulas give the answer:

• When n is even: 2(10^n/2 – 1)
• When n is odd: 11·10^(n-1)/2 – 2

So for example, there are 900 5-digit decimal palindromes, 9,000 8-digit decimal palindromes, 1,098 decimal palindromes of 5 digits or less, and 19,998 decimal palindromes of 8 digits or less.

In this article, I will derive similar formulas to count binary and hexadecimal number palindromes.

Continue reading …

In my article “Patterns in the Last Digits of the Positive Powers of Five” I noted that the positive powers of five modulo 10^m cycle with period 2^m-2, m ≥ 2, starting at 5^m. In this article, I’ll present my proof, which has two parts:

• Part 1 shows that the powers of five mod 2^m cycle with period 2^m-2, m ≥ 2, starting at 5⁰.
• Part 2 shows that the powers of five mod 10^m cycle with the same period as the powers of five mod 2^m, starting at 5^m.

The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2^m is 2^m-2. While it is in general not possible to derive a formula for the order of a number, I’ll show it is possible for the powers of five mod 2^m — due to a hidden, binary structure I’ve uncovered.

Continue reading …

The positive powers of five — 5, 25, 125, 625, 3125, 15625, … — have a compact, repeating pattern in their ending m digits, in the powers of five from 5^m on. For example: starting with 5, their last digit is always 5; starting with 25, their last two digits are always 25; starting with 125, their last three digits alternate between 125 and 625. These cycles come in lengths of powers of two.

Cycles in the Ending Digits of the Powers of Five

I will show you why these cycles exist, how they are expressed mathematically, and how to visualize them.

Continue reading …

The decimal representations of oppositely signed powers of two and powers of five look alike, as seen in these examples: 2^-3 = 0.125 and 5³ = 125; 5^-5 = 0.00032 and 2⁵ = 32. The significant digits in each pair of powers is the same, even though one is a fraction and one is an integer. In other words, a negative power of one base looks like a positive power of the other.

Powers of Two and Powers of Five that Look Alike

This relationship is not coincidence; it’s a by-product of how fractions are represented as decimals. I’ll show you simple algebra that proves it, as well as algebra that proves similar properties — in products involving negative powers.

Continue reading …

In my article “Patterns in the Last Digits of the Positive Powers of Two” I noted that the positive powers of two modulo 10^m cycle with period 4·5^m-1, starting at 2^m. For example, the powers of two mod 10 cycle with period four: 2, 4, 8, 6, 2, 4, 8, 6, … . In this article, I’ll present my proof, which has two parts:

• Part 1 shows that the powers of two mod 5^m cycle with period 4·5^m-1, starting at 2⁰.
• Part 2 shows that the powers of two mod 10^m cycle with the same period as the powers of two mod 5^m, starting at 2^m.

Continue reading …