[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] exact quotient
From: |
Ralf Hemmecke |
Subject: |
Re: [Axiom-developer] exact quotient |
Date: |
Tue, 19 Jun 2007 15:33:42 +0200 |
User-agent: |
Thunderbird 2.0.0.4 (X11/20070604) |
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
- [Axiom-developer] exact quotient, Martin Rubey, 2007/06/19
- Re: [Axiom-developer] exact quotient,
Ralf Hemmecke <=
- Re: [Axiom-developer] exact quotient, Waldek Hebisch, 2007/06/19
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/20
- Re: [Axiom-developer] exact quotient, Waldek Hebisch, 2007/06/20
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, William Sit, 2007/06/21
- Re: [Axiom-developer] exact quotient, William Sit, 2007/06/21