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