home   |   the links mine   |   6502 primer
intro: integer math & tables   |   math table files' descriptions   |   rational-number approximations   |   how Intel Hex files work   |   how the files were calc'd & formed



Large Look-up Tables for Fast, Accurate, 16-Bit Fixed-Point/Scaled-Integer Math


Rational-number approximations for fixed-point and scaled-integer math

These are especially intended for use with methods like Forth's */ which multiplies by the first number and divides the product by the second number, with double-precision intermdediate results.  The few in parentheses are numbers too big to use with with the minimum-size 16-bit cells.  Larger cells would of course offer reduced error size but also require more time to find the most accurate numbers, since as far as I know, the only way to find these numbers is just to have a computer try a particular numerator or denominator, find the closest other number (denominator or numerator), check the error against your maximum target error, and move on to the next number and try again and again in a loop until it finds an acceptable combination of numbers.

It's interesting that the common 355/113 approximation for π (Greek letter pi) is accurate to about eight digits in spite of the low numbers, but there are no other combinations that can be represented in 16-bit cells that are much better.  The best I found was less than twice as accurate, and required going nearly to the end of the 16-bit unsigned range to get it.

A few numbers below are good for about ten digits.  Such accuracy may well come into play with UT*/ or M*/ , less-common Forth integer operators that take a double number (which means at least 32-bit), multiply it by one 16-bit number, and divide the 48-bit intermediate result by another 16-bit number to arrive at a 32-bit final result.

This is by no means an exhaustive list of all close combinations in descending order of error size.  It offers a range from combinations that can be represented with 8-bit numbers up to the most accurate 16-bit ones I've found, and some in between.  For example, for signed numbers, you may want the most accurate numbers under 32,768 so they fit in 15 bits.

The 12√2 is useful in calculating music note frequencies.  10-digit accuracy is definitely not needed for that, but you have it anyway here.

At the time of this writing, I do not know the significance of the numbers with the 16.384 or 1.6384 (although the 16384 looks like a 14-bit scale factor), or what the two at the end are with the "22-bit" reference.  They are borrowed from another source where someone thought they were important enough to include.  Maybe someone will have a use for them.  The "c" is the speed of light in hundreds of millions of meters per second.


NUMBER          DECIMAL        APPROXIMATION    ERROR
π               3.14159265359      22/7         +4.0E-4  or +.04%
                                  245/78        -1.8E-4  or -.018%
                                  355/113       +8.5E-8  or +.0000085%
                                65298/20785     -5.1E-8  or -.0000051%
                              ( 93343/29712     -9.9E-9  or -.00000099% )

√2              1.41421356237       7/5         -1.0E-2  or -1.0%
                                   99/70        +5.1E-5  or +.0051%
                                  239/169       -8.8E-6  or -.00088%
                                19601/13860     +1.3E-9  or +.00000013%

√3              1.73205080757      26/15                    +.074%
                                   97/56                    +.0053%
                                18817/10864     +1.4E-9  or +.00000014%

e               2.71828182846     106/39        -1.2E-4  or -.012%
                                  193/71        +1.0E-5  or +.001%
                                23225/8544      +2.5E-9  or +.00000025%
                                25946/9545      -2.0E-9  or -.0000002%

√5              2.23606797750     123/55        +1.2E-4  or +.013%
                                  161/72        +1.9E-5  or +.0019%
                                  521/233       -7.4E-6  or -.00074%
                                12238/5473      -3.3E-9  or -.00000033%
                                51841/23184     +1.9E-10 or +.000000019%

√10             3.16227766017     117/37        -3.7E-5  or -.0037%
                                27379/8658      +6.7E-10 or +.000000067%

12√2            1.05946309436   26797/25293     -1.7E-9  or -.00000017%
LOG10(2)/1.6384 .183734128213    2040/11103     -1.2E-8  or -.0000011%
ln(2)/16.384    .0423063464697    846/19997     -1.2E-8  or -.0000012%

LOG10(e)        .434294481903  is the inverse of ln(10) below:
ln(10)          2.30258509299      16/7         -7.3E-3  or -.73%
                                   99/43        -1.1E-4  or -.011%
                                  175/76        +2.0E-5  or +.0020%
                                 3919/1702      +4.4E-8  or +.0000044%
                                12381/5377      -3.6E-9  or -.00000036%
                                41062/17833     +8.9E-10 or +.000000089%

LOG2(e)         1.44269504089  is the inverse of ln(2) below:
ln(2)           .69314718056       61/88        +5.0E-5  or +.0050%
                                  131/189       -3.7E-5  or -.0037%
                                  192/277       -9.2E-6  or -.00092%
                                 2731/3940      +4.0E-8  or +.0000040%
                                 7050/10171     +3.8E-9  or +.00000038%
                                25469/36744     -9.8E-11 or -.0000000098%

LOG2(10)        3.32192809488  is the inverse of ln(2)/ln(10) below, and
LOG10(2)        .301029995665  is the same as    ln(2)/ln(10) below:
ln(2)/ln(10)    .301029995665      28/93        +1.5E-4  or +.015%
                                   59/196       -3.2E-5  or -.0032%
                                  643/2136      -1.1E-7  or -.000011%
                                 2718/9029      +6.2E-8  or +.0000062%
                                 4004/13301     +6.9E-9  or +.00000069%
                                12655/42039     +9.7E-10 or +.000000097%
                              ( 21306/70777     +1.5E-10 or +.000000015% )
                                  500/1661      +2.2E-5  or +.0022%

φ = 1/φ+1 = φ²-1 = (1+√5)/2
                1.61803398875      34/21        +6E-4    or +.06%
                                 1097/678       -2.5E-5  or -.0025%
.001°/22-bit rev                18118/21109     1.4E-9   or .00000014%	?
arc-sec/22-bit rev               9118/29509     1E-9     or .0000001%	?
c               2.9979248       24559/8192      1.6E-9   or .00000016%


(For 1/(any_of_the_above_numbers), just swap numerator and denominator above)
1/π             .318309886184
1/√2            .707106781188
1/√3            .577350269189
1/e             .367879441171
1/√5            .447213595500
1/√10           .316227766017
1/2^(1/12)      .943874312681
1/ln(10)        .434294481904
1/ln(2)        1.44269504089


HP-71 BASIC program APROXFIX to find the rational-number approximations:
(This appears to be the final version used, as I found it in the 71 after 10 years of not paying any attention to it.)
(The Hewlett-Packard HP-71 hand-held computer uses 12 digits, with 15-digit intermediate precision.)

APROXFIX:  DIM N,I,R,E        ! desired number, incremeter it's working on (denominator), current result, acceptable error in %
INPUT "Target number=",STR$(N);N
INPUT "% err allowable=";E  @  E=E*.01
INPUT "Starting denominator=","1";I
"Denominator="  @  WINDOW 13  @  STD
LOOP:  I @ R=I*N @ IF ABS(RES/IP(RES+.5)-1)>E THEN I=I+1 @ GOTO LOOP
WINDOW 1 @ "Use "&STR$(IP(R+.5))&"/"&STR$(I) @ BEEP 

On the 6502.org forum, bogax posted a link to javascript to generate rational approximations, http://pastebin.com/CFVVEbWX.

last updated Oct 18, 2013               contact: Garth Wilson, wilsonmines@dslextreme.com