C program to rapidly verify all factors in GIMPS database

[GP2]

This was already posted in the Data forum.

Attached is a C program that can be used to verify factors of Mersenne exponents. It's intended for use under Unix (and uses the GMP multiple-precision library that comes with most Linux distributions).

On a 2.8GHz Pentium 4, it verifies all 2.6 million factors in the GIMPS database in less than 20 seconds.

[junky]

hi GP2, im checking the code, and at the beginning, im seeing:
#include <gmp.h>

is it a custom header ya made ?
could ya attach that file please ?

im using windows.
gonna make some tests, but if ya could attach a windows version of gmp, that would be great.

thanks.

[dsouza123]

That verification speed is incredible.

I wrote a program in windows that just reads each line of the file ( 59 MB),
separates the exponent and factor into two strings,
converts each to a large binary integer,
it takes 27 seconds on an 1.17 Ghz Athlon.

The powermod function in the gmp library must be incredibly fast.

[ewmayer]

Originally Posted by GP2

On a 2.8GHz Pentium 4, it verifies all 2.6 million factors in the GIMPS database in less than 20 seconds.

Originally Posted by dsouza123

The powermod function in the gmp library must be incredibly fast.

Let's see - 2.6 million factors verified in ~20 seconds on a 2.8GHz machine corresponds to ~10,000 cycles per factor. Let's assume that the average exponent in the GIMPS database is ~2^23 bits (it doesn't matter whether it's a a few more or less, this is just for ballpark-style estimation purposes.) Using the standard left-to-right binary exponentiation, we'll need ~20 modular multiplies for each powermod, which works out to ~500 cycles per modmul, which is no great shakes - a good sieving program will be roughly 20-50x as fast.

I'm sure the GMP stuff is quite good as far as generic arithmetic functionality is concerned, but my point is, specialized code for doing these operations is much, much faster. Of course, strictly for purposes of verification of factors, speed is not terribly important.

[michael]

Is it possible to use this program in windows?

-michael

[Xyzzy]

Originally Posted by michael

Is it possible to use this program in windows?

You can use this one:

http://www.mersenneforum.org/showpos...05&postcount=3

[michael]

I don't think i can do a list of exponents there...i don't fancy typing out 40.000 probably factors.

-michael

[FeLiNe]

Originally Posted by ewmayer

Let's see - 2.6 million factors verified in ~20 seconds on a 2.8GHz machine corresponds to ~10,000 cycles per factor. {...}

Uh - I don't think so. This sentence and the math that follows it are true only if every single cycle in those 20 seconds were spent on doing math. A someone else pointed out, there's considerable overhead in sheer file-I/O for a big file, for example. If you wanted to judge the efficiency of the math-code, you'd have to run the test twice, once with the math itself commented out (where you're opening the file and reading it and performing all kinds of oprations and conversions) and then a second time where you're doing the same thing but this time doing the actual verification itself as well as all the other stuff.

[HiddenWarrior]

The new project MPA 2005 needs a lot in a compiled version of verifyfactors! I wrote my own, but it is still are very slow... Compiled version for WinXP is very good! Maybe after I'll place documentation to the MPA plugins structure someone will code it using ASM?