I have fixed the remaining problems in the code and it now passes the test code.
The next step is for me to add code for unbalanced division. This is a much easier case to deal with fortunately. Bill. On 21 March 2013 20:25, Bill Hart <[email protected]> wrote: > 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.
