On 11 May 2010 04:02, William Stein <[email protected]> wrote: > 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.
My feeling is one or two of them can't be triggered. So even though we can prove they are correct if they are triggered (I have a written justification in the code comments), we can't ever test them. They have the virtue of being extremely short (just 3-4 short lines of code). > > -- 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. > > -- 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.
