search

parallella / pal

An optimized C library for math, parallel processing and data movement
Apache License 2.0
302 stars 110 forks source link

When should sqrt and invsqrt stop iterating? #115

Open HenryJia opened 9 years ago

HenryJia commented 9 years ago

Following on from the discussion in pull request #105, should those 2 functions have a hard limit on how many iterations or should it just keep iterating until convergence?

Personally I think there should be a pair of functions instead for each of those functions, one with a limit (lower accuracy) and one that keeps iterating until an accuracy set by the user (e.g. iterate until each iteration only changes by 1% or less).

@aolofsson , it'd also be great if you could tell us which one would be better

aolofsson commented 9 years ago

Branching that depends on data is very expensive, so it would make sense to split into high precision and low precision. @syoyo also suggested something along these lines

syoyo commented 9 years ago

You could use gappa to formally verify the error of designed math functions : http://gappa.gforge.inria.fr

pchambers24 commented 8 years ago

This is an interesting question. The PAL project is an exercise in optimisation and there are five sensible design goals. However I think we are missing one constraint - accuracy.

I have been researching atan2, and hence atan(), for some SDR uses. I looked at the PAL master code and several papers, published code and books. I came to realise that there are many different accuracy requirement levels. Mine would be satisfied by 3 decimal places and for 'small angles', which means low magnitude of argument of atan(). Other people might like accuracies close to the math lib of gcc. What is the constraint that is 'good enough' for PAL.

When I looked at the provenance of some of the code I have used in DSP work I came across the names Cody and Waite. Apparently they wrote a book in 1980 that was a landmark in the field and recommends algorithms and expected accuracies, their book is: "Software Manual for the Elementary Functions". They also wrote a test package for implementations of elementary math functions. I have downloaded and run this on x86-64 Linux without problems.

ELEFUNT

I would recommend that the project define at least one level of accuracy requirement, against a test package, so that contributors can know when optimisation is 'good enough'.