I fixed the problem I had with inconsistent results when compiling with clang vs gcc and with/without assembly optimisation. It turns out I was just missing the __volatile__ keyword in the assembly code.
My assert still fails, but consistently so. I now need to study whether I should expect it to (in which case I know how to deal with the special case) or whether this represents a bug in my code. I will report back when I have sorted it out. I am very keen on using this approach in MPIR now. I am certain it is better than what we have for numerous reasons! Bill. On 21 March 2013 02:59, Bill Hart <[email protected]> wrote: > Hi all, > > I've been playing around with integer division code. After an arduous > week long debugging session (!) I have finally written some code which > is basically working (see nn_divapprox_divconquer_preinv_c): > > https://github.com/wbhart/bsdnt/blob/v0.32/nn_subquadratic.c > > The code still fails about every 500,000 iterations, though not if I > compile using clang instead of gcc and use the assembly language > optimisation instead of the generic C code. So I may have either a > compiler bug or some undefined data hanging around (valgrind finds no > problems, however). It also doesn't handle some cases efficiently and > has some other limitations at present, which will shortly be lifted. > > However, I think we should eventually move towards using this code in > MPIR. The reason is that I trust it (or rather will trust it, when I > am done) with a high degree of confidence, and it should in theory be > a slight improvement over the existing code that we use (which has an > additional copy and some overcompensation). > > It's not ready to use right this moment, but I thought I would make > everyone aware of it. With some very minor modifications it should > work with the existing very fast schoolbook approximate division code > that we incorporated from GMP. I haven't checked this, but it should > only be necessary to return a certain piece of carry information at > the right point in that code and it should work just as well with this > new divide and conquer code. That is if I can figure out how that code > works. > > One slight complication is that the existing code uses a precomputed > inverse coming from two limbs, whereas my rather simple minded library > uses only one (normalised) limb. However, I think any problems should > go away if we switch over to using the new basecase division code I > wrote some time back, as it operates essentially the same as the new > code I've written (modulo the fact that it uses two limbs to compute > the precomputed inverse). > > I'll update the list when I sort out the remaining issues with my new > code, though that may take some time (probably a week or more, not a > day). > > Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/mpir-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
