Editing Lookup table (section)

=== Computing sines ===
Most computers only perform basic arithmetic operations and cannot directly calculate the [[sine]] of a given value. Instead, they use the [[CORDIC]] algorithm or a complex formula such as the following [[Taylor series]] to compute the value of sine to a high degree of precision:<ref name="sharif14">{{cite journal|journal= Journal of Circuits, Systems and Computers|volume=23|number=4|year=2014|first=Haidar|last=Sharif|doi=10.1142/S0218126614500510|url=https://www.worldscientific.com/doi/abs/10.1142/S0218126614500510|title=High-performance mathematical functions for single-core architectures|publisher=World Scientific}}</ref>{{rp|p=5}}

:<math>\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}</math> (for ''x'' close to 0)

However, this can be expensive to compute, especially on slow processors, and there are many applications, particularly in traditional [[computer graphics]], that need to compute many thousands of sine values every second. A common solution is to initially compute the sine of many evenly distributed values, and then to find the sine of ''x'' we choose the sine of the value closest to ''x'' through array indexing operation. This will be close to the correct value because sine is a [[continuous function]] with a bounded rate of change.{{r|sharif14|p=6}} For example:<ref>{{cite book|title= The Art of Assembly Language, 2nd Edition |author=Randall Hyde|date=1 March 2010|publisher=No Starch Press|isbn=978-1593272074|url=https://www.ic.unicamp.br/~pannain/mc404/aulas/pdfs/Art%20Of%20Intel%20x86%20Assembly.pdf|via=University of Campinas Institute of Computing}}</ref>{{rp|p=545–548}}

<syntaxhighlight lang="abap">
real array sine_table[-1000..1000]
for x from -1000 to 1000
    sine_table[x] = sine(pi * x / 1000)

function lookup_sine(x)
    return sine_table[round(1000 * x / pi)]
</syntaxhighlight>

[[File:Interpolation example linear.svg|thumb|Linear interpolation on a portion of the sine function|right]]

Unfortunately, the table requires quite a bit of space: if IEEE double-precision floating-point numbers are used, over 16,000 bytes would be required. We can use fewer samples, but then our precision will significantly worsen. One good solution is [[linear interpolation]], which draws a line between the two points in the table on either side of the value and locates the answer on that line. This is still quick to compute, and much more accurate for [[smooth function]]s such as the sine function. Here is an example using linear interpolation:

<syntaxhighlight lang="abap">
function lookup_sine(x)
    x1 = floor(x*1000/pi)
    y1 = sine_table[x1]
    y2 = sine_table[x1+1]
    return y1 + (y2-y1)*(x*1000/pi-x1)
</syntaxhighlight>

Linear interpolation provides for an interpolated function that is continuous, but will not, in general, have continuous [[derivative]]s.  For smoother interpolation of table lookup that is continuous '''and''' has continuous [[first derivative]], one should use the [[cubic Hermite spline#Interpolation on the unit interval with matched derivatives at endpoints|cubic Hermite spline]].

When using interpolation, the size of the lookup table can be reduced by using ''[[nonuniform sampling]]'', which means that where the function is close to straight, we use few sample points, while where it changes value quickly we use more sample points to keep the approximation close to the real curve. For more information, see [[interpolation]].