I have now completely implemented divide and conquer approximate division and div with remainder. This scheme is a lot neater than what we currently have in MPIR.
See divapprox and divrem functions in: https://github.com/wbhart/bsdnt/blob/v0.32/nn_quadratic.c and https://github.com/wbhart/bsdnt/blob/v0.32/nn_subquadratic.c These four functions effectively do the job of the following files in MPIR: dc_div_q.c dc_div_qr.c dc_div_qr_n.c dc_divappr_q.c dc_divappr_q_n.c sb_div_q.c sb_div_qr.c sb_divappr_q.c Moreover, the new code is definitely much more efficient in theory than what we currently have (assuming we do a lot of work writing assembly basecases and efficient divide and conquer code for mulmid and mullow). Bill. On 22 March 2013 00:47, Bill Hart <[email protected]> wrote: > 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.
