Example of Binary Addition

Binary Arithmetic

Binary arithmetic is of interest because that’s how computers do math. When implemented in computers, many things must be taken into account: format (fixed-point, floating-point, etc.), word size (8-bit, 16-bit, 32-bit, etc.), sign representation (sign-magnitude, ones’ complement, two’s complement, etc.), overflow (when numbers are too big), and underflow (when numbers are too small). Furthermore, there is the design of the circuits to perform the algorithms (full adders, half adders, ripple carry adders, carry-lookahead adders, restoring dividers, non-restoring dividers, etc.). These are not inherent properties of binary arithmetic — they’re just implementation issues.

The truth is, in its purest form, binary arithmetic is very simple. The same “pencil and paper” algorithms you learned in grade school work for binary numbers. All you do differently is apply the “facts” for binary numerals, the (small) set of rules for manipulating 0s and 1s. And binary numbers on paper are written as you’d expect: without leading zeros, and with a minus sign (‘-’) if negative.

In my series of articles, I will explain the pure forms of the four basic operations of binary arithmetic: addition, subtraction, multiplication, and division. In this first article, I will discuss binary addition.

Decimal Addition

To add two multiple-digit decimal numbers, you first need to know how to add two single-digit decimal numbers. This requires the memorization of 100 facts, or 55 facts if you exclude the commutative or “turnaround” facts. Also, because of carries, you need to know ten additional facts: 10 + 0 = 10, 10 + 1 = 11, … , 10 + 9 = 19. The latter apply when there’s a carry (always 1) and the “top” digit is 9.

For example, let’s add 19.7 and 12.8:

Example of Decimal Addition

Let’s think about what a carry does. It turns our neat “add two single-digit numbers per column” problem into “add three single-digit numbers per column.” But addition is a binary (in a different sense) operation, meaning it operates on two numbers at a time. So what we do is add the carry to the “top” digit, and then add that result to the “bottom” digit. The first addition may result in a double digit answer (10), which means we’d have to use one of the ten extra facts to do the second addition.

In our example, the carry is added to 9, giving 10, and then 10 is added to 2, giving 12. The second addition used the extra “10 + 2 = 12″ fact.

Decimal Addition Showing Intermediate Additions

Binary Addition

Binary addition works the same way as decimal addition, except it uses a different — and much smaller — set of facts. There are only four single-digit facts, or three if you exclude the commutative fact. To handle carries, you need to know two additional facts, 10 + 0 = 10 and 10 + 1 = 11. (Resist the urge to pronounce 10 as ten and 11 as eleven; either call them one-zero and one-one, or two and three.) The latter apply when there’s a carry (always 1) and the “top” digit is 1.

Of the five order-independent facts, two are the same as in decimal (0 + 0 = 0 and 1 + 0 = 1), and one is trivial since it just adds zero (10 + 0 = 10). This leaves only two facts to memorize: 1 + 1 = 10 and 10 + 1 = 11!

To add two binary numbers, proceed as in decimal addition:

• If one or both numbers has a fractional part, line up the radix points.
• Proceeding from right to left, add the digits in each “column,” according to the facts table.
• If the result has two-digits, write down the least significant digit; carry the most significant digit to the next column.

Let’s return to the example in the introduction, 1011.01 + 11.011, this time showing it step-by-step:

Steps of Binary Addition

Eventually you won’t need to write down the intermediate additions, and you might even start doing ‘1 + 1 + 1’ as one step.

Checking the Answer

You can verify the answer by converting the operands to decimal, doing decimal addition, and then converting the decimal answer to binary (of course you can do it that way period, avoiding binary arithmetic entirely!). 1011.01 = 11.25, and 11.011 = 3.375. They sum to 14.625, which is 1110.101, the answer we got using binary addition.

Discussion

We didn’t need to know the place value of columns, or that a carry represents a power of the base; the algorithm is base-independent. We did however need a base-dependent set of facts, which allowed us to manipulate binary numerals according to the basic rules of binary addition.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Binary Addition

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.

When Bigcomp Applies

