Karim Belabas on Wed, 23 Jun 2004 15:32:53 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
t_FRACN / t_RFRACN |
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. Cheers, Karim. 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]