Differences

This shows you the differences between two versions of the page.

--- pdclib:floatingpoint [2019/10/09 10:36]
solar [Fixed Point]
+++ pdclib:floatingpoint [2019/10/18 14:40]
solar [Fixed Point Fraction Output]
@@ Line 157: / Line 157: @@
 Steele & White approach the presentation of their Dragon algorithm as a series of "lesser" algorithms building on each other.
-==== Fixed Point ====
+==== Fixed Point Fraction Output ====
 Given:
@@ Line 165: / Line 165: @@
 Output:
-  * A value //F// of //N// digits to base //B// (usually 10).
+  * A value //F// of //N// digits to (output) base //B// (usually 10).
 Such that:
   - <m>delim{|}{F - f}{|} < { b^{-n} } / 2</m>
+    * The difference between representations is less than half the positional value of the //n//th digit of //f//.
   - <m>N</m> is the smallest number of digits so that 1. can be true.
-  - <m>delim{|}{F - f}{|} <= { B^{-n} } / 2</m>
+  - <m>delim{|}{F - f}{|} <= { B^{-N} } / 2</m>
+    * 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>(FP)^3</m> (Finite-Precision Fixed-Point Fraction Printout):
+  * <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/2</m> )
+    * append( F, U )
+  * if ( <m>R >= 1/2</m> )
+    * append( F, U + 1 )
+At the end, <m>k</m> is <m>N</m>, i.e. the number of digits in <m>F</m>.
+Example:
+  * Given the base <m>b = 2</m> number <m>f = .10110</m>, with <m>n = 5</m>, to be converted to base <m>B = 10</m>
+  * The //exact// decimal representation would be <m>.6835</m>
+    * The next higher number (<m>f_{+1} = .10111</m>) would be decimal <m>0.71475</m>
+    * The next lower number (<m>f_{-1} = .10101</m>) would be decimal <m>0.65225</m>
+  * The Mask would be <m>M = { b ^ {-n} } / 2 = { 2 ^ { -5 } } / 2 = 0.015625</m>
+  * First (<m>k = 1</m>) loop
+    * multiply <m>R = 0.6835</m> by <m>B = 10</m> for integral part <m>6</m>, fractional part <m>0.835</m>
+    * multiply <m>M = 0.015625</m> by <m>B = 10</m> for new <m>M = 0.15625</m>
+    * Fractional part <m>0.835</m> is larger than mask <m>0.15625</m>, and smaller than <m>1 - 0.15625 = 0.84375</m>, so <m>6</m> is our first (fractional) digit, and the loop continues
+  * Second (<m>k = 2</m>) loop
+    * multiply <m>R = 0.835</m> by <m>B = 10</m> for integral part <m>8</m>, fractional part <m>0.35</m>
+    * multiply <m>M = 0.15625</m> by <m>B = 10</m> for new <m>M = 1.5625</m>
+    * Fractional part <m>.35</m> is smaller than mask <m>1.5625</m>, and not smaller than <m>1 - 1.5625 = -0.5625</m>, so the loop terminates
+  * Post-loop
+    * Fractional part <m>.35</m> is smaller than <m>1/2</m>, so <m>8</m> is our next fractional digit
+    * We have <m>N = k = 2</m> fractional digits in our result of <m>0.68</m>, which is the smallest <m>N</m> that uniquely identifies our original <m>f = .10110</m>
+==== Floating-Point Printout ====
+Given:
+  * A base //b// floating-point number <m>v = f * b ^ (e - p)</m>, where //e//, //f//, and //p// are integers with <m>p >= 0</m> and <m>0 <= f < b ^ p</m>.
+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}</m>, where <m>x</m> is chosen so that the result either is between 1 / //B// and 1, or between 1 and //B//
+   * Print the integer part of <m>v prime</m>
+   * Print a decimal point
+   * Take the fractional part of <m>v prime</m>, let <m>n = p - floor ( log_ b v prime ) - 1</m>
+   * Apply algorithm <m>(FP)^3</m> to //f// and //n//
+   * If <m>x</m> was not zero, append the letter "E" and a representation of the scale factor <m>x</m>

Solar's Rootdirectory

User Tools

Site Tools

Differences

Page Tools