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:
'ooooo' 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 = <STDIN>)
{
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~^
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
