\nSign
\nNegative<\/th>\n | Negative,
\nLess than -1<\/td>\n | Negative,
\nFractional<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\nPutting this all together, a 32-bit floating point looks like this:<\/p>\n s<\/span>eeeeeeee<\/span>bbbbbbbbbbbbbbbbbbbbbbb<\/span>\r\n 1 sign bit\r\n 8 exponent bits (Offset from -127)\r\n23 significand bits<\/pre>\nHowever, recall that every number in binary, except 0, starts with a “1”.\u00a0 This includes fractions, and any other number you can think of.\u00a0 We can exploit this by always assuming that the first digit is 1, and that the significand bits encode digits 2-24, giving us 24 bits of precision, even though we only have 23 significand bits.<\/p>\n To represent the number “0”, we leave both the exponent and significand empty.<\/p>\n So even though we can store very large or small numbers, we only have 24 bits to store the actual digits, which equates to about 7 digits in base 10.\u00a0 This is called the precision limit.<\/p>\n Here are some examples:<\/p>\n 0-00000000-00000000000000000000000 = 0\r\n0-01111111-00000000000000000000000 = 1.0 x 2^(127-127) = 1.0 x 2^1 = 1\r\n0-01111110-10000000000000000000000 = 1.1 x 2^(126-127) = 0.11b = 0.75\r\n1-10000100-00100000000000000000000 = -1.001 x 2^(132-127) = -1.125 x 32 = -36<\/pre>\n <\/p>\n <\/span>Inside the Computer<\/span><\/h2>\nFrom a program’s standpoint, there are three main components:<\/p>\n \n- The program itself<\/li>\n
- Data<\/li>\n
- CPU Registers (and other parts)<\/li>\n<\/ul>\n
A “register” is a temporary holding area inside the computer’s CPU.\u00a0 Like a tiny, digital, robotic arm, the program tells the register what data to grab, and what to do with it.<\/p>\n It’s been over 30 years since I’ve done any assembly programming, so I’ll discuss a “generic 32-bit CPU” without getting in to specific architectures and implementations.<\/p>\n Every assembly program consists of several types of instructions:<\/p>\n \n\n\n| Instruction<\/th>\n | Effect<\/th>\n<\/tr>\n | \n| LOAD<\/td>\n | Go get something from memory, and put it in a register.<\/td>\n<\/tr>\n | \n| STORE<\/td>\n | Take what’s in a register and put it in memory.<\/td>\n<\/tr>\n | \n| ADD<\/td>\n | Add some number (or a value in memory) to the value currently in one of the registers.<\/td>\n<\/tr>\n | \n| SUB<\/td>\n | Subtract some number (or a value in memory) to the value currently in one of the registers<\/td>\n<\/tr>\n | \n| MUL<\/td>\n | Multiply (etc…)<\/td>\n<\/tr>\n | \n| DIV<\/td>\n | Divide (etc…)<\/td>\n<\/tr>\n | \n| SHIFTL<\/td>\n | Shift Left.\u00a0 Move all the bits in a specified register, some positions to the left.\u00a0 This has the effect of multiplying by 2, and since most CPUs implement SHIFT in hardware, it’s a very fast operation.<\/td>\n<\/tr>\n | \n| SHIFTR<\/td>\n | Shift Right.\u00a0 Like left shift, right shift has the effect of dividing by 2.<\/td>\n<\/tr>\n | \n| INC, DEC<\/td>\n | Increment or decrement – add or subtract one to the value stored in one of the registers<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n There are also instructions such as JUMP that allow for flow control, and port manipulation via IN \/ OUT, but we can ignore these in our simple example.<\/p>\n Machine language is an all-numeric way to represent CPU instructions so that they can be stored as data.\u00a0 The computer reads program instruction bytes from memory, loads them in to the instruction register, and then the instruction register tells the other registers what to do based on instruction codes and other operands that are included with the instruction.<\/p>\n You can think of assembly as human-readable machine language.<\/p>\n When you compile something in a higher-level language like C, it takes your source code and turns it in to machine instructions, that we can then view as assembly.<\/p>\n You might write this in C:<\/p>\n int i=10, j=++i, k=i+j;\r\n\/* i==11, j==11, k==22 *\/<\/span><\/pre>\nIn assembly, it might look like this, after you compile it:<\/p>\n LOAD A $0x0A\r\nSTORE A 0xD001\r\nLOAD A 0xD001\r\nINC A\r\nSTORE A 0xD001\r\nSTORE A 0xD002\r\nLOAD A 0xD001\r\nADD A 0xD002\r\nSTORE A 0xD003<\/pre>\nOf course, compilers usually have optimizers that help avoid all of the back and forth silliness, but again, this is an example.<\/p>\n In the above, “A” is the CPU register – there may be as few as 2 “general purpose” registers, while most have at least 4.<\/p>\n We have notation for constants, such as 0x0A, which would be interpreted as the 32-bit value, 0x0000000A (0x means “hex”).<\/p>\n We also use direct notation, such as 0xD001 that specifies a memory address that the CPU’s register reads or writes.\u00a0 For simplicity, we can skip indirect notation, which acts like a pointer.<\/p>\n Once we throw the code above through an optimizer, it might look like this:<\/p>\n LOAD A $0x0A\r\nSTORE A 0xD001\r\nINC A\r\nSTORE A 0xD001\r\nSTORE A 0xD002\r\nADD A 0xD002\r\nSTORE A 0xD003<\/pre>\nWhen we load our program in to memory, the computer might look something like the table below.\u00a0 Keep in mind that the program basically shares the same memory as data, and there are pointers that point to different sections of memory for different purposes, but again, this is simplified.<\/p>\n Also, remember that “LOAD A $0x0A” might be 0x0A01DD00 in machine language, but we’re viewing this in human-readable assembly…<\/p>\n \n\n\n| <\/td>\n | Program<\/th>\n | <\/td>\n | <\/td>\n | Registers<\/th>\n | <\/td>\n | <\/td>\n | Data<\/th>\n<\/tr>\n | \n| 0x0100<\/span><\/td>\n | LOAD A $0x0A<\/span><\/td>\n | <\/td>\n | A<\/td>\n | <\/td>\n | <\/td>\n | 0xD000<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0101<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | B<\/td>\n | <\/td>\n | <\/td>\n | 0xD001<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0102<\/td>\n | INC A<\/td>\n | <\/td>\n | C<\/td>\n | <\/td>\n | <\/td>\n | 0xD002<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0103<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | D<\/td>\n | <\/td>\n | <\/td>\n | 0xD003<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0104<\/td>\n | STORE A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | 0xD004<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0105<\/td>\n | ADD A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | …<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0106<\/td>\n | STORE A 0xD003<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0107<\/td>\n | STOP<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| …<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n The CPU reads each instruction, which tells a specific register what to do next.<\/p>\n After the first instruction, our computer looks like this:<\/p>\n \n\n\n| <\/td>\n | Program<\/th>\n | <\/td>\n | <\/td>\n | Registers<\/th>\n | <\/td>\n | <\/td>\n | Data<\/th>\n<\/tr>\n | \n| 0x0100<\/td>\n | LOAD A $0x0A<\/td>\n | <\/td>\n | A<\/td>\n | 0x0000000A<\/span><\/td>\n | <\/td>\n | 0xD000<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0101<\/span><\/td>\n | STORE A 0xD001<\/span><\/td>\n | <\/td>\n | B<\/td>\n | <\/td>\n | <\/td>\n | 0xD001<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0102<\/td>\n | INC A<\/td>\n | <\/td>\n | C<\/td>\n | <\/td>\n | <\/td>\n | 0xD002<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0103<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | D<\/td>\n | <\/td>\n | <\/td>\n | 0xD003<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0104<\/td>\n | STORE A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | 0xD004<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0105<\/td>\n | ADD A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | …<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0106<\/td>\n | STORE A 0xD003<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0107<\/td>\n | STOP<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| …<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n As our program progresses, we move data in and out of the A register, and memory locations that represent our C variables.<\/p>\n \n\n\n| <\/td>\n | Program<\/th>\n | <\/td>\n | <\/td>\n | Registers<\/th>\n | <\/td>\n | <\/td>\n | Data<\/th>\n<\/tr>\n | \n| 0x0100<\/td>\n | LOAD A $0x0A<\/td>\n | <\/td>\n | A<\/td>\n | 0x0000000B<\/span><\/td>\n | <\/td>\n | 0xD000<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0101<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | B<\/td>\n | <\/td>\n | <\/td>\n | 0xD001<\/td>\n | 0x0000000B<\/span><\/td>\n<\/tr>\n\n| 0x0102<\/td>\n | INC A<\/td>\n | <\/td>\n | C<\/td>\n | <\/td>\n | <\/td>\n | 0xD002<\/td>\n | 0x0000000B<\/span><\/td>\n<\/tr>\n\n| 0x0103<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | D<\/td>\n | <\/td>\n | <\/td>\n | 0xD003<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0104<\/td>\n | STORE A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | 0xD004<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0105<\/span><\/td>\n | ADD A 0xD002<\/span><\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | …<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0106<\/td>\n | STORE A 0xD003<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0107<\/td>\n | STOP<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| …<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n At its final state, we add “i” and “j”, and store the result as “k”.\u00a0 Remembering that program is data and vice-versa, the last instruction, STOP, tells the CPU to stop executing instructions, so that it doesn’t start executing data!<\/p>\n \n\n\n| <\/td>\n | Program<\/th>\n | <\/td>\n | <\/td>\n | Registers<\/th>\n | <\/td>\n | <\/td>\n | Data<\/th>\n<\/tr>\n | \n| 0x0100<\/td>\n | LOAD A $0x0A<\/td>\n | <\/td>\n | A<\/td>\n | 0x00000016<\/span><\/td>\n | <\/td>\n | 0xD000<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0101<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | B<\/td>\n | <\/td>\n | <\/td>\n | 0xD001<\/td>\n | 0x0000000B<\/span><\/td>\n<\/tr>\n\n| 0x0102<\/td>\n | INC A<\/td>\n | <\/td>\n | C<\/td>\n | <\/td>\n | <\/td>\n | 0xD002<\/td>\n | 0x0000000B<\/span><\/td>\n<\/tr>\n\n| 0x0103<\/td>\n | STORE A 0xD001<\/td>\n | <\/td>\n | D<\/td>\n | <\/td>\n | <\/td>\n | 0xD003<\/td>\n | 0x00000016<\/span><\/td>\n<\/tr>\n\n| 0x0104<\/td>\n | STORE A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | 0xD004<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0105<\/td>\n | ADD A 0xD002<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | …<\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0106<\/td>\n | STORE A 0xD003<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| 0x0107<\/span><\/td>\n | STOP<\/span><\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n | \n| …<\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n | <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Although this is a very simplified model, we can see what happens when we perform math operations on integers.<\/p>\n <\/p>\n <\/span>Integer Math<\/span><\/h2>\nInteger math instructions look like this:<\/p>\n \n- Go get something<\/li>\n
- Do something with it<\/li>\n
- Store the result in a register<\/li>\n<\/ol>\n
From the CPU’s perspective, even though this is a single programming instruction, there are 3 steps, and thus it might take up to 3 CPU cycles to execute one instruction.<\/p>\n Simple operations like addition are usually built right in to the register so that they only take one CPU cycle.<\/p>\n Integer multiplication might take 1 or 2 extra CPU cycles, even when using purpose-specific hardware.\u00a0 Multiplication is a combination of addition and bit shifting.<\/p>\n For example, to multiply 0b0101 (5) by 0b1011 (11), we would LOAD A $0x05, and then MUL A “x”, where x is some memory location.<\/p>\n Without<\/strong><\/em> a dedicated multiplier, assuming we already have 5 in the A register, here is what the CPU might do behind the scenes when we ask it to MUL A “x”:<\/p>\n\n- Go read memory location x (value 11)<\/li>\n
- Multiply by A (value 5)\n
\n- Set C to 0<\/li>\n
- Loop from 0 to 7 (We’ll call this “S”)\n
\n- If x AND 1\n
\n- Store A (value 5) in B<\/li>\n
- Shift B left by S<\/li>\n
- Add B to C and store in C<\/li>\n<\/ol>\n<\/li>\n
- Shift x right by 1<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\n
- Store C (value 55) in A<\/li>\n<\/ol>\n
By my count, that’s 33 CPU cycles for a single instruction!<\/p>\n Modern CPUs have hardware multipliers that perform this entire process as 1 or 2 instructions, so the microcode might look like this:<\/p>\n \n- Go read memory location x (value 11)<\/li>\n
- Send A to the multiplier<\/li>\n
- Send x to the multiplier<\/li>\n
- Read a result from the multiplier, and store in A<\/li>\n<\/ol>\n
Here is what an 8-bit hardware “Lattice” multiplier looks like:<\/p>\n ![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Floating-Points-Figures-1v2.png\") <\/p>\n
Here is how it works:<\/p>\n \n- As the first value is loaded, it populates the lattice, where each row is offset by one position (multiplied by 2).<\/li>\n
- As the second value is loaded, any “zero” bits disable rows in the lattice using AND<\/li>\n
- The remaining rows in each column of the lattice are then added to obtain two 8-bit result fields.<\/li>\n
- The low byte and high byte are fed in to the result register, which can then be read by the CPU.<\/li>\n<\/ol>\n
In this example, although it takes 3 steps write to and read from the multiplier, the multiplication itself is handled instantaneously.<\/p>\n <\/p>\n <\/span>Floating Point Math<\/span><\/h2>\nIf you recall, a floating point number is like two numbers stored as one:<\/p>\n n = s * 2^b<\/pre>\nSo, although you can absolutely load or store a floating point just like any other number, math isn’t so straightforward.<\/p>\n Let’s assume we have two floats, n and m.\u00a0 The first step is to decode the sign, exponent, and significand:<\/p>\n \n\n\n| <\/td>\n | m<\/th>\n | n<\/th>\n<\/tr>\n | \nRaw number:<\/strong><\/td>\n| 174,587.904<\/span><\/td>\n | 0.30690625<\/span><\/td>\n<\/tr>\n\nBinary:<\/strong><\/td>\n| 101010100111111011.11100111011<\/span><\/td>\n | 0.01001110100<\/span><\/td>\n<\/tr>\n\nSignificand
\nand Exponent:<\/strong><\/td>\ns = 1.01010100111111011111001<\/span>
\ne = 10001<\/span><\/td>\n | s = 1.001110100<\/span>
\ne = -10<\/span><\/td>\n<\/tr>\n\nEncoded:<\/strong><\/td>\n0-10010000-<\/span>
\n01010100111111011111001<\/span><\/td>\n | 0-10000001-<\/span>
\n00111010000000000000000<\/span><\/td>\n<\/tr>\n\nBase 10:<\/strong><\/td>\n| 1.3319998979568 x 2^17<\/span><\/td>\n | 1.227625 x 2^(-2)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Remember the special case of zero:<\/p>\n If e=0 (after shift) and s=0 then the value is 0.\u00a0 For our example, this is not the case, but the CPU still has to deal with checking for a zero and other special values, which takes time.<\/p>\n Floating point multiplication is actually easier than addition:<\/p>\n \n\n\n| Step<\/th>\n | Result<\/th>\n<\/tr>\n | \n| 1. Multiply ms * ns<\/td>\n | 1.3319998979568<\/span> x 1.227625<\/span>\u00a0=
\n1.6351963747292166<\/span><\/td>\n<\/tr>\n\n2. While result > 2,
\ndivide by 2, add 1 to me<\/td>\n | (n\/a)<\/td>\n<\/tr>\n | \n| 3. Add me + ne<\/td>\n | 17<\/span> + (-2<\/span>) =
\n15<\/span><\/td>\n<\/tr>\n\n| 4. Re-encode the result<\/td>\n | s = 1.6351963747292166<\/span>
\ne = 15<\/span><\/td>\n<\/tr>\n\n| (In decimal)<\/td>\n | 53,582.11328125<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n This seems complicated, but addition is even more so:<\/p>\n \n\n\n| Step<\/th>\n | Result<\/th>\n<\/tr>\n | \n1. If n>m then swap n,m
\n(Ensure n<m)
\n1.a. Compare exponents
\n1.b. If exponents are equal,
\ncompare significands<\/td>\n | No swap required<\/td>\n<\/tr>\n | \n| 2. Subtract ne-me = ee<\/td>\n | -2<\/span> – 17<\/span> = -19<\/span><\/td>\n<\/tr>\n\n3. Left shift ns by ee
\n(Note that a negative left
\nshift is a right shift)<\/td>\n | 1.227625<\/span> << -19<\/span> =
\n0.00000234150886536<\/span><\/td>\n<\/tr>\n\n| 4. Add ns to ms = ss<\/td>\n | 1.3319998979568<\/span> + 0.00000234150886536<\/span>\u00a0=
\n1.33200223946<\/span><\/td>\n<\/tr>\n\n5. While result >2,
\ndivide by 2, add 1 to me<\/td>\n | n\/a<\/td>\n<\/tr>\n | \n| 6. Re-encode the result<\/td>\n | s = 1.33200223946<\/span>
\n<\/span>e = 17<\/span><\/td>\n<\/tr>\n\n| (In decimal)<\/td>\n | 174,588.19753<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Just as integer multiplication would chew up CPU cycles without special hardware, most modern CPUs have floating point hardware (called a Floating Point Unit) that is dedicated to floating point math and manipulation.<\/p>\n <\/p>\n <\/p>\n <\/span>Comparing Floats to Ints<\/span><\/h2>\nThe point of demonstrating all of this complexity is to show all of the extra work that has to be done to support floating point numbers, compared to integers.<\/p>\n We’ve looked at the internal CPU process, and it’s easy to see why floats are slower than ints:<\/p>\n \n\n\n| Floating Point<\/th>\n | Integer<\/th>\n<\/tr>\n | \n| Special cases include zero, infinity, and infinitesimal, that all require extra handling steps.<\/td>\n | Integers have no special cases.<\/td>\n<\/tr>\n | \n| Each floating point consists of two numbers, each pair requiring separate manipulation and normalization steps.<\/td>\n | All integers are a single component.<\/td>\n<\/tr>\n | \n| Floating point arithmetic, even if implemented in hardware, requires a discreet set of steps that can be computationally-expensive.<\/td>\n | Integer arithmetic, if implemented in hardware, only requires 1 or 2 steps.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n What all of this means is that the CPU has to work harder during floating-point operations compared to integer operations:<\/p>\n | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |