division

[Torbjorn Granlund]

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