This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
pdclib:floatingpoint [2019/10/02 11:24] solar [Dragon 4 and Grisu 3] |
pdclib:floatingpoint [2019/10/21 10:13] (current) solar [Floating-Point Printout] |
||
---|---|---|---|
Line 9: | Line 9: | ||
==== Decimal Notation ==== | ==== Decimal Notation ==== | ||
- | [[https:// | + | [[https:// |
^ Digit ^ 1 ^ 2 ^ 3 ^ . ^ 4 ^ | ^ Digit ^ 1 ^ 2 ^ 3 ^ . ^ 4 ^ | ||
- | ^ Value | %%10^2%% | %%10^1%% | %%10^0%% | | %%10^-1%% | | + | ^ Value | <m>*10^2</m> (100) | <m>*10^1</m> (20) | <m>*10^0</m> (3) | | <m>*10^-1</m> (0.4) | |
==== Scientific Notation ==== | ==== Scientific Notation ==== | ||
- | Decimal notation gets more and more unwieldy the further your significant digits are away from the decimal point -- very large, or very small numbers. For these, you would use [[https:// | + | Decimal notation gets more and more unwieldy the further your significant digits are away from the decimal point -- very large, or very small numbers. For these, you would use [[https:// |
- | The '' | + | The <m> |
- | Let's return to our number | + | Let's return to our number |
- | Increment or decrement the exponent to shift the decimal point of the significand one digit to the left or the right, respectively. So we could also write '' | + | Increment or decrement the exponent to shift the decimal point of the significand one digit to the left or the right, respectively. So we could also write <m>12.34*10^1</m>, < |
- | This allows us to write very large numbers, like '' | + | This allows us to write very large numbers like <m>1.234*10^78</m>, or very small numbers like <m>1.234*10^-34</ |
==== Normalized Number ==== | ==== Normalized Number ==== | ||
Line 36: | Line 36: | ||
==== Binary Encoding ==== | ==== Binary Encoding ==== | ||
- | First thing, the //base// used by a computer is '' | + | First thing, the //base// used by a computer is (usually) |
One bit is used as //sign bit// for the mantissa (i.e. whether the whole number is positive or negative). | One bit is used as //sign bit// for the mantissa (i.e. whether the whole number is positive or negative). | ||
Line 46: | Line 46: | ||
=== Sign === | === Sign === | ||
- | '' | + | Unset indicates positive, |
=== Mantissa === | === Mantissa === | ||
- | The mantissa is assumed to be // | + | The mantissa is assumed to be // |
- | Most people who read thus far can probably rattle down the values for // | + | Most people who read thus far can probably rattle down the values for // |
=== Exponent === | === Exponent === | ||
- | The exponent is a funny bugger. IEEE 754 defines the exponent as an absolute (positive) offset to a (negative) bias. That bias is calculated as '' | + | The exponent is a funny bugger. IEEE 754 defines the exponent as an absolute (positive) offset to a (negative) bias. That bias is calculated as <m>1-2^(bits-1)</m>. "All bits clear" and "all bits set" are reserved (we will come to this later), so the smallest meaningful exponent is 1. |
- | For our 3-bit exponent, we get a bias of '' | + | For our 3-bit exponent, we get a bias of <m>1-2^2 = -3</m>, with a practical range of <m>-2..3</m>: |
^ Exponent ^ Value ^ | ^ Exponent ^ Value ^ | ||
Line 90: | Line 90: | ||
=== Denormalized Numbers === | === Denormalized Numbers === | ||
- | When all exponent bits are cleared, the mantissa is considered to be [[https:// | + | When all exponent bits are cleared, the mantissa is considered to be [[https:// |
In other words, the smallest representable exponent (with only the lowest bit set) is applied, //with the usually implied pre-fractional bit unset//. The purpose, here, is to allow a bit of additional precision in the very smallest numbers presentable. | In other words, the smallest representable exponent (with only the lowest bit set) is applied, //with the usually implied pre-fractional bit unset//. The purpose, here, is to allow a bit of additional precision in the very smallest numbers presentable. | ||
Line 97: | Line 97: | ||
^ Exponent ^ Mantissa (stored) ^ Mantissa (implied) ^ Value ^ | ^ Exponent ^ Mantissa (stored) ^ Mantissa (implied) ^ Value ^ | ||
- | | 001 | 11 | 1.11 | + | | 001 | 11 | 1.11 |
- | | 001 | 10 | 1.10 | + | | 001 | 10 | 1.10 |
- | | 001 | 01 | 1.01 | + | | 001 | 01 | 1.01 |
- | | 001 | 00 | 1.00 | + | | 001 | 00 | 1.00 |
- | | 000 | 11 | **0**.11 | + | | 000 | 11 | **0**.11 |
- | | 000 | 10 | **0**.10 | + | | 000 | 10 | **0**.10 |
- | | 000 | 01 | **0**.01 | + | | 000 | 01 | **0**.01 |
| 000 | 00 | **0**.00 | | 000 | 00 | **0**.00 | ||
Line 152: | Line 152: | ||
(Thanks to [[https:// | (Thanks to [[https:// | ||
+ | |||
+ | ===== Dragon ===== | ||
+ | |||
+ | Steele & White approach the presentation of their Dragon algorithm as a series of " | ||
+ | |||
+ | ==== Fixed Point Fraction Output ==== | ||
+ | |||
+ | Given: | ||
+ | |||
+ | * A positive value //f// less than 1, with //n// digits to (input) base //b// (usually 2). | ||
+ | |||
+ | Output: | ||
+ | |||
+ | * A value //F// of //N// digits to (output) base //B// (usually 10). | ||
+ | |||
+ | Such that: | ||
+ | |||
+ | - < | ||
+ | * The difference between representations is less than half the positional value of the //n//th digit of //f//. | ||
+ | - < | ||
+ | - < | ||
+ | * The difference between representations is no more than half the positional value of the //N//th digit of //F//. | ||
+ | - Each digit of //F// is output before the next is generated; no "back up" for corrections. | ||
+ | |||
+ | Algorithm < | ||
+ | |||
+ | * <m>k = 0, R = f, M = { b ^ { -n } / 2 }</m> | ||
+ | * while ( 1 ) | ||
+ | * k++ | ||
+ | * U = floor( R * B ) | ||
+ | * R = ( R * B ) % 1 | ||
+ | * M *= B | ||
+ | * if ( <m>R >= M AND <= 1 - M</m> ) | ||
+ | * append( F, U ) | ||
+ | * else | ||
+ | * break | ||
+ | * if ( <m>R <= 1/ | ||
+ | * append( F, U ) | ||
+ | * if ( <m>R >= 1/ | ||
+ | * append( F, U + 1 ) | ||
+ | |||
+ | At the end, < | ||
+ | |||
+ | Example: | ||
+ | |||
+ | * Given the base <m>b = 2</m> number <m>f = .10110</ | ||
+ | * The //exact// decimal representation would be < | ||
+ | * The next higher number (< | ||
+ | * The next lower number (< | ||
+ | * The Mask would be <m>M = { b ^ {-n} } / 2 = { 2 ^ { -5 } } / 2 = 0.015625</ | ||
+ | |||
+ | * First (<m>k = 1</ | ||
+ | * multiply <m>R = 0.6835</ | ||
+ | * multiply <m>M = 0.015625</ | ||
+ | * Fractional part < | ||
+ | * Second (<m>k = 2</ | ||
+ | * multiply <m>R = 0.835</ | ||
+ | * multiply <m>M = 0.15625</ | ||
+ | * Fractional part < | ||
+ | * Post-loop | ||
+ | * Fractional part < | ||
+ | * We have <m>N = k = 2</m> fractional digits in our result of < | ||
+ | |||
+ | ==== Floating-Point Printout ==== | ||
+ | |||
+ | Given: | ||
+ | |||
+ | * A base //b// floating-point number <m>v = f * b ^ (e - p)</ | ||
+ | |||
+ | Output: | ||
+ | |||
+ | * An approximate representation to base //B//, using exponential notation if the value is very large or very small. | ||
+ | |||
+ | Algorithm (Dragon2): | ||
+ | |||
+ | * Compute <m>v prime = v * B ^ {-x}</ | ||
+ | * Print the integer part of <m>v prime</ | ||
+ | * Print a decimal point | ||
+ | * Take the fractional part of <m>v prime</ | ||
+ | * Apply algorithm < | ||
+ | * If < |