Re: addfrac() + Karatsuba = bug (fwd)

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

On Tue, 4 Sep 2001, Michael Somos wrote:
> Christian Cornelssen mentioned his testing of the bug code. However,
> I should mention that I did extensive testing and debugging before
> I posted the message. I found that the 'avma = (long)z;' in three
> places near the end of 'addfrac()' leads to 'quickmulii()' eventually
> clobbering 'delta' in 'addfrac()' near the end. I suggest using the
> alternate 'avma = (long)delta;' in these threee cases. I did not have
> time to fully test if this is the correct solution.

The current CVS has been corrected. I did minimal changes to 2.1.1 (stable
version), and extensive changes to 2.2.1 (alpha).

I'll try to release those two versions in the near future (it may be
difficult, I'm moving houses).

> There may be lot of other issues involved here with interaction of code
> with respect to setting of 'avma'.

The old code [due to me:-(] assumed that mulii(x,y) wouldn't need more than
lgefint(x) + lgefint(y) scratch words, which wasn't a documented feature of
mulii, but happened to be true at the time.

When I later changed mulii to at least use (a primitive) Karatsuba, the old
assumption wasn't valid anymore, hence the bug.

I've checked the whole library code [most recent CVS] for such
"efficient-but-dangerous" garbage collections; I found about 40 places.
They only make use of the following "features",

  icopy(x) needs lgefint(x) words
  subii/addii(x,y) needs max(lgefint(x), lgefint(y)) words
  modii(x,y) needs (at most) lgefint(x) + 2 * lgefint(y) words 

The first two are hardly likely to change. It's not clear for the last one,
especially if Montgomery multiplication is introduced (as it should).
I left a /* HACK */ marker in those places where it still survives.

This is still quite unsatisfactory: direct memory access should be restricted
to the src/kernel routines, and duly commented.  So far, they make the
routines about 20% more efficient than they would be using regular gerepiles
(which are much sturdier, at least in such simple situations) for typical
examples [e.g single word]. But they shouldn't be spread out in the code like
that. I will think it over.

> Certainly it would have saved lots of debugging time if more effective
> memory allocation monitoring were in place. I don't see any such capability
> right now. That seems to be why small changes in one routine was able to
> clobber memory used by another.

No such capability indeed; stack corruption is a nightmare to debug.
Fortunately it's quite a rare occurence (so far), and easily spotted when it
affects a gerepile ("pointers lost in gerepile") [not so for direct
accesses]. But the development effort to change the memory management [e.g
using Boehm's GC], without sacrificing performance, is staggering (to me at
least).

Cheers,

    Karim.
-- 
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/