Isolating critical cases for reciprocals using integer factorization

John Harrison.

Proceedings of the 16th IEEE Symposium on Computer Arithmetic, Santiago de Compostela, Spain 2003, IEEE Computer Society Press, pp. 148-157 2003.

Abstract:

One approach to testing and/or proving correctness of a floating-point algorithm computing a function a is based on finding input floating-point numbers a such that the exact result f(a) is very close to a "rounding boundary", i.e. a floating-point number or a midpoint between them. In the present paper we show how to do this for the reciprocal function by utilizing prime factorizations. We present the method and show examples, as well as making a fairly detailed study of its expected and worst-case behavior. We point out how this analysis of reciprocals can be useful in analyzing certain reciprocal algorithms, and also show how the approach can be trivially adapted to the reciprocal square root function.

DVI, PostScript or PDF

Bibtex entry:

@INPROCEEDINGS{harrison-arith16,
        crossref        = "arith16",
        author          = "John Harrison",
        title           = "Isolating critical cases for reciprocals using
                           integer factorization",
        pages           = "148--157",
        note            = "Currently available from symposium Web site at
{\tt http://www.dec.usc.es/arith16/papers/paper-150.pdf}"}

@PROCEEDINGS{arith16,
        editor          = "Jean-Claude Bajard and Michael Schulte",
        booktitle       = "Proceedings, 16th {IEEE} Symposium
                           on Computer Arithmetic",
        address         = "Santiago de Compostela, Spain",
        date            = "15--18 June 2003",
        publisher       = "IEEE Computer Society",
        year            = 2003}