32/64 bit gmp-ecm issue...

[WraithX]

I have recently come across an issue that others on mersenneforum have encountered. When building 64-bit gmp-ecm on Windows, both ecm and p+1 restrict B1 to be < ULONG_MAX, which is always 32-bits on Windows. All my comments on code line numbers will be based on the 6.3 release.

The restriction for ecm is on line 904 of ecm.c. This appears to be due to prac() (line 410 of ecm.c) taking an (unsigned long)k. If we could change the definition of prac for 64-bit builds to use unsigned long long (or some suitable uint64_t), and change the unsigned long variables used internally in prac to be the same type, then we can fix this issue for Win64 (actually, for all 64-bit) builds.

For p+1, the restriction is defined on line 975 of pp1.c. There is a comment directly above it stating that: /* since pp1_mul_prac takes an unsigned long, we have to check that B1 <= MAX_ULONG */. This is the same situation as with ecm. pp1_mul_prac is defined on line 147 of lucas.c. If we could change its definition and internal variables to use a suitable uint64_t for 64-bit builds, then this issue will also be fixed.

This is based on a quick look at the source. There may be (and are, I see lucas_cost will need an update) more functions that need to be adjusted due to this change. Actually, if a 32-bit build supports a 64-bit data type, can we just allow all builds to select a B1 up to MAX_B1? Or are there other restrictions to keep this from being practical?

I know there are probably other (higher?) priorites in developing gmp-ecm, but is this something the developers can work on? Or, if I could contribute, what would be the recommended way to proceed on an issue such as this? Hopefully we can use this thread to coordinate any effort along these lines.

[Brian Gladman]

If there are calls to MPIR that involve integers, these will unfortunately only allow 32-bit values on Windows x64 at the moment. The MPIR team is now looking at this and it is likely that we will add at least mpz set/get functions for intmax_t and uintmax_t integer types as a way of tackling this problem in places where MPIR is used.

But, as you indicate, this also needs a review of applications such as GMP-ECM to find where it would make sense to replace integer types with intmax_t or uintmax_t types.

Brian

[ATH]

I think the P+1 and ECM maximum value is artificially limited at 2^32-1, since there is the clear warning messages instead of just a crash like when P-1 B2 is chosen too high: http://www.mersenneforum.org/showthread.php?t=14785

Error, maximal step1 bound for P+1 is 4294967295.
Error, maximal step 1 bound for ECM is 4294967295.

Error: cannot choose suitable P value for your stage 2 parameters.
Try a shorter B2min,B2 interval.

Its probably a leftover from back when it was inconceivable with such high B1. It's still a very high B1 for ecm, but for P+1 I have been looking for higher B1 for a while.

[ATH]

Actually it seems I was wrong about P+1, it looks like an actual error. If you do:
ecm -pp1 -v -v -v -v 5e9 < somenumber.txt
you can see it tries a lot of things before the error message:

ecm -pp1 -v -v -v -v 5e9 < HP49-106.txt
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [P+1]
Input number is 3472467444205921599314517797503819477589734084122870541677198725
33271934546286669814833105704529883802695727555197511968308548810003942514015685
156434289609169900936632761084050232224864731326076358951406247481 (210 digits)
Using MODMULN
NTT can handle lmax <= 268435456
choose_P: trying P = 3, eulerphi(P) = 2
choose_P: lmin = 485953849758754 for P = 3
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 5, eulerphi(P) = 4
choose_P: lmin = 291572309855253 for P = 5
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 9, eulerphi(P) = 6
choose_P: lmin = 161984616586252 for P = 9
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 15, eulerphi(P) = 8
choose_P: lmin = 97190769951751 for P = 15
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 21, eulerphi(P) = 12
choose_P: lmin = 69421978536965 for P = 21
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 17, eulerphi(P) = 16
choose_P: lmin = 85756561722133 for P = 17
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 27, eulerphi(P) = 18
choose_P: lmin = 53994872195418 for P = 27
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 33, eulerphi(P) = 20
choose_P: lmin = 44177622705342 for P = 33
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 45, eulerphi(P) = 24
choose_P: lmin = 32396923317251 for P = 45
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 51, eulerphi(P) = 32
choose_P: lmin = 28585520574045 for P = 51
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 63, eulerphi(P) = 36
choose_P: lmin = 23140659512322 for P = 63
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 75, eulerphi(P) = 40
choose_P: lmin = 19438153990351 for P = 75
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 105, eulerphi(P) = 48
choose_P: lmin = 13884395707393 for P = 105
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 99, eulerphi(P) = 60
choose_P: lmin = 14725874235114 for P = 99
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 135, eulerphi(P) = 72
choose_P: lmin = 10798974439084 for P = 135
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 165, eulerphi(P) = 80
choose_P: lmin = 8835524541069 for P = 165
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 195, eulerphi(P) = 96
choose_P: lmin = 7476213073212 for P = 195
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 189, eulerphi(P) = 108
choose_P: lmin = 7713553170774 for P = 189
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 231, eulerphi(P) = 120
choose_P: lmin = 6311088957906 for P = 231
choose_P: lmin > lmax, this P is too small
choose_P: trying P = 255, eulerphi(P) = 128
choose_P: lmin = 5717104114809 for P = 255
.
.
.
.
.
.
alot of lines cut out
.
.
.
.
.
.
.
choose_P: trying P = 780825045, eulerphi(P) = 255467520
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 790524735, eulerphi(P) = 268738560
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 821665845, eulerphi(P) = 278691840
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 851275425, eulerphi(P) = 283852800
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 863017155, eulerphi(P) = 298045440
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 909984075, eulerphi(P) = 304128000
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 936020085, eulerphi(P) = 318504960
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 984518535, eulerphi(P) = 325140480
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 1017041025, eulerphi(P) = 342144000
choose_P: tryphiP > cost = 93952409, this P is too large
choose_P: trying P = 1052416365, eulerphi(P) = 348364800
choose_P: tryphiP > cost = 93952409, this P is too large
Using B1=5000000000, B2=3231568167643630, polynomial x^1, x0=315177856
P = 88062975, l = 33554432, s_1 = 15206400, k = s_2 = 2, m_1 = 24
Error, maximal step1 bound for P+1 is 4294967295
Please report internal errors at <ecm-discuss@lists.gforge.inria.fr>.

