# division

**Torbjorn Granlund
**
tege@swox.com

*08 Nov 2002 09:12:34 +0100*

Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
Attached are some times for varible precision newton
iteration for calculation quotient and/or remainder
the numbers are speedup's over GMP4.1 and GMP4.1+div-patch
the left hand column is the number of limbs in the
numerator and the top row is the number of limbs in the
denominator as a fraction of the number of limbs in the
numerator
You cannot expect the readers of this list to know what
GMP4.1+div-patch could be.
It's still generic inverse k'th root preliminary code, but I doubt
that the speedup's will change much.
Are you dividing with a kth root computation algorithm?? Or
are you comparing division of GMP with your kth root code?
The runtime is proportional to the quotient, so for large
n and small q there is a large speed up (upto
5000x), though I thought gmp already had code for this
special case?
I assume the runtime when generating just the quotient is in
most cases a function of just the quotient size, but when
the remainder is close to 0, I think it will need more time.
I havent yet testing using this for barrett type division,
but it should be fairly good.
I am confused, are you dividing or not? Are you using a
pre-inverse, but not Barrett's algorithm?
Please try to work more with your postings to gmp-devel. They
come through as rather sloppy now.
--
Torbjörn