On Mon, May 10, 2010 at 9:26 PM, Bill Hart <[email protected]> wrote: > 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.
In these cases, the result would be a non-normalized but *correct* XGCD, right? Really the main reason -- by far -- that we care in Sage about normalizations being consistent is because otherwise our automated test suite is too hard to maintain and validate. -- William -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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.
