[QUOTE=jasonp;128545]Does anyone know if GMP now implements a subquadratic GCD?[/QUOTE]

I believe GMP 4 now supports this.

Yes, GMP 4's GCD is sub-quadratic, but when I timed it last night the exponent seemed to be something like 1.75; at [url]http://gmplib.org/devel/[/url] there is a patch which claims to do the GCD of two gigabit numbers in 1890 seconds and of two 100Mbit numbers in 112 seconds, which is a much nicer sort of exponent (around 1.22).

Tom W, could you generate a pair of random integers in the F31-sized range and feed them to the current GMP gcd routine to see what happens? Jason, maybe while Tom does that you could tweak your FGT code to take your F31 stage 1 residue and power it to the single stage 2 prime needed to reproduce the known Kruppa-Forbes factor - that way, if Tom's random-input test finishes [i.e. we know it at least doesn't crash], we can then do correct-result test using inputs with a known nontrivial gcd.

I am currently running some code which computes lots of GCD's on fairly large numbers (but no bigger than 10^10000), in Mathematica. I'd like to use something a little nicer than Mathematica (especially since there is a bug in the program when run on a 32-bit system). Should I try to use GMP 4? Or is there better stuff out there to try it on?

Addendum to my post above [this occurred to me shortly after posting, but by then I had left work to play judge at the annual Synopsys Championship science fair in downtown San Jose, where I spent the rest of the day]:

Even better than strictly random-integer inputs - which have a fairly decent chance of having a nontrivial small factor in common, and [in the absence of multiple runs using independent GCD software] one can't be sure that that should be the *only* factor they have in common, a good software test of an F31-sized GCD would be to construct 2 inputs as follows:

1. Multiply the known factor of F31 by a set of random primes in some convenient size range [or just a suitable power of a single prime] to construct an F31-sized composite;

2. F31 itself.

[QUOTE=ewmayer;128747]Even better than strictly random-integer inputs - which have a fairly decent chance of having a nontrivial small factor in common, and [in the absence of multiple runs using independent GCD software] one can't be sure that that should be the *only* factor they have in common, a good software test of an F31-sized GCD would be to construct 2 inputs as follows:

1. Multiply the known factor of F31 by a set of random primes in some convenient size range [or just a suitable power of a single prime] to construct an F31-sized composite;

2. F31 itself.[/QUOTE]

A good thought; I've implemented that, for a number of the large known Fermat factors, multiplying by 17^lots to get the composite of an appropriate size. Compiling the new gmp was not immediate, since the patch didn't include any makefile information, but I bodged something together.

A GCD on two Fermat(21)-sized numbers takes 6Gticks with the new code and 37Gticks with the old; on Fermat(25)-sized numbers the new code takes about 230Gticks and 320M Vsize, the old code about 21.2Tticks and 70M. On Fermat(27), the new takes 1.2GBytes Vsize with up to half of that resident at a time, and 1304Gticks; on Fermat(28), 2.5G Vsize and 3050Gticks, on Fermat(29), 5.1G Vsize and 9.64Tticks. See attached plot of Vsize (red) and Rsize (green) against time: the part with the periodic upticks is computing 17^lots, the very flat part is the GCD itself.

Fermat(30) crashed my machine at almost exactly the moment that resident-size hit 4GB. On the other hand, this machine has proved itself unreliable in other circumstances too.

So on Fermat(31) it will swap quite severely (I have 8G RAM + 16G swap) but the working set [i]should[/i] fit in RAM; if I extrapolate correctly, the runtime will be not much more than 1e14 ticks CPU time, which is half a day.

F(33) is still quite a large problem, though 80G of swap can be procured, and with luck the FFTs will be reasonably local.

I made a mistake with operator precedence and the numbers in the previous posts are wrong - I computed 17^(2^n) as the prime power to multiply by, rather than 17^(2^n / log(17)).

Better GCD timings:

[code]
16 16.6Mt
17 54.4Mt
21 3.8Gt
25 158Gt, 100MB/75MB virtual/used
27 878Gt, 370MB/290MB virtual/used
28 2.1Tt, 680MB/580MB
29 4.8Tt, 1400MB/1150MB
30 11.1Tt, 2800MB/2300MB
[/code]

Which suggest that the n=31 case should be absolutely straightforward - a single evening - on a 6G machine with a reasonable amount of swap and an appropriately patched-up gmp.

(To make an appropriately patched-up gmp, take the standard 4.2.2 distribution and the files from [url]http://gmplib.org/devel/;[/url] append [url]http://gmplib.org/devel/gmp-impl.h-gcd-newlines[/url] to the distribution's gmp-impl.h, replace mpn/generic/gcd.c and mpn/generic/gcdext.c from the distribution with the new versions, build the library, and then compile your code with

[code]
g++ -O3 -o with-new-gmp fermat-gmp-test.cpp -Lgmp-4.2.2 gmp-4.2.2/.libs/libgmp.a hgcd.c qstack.c hgcd2.c
[/code]

where the last three files are from the /devel page.

[QUOTE=fivemack;128840]
Which suggest that the n=31 case should be absolutely straightforward - a single evening - on a 6G machine with a reasonable amount of swap and an appropriately patched-up gmp.
[/QUOTE]
Thanks a bunch for the help. I've rebuilt the library and confirmed the F26 factor is found with the new GMP (it's incredibly fast too). I've started a run on the F31 residue; we'll see how far it gets with 6GB of memory and 14GB of swap.

I vaguely remember a paper published somewhere that found, for extremely difficult computational problems, that the most efficient solution method is to wait a few years until more powerful hardware and software is available :)

Last night's run successfully computed GCD(46931635677864055013377*17^520129198, F31) in 25.1Tticks with physical memory use no more than 5GB and virtual memory no more than 6GB, so I anticipate success with your residue.

[QUOTE=fivemack;128868]Last night's run successfully computed GCD(46931635677864055013377*17^520129198, F31) in 25.1Tticks with physical memory use no more than 5GB and virtual memory no more than 6GB, so I anticipate success with your residue.[/QUOTE]
It took 2 hours 5 minutes, and found a GCD of 1.

Ah well. Someday I'll perform the test Ernst suggested, just to perform a sanity check on the residue I have. So closes another sordid chapter of Jason's computational history.

PS: Who thinks I should repeat the exercise on F33? By the time a moderate size stage 1 is done, GMP5.0 will be out and will have all of the patches at gmplib.org folded in. Also, Maybe I'll consider a (distributed?) stage2 with the residue I have.

[QUOTE=jasonp;128850]I vaguely remember a paper published somewhere that found, for extremely difficult computational problems, that the most efficient solution method is to wait a few years until more powerful hardware and software is available :)[/QUOTE]
At some point the current content of the Cunningham tables will not be worth storing, as it will be easier to compute it on the fly. Of course, such a state may never be reached if folks give up factoring large numbers in the present.