I am making good progress with getting the normalisation working for xgcd. There are 21 places where the xgcd code can return from, and each one needs to be dealt with.
The first step was to write test code which checks the normalisation. I've got that working well now. Actually checking whether you have the right normalisation and modifying if not, is far too expensive, and thus this is not the right way to do it. One needs to actually fiddle with the code so that it just happens to return the correct normalisation. The three most difficult cases are the lehmer gcdext and the mpn_gcdext_1 and mpn_gcdinv_1. I'm absolutely amazed that I found a way of normalising the latter two correctly by *removing* code!! These functions were already really fast, and now they are even faster! The lehmer gcdext took me ages to figure out, as I had to remind myself how it actually worked. But the test code for that now passes. With the above changes I can get the correct normalisation for operands up to the crossover size between lehmer gcdext and the ngcdext, which on my machine is about 150 limbs. I've run 100's of millions of xgcds in this range and all pass the new test code now. I still have quite a few exit points to check, for the cases where we are above the crossover, i.e. above 150 limbs. But many of these are trivial cases. There's some chance I'll be done in about another day. Unfortunately there are some cases in the code which are never observed to occur. They either don't ever occur or I can't come up with operands which cause them to occur. I'll simply have to put in what I believe to be correct for those cases and hope that they are working, as I did when I put the xgcd code together in the first place. Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