Bigcomp is enabled by default in strtod() (it can be disabled by “#defining” the variable “NO_STRTOD_BIGCOMP”). It applies to decimal strings longer than STRTOD_DIGLIM significant digits, which by default is “#defined” to 40. For decimal inputs dStr of 40 significant digits or less, the normal approximation check is done, using all significant digits of dStr for its big integer representation d; for inputs longer than 40 digits, only the first 18 digits are used for d. This truncation of d leads to smaller big integers, but it can lead to cases where the approximation check cannot decide between adjacent floating-point values. When that happens, the bigcomp procedure kicks in, through a call to the bigcomp() function.

Specifically, bigcomp() is called when the approximation check cannot decide between the approximation b and its successor, b + u. (As with all my articles in this series, I will only be discussing how strtod() works for round-to-nearest/round-half-to-even rounding.) This happens when the truncated value of d falls between b and b + h; that is, between b and one-half ULP above b.

(In this article, I distinguish between the input dStr and its big integer representation d, which may or may not be a truncation of dStr.)

Overview of the Algorithm

bigcomp() compares the significant digits of dStr to a string representation of the significant digits of b + h. It goes left-to-right, digit by significant digit, stopping when the two strings differ. (In the bulk of cases, the difference occurs between the 16th and 18th digits, although in the worst case the difference can occur at the 54th digit; it depends on how close the decimal number is to b + h.) If dStr is less than b + h, bigcomp() returns b; if dStr is greater than b + h, bigcomp() returns b + u; if dStr equals b + h, either b or b + u is chosen, according to round-half-to-even rounding.

bigcomp() generates the significant digits of b + h using essentially the same algorithm as the dtoa() function, the floating-point to decimal conversion routine co-located in David Gay’s dtoa.c. It uses big integer arithmetic, including big integer division.

bigcomp() starts by creating a fraction that represents the significant digits of b + h (not b + h itself). In this form, it generates a digit by multiplying the numerator of the fraction by ten, and then using integer division to form a quotient and remainder. The quotient represents the next digit; the remainder represents the remaining digits, which are accessed one at a time by repeating this process. Digits are generated until there is a mismatch between dStr and b + h.

The Algorithm, By Example

I’ll break the algorithm into five steps, and illustrate it with two examples. I set STRTOD_DIGLIM to 19 so I could generate shorter examples (both are 20 digits).

Example 1: Check 1.3694713649464322631e-11

In this example, we want to check if dStr = 1.3694713649464322631e-11 is closer to b = 0x1.e1d703bb5749cp-37 or b + u = 0x1.e1d703bb5749dp-37. We do this by comparing dStr to b + h = 0x1.e1d703bb5749c8p-37. (I describe b + h using a hexadecimal floating-point constant, even though it won’t be represented as an IEEE floating-point number. This number has 54 bits, with bit 54 being a 1. It is b with a hexadecimal ‘8’ tacked on at the end.)

1. Represent b + h as an integer times a power of two

We start by representing b as a 53-bit integer times a power of two, as we do in the basic approximation check:

b = bInt x 2bExp
  = 8476617176609948 x 2-89

Since bInt is 53-bit integer, u = 2^bExp, and h is 2^bExp-1. Therefore,

b + h = bInt x 2bExp + 2bExp-1
      = (bInt x 2 + 1) x 2bExp-1
      = (8476617176609948 x 2 + 1) x 2-90
      = 16953234353219897 x 2-90

In code: We create bInt and bExp from b’s underlying floating-point representation: we treat its significand as a 53-bit integer, and subtract 52 from its power of two exponent. We create a big integer from bInt, and then we make it the integer portion of b + h by shifting it left and ‘ORing’ a 1 into its least significant bit. We maintain the exponent of the power of two as a native integer, setting it to bExp-1.

2. Scale b + h so its first significant digit is just to the left of the decimal point

If you were to compute b + h from the expression above, you’d see its value is

0.0000000000136947136494643226044416541235590733258456475063269408565
24743139743804931640625

(We’re not going to do that; I just wanted to show you where we’re headed. By the way, I computed it using PARI/GP.)

What we want to do is scale b + h so that it looks like

1.3694713649464322604441654123559073325845647506326940856524743139743
804931640625

In other words, we want to multiply it by a power of ten so that, when viewed as a decimal number, its significant digits look normalized; 10¹¹ does the trick, effectively shifting b + h left by 11 decimal places:

Scaled b + h = 16953234353219897 x 2-90 x 1011

This “normalization” sets up the digit generation algorithm.

In code: A full-blown floating-point to decimal conversion would need to use logarithms to compute the power of ten; but in this case, we can obtain the power of ten exponent directly from dStr.

3. Combine powers of two

If we decompose the power of ten into a power of two and a power of five, we get

Scaled b + h = 16953234353219897 x 2-90 x 211 x 511

We can now combine powers of two to reduce the size of the resulting big integers.

Scaled b + h = 16953234353219897 x 2-79 x 511

In code: The code is simple: just add the exponents of the power of two from b + h and the power of two from the power of ten scaling factor.

4. Express scaled b + h as a fraction

The negative power of two, 2^-79, makes this a fraction:

Scaled b + h = (16953234353219897 x 511)/279
             = 827794646153315283203125/604462909807314587353088

In code: Compute the powers as big integers, using the absolute values of the exponents; then, multiply the terms out, as appropriate.

5. Generate and check digits

Scaled b + h has a numerator num and denominator den:

num = 827794646153315283203125
den = 604462909807314587353088

The significant digits are generated from these integers using the “repeated multiplication by ten” algorithm; this is what’s done at each iteration (dig stands for ‘digit’, and rem stands for ‘remainder’):

1. dig = num/den (just the integer part of the quotient)
2. rem = num – dig x den
3. num = rem x 10

In other words, at each iteration, a digit is peeled off and the rest of the number is shifted left one decimal place. This step is repeated until a corresponding digit from dStr and b + h don’t match; here are the first three iterations:

1. 827794646153315283203125/den  = 1 rem 223331736346000695850037
2. 2233317363460006958500370/den = 3 rem 419928634038063196441106
3. 4199286340380631964411060/den = 6 rem 572508881536744440292532
4. ...

This stops after step 19; that is, dStr and b + h differ at the 19th digit. Here are the digits of dStr and b + h aligned, to show where they differ:

Digits of dStr  = 13694713649464322631
Digits of b + h = 1369471364946432260444165412355907332584564750632
6940856524743139743804931640625

Since 3 is greater than 0, dStr is closer to b + u than it is to b, so b + u is the answer.

Example 2: Check 9.3170532238714134438e+16

In this example, we want to check if dStr = 9.3170532238714134438e+16 is closer to b = 0x1.4b021afd9f651p+56 or b + u = 0x1.4b021afd9f652p+56. We do this by comparing dStr to b + h = 0x1.4b021afd9f6518p+56.

1. Represent b + h as an integer times a power of two

b = bInt x 2bExp
  = 5823158264919633 x 24

b + h = (bInt x 2 + 1) x 2bExp-1
      = (5823158264919633 x 2 + 1) x 23
      = 11646316529839267 x 23

2. Scale b + h so its first significant digit is just to the left of the decimal point

If you were to compute b + h from the expression above, you’d see its value is

93170532238714136

We want to shift it right 16 decimal places so it looks like

9.3170532238714136

Scaled b + h = 11646316529839267 x 23 x 10-16

3. Combine powers of two

If we decompose the power of ten into a power of two and a power of five, we get

Scaled b + h = 11646316529839267 x 23 x 2-16 x 5-16

Combining powers of two we get

Scaled b + h = 11646316529839267 x 2-13 x 5-16

4. Express scaled b + h as a fraction

The negative powers of two and five make this a fraction:

Scaled b + h = 11646316529839267/(213 x 516)
             = 11646316529839267/1250000000000000

5. Generate and check digits

Scaled b + h has a numerator num and denominator den:

num = 11646316529839267
den = 1250000000000000

Here are the first three iterations of the repeated multiplication by ten algorithm:

1. 11646316529839267/den = 9 rem 396316529839267
2. 3963165298392670/den  = 3 rem 213165298392670
3. 2131652983926700/den  = 1 rem 881652983926700
4. ...

This stops after step 17; that is, dStr and b + h differ at the 17th digit. Here are the digits of dStr and b + h aligned, to show where they differ:

Digits of dStr  = 93170532238714134438
Digits of b + h = 93170532238714136

Since 4 is less than 6, dStr is closer to b than it is to b + u, so b is the answer.

Discussion

strtod() has an extra step, which I’ve not described. It scales the numerator and denominator by a common power of two, which is necessary for its ‘quorem()’ function to compute the quotient and remainder properly. The power of two exponent is determined by a function called ‘dshift().’

If dStr represents a fractional value, step 2 (scale by power of ten) and step 3 (combine powers of two) are technically unnecessary. Without them, step 5 (generate digits) would generate leading zeros, which could be ignored. (Of course, the pre-scaling is more elegant, as it reduces everything to one form.)

The 40-Digit Cutoff Is Too Low

bigcomp() does a lot of work with big integers, which made me wonder why it performed better than the basic approximation check. I ran some tests, and found that it doesn’t perform better — not at the default STRTOD_DIGLIM value of 40! My tests indicate that bigcomp() only performs better starting at somewhere between 80 and 83 digits. (I don’t know why 40 was chosen as the default.) bigcomp() outperforms the basic check for really long inputs; for example, the difference in performance is great at 500 digits, and substantial at 1000 digits.

Let’s look at a 1000-digit input to see the difference in the big integers involved:

dStr = 5.39393324717760434968487301635560570642059608762708229108908
24537754965408622951477281124864324524316631524646435056101989215441
13243584680626358335990970896315873327586087827333915843584231417344
18113410301502801068079096892041478634628161830670245841932386407800
12745803879948980583567722824049594060350336856210415679895612943123
50098271611832693583464221850190462604938332826437767915224673375308
74570398083131101089815004834148500912320646940469604931721018872877
13566715387976682236017863055187831755129573243931855002598816011501
73130862094578091926124182802567489337171671008075773833668718543916
59331687129078431660248055444327878892028873933579030052796118406453
59419797286387142281725295340184928613290361074947899276429780250293
85401861377815243939607988608126354001619571808095966555370152710852
57007714188421395421027623995592231545518458559072989336658831420578
08271261804364513313549623924640140003927894134813865873451090057841
21193123838848522389829029095139051820951352412966707477e+16

Without bigcomp, using the basic approximation check, these are the variables involved:

dS = 539393324717760434968487301635560570642059608762708229108908245
37754965408622951477281124864324524316631524646435056101989215441132
43584680626358335990970896315873327586087827333915843584231417344181
13410301502801068079096892041478634628161830670245841932386407800127
45803879948980583567722824049594060350336856210415679895612943123500
98271611832693583464221850190462604938332826437767915224673375308745
70398083131101089815004834148500912320646940469604931721018872877135
66715387976682236017863055187831755129573243931855002598816011501731
30862094578091926124182802567489337171671008075773833668718543916593
31687129078431660248055444327878892028873933579030052796118406453594
19797286387142281725295340184928613290361074947899276429780250293854
01861377815243939607988608126354001619571808095966555370152710852570
07714188421395421027623995592231545518458559072989336658831420578082
71261804364513313549623924640140003927894134813865873451090057841211
93123838848522389829029095139051820951352412966707477

bS = 539393324717760400000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000

hS = 400000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000

|dS-bS| = 3496848730163556057064205960876270822910890824537754965408
62295147728112486432452431663152464643505610198921544113243584680626
35833599097089631587332758608782733391584358423141734418113410301502
80106807909689204147863462816183067024584193238640780012745803879948
98058356772282404959406035033685621041567989561294312350098271611832
69358346422185019046260493833282643776791522467337530874570398083131
10108981500483414850091232064694046960493172101887287713566715387976
68223601786305518783175512957324393185500259881601150173130862094578
09192612418280256748933717167100807577383366871854391659331687129078
43166024805544432787889202887393357903005279611840645359419797286387
14228172529534018492861329036107494789927642978025029385401861377815
24393960798860812635400161957180809596655537015271085257007714188421
39542102762399559223154551845855907298933665883142057808271261804364
51331354962392464014000392789413481386587345109005784121193123838848
522389829029095139051820951352412966707477

|dS-bS| is less than hS, so b is chosen.

With bigcomp, there are two sets of big integers involved: one set for the basic approximation check (on the truncated value), and one set for bigcomp. Here are the big integers used for the basic approximation check:

dS = 539393324717760434
bS = 539393324717760400
hS = 40
|dS-bS| = 34

Here are the big integers used for bigcomp (not shown is the extra factor of 2⁸ in the numerator and denominator due to dshift()):

num = 13484833117944011
den = 2500000000000000

bigcomp() finds that digit 17 of dStr (3) is less than digit 17 of b + h (4), so it chooses b.

Acknowledgement

Thanks to Mark Dickinson for his commentary on bigcomp, both in Python’s version of David Gay’s dtoa.c, and in private communication.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Bigcomp: Deciding Truncated, Near Halfway Conversions

WordPress.com Stats Reports One Million Views

This site went live on November 14, 2008; that works out to an average of over 920 views per day. My decimal/binary converter (an HTML form with an accompanying article) accounts for nearly half of those views (445,700+). Not counting my converter, these are my top ten articles:

1. Java Hangs When Converting 2.2250738585072012e-308 (134,500+ views)
2. PHP Hangs On Numeric Value 2.2250738585072011e-308 (93,600+ views)
3. Binary Dates in 2010 and 2011 (45,600+ views)
4. Ten Ways to Check if an Integer Is a Power Of Two in C (37,400+ views)
5. Converting Floating-Point Numbers to Binary Strings in C (15,200+ views)
6. Why “Volatile” Fixes the 2.2250738585072011e-308 Bug (12,200+ views)
7. FPUpdater Fixes the Java 2.2250738585072012e-308 Bug (10,600+ views)
8. How I Taught Third Graders Binary Numbers (9,800+ views)
9. The Answer is One (Unless You Use Floating-Point) (9,700+ views)
10. A Closer Look at the Java 2.2250738585072012e-308 Bug (9,200+ views)

Five of my top ten articles are related to the PHP and Java floating-point conversion bugs; together they total 260,200+ views.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Exploring Binary: One Million Views

Overview

The goal of David Gay’s strtod() is to perform efficient, correctly rounded decimal to floating point conversion. To that end, it minimizes the overhead due to arbitrary-precision arithmetic, which is unavoidable for some conversions. In particular, strtod() avoids division of big integers, as would be required by a full-blown big integer algorithm. Instead of dividing, it multiplies, adds, subtracts, and compares.

The key to the algorithm is the floating-point approximation. It can be compared to the original decimal input to see if it’s too small, correct, or too big (it will be within 10 ULPs or so of correct). The approximation can be adjusted accordingly.

(My discussion will deal only with normal double-precision numbers; strtod() handles subnormal numbers as well.)

Correctly Rounded Conversions

For a floating-point number b to be considered the correctly rounded conversion of a decimal number d, it must be the closest floating-point number to d. That definition sounds simple enough, but there’s a problem: the meaning of “closest” can depend on the value of b. In any case, the tests for closeness are all based on a measure called a ULP — a binary (for our purposes) unit in the last place. A ULP is the gap between adjacent floating-point numbers.

I’ll present the tests as three separate cases, although in code they must be considered together.

Case 1: d is less than one-half ULP away from b

If d is less than one-half of a ULP from b, then b is the correctly rounded conversion of d (this test is ambiguous when b is a power of two — I’ll explain below). Mathematically, this is stated as

b – h < d < b + h ,

where h = 1/2·u, and where u equals one ULP.

Here’s what the relationship looks like:

Correct rounding when d is less than one-half ULP away from b

Equivalently, this relationship can be written as

-h < d – b < h ,

or

|d – b| < h .

Case 2: d is one-half ULP away from b

If d is one-half of a ULP away from b, then b is the correctly rounded conversion of d only if b’s least significant bit is 0 (this test is ambiguous when b is a power of two — I’ll explain below). This is called round-half-to-even rounding.

The relationship is written as

|d – b| = h

Correct rounding when d is one-half ULP away from b

Case 3: b is a power of two

If b is a power of two, two different ULP values come into play, making our half ULP test ambiguous. One ULP below b is half as much as one ULP above b, since a ULP doubles at each increasing power of two boundary. This means that if b is a power of two, it is the correctly rounded conversion of d only if d is no more than one-half ULP above b or no more than one-quarter of that same (upper) ULP below b; here is the inequality:

-h/2 ≤ d – b ≤ h .

This is what it looks like:

Correct rounding when b is a power of two

We use the “≤” signs in the inequality because b is the correctly rounded result even if d = b – h/2 or d = b + h. This is because the significands of (normal) powers of two are zero.

Comparing Using Big Integers

To explain how the algorithm works, I will use this example: d = 1.7864e-45 and b = 0x1.465a72e467d88p-149 (the latter is expressed as a hexadecimal floating-point constant). Here’s how d and b are related:

1.7864 x 10^-45 In Relation to Its Binary Floating-Point Approximation, 0x1.465a72e467d88p-149

The diagram shows that b is the closest floating-point number to d — but how do we check that programmatically, using binary arithmetic? We need to apply the above test: |d – b| < h. (I know a priori this is not a special case — I wanted to keep my example simple.) But there’s a problem: how do we represent d? Answer: as a big integer. If we also represent b and h as big integers, such that they are proportional to d, we can apply the test given by the inequality.

I’ve broken the process into four steps:

Step 1: Represent the significant digits of d and b as integers

The first step is to represent d as an integer times a power of ten, and b as an integer times a power of two:

d = dInt x 10^dExp
b = bInt x 2^bExp

d was already put in this form when the floating point approximation b was computed (but for the purposes of the comparison, all digits of d are used, not just the first 16). b can be put in this form simply, by accessing its underlying floating-point representation: we “unnormalize” its significand into an integer by decreasing its power of two exponent. We represent the significant digits as a 53-bit integer, which means we subtract 52 from its power of two exponent.

For our example, d = 1.7864e-45 is represented as 17864 x 10^-49, and b = 0x1.465a72e467d88p-149, which in binary scientific notation is

1.0100011001011010011100101110010001100111110110001 x 2^-149 ,

is represented (in decimal numerals) as 5741268244528520 x 2^-201.

Step 2: Represent h as a power of two

Since bInt is 53-bit integer, u = 2^bExp, and h is half that: 2^bExp-1. For consistency in my discussion, I’ll substitute the variable hExp for bExp-1, giving

h = 2^hExp .

Step 3: Scale the inequality

To complete the conversion to integers, we need to get rid of any negative powers; we do this by scaling both sides of the inequality. Let’s look at the inequality again:

|d – b| < h .

Here are the three values as we expressed them above:

d = dInt x 10^dExp
b = bInt x 2^bExp
h = 2^hExp

For efficiency, the scaling process will factor out common powers of two from the three powers; to facilitate this, we rewrite 10^dExp as 2^dExp x 5^dExp; now we have

d = dInt x 2^dExp x 5^dExp
b = bInt x 2^bExp
h = 2^hExp

If any of the exponents dExp, bExp, or hExp are negative, we make them nonnegative by scaling. To reflect any scaling, let’s rename d, b, and h to dS, bS, and hS, respectively. The scaled inequality is now written

|dS – bS| < hS ,

and the initial values of dS, bS, and hS are

dS = dInt x 2^dExp x 5^dExp
bS = bInt x 2^bExp
hS = 2^hExp

To show how scaling works, let’s continue with our example above; here are the initial values of the variables:

dS = 17864 x 2^-49 x 5^-49
bS = 5741268244528520 x 2^-201
hS = 2^-202

In this example, all three exponents — dExp, bExp, and hExp — are negative; we scale the values with a common factor S that makes them all nonnegative. The least common factor that does this is S = 2²⁰² x 5⁴⁹; our variables then become

dS = 17864 x 2¹⁵³
bS = 5741268244528520 x 2¹ x 5⁴⁹
hS = 5⁴⁹

Multiplied out, these are

dS = 203970822259994138521801764465966248930731085529088
bS = 203970822259994122305215569213032722473144531250000
hS = 17763568394002504646778106689453125

Step 4: Apply the test

Now all we have to do is check the inequality, |dS – bS| < hS:

|dS – bS| = 16216586195252933526457586554279088, which is less than hS = 17763568394002504646778106689453125. This proves that b is the correct conversion of d.

(In the diagram for this example above, I’ve drawn the relationship of d and b proportionally: (dS – bS)/hS is approximately 0.91, which means that d is about 0.91h above b.)

Computing the Scaling Exponents In Code

In code, the scaling is done by operating on native integer variables representing the exponents of the powers of two and five in each of the three scaled values. After the exponents are created, common factors of two are removed to reduce the size of the resulting big integers. Here is how I coded it in C (this is essentially how it’s done in David Gay’s strtod() and Java’s FloatingDecimal class; I’ve renamed the variables and structured it a bit differently to make it clearer):

//Initialize scaling exponents
dS_Exp2 = 0;
dS_Exp5 = 0;
bS_Exp2 = 0;
bS_Exp5 = 0;
hS_Exp2 = 0;
hS_Exp5 = 0;

//Adjust for decimal exponent
if (dExp >= 0) {
   dS_Exp2 += dExp;
   dS_Exp5 += dExp;
   }
else {
   bS_Exp2 -= dExp;
   bS_Exp5 -= dExp;
   hS_Exp2 -= dExp;
   hS_Exp5 -= dExp;
   }

//Adjust for binary exponent
if (bExp >= 0) {
    bS_Exp2 += bExp;
   }
else {
   dS_Exp2 -= bExp;
   hS_Exp2 -= bExp;
   }

//Adjust for half ulp exponent
if (hExp >= 0) {
   hS_Exp2 += hExp;
   }
else {
   dS_Exp2 -= hExp;
   bS_Exp2 -= hExp;
   }

//Remove common power of two factor from all three scaled values
common_Exp2 = min(dS_Exp2, min(bS_Exp2, hS_Exp2));
dS_Exp2 -= common_Exp2;
bS_Exp2 -= common_Exp2;
hS_Exp2 -= common_Exp2;

Here is how the code executes for our example (I’ll show the state of the exponent variables after adjusting for each exponent):

//After initializing scaling exponents
dS_Exp2 = 0;
dS_Exp5 = 0;
bS_Exp2 = 0;
bS_Exp5 = 0;
hS_Exp2 = 0;
hS_Exp5 = 0;

//After adjusting for decimal exponent (dExp = -49)
dS_Exp2 = 0;
dS_Exp5 = 0;
bS_Exp2 = 49;
bS_Exp5 = 49;
hS_Exp2 = 49;
hS_Exp5 = 49;

//After adjusting for binary exponent (bExp = -201)
dS_Exp2 = 201;
dS_Exp5 = 0;
bS_Exp2 = 49;
bS_Exp5 = 49;
hS_Exp2 = 250;
hS_Exp5 = 49;

//After adjusting for half ulp exponent (hExp = -202)
dS_Exp2 = 403;
dS_Exp5 = 0;
bS_Exp2 = 251;
bS_Exp5 = 49;
hS_Exp2 = 250;
hS_Exp5 = 49;

//After removing common power of two factor of 2^250
dS_Exp2 = 153;
dS_Exp5 = 0;
bS_Exp2 = 1;
bS_Exp5 = 49;
hS_Exp2 = 0;
hS_Exp5 = 49;

After this code executes, the powers are multiplied out as big integers and used to create big integers dS, bS, and hS.

When d, b, and h are already integers

When all three exponents are nonnegative, d, b, and h start out as integer values. In this case, they are scaled down, by their common power of two factor.

Testing the Inequality In Code

In strtod(), the checking centers around a comparison of |d – b| (actually, |b – d|, which is equivalent) to h, which results in three outcomes: |d – b| < h, |d – b| = h, or |d – b| > h. The special cases are worked into the first two outcomes. (Java’s FloatingDecimal class does similar checks, but it is structured differently.)

Regarding the required check at a power of two boundary (comparing d – b to -h/2), strtod() scales d – b by two — to ensure that all values remain integers. This gives the equivalent comparison of 2(d – b) to -h. (In many cases, h is divisible by two; strtod() could just as easily divide h by two instead of multiplying d – b by two. Java’s FloatingDecimal class does the former.)

Adjusting b

strtod() makes theses checks in a loop, and adjusts b as necessary (that is beyond the scope of this article).

strtod()’s Optimization Called “Bigcomp”

strtod() has an optimization called “bigcomp”, which limits the big integer value of d to 40 decimal digits. For decimal inputs of 40 significant digits or less, all 40 are used for d; for decimal inputs greater than 40 digits, only the first 18 are used. Compensating for this truncation of d leads to a more complicated test procedure. (This optimization is on by default; you have to #define variable “NO_STRTOD_BIGCOMP” to turn it off.)

References

• David Gay’s dtoa.c (see the strtod() function).
• David Gay’s Technical Report “Correctly Rounded Binary-Decimal and Decimal-Binary Conversions”.
• William D. Clinger’s paper “How to Read Floating Point Numbers Accurately” (see ‘algorithmR’).
• FloatingDecimal.java (see the doubleValue() method).
• Python’s version of David Gay’s dtoa.c.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Using Integers to Check a Floating-Point Approximation

Overview of the Approximation Calculation

Conceptually, the approximation calculation involves two floating-point values: the significant digits of the decimal number, expressed as an integer, and a corresponding power of ten. For example, for the decimal string 163.118762e+109, the calculation is 163118762 x 10¹⁰³; for the decimal string 8.453127e-67, the calculation is 8453127 x 10^-73. If there are more than 16 significant digits, only the first 16 are used. The decimal string 6.2187331579177550499956283e+100, for example, would be treated as 6.218733157917755e+100, making the calculation 6218733157917755 x 10⁸⁵.

The powers of ten can be very small or very large. For double-precision floating-point (I’m considering normal numbers only), they range from 10^-323 (e.g., for DBL_MIN = 2.2250738585072014e-308) to 10³⁰⁸ (e.g., for 1e+308). The goal is to compute them efficiently.

Right-to-Left Binary Exponentiation

An efficient way to compute powers of ten is using right-to-left binary exponentiation. Conceptually, the process is this: given a power bⁿ to compute, write n as a sum of powers of two; then, using the laws of exponents, rewrite bⁿ as a product of b raised to each power of two. For example:

10¹⁰³ = 10^{1 + 2 + 4 + 32 + 64} = 10¹ * 10² * 10⁴ * 10³² * 10⁶⁴ .

Evaluating this expression requires only ten multiplications — six to compute the powers of ten 10² through 10⁶⁴ (by successive squaring), and four to multiply the five required powers together. If 10¹⁰³ were computed naively, it would require 102 multiplications.

As an example for computing negative exponents, consider

10^-73 = 10^{-(1 + 8 + 64)} = 10^-1 * 10^-8 * 10^-64 .

This requires eight multiplications — six to compute the powers of ten 10^-2 through 10^-64, and two to multiply the three required powers together. The naive calculation would do 72 multiplications.

Required Set of Powers

For the range of exponents of double-precision values, the required set of “binary powers” (powers of ten raised to powers of two) for right-to-left binary exponentiation are

• {10^-1, 10^-2, 10^-4, 10^-8, 10^-16, 10^-32, 10^-64, 10^-128, 10^-256} for negative exponents, and
• {10¹, 10², 10⁴, 10⁸, 10¹⁶, 10³², 10⁶⁴, 10¹²⁸, 10²⁵⁶} for positive exponents.

Instead of computing these powers for each conversion, they can be computed once and stored in a table. This reduces the number of multiplications further. In the case of our examples, 10¹⁰³ would now require only four multiplications, and 10^-73 would require only two.

The Approximation Calculation in strtod()

The approximation calculation in strtod() is based on the calculations I just described, but there are a few differences. The significant digits and power of ten are not built in two variables; one variable is initialized with the significant digits, and then the power of ten is factored in incrementally. This allows for a two-phased calculation: the first phase is a fast-path like calculation that handles any component power of ten between 10^-15 and 10¹⁵; the second phase uses binary exponentiation to finish the computation of the power of ten, for component binary powers 10^-16 and smaller and 10¹⁶ and greater.

In the first phase of the calculation, only positive powers of ten, 10¹ to 10¹⁵, are used. When negative powers of ten 10^-1 to 10^-15 are called for, the calculation is changed to the equivalent calculation that divides the significant digits by the corresponding positive power of ten. A separate table contains each of the powers of ten from 10¹ to 10¹⁵, which are looked up directly. The one division or multiplication replaces the up to three multiplications that might be needed for binary exponentiation (10¹ * 10² * 10⁴ * 10⁸). This not only is potentially more efficient, but reduces the number of possibly inexact operations (operations in which the result must be rounded).

Here are two examples: 163.118762e+109, which is parsed as 163118762 x 10¹⁰³, is calculated as 163118762 * 10⁷ * 10³² * 10⁶⁴; 8.453127e-67, which is parsed as 8453127 x 10^-73, is calculated as 8453127/10⁹ * 10^-64.

The Calculation In Code

I’ve taken strtod()‘s approximation code and distilled it into my own C program. The main difference between my code and strtod() is that strtod() handles overflow (for values near DBL_MAX) and underflow (for values that are near DBL_MIN or are subnormal). I’ve also renamed a few variables and made a few other small changes to make the code more readable.

double strtod_approx(char* decimal)
{
 int exponent, sign, i;
 long long sigDigits16;

 static const double fastPosTens[] = {
   1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
   1e10, 1e11, 1e12, 1e13, 1e14, 1e15};
 static const double binaryPosTens[] = {
   1e16, 1e32, 1e64, 1e128, 1e256};
 static const double binaryNegTens[] = {
   1e-16, 1e-32, 1e-64, 1e-128, 1e-256};

 double d;

 parseDecimalApprox(decimal,&sign,&sigDigits16,&exponent);

 d = sigDigits16;
 if (sign)
   d = -d;

 if (exponent > 0)
   {
    if (i = exponent & 0xF)
      d *= fastPosTens[i];
    if (exponent >>= 4)
      for(i = 0; exponent > 0; i++, exponent >>= 1)
        if (exponent & 1)
          d *= binaryPosTens[i];
   }
 else
   if (exponent < 0)
     {
      exponent = -exponent;
      if (i = exponent & 0xF)
        d /= fastPosTens[i];
      if (exponent >>= 4)
        for(i = 0; exponent > 0; i++, exponent >>= 1)
          if (exponent & 1)
            d *= binaryNegTens[i];
     }

 return d;
}

Notes

• This function calls an auxiliary function I wrote called parseDecimalApprox(), which I’ve not shown. It returns the sign of the number, the value of its first 16 significant digits, and its power of ten exponent.
• There are three tables of powers of ten, all precomputed at compile time:
  • fastPosTens: This holds the 15 exactly representable powers of ten needed for the first phase of the calculation (1e0 is not used — it’s just a placeholder).
  • binaryPosTens: This holds the five positive powers of ten used for binary exponentiation.
  • binaryNegTens: This holds the five negative powers of ten used for binary exponentiation.
• If the exponent is zero, no power of ten is factored in (it would be 10⁰ = 1).

Realized in code, you can see why the algorithm to compute the power of ten is called right-to-left binary exponentiation. Converting the exponent to a sum of powers of two is the same as converting it to binary; in code, the exponent is a binary integer. The bits of the exponent are accessed from right to left — least significant to most significant — using the right shift operator; a 1-bit means the corresponding power of two is part of the exponent. The exponent will be a maximum of 9 bits long.

Analysis

There are at most five floating-point multiplications and divisions in this calculation: three multiplications plus one multiplication or division for the worst case powers of ten, and one multiplication to combine the significant digits and the power of ten. If the significant digits start out inexact — either because they are truncated to 16 digits, or they are 16 digits (truncated or otherwise) but represent a value greater than 2⁵³ – 1 — that’s a maximum of six inexact operations.

Using my code above, I measured approximations as far as 10 ULPs off; 1.00431469722921494e-140 is one example. (This is consistent with my analysis of David Gay’s code, where the maximum difference I found was 11 ULPs. Why the difference? It could be due to the code that handles underflow and overflow, or it could be because I didn’t run the same exact tests in both cases.)

Contrast this with my quick and dirty decimal to floating-point conversion program, which does a multiplication or division for every digit. Using that program, I found an example that was 14 ULPs off.

Discussion

A Program That Converts Decimal Values Uses Decimal Values?

The code converts decimal numbers to floating-point, and yet it itself needs decimal numbers converted to floating-point — isn’t that circular? Not really. The compiler’s implementation would have to be different, or at least modified so that the decimal constants are specified in some other way — say as hexadecimal floating-point constants.

This raises another issue: what if the compiler converts these decimal literals incorrectly? After all, this is part of a larger conversion routine whose goal is correct conversion. My guess is that it does not matter. The worst that can happen is that the approximation will be a little less accurate; it will ultimately be corrected — by the arbitrary-precision based reconciliation process in strtod(). (For what it’s worth, I checked — Visual C++ got all of the conversions right.)

Java’s FloatingDecimal Class

The same approximation calculation is done in the doubleValue() method of Java’s FloatingDecimal Class, which is modeled on David Gay’s strtod().

Using Division For the Negative Exponent Case

For the negative exponent case of the binary exponentiation calculation, I tried using division (by positive powers of ten) instead of multiplication (by negative powers of ten). The division-based calculation ran a little slower, which was expected. But interestingly, the approximations were a little less accurate, on average. I don’t know why.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

strtod()’s Initial Decimal to Floating-Point Approximation

An Unnormalized Form of Decimal Scientific Notation

Any number can be expressed in decimal scientific notation, a form where it is written as a product of its significant digits and a power of ten. Conventionally, the significant digits are expressed in normalized form, where the first digit is between 1 and 9, and any subsequent digits follow a decimal point. For example, 0.0926 would be written as 9.26 x 10^-2, and 7390 would be written as 7.390 x 10³.

In the context of decimal to floating-point conversion, a nonstandard, unnormalized form of scientific notation is used, where the significant digits are written as an integer. For example, 0.0926 would be written as 926 x 10^-4, and 7390 would be written as 739 x 10¹.

In this unnormalized form, there are two cases: one where the integer containing the significant digits is multiplied by a nonnegative power of ten, and one where it’s multiplied by a negative power of ten. It’s convenient to think of the latter case as a fraction, where the significant digits integer is divided by the corresponding positive power of ten. For example, 926 x 10^-4 equals 926/10⁴. These two cases — multiplication or division of an integer by a power of ten that is an integer — form the basis of fast path conversion.

The Fast Path

For the fast path conversion process, we take a decimal number, represented as a string, and convert it to the nearest IEEE double-precision binary floating-point number. You can view this process as having two main steps. In the first step, floating-point integers s and p are created: s represents the significant digits of the decimal number (positive or negative), and p represents the corresponding nonnegative power of ten. In the second step, an IEEE floating-point multiplication or division (the fmul or fdiv instruction on Intel processors) operates on s and p, producing the desired double-precision result.

This process is guaranteed to work only when s and p are exactly representable in double-precision; this happens when their binary representations have no 1 bits beyond bit 53. The values of p that meet this criteria are 10⁰ ≤ p ≤ 10²². The values of s that meet this criteria are, by definition, all floating-point integers. (Think of it this way: Take any floating-point integer and print all the digits of its decimal equivalent — that would be a valid value for s. For example, 52882540679000003517910258026656900519026609372478984461456769024, which is the floating-point integer 0x1.0119c58f25bc6p+215.)

Practically speaking, there is no simple test to check all the valid values of s. But there is a simple test that identifies a subset of its values, 0 ≤ s ≤ 2⁵³ – 1 = 9,007,199,254,740,991. I will consider only these 2⁵³ values as fast path cases.

This process relies implicitly on two things — that base conversion between integers is exact, and that IEEE multiplication and division produce correctly rounded results. Under these conditions, a maximum of one rounding is done; the result is a correctly rounded decimal to floating-point conversion.

Regarding the power of ten, it can be looked up in a table, or it can be computed. If it’s computed — say naively by repeated multiplication by ten — it will be done exactly. Also, if p = 1, a further optimization applies — the multiplication can be skipped.

Examples

Here are some examples that qualify for fast path conversion:

Fast Path Cases In Disguise

There is another set of decimal numbers that can be transformed easily into fast path multiplication cases: numbers with a p greater than 10²² but with an s that can be multiplied by those excess powers of ten and still remain exact. For example, take the number 123e34. As written, it has s = 123 and p = 10³⁴; p is too big. However, if you treat it as 123000000000000e22, it qualifies as a fast path case. You transform it by multiplying s by 10¹² and by using a p that’s 12 orders of magnitude smaller. In other words, if you can transfer the extra powers of ten to the significant digits, you have a fast path case.

The Fast Path in David Gay’s strtod()

David Gay’s strtod() function implements a fast path for significant digits 0 ≤ s ≤ 10¹⁵ – 1 = 999,999,999,999,999 and powers of ten 10⁰ ≤ p ≤ 10²² (the powers of ten are precomputed and stored in a table). It also handles the “disguised” fast path cases, up to the same 15-digit limit.

Why is strtod()’s fast path limited to 15 digits? My guess is because that was the easiest check to make; all integers of 15 digits or less are exact. But what about the remaining fast path cases? At a minimum, we could easily allow any s up to 8,999,999,999,999,999 — an eightfold increase in the number of fast path cases. All we’d need to do is add a check for “number of digits = 16 and first digit ≤ 8.”

To cover the remaining cases, we could convert the entire 16-digit string to a double and then check whether its value is less than or equal to 2⁵³ – 1. The code currently converts the significant digits to a double anyhow, so why not use it for an additional fast path test? In fact, why not check the double value exclusively, skipping testing of the string altogether?

(I have a note out to Dave Gay asking him these questions; I’ll update this article if he responds. Update: Dave Gay agrees that the change to check for 16 digits/first digit ≤ 8 would work and would be simple enough, but he’s not sure if it is worth making.)

The Fast Path in Java’s FloatingDecimal Class

Java does its decimal to floating-point conversion in the doubleValue() method of its FloatingDecimal class. It is modeled on David Gay’s strtod(), and covers the exact set of fast path cases.

Discussion

Fast Path Vs. the Arbitrary-Precision Integer Algorithm

Fast path conversion is simple because most of the work is done in IEEE floating-point. Contrast this with the arbitrary-precision integer conversion algorithm, which

• Scales the fraction to make rounding of the significand easier.
• Normalizes the result.
• Encodes the result in IEEE floating-point format.

In IEEE floating-point, scaling is unnecessary; correct rounding is handled automatically. Also, there is no need for explicit normalization, nor any need to encode the result — it’s already encoded! Additionally, IEEE floating-point handles the edge case, where the significand would otherwise round up to 2⁵³.

The fast path reduces decimal to floating-point conversion to this: parsing of the decimal string, creation of two binary floating-point integers to represent it, and delegation of the hard work to a single floating-point instruction.

Processor Rounding Mode

Because the fast path algorithm uses IEEE arithmetic, it will be sensitive to the processor rounding mode. Typically, the rounding mode is set to round-to-nearest, but it could be set to one of three other modes. A conversion routine must ensure that both its fast path and arbitrary-precision path round the same way.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Fast Path Decimal to Floating-Point Conversion

Trailing Zeros Become “Significantly Insignificant”

10¹⁵ is the largest power of ten less than 2⁵³ – 1, the largest integer representable in 53 bits. 10¹⁵ has 50 bits, and the next larger power of ten, 10¹⁶, has 54 bits. So how can 10¹⁶ — and the 74-bit 10²² for that matter — have an exact double-precision representation, when doubles only store a 53-bit significand? The answer is simple: it has a binary representation with trailing zeros after bit 53.

A nonnegative power of ten 10ⁿ equals 5ⁿ * 2ⁿ; in binary, that’s a power of five followed by n zeros (a power of five always ends in ‘1’). For example, 10²² (10000000000000000000000) is

10000111100001100111100000110010011011101010110010010000000000000000000000

This is 5²² (2384185791015625), which is 52 bits long, followed by 22 zeros. Here it is in binary scientific notation, showing only its leading nonzero significant bits — the bits of its power of five factor:

1.000011110000110011110000011001001101110101011001001 x 2⁷³

Since this is 52 bits, it maps directly to a double — no rounding is required.

So what happened to the 22 significant trailing zeros? They were preserved in the exponent, as the factor 2²². (The remaining factor, 2⁵¹, undoes the normalization.)

Why 10²² Is the Maximum

To see why 10²² is the maximum exact power of ten, look at 10²³. Its power of five factor is 5²³ (11920928955078125), which is 54 bits long; this is too long for exact representation in a double.

10¹⁶ to 10²²

Here are the powers of ten from 10¹⁶ to 10²², shown in binary and in binary scientific notation (in the binary representation, bits 54 and beyond are highlighted):

On Binary Scientific Notation for Exact Integers

In decimal scientific notation, when trailing zeros are significant, they are displayed. For example, if you know a value to be exactly 300,000, you would write it as 3.00000 x 10⁵. In binary scientific notation, however, this convention is not followed. I don’t know if there’s an official explanation, but I have my own. Binary scientific notation is used to represent binary floating-point numbers, and binary floating-point numbers are, in general, approximations to decimal numbers. Displaying trailing zeros, which could be the result of rounding, might imply an exactness that’s not there. Also, binary floating-point numbers have a limited length significand; keeping the number of significant bits displayed within this limit makes the mapping clearer.

Other Large Numbers With Exact Representations

For the same reason, other large numbers — like 14¹⁸ (greater than 10²⁰), 6³³ (greater than 10²⁵), and 2¹⁰²³ (greater than 10³⁰⁷) — are exact as doubles. In fact, any integer with a power of two factor that takes it beyond 53 bits can be represented exactly (as long as the maximum exponent isn’t exceeded). In this case, a double can represent more than 53 significant bits!

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Why Powers of Ten Up to 10²² Are Exact As Doubles

Ratio of Big Integers (2¹¹⁹/10²⁰) Producing the 53-Bit Significand of 1e-20

Arbitrary-Precision is Needed

Our task is to write a computer program that uses binary arithmetic to convert a decimal number — represented as a character string in standard or scientific notation — into an IEEE double-precision binary floating-point number. What makes this task difficult is that a given decimal number may not have a double-precision equivalent; an approximation — the double-precision number closest to it — must be used in its place.

An IEEE double-precision binary floating-point number, or double, represents a number in binary scientific notation, with a 53-bit significand (subnormal numbers have less than 53 bits, but I won’t be discussing them) and an 11-bit power of two exponent. The limited precision of the significand is what makes approximation necessary. For example, a decimal fraction like 0.1 has an infinite binary representation, so it must be rounded to 53 significant bits. A large integer like 9007199254740997 has a binary representation that, although finite, is more than 53 bits long; it must also be rounded to 53 bits.

To round correctly, in general, you need to compute the approximation using more than 53 bits of precision; arbitrary-precision is required, an amount which depends on the input. An arbitrary-precision floating point or arbitrary-precision integer based algorithm could be used, but the algorithm I’ll discuss uses arbitrary-precision integers — AKA big integers. This makes for a more elegant solution.

Big Integer Based Algorithm

The big integer based algorithm I will show you is essentially AlgorithmM, as described in William D. Clinger’s paper “How to Read Floating Point Numbers Accurately.” He presents it in the programming language Scheme, but I will present it to you in words, and by example. (Like Clinger, I will deal only with positive, normal numbers.)

53-Bit Integer Significands

The significand of a normalized double-precision floating-point number is 53 bits, with its most significant bit equal to 1. For the purposes of our conversion algorithm, we’ll think of it as a 53-bit integer; that is, an integer between 2⁵² (4503599627370496) and 2⁵³ – 1 (9007199254740991).

Overview

The idea of the algorithm is to represent the decimal number as a fraction, one that produces a 53-bit integer quotient and an arbitrary-precision integer remainder. The significand is the quotient, rounded up or down according to the remainder; the power of two exponent is derived from the binary scale factor used to produce the fraction.

There are two basic cases the algorithm must handle: one where the fraction needs to be scaled up to produce a 53-bit quotient, and one where the fraction needs to be scaled down to produce a 53-bit quotient. I will demonstrate the algorithm with an example of each case.

Converting 3.14159 to Double-Precision

Here’s how to convert the decimal literal 3.14159 to double-precision floating-point:

1. Express as an integer times a power of ten

   3.14159 = 314159 x 10^-5

   In code: This step is done as the decimal string is parsed. The significant digits are collected (sans the decimal point) and then converted to binary as a big integer. The exponent of the power of ten is determined based on the correct placement of the decimal point. (For strings expressed in decimal scientific notation, the exponent must be converted to binary, and then adjusted for the decimal point accordingly.)

2. Express as a fraction

   The negative power of ten, 10^-5, makes this a fraction, with 314159 as the numerator and 10⁵ = 100000 as the denominator:

   314159/100000

   In code: The positive power of ten is computed as a big integer, raising ten to the absolute value of the exponent.

3. Scale into the range [2⁵²,2⁵³)

   314159/100000 is a number r, 2¹ ≤ r < 2². We need to scale it up, so that we have a scaled value r’ in the range 2⁵² ≤ r’ < 2⁵³; we do this by multiplying the numerator by 2⁵¹:

   314159 x 2⁵¹/100000 = 707423177667543826432/100000

   (We scale the numerator because we need the scaling done before the division, not after!)

   In code: You could use logarithms to compute the scale factor, but you’d have to use care. You would need arbitrary precision to properly distinguish values near powers of two. A simpler approach, in the spirit of sticking with integer arithmetic, is to use a loop: multiply the numerator by two until the quotient is in range. (For conversions where the quotient starts out above range, multiply the denominator by two until the quotient is in range.)

4. Divide and round

   707423177667543826432/100000 = 7074231776675438 remainder 26432

   The quotient is an integer q in the range 2⁵² ≤ q ≤ 2⁵³ – 1. The remainder is an integer r in the range 0 ≤ r < 100000, and it tells us which way to round q — up or down to the next integer, which we do according to IEEE 754 round-half-to-even rounding: if r is less than half the denominator, we round q down; if r is more than half the denominator, we round q up; if r equals half the denominator, we round q down if q is even, and round q up if q is odd. In our example, r is less than half the denominator, so q rounds down to 7074231776675438; this is our significand.

   (In the event that q rounds up to 2⁵³, set it to 2⁵² instead, and decrement the exponent of the scale factor.)

   In code: The remainder is easily calculated as r = numerator – q x denominator. For the “half the denominator” comparison, note that the denominator will either be 1 (for integers that start out in range and thus don’t need scaling) or divisible by 2: if it’s 1, there’s no remainder and no rounding; if it’s divisible by 2, then half the denominator is an integer, and the remainder can be compared to it with integer operations. For the test for evenness, just divide the quotient by two and check for a remainder of zero.

5. Express in normalized binary scientific notation

   For this step, it’s easiest to think in terms of binary. The significand, 7074231776675438, converts to

   11001001000011111100111110000000110111000011001101110

   This value is scaled, by 2⁵¹; we unscale it by multiplying it by 2^-51. Actually, we don’t multiply; we just express the number in unnormalized binary scientific notation:

   11001001000011111100111110000000110111000011001101110 x 2^-51

   To be represented in the double-precision format, the significand must be normalized; this means we must move the radix point 52 bits to the left, and multiply the resulting binary fraction by 2⁵². The unscaled and normalized value becomes:

   1.100100100001111110011111000000011011100001100110111 x 2^-51 x 2⁵²

   By the laws of exponents, 2^-51 x 2⁵² = 2¹, so our resulting double-precision value, in normalized binary scientific notation, is

   1.100100100001111110011111000000011011100001100110111 x 2¹

   In code: The code for this step is trivial: all we do is compute a power of two exponent, by adding 52 to the negative of the exponent of the scale factor.

6. Encode as a double

   Normalized binary scientific notation maps straightforwardly to the IEEE double-precision format; here are the values of the fields for our example, in decimal:

   • The sign field is 0, since the number is positive.
   • The exponent field is 1024, which equals the power of two exponent (1) plus the exponent bias (1023).
   • The fraction field is 2570632149304942, which is 7074231776675438 – 2⁵², the trailing 52 bits of the significand (the leading 1 bit is implicit).

   Here is the encoded double, in binary:

   0100000000001001001000011111100111110000000110111000011001101110

   The sign field is 0, the exponent field is 10000000000, and the fraction field is 1001001000011111100111110000000110111000011001101110.

   This double has the exact decimal value of

   3.14158999999999988261834005243144929409027099609375

   In code: In C, you can set these values directly by casting the double as a 64-bit integer and treating the fields as integer subfields within it.

Converting 1.2345678901234567e22 to Double-Precision

Here’s how to convert the decimal literal 1.2345678901234567e22 to double-precision floating-point:

1. Express as an integer times a power of ten

   1.2345678901234567e22 = 12345678901234567 x 10⁶

2. Express as a fraction

   The positive power of ten makes this an integer, but for the purposes of our algorithm, we still want to express it as a fraction; the numerator is 12345678901234567 x 10⁶ = 12345678901234567 x 1000000 = 12345678901234567000000, and the denominator is 1:

   12345678901234567000000/1

3. Scale into the range [2⁵²,2⁵³)

   12345678901234567000000/1 is a number r, 2⁷³ ≤ r < 2⁷⁴. We need to scale it down, so that we have a scaled value r’ in the range 2⁵² ≤ r’ < 2⁵³; we do this by multiplying the denominator by 2²¹:

   12345678901234567000000/2²¹ = 12345678901234567000000/2097152

4. Divide and round

   12345678901234567000000/2097152 = 5886878443352969 remainder 1355712

   The remainder is more than half the denominator, so the quotient — our significand — rounds up to 5886878443352970.

5. Express in normalized binary scientific notation

   In binary, 5886878443352970 is

   10100111010100001010110110010011100111011001110001010

   Unscaled, it is

   10100111010100001010110110010011100111011001110001010 x 2²¹

   Normalized, it is

   1.010011101010000101011011001001110011101100111000101 x 2²¹ x 2⁵²

   Simplified, it is the resulting double-precision value

   1.010011101010000101011011001001110011101100111000101 x 2⁷³

6. Encode as a double

   Here are the values of the fields for our example, in decimal:

   • The sign field is 0, since the number is positive.
   • The exponent field is 1096, which equals the power of two exponent (73) plus the exponent bias (1023).
   • The fraction field is 1383278815982474, which is 5886878443352970 – 2⁵².

   Here is the encoded double, in binary:

   0100010010000100111010100001010110110010011100111011001110001010

   The sign field is 0, the exponent field is 10001001000, and the fraction field is 0100111010100001010110110010011100111011001110001010.

   This double has the exact decimal value of

   12345678901234567741440

The Integers Get Huge

For very large and very small decimal numbers, the scaled fractions have very large numerators and denominators. For example, for DBL_MAX, which is defined as the decimal literal 1.7976931348623158e308, the algorithm produces this scaled fraction:

179769313486231580000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000/19958403095347198116563727130368385
660674512604354575415025472424372118918689640657849579654926357010893
424468441924952439724379883935936607391717982848314203200056729510856
765175377214443629871826533567445439239933308104551208703888888552684
480441575071209068757560416423584952303440099278848

(The numerator is 1.7976931348623158 x 10³⁰⁸; the denominator is 2⁹⁷¹. The quotient rounds to 9007199254740991, which in binary is 53 bits of 1s.)

Another example is DBL_MIN, which is defined as 2.2250738585072014e-308; it results in a fraction with even larger integers.

Handling Remaining Cases

The algorithm as presented only deals with positive, normal numbers. If you were to implement this according to the IEEE 754 specification, you’d have to handle zero, negative numbers, subnormal numbers, underflow, and overflow:

• To handle zero, check for it as a special case when parsing the input string.
• To handle negative numbers, treat the number as positive and then just negate the converted result.
• To handle subnormal numbers, reduce the precision of the significand — to between 1 and 52 bits — when scaling to 53 bits would take the power of two exponent into the subnormal range.
• To handle underflow, return zero when the result would be below the subnormal range.
• To handle overflow, return “infinity” when the result would be bigger than DBL_MAX.

Discussion

Big Integers vs. Big Floats

As I mentioned, correct conversion can be done using arbitrary-precision floating point arithmetic — AKA big floats. However, I think the big integer based algorithm is cleaner. Its main advantage comes from the “baselessness” of integers. You can work with them conceptually as decimal numbers, blissfully ignorant that they are implemented in binary — conversion of integers to and from binary is exact.

A big advantage of “baselessness” is in rounding. To round correctly, there must be enough precision to ensure the accuracy of the rounding bits — significant bit 54 and an arbitrary number of bits beyond. In the integer algorithm, the required precision comes automatically, through scaling. Each conversion gets the rounding precision it needs, as reflected in the integer remainder. And the calculation is simple: the remainder is compared to one-half of the denominator.

In a floating-point algorithm, precision needs to be set explicitly (either on a case-by-case basis, or once, covering the worst case). Also, the calculation is not as straightforward, requiring knowledge of the absolute location of the rounding bits. For example, consider 3.08984926168550152811e-32, a decimal number very nearly halfway between two floating-point numbers. The calculation a floating-point algorithm must make is to compare 2^-158 (one-half ULP) to 2^-158 + 2^-234 (the value of the 77 required rounding bits).

Sometimes Arbitrary-Precision Is Overkill

The algorithm I presented is simple and works for every case, but sometimes it is overkill. For many conversions, a simple IEEE double-precision floating-point calculation does the trick. For example, 3.14159 can be converted by this line of standard C code: double d = 314159.0/100000;. This works because both 314159 and 100000 are exactly representable in double-precision, and a standard IEEE floating-point multiplication is guaranteed to produce a correctly rounded result. (This is one optimization used in David Gay’s strtod().)

Arbitrary-precision is required for my second example though, since 12345678901234567 is not exactly representable in double-precision; double d = 12345678901234567.0*1000000; produces a result that is 1 ULP off.

(After publishing this I realized that the C statements above are processed by the compiler — constant folding. There’s no guarantee that the compiler will use floating-point division and multiplication instructions; it could use its own algorithms. My point is still valid though. In a real program, the two integer arguments will not be constants, so floating-point instructions will be used — at runtime.)

Implemented In a C++ Program

I implemented the big integer algorithm in a C++ program using GMP (MPIR). I validated it by comparing its results to David Gay’s strtod(). (I have used strtod() as a benchmark against which to compare other conversion routines; by writing this program, I’ve gotten a way to confirm that strtod() in fact produces correct results.)

Summary

I showed you a simple algorithm that uses binary integer arithmetic to convert a decimal string to an IEEE double-precision binary floating-point number. The algorithm starts by representing a decimal number as fraction, with a numerator and denominator that are arbitrary-precision integers. The fraction is scaled by a power of two — positive or negative — so that the integer part of the resulting quotient will contain exactly 53 bits. The 53-bit quotient is rounded to the nearest integer, unambiguously according to the value of the integer remainder. The rounded quotient — the 53 bits of the floating-point number — is unscaled and normalized by setting the power of two exponent of the floating-point number accordingly.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Correct Decimal To Floating-Point Using Big Integers

(Please post your own in the comments.)

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Binary Numbers Haiku

My presentation was based on base-ten-block-like imagery, since I knew the students were comfortable expressing numbers with base ten blocks. I thought extending the block model to other bases would work well. I think it did.

The Number Twenty-Seven in Tape Flags, Broken Into Powers of Two

Introduction

Before my presentation, I put twenty-seven tape flags on the whiteboard, in an unorganized fashion like this:

Twenty-Seven Objects

(I would have preferred to use magnets instead of tape flags, since they would have been easier to move and align; but I didn’t have twenty-seven identical magnets.)

I started my presentation by telling the class that I would teach them about something called binary numbers, but that first I would review the numbers they already know — decimal numbers (I took a moment to explain that this was not the same as “decimals”). The first thing we did was count the tape flags, and as we counted together I rearranged them into a line:

Twenty-Seven Objects, Arranged In a Line

I asked them how they would write that number. One student came up and wrote “27,” which is the first answer I expected. Other suggestions were Roman numerals (“XXVII”) and “twenty-seven,” also as I anticipated. One student suggested writing it in Japanese (I was expecting a foreign language, but Spanish: “veintisiete”). Some students suggested arithmetic expressions, like 20 + 7. One unexpected answer was from a girl who wrote it on the board in base ten blocks, which is how I was planning to rearrange the tape flags next!

I suggested tally marks as another alternative, and wrote twenty-seven in tally marks on the board.

Decimal

I singled-out the answer “27” and said it is written in place value. I reviewed how the places were powers of ten. Then, as the class counted along to twenty-seven, I rearranged the flags into base ten block powers of ten groups, under headings labeled “tens” and “ones”:

Twenty-Seven Objects, Broken Into Powers of Ten

We counted the powers of ten and wrote the totals in the blanks I drew below each grouping of blocks; we came up with the numeral “27”: two tens and seven ones.

Quinary

I told the class that place value is not limited to base ten. I said, for example, you could write any number in base five, or quinary. (I wanted to take an intermediate step to binary, which is the simplest base, having only a maximum of one instance of each power.) I had them compute the powers of five from one to 625, and I explained that these are the places in quinary. I told them we would group the flags into powers of five. I wrote three headings on the board: “twenty-fives,” “fives,” and “ones.”

I asked “are there any twenty-fives in twenty-seven” and they said “yes.” We then counted out twenty-five flags, which I removed from the decimal grouping we’d just done. I built a block as we went, under the twenty-five label. Next I asked if there were any more twenty-fives in the flags that remained, and they quickly said “no.” They could also see there were no fives, and that there were only two ones left, which I moved under the ones label.

Twenty-Seven Objects, Broken Into Powers of Five

We counted the powers of five and wrote them under each grouping of blocks, coming up with the numeral “102”: one twenty-five, zero fives, and two ones. Some kids wanted to pronounce this as “one-hundred and two”, but I told them you pronounce it as “twenty-seven,” or “one-zero-two base five.”

Binary

Now I said let’s look at another example of place value: base two, or binary. I said it is based on powers of two. We computed the powers of two from one to thirty-two (my son was rattling them off to 4096 before I could cut him off ), which they remembered from my last visit.

We proceeded as above, except we pulled out the powers of two (from the flags in the quinary grouping): first we looked for sixteens, then eights, then fours, then twos, and then ones.

Twenty-Seven Objects, Broken Into Powers of Two

We counted the powers of two and wrote them under each label, coming up with the numeral “11011”: one sixteen, one eight, zero fours, one two, and one one.

Number of Digits

When I was done with the tape flag examples, I took a moment to explain that base ten has ten digits, base five has five digits, and base two has two digits. As an example, I said that in base ten you could never have a 10 in any place, because that would be the same as a 1 in the next higher place. Similarly for base two, a 2 in a place would equal the next higher power of two, which also would be the same as a 1 in the next higher place.

Other Bases

I told the class that you could write any whole number in any base. One kid asked if I could do it in a base that was greater than ten (I forget which base he used as an example). I said any number could be the base, but you’d have to have enough symbols. I briefly explained why you wouldn’t want a multi-digit number in a place (it would make the numeral ambiguous). I mentioned base sixteen, and said it uses the letters A through F for the values ten through fifteen. (I did not intend to get into hexadecimal, but hey, I wanted to answer the question!)

Students as Binary Numbers

At the front of the classroom, just below the whiteboard, I arranged five chairs, facing the class. I wrote the names of the binary places above the chairs, left to right from the class’s point of view: sixteens, eights, fours, twos, ones. I got five volunteers to come up, and said that I would turn them into a binary number. I said if I told them to sit in their chair, they would count as a 0; if I told them to stand in front of their chair, they would count as a 1.

For my first example, I put the students in the pattern 11011, which the class correctly read as twenty-seven (they added the place values above the chairs of the standing students — that or they read the numerals I had left on the board under the tape flags ). I did a few other examples like this, which amounted to binary to decimal conversion. They got them all right.

Next I did what amounted to decimal to binary conversion, asking the class how to arrange the volunteers to represent a given number. For example, when I said “nine,” they called out instructions to make the volunteers stand and sit to make the pattern 1001. They got all of these examples correct as well.

Binary Counting

The above discussion took about twenty-five minutes, so with the extra five minutes I squeezed in a demonstration of a binary counter. I took a new set of five volunteers and had the class direct them through the sequence zero to thirty-one. We got through the count, but I think a few students got lost as some of the faster adders called out instructions. In any case, there were definitely some who understood the process, enough to know that when I asked them to display thirty-two, they said we would need another volunteer.

If I had more time, I would have done the count a second time, with the volunteers driving the counting; I came up with this scheme after I left the class:

• All volunteers start out sitting, representing zero.
• Whenever I say “count”
  • The ones place volunteer does the opposite of what she is currently doing: if she’s sitting, she stands; if she’s standing, she sits.
  • For everyone not in the ones place, if the kid to your left sits, you do the opposite of what you’re currently doing.

I think this would have made the counting easier and more fun.

Binary Fractions

I mentioned briefly that there is an equivalent of decimals in binary numbers. Instead of the tenths, hundredths, etc. places there are the halves, quarters, eighths, etc. places.

Discussion

I think most of the kids understood the presentation; certainly, they were all engaged. I’d like to think it gave them a better understanding of decimal, even if they didn’t understand the details of binary. I told them “you may not understand this now, but when you see it again someday, you’ll remember back to this day in third grade and it will come to you.” Someone then asked what grade they teach this in. I said it’s not really part of any particular math class (as far as I know) but that they would be taught it in a high-school computer class if they took one.

I used number words when I wanted to avoid decimal numerals; for example, when describing a number or when labeling places. Unfortunately, number words have decimal place value built-in, but that’s the closest I know how to get to a base-independent description of a number. That said, I don’t think the class recognized this, so I don’t think it caused any confusion.

I didn’t explain why we broke the numbers down by starting with the largest powers and working down. If I had more time, maybe I would have let them discover the algorithm themselves.

I use the term “number” when I really mean “numeral”, as in “binary number” or “decimal number.” This terminology is unfortunate, but it is standard.

References

• Rick Garlikov’s use of the Socratic method to teach binary numbers to third graders.

  I used a different approach, but a lot of the same concepts are involved. Rick’s method centered on binary counting, which lead to a discussion of powers and places. My method started with powers and places, and lead to binary numerals and then binary counting. Rick discussed other bases after discussing binary, whereas I discussed them before. Also, he discussed binary arithmetic, but I did not.

  One thing I liked about my approach is that I built in the concept of base conversion, showing the equivalence of whole numbers written in any base. I also liked the way I exhibited the concept of “number vs. numeration.”

• Computer Science Unplugged Page on Binary Numbers.

  This page contains videos on binary counting, which inspired my own binary counting demonstration.

• My article “How I Taught My Mother Binary Numbers.”

  I taught my mother a little differently (at least in my second attempt), mainly because I think most adults don’t think explicitly about place value.

Please Try This

I’d love to know if this method works for you; if you try it, please let me know!

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

How I Taught Third Graders Binary Numbers

The first 43 bits of pi and e

Binary Floating-Point Formats

In binary floating-point, infinitely precise values are rounded to finite precision. Here’s how rounding works in five different levels of precision:

• In half-precision, values are rounded to 11 significant bits.
• In single-precision, values are rounded to 24 significant bits.
• In double-precision, values are rounded to 53 significant bits.
• In extended-precision, values are rounded to 64 significant bits.
• In quadruple-precision, values are rounded to 113 significant bits.

The rounding rule used most often in practice is round-to-nearest, round-half-to-even; that’s the rule I will use. For pi and e, there are no “half to even” cases, since their binary expansions are infinite. This makes the rounding rule simple: if the rounding bit is 0, round down; if the rounding bit is 1, round up.

I will show the correctly rounded approximations of pi and e in these five formats.

Pi (π)

Here are the first 50 decimal digits of pi:

3.1415926535897932384626433832795028841971693993751…

Here are the first 128 bits of pi:

11.00100100001111110110101010001000100001011010001100001000110100
1100010011000110011000101000101110000000110111000001110011010001...

Here are the 128 bits again, with the rounding bit for each level of precision highlighted (bits 12, 25, 54, 65, and 114):

11.00100100001111110110101010001000100001011010001100001000110100
1100010011000110011000101000101110000000110111000001110011010001...

Here are the correctly rounded values of pi in each of the five levels of precision, shown in normalized binary scientific notation and as hexadecimal floating-point constants:

Half-Precision

pi = 1.1001001 x 21
   = 0x1.92p+1

This equals 3.140625 in decimal (all binary floating-point numbers have exact decimal representations), which approximates pi accurately to about 4 decimal digits.

(You can verify this conversion by hand, by adding the powers of two corresponding to the positions of the 1 bits: 11.001001 = 2¹ + 2⁰ + 2^-3 + 2^-6 = 3.140625.)

Single-Precision

pi = 1.10010010000111111011011 x 21
   = 0x1.921fb6p+1

This equals 3.1415927410125732421875, which approximates pi accurately to about 8 decimal digits.

Double-Precision

pi = 1.1001001000011111101101010100010001000010110100011 x 21
   = 0x1.921fb54442d18p+1

This equals 3.141592653589793115997963468544185161590576171875, which approximates pi accurately to about 16 decimal digits.

Extended-Precision

pi = 1.100100100001111110110101010001000100001011010001100001000110
     101 x 21
   = 0x1.921fb54442d1846ap+1

This equals

3.14159265358979323851280895940618620443274267017841339111328125

which approximates pi accurately to about 20 decimal digits.

Quadruple-Precision

pi = 1.100100100001111110110101010001000100001011010001100001000110
     1001100010011000110011000101000101110000000110111 x 21
   = 0x1.921fb54442d18469898cc51701b8p+1

This equals

3.141592653589793238462643383279502797479068098137295573004504331
874296718662975536062731407582759857177734375

which approximates pi accurately to about 35 decimal digits.

Euler’s Number (e)

Here are the first 50 decimal digits of e:

2.7182818284590452353602874713526624977572470936999…

Here are the first 128 bits of e:

10.10110111111000010101000101100010100010101110110100101010011010
1010111111011100010101100010000000100111001111010011110011110001...

Here are the 128 bits again, with the rounding bits for each level of precision highlighted:

10.10110111111000010101000101100010100010101110110100101010011010
1010111111011100010101100010000000100111001111010011110011110001...

Here are the correctly rounded values of e in each of the five levels of precision:

Half-Precision

e = 1.010111 x 21
  = 0x1.5cp+1

This equals 2.71875, which approximates e accurately to about 4 decimal digits.

Single-Precision

e = 1.010110111111000010101 x 21
  = 0x1.5bf0a8p+1

This equals 2.71828174591064453125, which approximates e accurately to about 8 decimal digits.

Double-Precision

e = 1.0101101111110000101010001011000101000101011101101001 x 21
  = 0x1.5bf0a8b145769p+1

This equals 2.718281828459045090795598298427648842334747314453125, which approximates e accurately to about 16 decimal digits.

Extended-Precision

e = 1.010110111111000010101000101100010100010101110110100101010011
    011 x 21
  = 0x1.5bf0a8b145769536p+1

This equals

2.71828182845904523542816810799394033892895095050334930419921875

which approximates e accurately to about 20 decimal digits.

Quadruple-Precision

e = 1.010110111111000010101000101100010100010101110110100101010011
    010101011111101110001010110001000000010011100111101 x 21
  = 0x1.5bf0a8b1457695355fb8ac404e7ap+1

This equals

2.718281828459045235360287471352662314358421867193548862669230860
32766716801933881697550532408058643341064453125

which approximates e accurately to about 34 decimal digits.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

Pi and e In Binary

1. Unconscious incompetence: You don’t know what you don’t know.
2. Conscious incompetence: You know what you don’t know.
3. Conscious competence: You know what you know.
4. Unconscious competence: You don’t know what you know.

I’ve applied this model to assess competence in binary floating-point arithmetic; let’s see where you stand:

$19.24 plus $6.95 equals $26.189999999999998; you are

1. Unconsciously incompetent when you think there’s a bug in your programming language.
2. Consciously incompetent when you realize that most decimal fractions are infinite in binary.
3. Consciously competent when you study and apply the principles discussed in “What Every Computer Scientist Should Know About Floating-Point Arithmetic.”
4. Unconsciously competent when you know to use decimal or integer arithmetic instead of binary floating-point.

By Rick Regan (Copyright © 2008-2012 Exploring Binary)

The Four Stages of Floating-Point Competence