[Aldor-l] [Axiom-developer] exact quotient

[Ralf Hemmecke]

On 06/19/2007 02:58 PM, Martin Rubey wrote:
> I am currently trying to correct a performance bug of my guessing package, and
> found out that exquo is in general not extremely intelligent.

> In axiom, what exquo really does is to perform division and return "failed" if
> it's not exact.  (I.e., it is in fact slower than quo.quotient)
> 
> What I need is a fast algorithm, that simply assumes that the division is
> exact, and should benefit from that assumption.  (If the assumption is not
> true, the computer may crash, if necessary...) As far as I know, using some
> tricks performance even better than n^2 (n being the size of the input) is
> achievable.

For integers that algorithm is due to Tudor Jebelean and implemented in GMP.

http://info2html.sourceforge.net/cgi-bin/info2html-demo/info2html?(gmp.info.gz)References

     * Tudor Jebelean, "An algorithm for exact division", Journal of
       Symbolic Computation, volume 15, 1993, pp. 169-180.  Research
       report version available
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz'

     * Tudor Jebelean, "Exact Division with Karatsuba Complexity -
       Extended Abstract", RISC-Linz technical report 96-31,
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-31.ps.gz'

     * Tudor Jebelean, "Practical Integer Division with Karatsuba
       Complexity", ISSAC 97, pp. 339-341.  Technical report available
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-29.ps.gz'

     * Tudor Jebelean, "A Generalization of the Binary GCD Algorithm",
       ISSAC 93, pp. 111-116.  Technical report version available
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz'

     * Tudor Jebelean, "A Double-Digit Lehmer-Euclid Algorithm for
       Finding the GCD of Long Integers", Journal of Symbolic
       Computation, volume 19, 1995, pp. 145-157.  Technical report
       version also available
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz'

     * Werner Krandick and Tudor Jebelean, "Bidirectional Exact Integer
       Division", Journal of Symbolic Computation, volume 21, 1996, pp.
       441-455.  Early technical report version also available
       `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1994/94-50.ps.gz'

But also in Aldor one is out of luck since AldorInteger builds on FOAM 
and exact division is (as far as I know) not available through FOAM.

http://info2html.sourceforge.net/cgi-bin/info2html-demo/info2html?(gmp.info.gz)References

BTW, does Axiom build on GMP? Or does it implement its own large integer 
package?

Ralf