Google is celebrating Leibniz’s 372nd birthday today, recognizing him for his writings on binary numbers and binary arithmetic:
The drawing shows the binary code for the ASCII characters that spell “Google”:
Google Doodle: Gottfried Wilhelm Leibniz
Tag: Binary integers
The Safe Range For PHP’s base_convert()
PHP’s base_convert() is a useful function that converts integers between any pair of bases, 2 through 36. However, you might hesitate to use it after reading this vague and mysterious warning in its documentation:
base_convert() may lose precision on large numbers due to properties related to the internal “double” or “float” type used.
The truth is that it works perfectly for integers up to a certain maximum — you just have to know what that is. I will show you this maximum value in each of the 35 bases, and how to check if the values you are using are within this limit.
My Fretlight Guitar Binary Clock: Raspberry Pi Edition
I’ve previously written a Windows program (in C++) and an Android app (in Java) to turn my Fretlight guitar into a binary clock. I’ve now written a Python program to do the same, running under Raspbian Linux on a Raspberry Pi computer. I will show you the code and tell you how to run it.
Continue reading “My Fretlight Guitar Binary Clock: Raspberry Pi Edition”
Gangnam Style Video Overflows YouTube Counter
On Monday, Psy’s Gangnam Style video exceeded the limit of YouTube’s view counter; this is what Google had to say (hat tip: Digg):
“We never thought a video would be watched in numbers greater than a 32-bit integer (=2,147,483,647 views)…”
2,147,483,647 is 231 – 1, the maximum positive value a 32-bit signed integer can contain.
Google has since fixed the counter, but they didn’t say how (32-bit unsigned integer? 64-bit integer?). (Update: By deduction from this Wall Street Journal article, Google is now using 64-bit signed integers — although the number they cite is 263, not 263 – 1.)
The interesing thing is the “Easter egg” Google placed. If you hover your mouse over the counter, it spins like a slot machine; if you hold the mouse there long enough it will show a negative number. But the negative number is not what I expected. Is there a bug in the Easter egg?
Continue reading “Gangnam Style Video Overflows YouTube Counter”
My Fretlight Guitar As a Binary Clock
With a little research and some USB tracing, I wrote a Windows program — and an Android app — that turns my Fretlight guitar into a BCD mode binary clock!
(Update: I now also have a Raspberry Pi version.)
Hour of Code: Binary Numbers and Binary Addition
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”
How GCC Converts Decimal Literals to Floating-Point
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”
How GLIBC’s strtod() Works
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.
A Better Way to Convert Integers in David Gay’s strtod()
A reader of my blog, John Harrison, suggested a way to improve how David Gay’s strtod() converts large integers to doubles. Instead of approximating the conversion and going through the correction loop to check and correct it — the signature processes of strtod() — he proposed doing the conversion directly from a binary big integer representation of the decimal input. strtod() does lots of processing with big integers, so the facility to do this is already there.
I implemented John’s idea in a copy of strtod(). The path for large integers is so much simpler and faster that I can’t believe it never occurred to me to do it this way. It’s also surprising that strtod() never implemented it this way to begin with.
Continue reading “A Better Way to Convert Integers in David Gay’s strtod()”
Decimal/Binary Conversion Using “Deci-Binary”
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””
Number of Decimal Digits In a Binary Integer
This is a companion article to “Number of Bits in a Decimal Integer”
If you have an integer expressed in decimal and want to know how many bits are required to express it in binary, you can perform a simple calculation. If you want to know how many bits are required to express a d-digit decimal integer in binary, you can perform other simple calculations for that.
What if you want to go in the opposite direction, that is, from binary to decimal? There are similar calculations for determining the number of decimal digits required for a specific binary integer or for a b-bit binary integer. I will show you these calculations, which are essentially the inverses of their decimal to binary counterparts.
Continue reading “Number of Decimal Digits In a Binary Integer”
Ratio of Bits to Decimal Digits
Excluding 0 and 1, it takes more digits to express an integer in binary than in decimal. How many more? The commonly given answer is log2(10) ≈ 3.32 times as many. But this is misleading; the ratio actually depends on the specific integer. So where does ‘log2(10) bits per digit’ come from? It’s a theoretical limit, a value that’s approached only as integers grow large. I’ll show you how to derive it.
