Karim BELABAS on Wed, 2 Oct 2002 21:50:02 +0200 (MEST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: bug in addrr

On Tue, 1 Oct 2002, Ilya Zakharevich wrote:

> On Tue, Oct 01, 2002 at 05:05:27PM +0200, Karim BELABAS wrote:
> > * So the number of significant bits remaining in the extra word we added is
> > at most m - sh. If this is <= 2, I cancel the extra word and round
> > appropriately.
> >
> > '2' is arbitrary. '0' is completely safe (we cancel nothing but bogus bits).
> > Could make it 1, 2, 3 ... [ here we do cancel a few correct bits ].
> >
> > As it stands, some routines lose precision (a little bit) faster. But it
> > doesn't seem to break anything, and it fixes a few problems like the above.
> What IEEE teaches us is that it is vital to have *exact* answers for
> the elementary operations.

I don't think this is true. IEEE computes exactly, then rounds.

> This algorithm breaks this principle; we know that it will lead to
> *significant* errors near the "critical" points.

The algorithm is not at fault. Only the parameter '2' above may be too
aggressive. To be conservative, I can replace it by '0'. In which case, it
is consistant with the IEEE algorithm (using guard digits).

> What IEEE does not have is a possibility to increase the precision and
> redo the calculations; so in the PARI situation this is a little bit
> less critical.  But still...

IEEE does not allow increasing the significand width, padding the output with
random bits either (which happened automatically in PARI...).

The problem is that we add entire _words_ to the output, which may not
contain a single correct bit [ Previous behaviour. Now they have to contain at
least 2 significant bits. I will lower this to 0, given convincing data ].

My original problem was that I was asked
- " What confidence can I have in this t_REAL output by PARI? How many
  correct digits are guaranteed? ".
I answered in good faith something like
- "If precision is exhausted, significand is shortened automatically. So
  barring bugs, the last word is dubious but the rest is correct".

I was immediately proven wrong.

I will check whether implementing GMP-style exponents is doable with moderate
effort. This would cancel all this (annoying) shifting business in the only
problematic cas: cancellation when subtracting two close numbers.  [storing
bit precision looks more complicated]

Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
PARI/GP Home Page: http://www.parigp-home.de/