But with ECM the error comes immediately like a hard-coded limit:
ecm -v -v -v -v 5e9 < hp49-106.txt

ecm -v -v -v -v 5e9 < HP49-106.txt
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [ECM]
Input number is 3472467444205921599314517797503819477589734084122870541677198725
33271934546286669814833105704529883802695727555197511968308548810003942514015685
156434289609169900936632761084050232224864731326076358951406247481 (210 digits)
Error, maximal step 1 bound for ECM is 4294967295.
Please report internal errors at <ecm-discuss@lists.gforge.inria.fr>.

[WraithX]

Originally Posted by ATH

Actually it seems I was wrong about P+1, it looks like an actual error. If you do:
ecm -pp1 -v -v -v -v 5e9 < somenumber.txt
you can see it tries a lot of things before the error message:

ecm -pp1 -v -v -v -v 5e9 < HP49-106.txt
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [P+1]
Input number is (210 digits)
Using MODMULN
NTT can handle lmax <= 268435456
<snip>
choose_P: trying P = 1052416365, eulerphi(P) = 348364800
choose_P: tryphiP > cost = 93952409, this P is too large
Using B1=5000000000, B2=3231568167643630, polynomial x^1, x0=315177856
P = 88062975, l = 33554432, s_1 = 15206400, k = s_2 = 2, m_1 = 24
Error, maximal step1 bound for P+1 is 4294967295
Please report internal errors at <ecm-discuss@lists.gforge.inria.fr>.

But with ECM the error comes immediately like a hard-coded limit:
ecm -v -v -v -v 5e9 < hp49-106.txt

No, you weren't wrong. In pp1.c line 892, there is a call to the choose_P method (which takes a couple of unsigned longs). This part of the code comes before the actual check to see if B1 is too large, which comes on line 975. Since you get the "maximal step1 bound" error, it means it that it got through choose_P just fine. I say this because at the end of choose_P it would return an error if it wasn't successful. choose_P starts on line 554 of pm1fs2.c, and the error (which we didn't get) is on line 727 and says:

  if (P == 0)
    {
      outputf (OUTPUT_ERROR, "Error: cannot choose suitable P value for your "
	       "stage 2 parameters.\nTry a shorter B2min,B2 interval.\n");
      return ECM_ERROR;
    }

It looks like we would also need this file to be Win64 friendly to have p+1 work as intended. My guess is that most all the files will need to be updated in some fashion to get this working correctly.

Alex or Paul (or any ecm dev/admin), what do you think about using intmax_t and uintmax_t for these variables that are currently unsigned long? We can check for existence in some appropriate place (not sure how configure works, maybe there?) and use the defined ones or define our own?

[ATH]

I think and hope they are already working on it or planning to: post #14 http://www.mersenneforum.org/showthread.php?t=14785

Don't bother, this mess needs a cleanup. We need to test for the largest natively supported integer type in ./configure and use its typedef everywhere.

[yoyo]

I have now exactly this issue with
GMP-ECM 6.3 [configured with GMP 5.0.1] [ECM] on Windows 64 bit. It seems to work on Linux 64 bit. I run a C200 with

ecm -v -nn -timestamp -chkpnt checkpnt -maxmem 10000 -inp in -savea save 7600e6 1

and get

Error, maximal step 1 bound for ECM is 4294967295.
Please report internal errors at <ecm-discuss@lists.gforge.inria.fr>.

I run the ecm63mpir230core2-64.exe, for which the download link was provided somewhere here in the forum.

Was this fixed in later versions?

yoyo

[henryzz]

It seems to work on 7.0.4. You should upgrade anyway. There would be speed improvements with later versions of MPIR.

[yoyo]

I use now the generix 32/64 bit versions from http://gilchrist.ca/jeff/factoring/index.html.

[ATH]

Check this thread: http://mersenneforum.org/showthread.php?t=4087

It should work in the 64bit binaries I posted:
Skylake (Windows): gmpecm7-svn2988-skylake.zip
Ivy Bridge (Windows): gmpecm7-svn2988-ivybridge.zip
Haswell (Windows): gmpecm7-svn2968-haswell.zip

Haswell (Linux): gmpecm7-svn2975-haswell.tar.gz


Which processor do you use? I can compile the newest SVN.

[yoyo]

I distribute the binary to thousands of hosts together with the workunits: http://www.rechenkraft.net/yoyo/apps.php

Therefore I need generic versions, not dedicated to a specific processor architecture, for 32 and 64 bit.
For Windows I have ecm 7 already.
Now I need it for Linux@x86, Mac, Linux@arm.

yoyo