Path: Eric’s Site
/ Work
/ What I Do |
Related:
Résumé,
Work Samples,
What I Do,
Apple Service
(Site Map) |

My work generally falls into two categories: high performance and numerical software.

- The computer is more responsive to the user and can play audio and video without skipping.
- Less heat is generated.
- The battery charge lasts longer.

That bookkeeping is so complicated it is actually easier for the processor to do the calculations than to do the bookkeeping. So processor designers have created instructions that do four calculations on four sets of data. One load instruction will load four things, or one add instruction will do four adds. We get four times as much work done for the same amount of bookkeeping.

Writing programs for SIMD is complicated. Most programming languages and most algorithms are designed for single-instruction single-data programming. Writing for SIMD often requires rewriting programs. It also requires writing a lot of software for special cases. For example, if you have 103 numbers to process, you could do 100 of them with 25 SIMD instructions, but then you need different instructions to handle the last three.

Floating-point arithmetic is different. With floating-point arithmetic, the
computer represents a number with a limited number of bits and a scale factor.
The scale factor allows the computer to represent very big or very small
numbers. For example, integers can represent 3, 30, 300, or 3,000,000,000, but
bigger numbers would cause an overflow and not work. With floating-point
numbers, these could be represented as 3×10^{0}, 3×10^{1},
3×10^{2}, 3×10^{9}.

An advantage of floating-point numbers is that they go further than integers.
They can also represent 3×10^{10}, 3×10^{20},
3×10^{30}. Or they can represent very small numbers, like
3×10^{-10}, 3×10^{-20}, 3×10^{-30}. A disadvantage is
that they have fewer regular bits, so we cannot always have exact answers.
Instead, floating-point numbers are rounded. When we add 1.2345 to 10, there
might not be room for the .0005, so the computer has to round and deliver
11.235 as a result instead of the exact answer 11.2345.

Actually, most computers use binary instead of decimal as I show here. However, the consequences are the same: Floating-point arithmetic is inexact.

Because there are errors in floating-point arithmetic, good programmers must prove or estimate how large the errors are. They should show that the errors do not prevent their programs from getting results that are close enough to the exact results. This requires detailed understanding of floating-point arithmetic and some skill in writing mathematical proofs.

Any well-behaved function, like sine(*x*), can be approximated with a
polynomial like c_{3}*x*^{3} +
c_{2}*x*^{2} + c_{1}*x* + c_{0}. The
polynomial only approximates the function for a fixed interval, say for
*x* from -π to +π, and the values for the coefficients,
c_{3}, c_{2}, c_{1}, and c_{0}, must be
carefully chosen.

Computers can calculate polynomials easily, because they use only addition and multiplication. However, there is an art to finding good polynomials. There is an algorithm that gives the best coefficients for a function, but you have to choose the number of terms in the polynomial and the interval where you make the polynomial fit the function. Using more terms makes the approximation better, but then the polynomial takes longer to compute. Sometimes it is better to break up the interval and use different polynomials for different parts. That is, you would use several polynomials with a few terms instead of one polynomial with many terms.

In the case of sine(*x*), we can approximate sine with a polynomial for
the interval from -π to +π, but the sine function should return an answer
for any value of *x*, not just those in that interval. It would be too
difficult to design polynomials for all of the numbers that floating-point
numbers can represent. Fortunately, sine(*x*) is a periodic function. That
is, it repeats itself. For any value of *x*, there is some value in -π
to +π that has the same sine. So, to implement a sine function in the
computer, we need two things: A polynomial for the interval from -π to
+π, and a way to change any *x* to a value in that interval.

In principle, all we need to do is to subtract multiples of π from *x*
until we have a value in the interval. However, π is an irrational number,
so it cannot be represented exactly with floating-point arithmetic. If we try
to subtract multiples of π, we will introduce errors into the calculation,
and those errors are bigger than we allow. To get the right answer, we design
special operations that allow us to subtract π with more precision than
usual, and we use some mathematical proofs to figure out how much precision we
need to keep the error under certain limits.

Path: Eric’s Site
/ Work
/ What I Do |
Related:
Résumé,
Work Samples,
What I Do,
Apple Service
(Site Map) |

© Copyright 2010 by Eric Postpischil.