Binary Numbers, Binary Code, and Binary Logic
The 2015 edition of Hour of Code includes a new blocks-based, Star Wars themed coding lesson. In one of the exercises — a simple sprite-based game — you are asked to code a loop that adds 100 to your score every time R2-D2 encounters a Rebel Pilot. But instead of 100, I plugged in a floating-point number; I got the expected “unexpected” results.
Continue reading “An Hour of Code… A Lifelong Lesson in Floating-Point”
I want to contribute to the Hour of Code event happening now during Computer Science Education Week.
I don’t write about computer programming, but I do write extensively about how computers work — in particular, about how they do arithmetic with binary numbers. For your “hour of code” I’d like to introduce you to binary numbers and binary addition. I’ve selected several of my articles for you to read, and I’ve written some exercises you can try on my online calculators.
Continue reading “Hour of Code: Binary Numbers and Binary Addition”
I’ve written about two implementations of decimal string to double-precision binary floating-point conversion: David Gay’s strtod(), and glibc’s strtod(). GCC, the GNU Compiler Collection, has yet another implementation; it uses it to convert decimal floating-point literals to double-precision. It is much simpler than David Gay’s and glibc’s implementations, but there’s a hitch: limited precision causes it to produce some incorrect conversions. Nonetheless, I wanted to explain how it works, since I’ve been studying it recently. (I looked specifically at the conversion of floating-point literals in C code, although the same code is used for other languages.)
Continue reading “How GCC Converts Decimal Literals to Floating-Point”
The string to double function, strtod(), converts decimal numbers represented as strings into binary numbers represented in IEEE double-precision floating-point. Many programming environments implement their string to double conversions with David Gay’s strtod(); glibc, the GNU C Library, does not.
Like David Gay’s strtod(), glibc’s strtod() produces correctly rounded conversions. But it uses a simpler algorithm: it doesn’t have a floating-point only fast path for small inputs; it doesn’t compute a floating-point approximation to the correct result; it doesn’t check the approximation with big integers; it doesn’t adjust the approximation and recheck it; it doesn’t have an optimization for really long inputs. Instead, it handles all inputs uniformly, converting their integer and fractional parts separately, using only big integers. I will give an overview of how glibc’s strtod() works.
I’ve been teaching my sons Java by watching the Udacity course “Introduction to Programming: Problem Solving with Java” with them. In lesson four, we were introduced to the vagaries of floating-point arithmetic. The instructor talks about how this calculation
double pennies = 4.35 * 100;
produces 434.99999999999994 as its output.
I told my kids “it has to do with binary numbers” and “I write about this all the time on my blog”. Now of course I know this trips people up, but it really struck me to see the reaction firsthand. (I have long since forgotten my own first reaction.) It really hit home that thousands of new programmers are exposed to this every day.
Continue reading “Floating-Point Is So Insane Even a Ten-Year Old Can See It”
I read about an interesting method for decimal/binary conversion in chapter two of Gerald R. Rising’s book “Inside Your Calculator”. Unlike the standard string-oriented conversion algorithms, the algorithms in his book perform arithmetic on an encoding I’ve dubbed “deci-binary”. Using this encoding, binary numbers are input and output as decimal strings consisting of only ones and zeros, exploiting built-in language facilities for decimal input and output. I will demonstrate this conversion process with Java code I have written.
Continue reading “Decimal/Binary Conversion Using “Deci-Binary””
Many new programmers become aware of binary floating-point after seeing their programs give odd results: “Why does my program print 0.10000000000000001 when I enter 0.1?”; “Why does 0.3 + 0.6 = 0.89999999999999991?”; “Why does 6 * 0.1 not equal 0.6?” Questions like these are asked every day, on online forums like stackoverflow.com.
The answer is that most decimals have infinite representations in binary. Take 0.1 for example. It’s one of the simplest decimals you can think of, and yet it looks so complicated in binary:
The bits go on forever; no matter how many of those bits you store in a computer, you will never end up with the binary equivalent of decimal 0.1.
There are several ways to convert a repeating bicimal to a fraction. I’ve shown you the subtraction method; now I’ll show you the direct method, my name for the method that creates a fraction directly, using a numerator and denominator of well-known form.
Continue reading “Converting a Bicimal to a Fraction (Direct Method)”
In my article “Binary Division” I showed how binary long division converts a fraction to a repeating bicimal. In this article, I’ll show you a well-known procedure — what I call the subtraction method — to do the reverse: convert a repeating bicimal to a fraction.
Continue reading “Converting a Bicimal to a Fraction (Subtraction Method)”
This is the fourth of a four part series on “pencil and paper” binary arithmetic, which I’ve written as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; the third article discusses binary multiplication; this article discusses binary division.
The pencil-and-paper method of binary division is the same as the pencil-and-paper method of decimal division, except that binary numerals are manipulated instead. As it turns out though, binary division is simpler. There is no need to guess and then check intermediate quotients; they are either 0 are 1, and are easy to determine by sight.
This is the third of a four part series on “pencil and paper” binary arithmetic, which I’m writing as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; this article discusses binary multiplication.
The pencil-and-paper method of binary multiplication is just like the pencil-and-paper method of decimal multiplication; the same algorithm applies, except binary numerals are manipulated instead. The way it works out though, binary multiplication is much simpler. The multiplier contains only 0s and 1s, so each multiplication step produces either zeros or a copy of the multiplicand. So binary multiplication is not multiplication at all — it’s just repeated binary addition!
This is the second of a four part series on “pencil and paper” binary arithmetic, which I’m writing as a supplement to my binary calculator. The first article discusses binary addition; this article discusses binary subtraction.
The pencil-and-paper method of binary subtraction is just like the pencil-and-paper method of decimal subtraction you learned in elementary school. Instead of manipulating decimal numerals, however, you manipulate binary numerals, according to a basic set of rules or “facts.”
