Mersenne: factoring and LL-testing with perl
Hi all,
I haven't run prime95 the past year and I'm still among the
top ten producers. Well, last time I checked I was.
Didn't think I would last that long up there. ;-)
I was goofing around with perl today and recalled a cool
way of factoring/primality checking using patternmatching.
I also tried out the bigint module and did some LL-testing,
verifying all known MP's from M2281 and down.
I thought I'd share some code, very simple but perhaps
interesting for some.
Here's an LL-test of M13. Change the assignment on the
first row to test another number, remember it has
to be prime. M13 is the biggest number this code can handle.
# LL-test 1
$P = 13;
$MP = (1 << $P) - 1;
$U = 4;
for ($i = 1; $i < $P - 1; $i++)
{
$U = ($U * $U - 2) % $MP;
}
if ($U == 0) { print "M$P is prime\n"; }
else { print "M$P is composite\n" }
Perl is nice, this particular code is very similar to C,
in case you haven't noticed.
Next step is incorporating the bigint module which is a part of the
standard perl distribution:
# LL-test 2
use Math::BigInt;
for $P (3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61) {
$MP = Math::BigInt->new(2);
$MP = ($MP ** $P) - 1;
$U = Math::BigInt->new(4);
for ($i = Math::BigInt->new(1); $i->bcmp($P - 1); $i = $i + 1)
{
$U = ($U * $U - 2) % $MP;
print "\r$i\t($P)\t";
}
$not = $U == 0 ? '' : ' not';
print "M$P is$not prime\n";
}
Besides support for big numbers the test is now wrapped up in a
loop that tests prime exponents <= 61 and > 2
Also, progress printing in the innermost loop has been added.
Now to the patternmatching, this is fun. The number to factor
is represented as a string of characters, eg:
'o' is 5
The concept is to find a sequence of 2 or more characters that
is repeated 2 or more times and matches the whole sequence.
The pattern for this is:
/^(oo+)\1+$/
Short explanation:
o matches a literal o
+ means 1 or more, thus oo+ matches 2 or more o's
Quantifiers in perl are greedy, meaning they match
as much as possible.
The parens are for catching parts of the matched string
to special variables. The first pair goes to $1, the second
to $2, etc.
\1 is a backreference, meaning the exakt sequence that was
matched by the first pair of parens.
^ means match at the beginning
$ means match at the end
The forward slashes are perls regex-operator.
Now some code:
while ($num = )
{
chomp $num; # ditch the newline char
last if $num == 0; # like C's break
$seq = 'o' x $num; # make a sequence of $num o's
# =~ is perls match-operator
print "$num is prime\n" unless $seq =~ /^(oo+)\1+$/;
}
When the pattern matches we have a factor represented by
the length of $1, the dividend of the number being
tested and it's smallest prime factor. We can alter the
regex slightly to get the smallest prime factor into $1
instead. Quantifiers are greedy by default in perl but
can be forced to the opposite by appending a ?
/^(oo+?)\1+$/
Imagine we are testing the number 30. The new regex will
match the 2 first o's with (oo+) and then repeat the sequence
15 times to exactly match the string. With the first regex
(oo+) would match all 30 o's before the engine continues,
only to fail immediately. It would the back up and pop off
1 char, matching 29 o's and try again. This proceeds until
until 15 is reached and the total expression matches. This
process is called backtracking. We need this knowledge for
the next step.
If we were to completely factorize our original number (30)
we would probably want do something like this:
while (match) {
print the found factor, $1
replace the number, $N, with the $N / $1
}
print the remaining prime factor
What's interesting in our case is that the number is
represented by the length of a sequence, so how do
we say N = N / F in an easy way? The obvious
$N = 'o' x (length($N) / length($1));
works fine, thats what I would have come up with. The
Perl Cookbook demonstrates a method using more pattern-
matching and substitution. The idea is to replace each
repeated sequence with a single o. With our example of
30 each pair of o's becomes a single o leaving 15. The
next step substitutes each triplet with a single o
leaving 5. In perl:
$N =~ s/$1/o/g;
This means search for $1 in $N and replace with o
The g is for global meaning all occurences.
# almost exactly from the book...
# shift is a function that pulls the next argument from the
# commandline.
for ($N = ('o' x shift); $N =~ /^(oo+?)\1+$/; $N =~ s/$1/o/g;) {
print length($1), " ";
}
print length($N);
Robert
~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^
>
> Robert Friberg
> Delphi, C, Perl developer for hire
> Boras, Sweden
>
~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^
Re: Mersenne: GUI for Linux
On Wed, 14 Apr 1999, Guillermo Ballester Valor wrote: > Hi to all: > > Henrik Olsen wrote: > > > > On Tue, 13 Apr 1999, Ernst W. Mayer wrote: > > > A bit off-topic, but I think there are enough Linux users out there > > > to justify it. Check out > > > > You are right, I think. I am a new user of linux, then a new mprime > user. I run both prime95/mprime in Win95/linux O.S. using the same > directory and files (except the executable file, of course). 99% of > iterations are made by mprime, 1% by prime95. Actually, I only use > prime95 like an administartion tool to configure the *.ini files. > > I know I can do that simply editing the files... but I like GUI in > prime95. I wrote a small tcl program to keep the last 25 lines of mprime's output in a file. I am planning to write a tcl/tk program to look at that file and tell me when mprime wants to connect and, having connected, when it's finished so that I can disconnect. But I don't know how to change the parameters of a running mprime. Can I open mprime bidirectionally from the tcl program and pass it commands? Or could mprime be modified to listen to some port, and then I could run a client to get at its menu? I run it as root, from rc.local, before any consoles are gotty. phma Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: GUI for Linux
>Forcing Linux users to run X just to be able to admin a program is in my >opinion quite silly. Agreed >What I really like about mprime is that it makes almost no demands on what >other crud is installed on the machine already. True enough >If you really want to gui for Linux, do it the Linux way and write one >yourself instead of asking others to do it. - or simply have a console window come up & execute "mprime -d" when you start X? I've no objection to anyone writing a fancy front-end for mprime, but I hope the existing "minimalist" version will be retained ... if only because the great beauties of linux are its incredible stability and the minimal configuration needed to run it, the first is reduced and the second vanishes as soon as you need to run X. Regards Brian Beesley Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Top Producers Reports
Hi all, At 11:23 AM 4/4/99 -0700, Terry S. Arnold wrote: >The top producers report over at Georges site appears to have wiped out all >of the V17 work (and maybe some more) while the equivalent report on >Scott's site has not. Could we at least be consistent. I just loaded the latest Top Producers page and v17 work should be recredited. As Scott noted, the Primenet server's page and mersenne.Org's page track two different things. Historically, mersenne.org does not track factoring work (I don't have the data to do so), decredits LL tests that were later found bad or a factor was found. It also applies the timings of the latest prime95 to produce its results. However, I understand that some people use that page as a motivator, and the v17 bug was my fault, so I've changed my programs to include those bad results. I thought about "phasing out" the credit for these v17 results (just so I don't have to track them), but did not reach a definitive decision. Note that when the next version of prime95 comes out, everyone will take a hit as the new faster timings are applied. Use the page as a rough indicator of where you stand relative to other GIMPS members. Don't take it as an overly accurate accounting of every CPU cycle you have invested. Best regards, George Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: GUI for Linux
Hi to all: Henrik Olsen wrote: > > On Tue, 13 Apr 1999, Ernst W. Mayer wrote: > > A bit off-topic, but I think there are enough Linux users out there > > to justify it. Check out > > You are right, I think. I am a new user of linux, then a new mprime user. I run both prime95/mprime in Win95/linux O.S. using the same directory and files (except the executable file, of course). 99% of iterations are made by mprime, 1% by prime95. Actually, I only use prime95 like an administartion tool to configure the *.ini files. I know I can do that simply editing the files... but I like GUI in prime95. > > http://www.fsf.org/press/gnome-1.0.html > Forcing Linux users to run X just to be able to admin a program is in my > opinion quite silly. > What I really like about mprime is that it makes almost no demands on what > other crud is installed on the machine already. > > If you really want to gui for Linux, do it the Linux way and write one > yourself instead of asking others to do it. > I like the core of mprime, it is enough to advanced users, but an optional GUI tool to administrate the program, the output, primenet count(s) and other user options (like prime95 do) would be a good thing. _ @ | |/ --- (. .) -ooOo---(_)---o0oo | Guillermo Ballester Valor | | [EMAIL PROTECTED] | | c/ cordoba, 19 | | 18151-Ogijares (Spain) | | (Linux registered user 1171811) | -- Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Single precision in consoles
I see your point, and I'm aware it can be done. I didn't mean any kind of personal attack on you for your idea. Creative thinking is one of the most important things in my opinion. I just think such important and interesting things as GIMPS shouldn't be spread over to consoles. GIMPS is working incredibly well and so many numbers are getting crunched so quickly by the mass effort. If we all remain patient, we will soon have another mersenne prime on the list. At 13:59 04/13/1999 +, you wrote: >Hello, > >I know many have complained about my console idea (which, as I said, was not >very realistic at this point), because they only have single precision. I >just want you to consider that George once had an _integer_ version of Prime95 >running, but it was roughly 7 times slower (if I remember right) that the >FPU version. (The factoring code for 486es and clones _is_ integer, BTW.) > >However, there is strength in numbers. A _lot_ of people have consoles. So >even if they aren't as much worth as a P3/Mhz or whatever, they still >_help_, much more than 486es. > >/* Steinar */ > >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: GUI for Linux
On Tue, 13 Apr 1999, Ernst W. Mayer wrote: > A bit off-topic, but I think there are enough Linux users out there > to justify it. Check out > > http://www.fsf.org/press/gnome-1.0.html Forcing Linux users to run X just to be able to admin a program is in my opinion quite silly. What I really like about mprime is that it makes almost no demands on what other crud is installed on the machine already. If you really want to gui for Linux, do it the Linux way and write one yourself instead of asking others to do it. -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ A Pentium is a terrible thing to waste, http://www.mersenne.org/prime.htm Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
