The other thing these affect is pari, which uses this function and relies on the normalisation being correct. But again, we can prove it is, just can't test that it is.
Bill. On 11 May 2010 04:14, Bill Hart <[email protected]> wrote: > 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.
