In my article “Quick and Dirty Decimal to Floating-Point Conversion” I presented a small C program that converts a decimal string to a double-precision binary floating-point number. The number it produces, however, is not necessarily the closest — or so-called correctly rounded — double-precision binary floating-point number. This is not a failing of the algorithm; mathematically speaking, the algorithm is correct. The flaw comes in its implementation in limited precision binary floating-point arithmetic.
The quick and dirty program is implemented in native C, so it’s limited to double-precision floating-point arithmetic (although on some systems, extended precision may be used). Higher precision arithmetic — in fact, arbitrary precision arithmetic — is needed to ensure that all decimal inputs are converted correctly. I will demonstrate the need for high precision by analyzing three examples, all taken from Vern Paxson’s paper “A Program for Testing IEEE Decimal–Binary Conversion”.
Continue reading …
This little C program converts a decimal value — represented as a string — into a double-precision floating-point number:
#include <string.h>
int main (void)
{
double intPart = 0, fracPart = 0, conversion;
unsigned int i;
char decimal[] = "3.14159";
i = 0; /* Left to right */
while (decimal[i] != '.') {
intPart = intPart*10 + (decimal[i] - '0');
i++;
}
i = strlen(decimal)-1; /* Right to left */
while (decimal[i] != '.') {
fracPart = (fracPart + (decimal[i] - '0'))/10;
i--;
}
conversion = intPart + fracPart;
}
The conversion is done using the elegant Horner’s method, summing each digit according to its decimal place value. So why do I call it “quick and dirty?” Because the binary floating-point value it produces is not necessarily the closest approximation to the input decimal value — the so-called correctly rounded result. (Remember that most real numbers cannot be represented exactly in floating-point.) Most of the time it will produce the correctly rounded result, but sometimes it won’t — the result will be off in its least significant bit(s). There’s just not enough precision in floating-point to guarantee the result is correct every time.
I will demonstrate this program with different input values, some of which convert correctly, and some of which don’t. In the end, you’ll appreciate one reason why library functions like strtod() exist — to perform efficient, correctly rounded conversion.
Continue reading …
Are there any multiple digit hexadecimal number palindromes that are also palindromic in binary and decimal? I have been searching but have not found any.
I started my search with my program that finds multiple-base palindromes. I generated palindromes in binary, and then checked them to see if they were also palindromes in hexadecimal and decimal. I looked for decimal/binary/hexadecimal palindromes up to 16 hex digits long, but did not find any.
To continue my search into bigger numbers, I wrote a program that uses arbitrary-precision integer arithmetic and a more efficient algorithm. Despite being able to search much further, I still have not found any.
In this article, I’ll analyze the size of the palindrome “search space”, explain my improved algorithm, and discuss the state of my search.
Continue reading …
In case you haven’t heard, Mattel® has created Computer Engineer Barbie®, based on popular vote. Here’s the laptop she is holding:
Binary Code on Barbie's Laptop
It spells “Barbie” — repeatedly, in ASCII code.
Continue reading …
In my article “When Floats Don’t Behave Like Floats” I explained how calculations involving single-precision floating-point variables may be done, under the covers, in double or extended precision. This leads to anomalies in expected results, which I demonstrated with two C programs — compiled with Microsoft Visual C++ and run on a 32-bit Intel Core Duo processor.
In this article, I’ll do a similar analysis for double-precision floating-point variables, showing how similar anomalies arise when extended precision calculations are done. I modified my two example programs to use doubles instead of floats. Interestingly, the doubles version of program 2 does not exhibit the anomaly. I’ll explain.
Continue reading …
These two programs — compiled with Microsoft Visual C++ and run on a 32-bit Intel Core Duo processor — demonstrate an anomaly that occurs when using single-precision floating point variables:
Program 1
#include "stdio.h"
int main (void)
{
float f1 = 0.1f, f2 = 3.0f, f3;
f3 = f1 * f2;
if (f3 != f1 * f2)
printf("Not equal\n");
}
Prints “Not equal”.
Program 2
#include "stdio.h"
int main (void)
{
float f1 = 0.7f, f2 = 10.0f, f3;
int i1, i2;
f3 = f1 * f2;
i1 = (int)f3;
i2 = (int)(f1 * f2);
if (i1 != i2)
printf("Not equal\n");
}
Prints “Not equal”.
In each case, f3 and f1 * f2 differ. But why? I’ll explain what’s going on.
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 …
Binary/hexadecimal palindromes are integers that are palindromic in both binary and hexadecimal. Unlike binary/decimal palindromes, for example, they have a predictable structure. This means they can be generated directly, rather than searched for. So what is their structure?
Certainly they’re made up of the hexadecimal digits that are themselves palindromic in binary: 0, 6, 9, F; for example, F060F16 = 111100000110000011112 and 9F916 = 1001111110012. Each of these four hexadecimal digits maps neatly to a 4-digit binary palindrome, so any hexadecimal palindrome made from them is automatically palindromic in binary.
But there are other binary/hexadecimal palindromes, like 52516 = 101001001012 and 7020716 = 11100000010000001112, that contain hexadecimal digits that are not palindromic in binary. In this case, binary palindromes are produced with combinations of hexadecimal digits. It turns out there are a limited number of valid combinations, and that they’re localized — they span only two hexadecimal digits.
In this article, I’ll analyze binary/hexadecimal palindromes and describe their structure — a structure due to the relationship of the two bases, binary and hexadecimal.
Example Binary/Hexadecimal Palindromes
Continue reading …
How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:
- When n is even: 9·10n/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(10n/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 10m cycle with period 2m-2, m ≥ 2, starting at 5m. In this article, I’ll present my proof, which has two parts:
- Part 1 shows that the powers of five mod 2m cycle with period 2m-2, m ≥ 2, starting at 50.
- Part 2 shows that the powers of five mod 10m cycle with the same period as the powers of five mod 2m, starting at 5m.
The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2m is 2m-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 2m — due to a hidden, binary structure I’ve uncovered.
Continue reading …
People have been tweeting about the upcoming dates that look like binary numbers. 10/10/10 seems to be a favorite, both because of its symmetry and because 101010 = 42 in decimal (you know, the answer to the ultimate question of life, the universe, and everything). Here are the nine dates in 2010, interpreted as binary numbers, and with their decimal equivalents:
Continue reading …
(Published May 20th, 2010) 
