I got the final cases of the xgcd normalisation sorted. The test code has been run on large sizes for ages and ages and everything now passes.
I've also added a number of new tuning cutoffs for GCD and XGCD to MPIR. However, at this point the code runs much slower than what we had before. This is nothing to do with the normalisation but the new tuning cutoffs (it affects GCD and XGCD). I will try to rearrange the code tonight when I get home to fix this and restore the earlier performance. The idea is it should run faster, not slower, when this is done correctly. We'll need to tune for all our architectures once this is working. As for a release, is there anyone who would like to do (or learn how to do) an MPIR release. It is relatively straightforward and I can explain it in detail. We would like a volunteer to do this for this release cycle as it is very bad practice to have a single person in charge of all releases. If anything happens to that person, or they become unavailable, the project grinds to a halt. Please let us know if you would like to volunteer for this. I'll advertise again in a new thread once I have the tuning sorted, at which time it will be time to start the release process (for this mini release). For Brian, there should be no changes to the Windows code, except for the new tuning cutoffs. But these are not available yet. I'll let you know when they are done for linux. Bill. On 11 May 2010 04:19, Bill Hart <[email protected]> wrote: > 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.
