Karim Belabas on Wed, 23 Jun 2004 15:32:53 +0200

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


Hello pari-dev,

  I have removed all support for the type t_FRACN and t_RFRACN 
([possibly] reducible fractions) in PARI :

1) they were only used in a single place of the whole library: t_RFRACN in
caract(), a variant of charpoly through Lagrange interpolation. 

2) they were inefficient: using the generic type t_RFRAC in the above
library instead made the routine _faster_. Switching to ordinary
polynomials and handling denominator separately made it even faster.

3) they were mostly untested, and only partially implemented. E.g. they had
to be removed from Bill's randomgen program ( which generate random objects
and throw them in devious combinations at all routines in sight ), because
they broke far too often.

4) after Bill's recent patch removing the infamous second (optional)
argument of type()  [ which allowed one to corrupt GP data structures ],
there was no way left to create a t_(R)FRACN under GP.

4') before that patch, a FRACN was dangerous to create [ type() ], and
cumbersome to keep alive [ any simplification, e.g when returning a result ]
would promote a FRACN to a FRAC

5) I have made some tests in library programming, and in the most
favourable cases [ e.g \sum 1/p, p prime ], t_FRACN was at most twice
faster than t_FRAC ( this would be lessened with a better gcd
implementation ). It was trivial to emulate using pairs of ordinary
integers, which became then much faster than t_FRACN due to better memory
management and divide/conquer methods. t_RFRACN was always slower than t_RFRAC.

For backward compatibility, I have defined
   t_FRACN  --> t_FRAC
   t_RFRACN --> t_RFRAC
so this change should not break any old code. At most it will incur a
small performance penalty.



P.S: It is an interesting goal to teach PARI some computer algebra, but
doing it through basic "immediate" types is an approach that failed.
POLMOD / INTMOD have the same problem ( although these two have their use
under GP ), they are horribly inefficient since reduction is done on the
spot after each basic operation.

Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]