Mersenne Digest Thursday, April 15 1999 Volume 01 : Number 545
----------------------------------------------------------------------
Date: Mon, 12 Apr 1999 21:01:25 -0400
From: Pierre Abbat <[EMAIL PROTECTED]>
Subject: Re: Mersenne: preventive measures
How about this?:
If mprime finds that it needs to update itself, it downloads the new files,
renames the old ones, renames the new ones, and quits at five 'til. One minute
past the hour, a cron job notices that mprime isn't running and restarts it.
phma
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 12 Apr 1999 21:30:12 -0500
From: Amy and Shane Sanford <[EMAIL PROTECTED]>
Subject: Re: Mersenne: preventive measures
A easy way with any OS that has some sort of easy batch file support (such
as the flavors of Windows & from what I remember Unix). Have the Prime
program download the files to the current directory (maybe a self
executable zip file). Then execute the download. The download will unzip
all the files including a batch file which when launched will replace the
nessecary files with the new ones. The orginal prime program then would
launch the batch file (maybe with a execution delay of 2 seconds) then
close itself (and unload any .dlls if nessecary). The Batch file then
takes over with the file updates, cleans up the mess, and then launches the
new prime program before it closes.
Shane
At 09:01 PM 4/12/99 -0400, Pierre Abbat wrote:
>How about this?:
>
>If mprime finds that it needs to update itself, it downloads the new files,
>renames the old ones, renames the new ones, and quits at five 'til. One
minute
>past the hour, a cron job notices that mprime isn't running and restarts it.
>
>phma
>________________________________________________________________
>Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
>
>
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 12 Apr 1999 22:49:31 -0400
From: Andrew Isaacson <[EMAIL PROTECTED]>
Subject: Re: Mersenne: preventive measures
On Mon, Apr 12, 1999 at 09:30:12PM -0500, Amy and Shane Sanford wrote:
> A easy way with any OS that has some sort of easy batch file support (such
> as the flavors of Windows & from what I remember Unix). Have the Prime
> program download the files to the current directory (maybe a self
> executable zip file). Then execute the download. The download will unzip
> all the files including a batch file which when launched will replace the
> nessecary files with the new ones. The orginal prime program then would
> launch the batch file (maybe with a execution delay of 2 seconds) then
> close itself (and unload any .dlls if nessecary). The Batch file then
> takes over with the file updates, cleans up the mess, and then launches the
> new prime program before it closes.
The problem really is NOT solving the technical problem of how to
update the program on the fly. That's a bit challenging, sure, but
it's really not all that hard.
The real problem is ensuring that this scheme is secure. When there's
no human being in the loop, the system becomes ripe for abuse. For
example, I could use established DNS poisoning attacks to redirect
ftp.mersenne.org (or wherever the software is automatically downloaded
from) to a host of my choosing, and provide malicious software there
posing as an "update" to the mersenne software. Then your computer
would happily dowload and install my evil program!
Any automatic executable download system is suceptible to this problem
in some form or another, unless it provides some form of cryptographic
signature or other verifiability check. But doing things like that
runs afoul of the US government's medieval crypto policy.
Now, providing a method for one person to automatically update a bunch
of remote computers they control is something else entirely, and that
does not have the same security implications. For example, Aaron
Blosser installed prime95 on 3000 (or so) Windows computers from his
desktop, using remote administration software. I've done similar
things on Solaris (Unix) here at school, to run Distributed.net's
client software.
Anyways, what does this have to do with Mersenne primes?
- -andy
- --
Andy Isaacson [EMAIL PROTECTED] [EMAIL PROTECTED] Fight Spam, join CAUCE:
http://www.csl.mtu.edu/~adisaacs/ http://www.cauce.org/
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 12 Apr 1999 23:09:32 -0400
From: Bassam Abdul-Baki <[EMAIL PROTECTED]>
Subject: Mersenne: Mime-Version: 1.0
Here's a website (http://www.directupdate.com) that has a free program that
allows you to auto-update any application.
Bassam
Anyone who goes to a psychiatrist ought to have his head examined.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 01:04:33 -0500
From: Ken Kriesel <[EMAIL PROTECTED]>
Subject: Mersenne: Whoa on the preventive measures thread
I agree with George, this discussion should go offline.
My original message on the V17 bug and preventive measures
was intended as a call for volunteers in two categories
(skilled code reviewers, and QA testers with cpu time to burn)
There have been a number of ok, good, and very good points made.
But I think many on this list could do without the large volume
of posts (about ways to do auto updates, for example).
I've contributed to the bloat myself. Mea culpa.
I see what features to include or not include in Prime95 and
its relatives, and primenet, as in the hands of their respective
creators, and beyond the scope of the QA project.
All these items might be better handled with direct email
correspondence rather than broadcast through the mailing list.
I request that people who want to review GIMPS C code
or assembly code, run QA tests, help design QA tests,
do statistics on test results, or work in more than one area,
say so in private email to me but not to the mailing list. QA
testers are encouraged to list what operating systems and
hardware they are willing to test on.
In several days I will summarize it in a single message to the list.
If someone wishes to participate, but not be publicly listed
in the summary for whatever reason, say so in your email to me.
Ken Kriesel
[EMAIL PROTECTED]
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 08:36:03 +0100
From: "James Smith" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: preventive measures
> The point is that I certainly couldn't accept software coming in from
outside &
> being run without any sort of intervention; however, I'm quite happy to
manually
> download a new version, virus check it & place it in a secure local
filestore for
> people to update automatically, if they wish.
So you would just leave the feature disabled then. I would be more than
happy to let it update manually, anything the virus checker dosn't spot on
the fly during the update, it wont spot on a file scan either so that isn't
a problem. And for those people out there who don't use one, well they wont
find virii whatever method is used for update.
> Actually the main problem is that many users seem to manage to operate
without an
> unZIPping utility anywhere on their command path... this makes it hard to
write a
> procedure which will work for all users, if the update package is a .ZIP
file. So
> I'm probably going to have to unZIP the file & place the constituent files
in
> local file store anyway. Might as well run a couple of virus scans whilst
I'm at
> it...
So make it a self extractor, where is the problem in that? In fact if it is
going to self extract you could compress with rar instead of zip and
increase the compression a bit.
- --
James Smith
[EMAIL PROTECTED]
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 09:05:44 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: [Mersenne] this setback
> With this setback, does it still make sense for machines slower than P-133
> to default to double checking, or should some of them go back to initial LL
> tests?
I think so ... of course, if you happen to disagree, you can
configure your own system to ask for only first tests irrespective of
the processor speed.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 13:48:33 +0000
From: "Steinar H . Gunderson" <[EMAIL PROTECTED]>
Subject: Mersenne: Re: Mersenne Digest V1 #544
(Sorry for replying to a digest, people... I haven't found an easy way to
extract and reply to a single message.)
On Mon, Apr 12, 1999 at 05:38:12PM -0700, Mersenne Digest wrote:
>> I would find a popup box a terrible nuisance, so I'd like an option
>> to turn it off or on, with default off.
>If it were an option, there should be a way for REALLY important alerts to
>get through, so that anyone running v17 would have been alerted about the
>bug even if normal alerting were turned off. Wouldn't you rather have some
>exceptions get through, with the decision about what qualifies as
>"exceptional" being made by George and/or Scott?
Have nobody considered the `good old' UNIX way? Especially with mprime, it
would be easy to send a _local_ e-mail to the `administrator' (ie. the
person who runs mprime). There is even a priority field in e-mail (although
I'm not sure if it is official or not), which could be utilized. Of course,
this would be a much bigger problem for Windows machines.
In general, I think the Primenet server should send out things like v17 bug
info in the future (via e-mail). Alternatively, it could reject all v17 clients,
but I suspect it already does that, and it could go months before the program
contacts the server and finds out. Perhaps we should have a `program
validation' function, in which the program _has_ to contact the Primenet
server (unless explicitly disabled by the user; not everybody has Internet
access...) before a certain amount of time.
/* Steinar */
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 13:59:28 +0000
From: "Steinar H . Gunderson" <[EMAIL PROTECTED]>
Subject: Mersenne: Single precision in consoles
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/5555Mhz or whatever, they still
_help_, much more than 486es.
/* Steinar */
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 13:44:59 -0400
From: "Ernst W. Mayer" <[EMAIL PROTECTED]>
Subject: Mersenne: GUI for Linux
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
- -Ernst
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 21:39:03 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: Mersenne: Unix versions for LL testing
Hello all,
I had a question from my brother who is interested in getting some of his
Unix boxes up and running. He was dismayed when he couldn't find any
versions that would use Primenet for automatic assignment.
So, I thought I'd ask, has anyone done any ports for the following that use
Primenet, or should I tell him to just use the manual testing page at
entropia:
a quad processor Sun box, a quad AS/400 and a single processor RS6000
I looked around on Conrad Curry's excellent page with links to ports of
various programs, but thought it'd be worth asking if anyone has had
experience with these machines running any prime number software, and what
they might share since the benchmark link doesn't seem to be working.
I'm looking to pick up a couple RS6000's sometime here so I should think
about finding a good program for that one myself.
Thanks,
Aaron
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 13 Apr 1999 23:41:22 -0700
From: "Scott Kurowski" <[EMAIL PROTECTED]>
Subject: Mersenne: RE: Mersenne Digest V1 #544
Hi all,
Please cc my direct address for any replies. I receive only the list
digests.
The Entropia.com team has expanded to five! We have added a new
PrimeNet support & operations engineer, Brad Bernard. Brad will soon
be picking up and answering traffic sent to <[EMAIL PROTECTED]>,
watching over the PrimeNet server, and helping George. I've known
Brad for 6 years, and know he'll continue making the job look much
easier than it really is.
[Shane:]
> There are a number of less intrusive options availible other
> than a message box which would REQUIRE user interaction.
> [...]
[Aaron:]
> Well, these are all good thoughts, let's see what George
> and Scott can do...they've already done so much as it is.
Shane's suggestions are closer to what we will probably do. PrimeNet
4.0 already supports client update notification, but we have yet to
decide how to best use it.
[Brian:]
> Interesting. rpcnet.dll from the v18 distribution is much
> smaller than that in the v17 distribution.
>
> Should be safe enough to keep the v17 distribution copy.
Yes, but it the v17 version uses a proxy running on the old PrimeNet
3.1 server's box. I'd rather everyone use HTTP if possible, or at
least use the updated v18 version dated 4/12/1999.
> Actually my systems are all using either http or the special
> rpcnet.dll used to connect to the PrimeNet Proxy server, so I just
> don't know how badly the v18 rpcnet.dll is broken.
The v18 program defaults to HTTP when you first install it, so new
users should not run into it. The PrimeNet FAQ page also describes
how to handle the RPC run-time library crash situation.
I've updated the posted v18.1 zips with a new RpcNet.dll. I couldn't
get it to crash. If you have an environment that can test this,
please do so and tell me how it went.
> Floris Looyesteyn ( who has to retest 2 7mil primes which
> were at 70%)
Floris, tell us which exponents those were and we'll credit your
account for the lost work.
[Martin:]
> Did someone else notice that the top producers lists on
> mersenne.org and entropia.com are inconsistent? Apparently,
> on mersenne.org the exponents that were affected by the
> V17-bug are no longer taken into account.
> Shouldn't this be dealt with consistently?
The GIMPS list and PrimeNet lists have never really been consistent.
They track different objectives, though I suppose we could be more
clear about calling attention to that.
GIMPS specifically reflects work accomplished toward a research
objective - completing valid LL primality test results. You lose time
to invalid results, factoring, earlier LL tests for numbers
subsequently factored, etc.
In contrast, PrimeNet simply tracks how much CPU time you gave in good
faith to GIMPS as part of its virtual machine. Primality tests,
factoring, double-checking, and even time lost to errors count. You
give the time to the networked project, and PrimeNet counts it.
Does anyone have AOL 4.0 working with Prime95 on a dialup account?
The problem I'm trying to solve for the FAQ page is how to configure
AOL to be the default dialup service so Prime95 checks AOL for a
connection, not Windows DUN. If Prime95's 'Use a dialup network
connection' box is checked, the symptom is Prime95 says there's no
dialup connection even when AOL's connection is open. Another symptom
is Prime95 causes the Windows dialup connection box to pop up instead
of AOL if the checkbox is off. One person told me he solved this by
configuring the AOL hotkeys, though I have no idea what this meant.
Best regards,
scott
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Wed, 14 Apr 1999 11:15:05 +0200 (CEST)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: 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
------------------------------
Date: Tue, 13 Apr 1999 19:16:53 -0400
From: Peter Doherty <[EMAIL PROTECTED]>
Subject: 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 +0000, 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/5555Mhz 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
------------------------------
Date: Wed, 14 Apr 1999 18:07:25 +0200
From: Guillermo Ballester Valor <[EMAIL PROTECTED]>
Subject: 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
------------------------------
Date: Wed, 14 Apr 1999 13:56:14 -0400
From: George Woltman <[EMAIL PROTECTED]>
Subject: 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
------------------------------
Date: Wed, 14 Apr 1999 15:37:58 -0400
From: Pierre Abbat <[EMAIL PROTECTED]>
Subject: 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
------------------------------
Date: Wed, 14 Apr 1999 19:45:36 -0000
From: [EMAIL PROTECTED]
Subject: 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
------------------------------
Date: Thu, 15 Apr 1999 02:01:18 +0200
From: "Robert Friberg" <[EMAIL PROTECTED]>
Subject: 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:
'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
------------------------------
Date: Thu, 15 Apr 1999 03:39:51 EDT
From: "Foghorn Leghorn" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Re: Factoring & bugs
>From: Paul Leyland <[EMAIL PROTECTED]>
>You are merely restating a law of nature. After a point, everything
>becomes useless.
I am reminded of a quote from Homer Simpson: "Trying is the first
step toward failure." :)
A question for George (and Scott): Is there any chance that Prime95's
ECM factoring will ever become automated as a part of PrimeNet? Even
if it is never given as a default type of assignment, it would still
be useful to dedicated number theory enthusiasts who want to run it
on more machines than they can manage manually.
_______________________________________________________________
Get Free Email and Do More On The Web. Visit http://www.msn.com
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #545
******************************
