One of the most ironic things about C++ is that it has made people aware that ++C is better.
Why?
Because if C has a constructor, then a C++ compiler has to create a copy, and to do that it has to call the constructor on the copy made by the C++ call in case there are side-effects. Which can be expensive But ++C does not create a copy.:-)
But the temperatures reached in manufacturing the material are very different from the temperatures that they need to subject the entire craft to. If you don't believe me consider what temperatures steel is made at and ask if they ever have to heat the entire plane to that temperature...
And about hard drives. Moore's law is faster for them than for other components. If current trends continue the in the next decade it will become reasonable to replace RAM with miniature hard drives!
Not that implementation (clearly) but the same program works. It is quite fast per prime found. In fact it is so fast that storing long lists of primes is not done any more - it is faster to calculate them than to read them out of storage!
The barrier is that the number of primes out to n is about n/log(n), and so no matter how quickly you list primes, there are just too many primes to list.
So it is utterly useless for cryptographic purposes.
As a point of comparison, standard general-purpose math programs such as Mathematica can factor ~20 digit numbers (e 70 bits) on commodity hardware in a fraction of a second.
If you cannot come within shouting range of that, your algorithm is not likely to be interesting. If it does then it would be interesting is to know how your algorithm scales to, say, 30 digit numbers...
Ben
*I* can find primes fast!
on
SSH v. SRP
·
· Score: 2
It isn't very hard. Finding primes has little to do with factoring though...
Cheers, Ben
PS Here is a moderately efficient algorithm in an unefficient language:
#!/usr/bin/perl -w # primes - generate primes # Written for the PPT initiative by Jonathan Feinberg. # The algorithm was substantially modified by Benjamin Tilly. # See docs for license. use strict; #use integer; # faster, but cuts the maxint down $|++; my @primes = (2, 3, 5, 7, 11); # None have been tested my @next_primes = (); # Avoid redoing work
my $VERSION = '1.002';
END { close STDOUT || die "$0: can't close stdout: $!\n"; $? = 1 if $? == 255; # from die }
chomp(my $start = @ARGV ? $ARGV[0] : <STDIN>); my $end = $ARGV[1] || 2**32 - 1; for ($start, $end) { s/^\s*\+?(\d{1,10}).*/$1/ || die "$0: $_: illegal numeric format\n"; $_ > 2**32 - 1 && die "$0: $_: Numerical result out of range\n"; } primes ($start, $end); exit 0;
sub primes { my ($start, $end) = @_; return if $end <= $start; if ($start <= 2 and 2 < $end) { print "2\n"; } $start = 3 if $start == 1; # Don't report 1 as a prime $end--; # Reindex # Initialize the list of primes &more_primes($primes[-1]+1, int(2 * sqrt($end))); while (scalar @next_primes) { push @primes, @next_primes; # Careful, we need to ensure that # we get a prime past sqrt($end)... &more_primes($primes[-1]+1, int(2 * sqrt($end))); } my $from = $start-1; my $to = $from; until ($to == $end) { $from = $to + 1; $to = $from + 99999; # By default do 100,000 $to = $end if $end < $to; # Unless I can finish in one pass &more_primes($from, $to); print map {"$_\n"} @next_primes; # Print primes } } sub more_primes { # This adds to the list of primes until it reaches $max # or the square of the largest current prime (assumed odd) my $base = shift; my $max = shift; my $square = $primes[-1] * $primes[-1]; $max = $square if $square < $max; # Determine what to find primes to $base++ unless $base % 2; # Make the base odd $max-- unless $max %2; # Make the max odd $max = ($max - $base)/2; # Make $max into a count of odds return @next_primes = () if $max < 0; # Sanity check my @more = map {0} 0..$max; # Initialize array of 0's for the # odd numbers in our range shift @primes; # Remove 2 foreach my $p (@primes) { my $start; if ($base < $p * $p) { $start = ($p * $p - $base)/2; # Start at the square if ($max < $start) { # Rest of primes don't matter! last; } } else { # Start at first odd it divides $start = $base % $p; # Find remainder $start = $p - $start if $start; # Distance to first thing it divides $start += $p if $start %2; # Distance to first odd it divides $start = $start/2; # Reindex for counting over odd! } for (my $i = $start; $i <= $max; $i += $p) { $more[$i] = 1; } } unshift @primes, 2; # Replace 2 # Read off list of primes @next_primes = map {$_ + $_ + $base} grep {$more[$_] == 0} 0..$max; }
__END__
=head1 NAME
B<primes> - generate primes
=head1 SYNOPSIS
B<primes> [I<start> [I<stop>]]
=head1 DESCRIPTION
The B<primes> utility prints primes in ascending order, one per line, starting at or above I<start> and continuing until, but not including I<stop>. The I<start> value must be at least 0 and not greater than stop. The I<stop> value must not be greater than 4294967295. The default value of I<stop> is 4294967295.
When the primes utility is invoked with no arguments, I<start> is read from standard input. I<stop> is taken to be 4294967295. The I<start> value may be preceded by a single C<+>. The I<start> value is terminated by a non-digit character (such as a newline).
=head1 BUGS
B<primes> has no known bugs.
=head1 AUTHOR
The Perl implementation of I<factor> was written by Jonathan Feinberg, I<jdf@pobox.com> and Benjamin Tilly, I<ben.tilly@alumni.dartmouth.org>.
=head1 COPYRIGHT and LICENSE
This program is copyright (c) Jonathan Feinberg and Benjamin Tilly (1999).
This program is free and open software. You may use, modify, distribute, and sell this program (and any modified variants) in any way you wish, provided you do not restrict others from doing the same.
I have several times had discussions with people who wondered why TeX continues to exist when PostScript is more universally available and gives a sufficiently good resolution for practically any purpose. These people generally fail to appreciate the following:
PostScript is not guaranteed to give the same output from printer to printer, let alone over a period of decades.
PostScript cannot easily be altered for different output formats. (eg The author and a publisher may wish to use different sizes of paper, or a different bibliography style.)
Extracting content from PostScript is a very non-trivial process. TeX is simple ASCII.
PostScript is insecure. PostScript is a full programming language, and the equivalent of the root password is rarely changed snd the default value is generally known. (IIRC it is "000000". I may have the number of 0's wrong.)
Try editing a PostScript document (say to insert a correction). I dare you.:-)
So if you need to store formatted documents for archival purposes in a system where you may later need to output the documents in a different form, you should look at TeX...
As was pointed out there are a number of changes. This is not just a bug-fix. The biggest new item is Unicode support. If you have to do things like match patterns in multi-byte character sets, this will be really cool. If you don't it will still be a nice feature since a lot of things (eg the web, file-systems, etc) are moving towards Unicode as internationalization becomes more and more important.
The biggest "missing features" continue to be solid multi-threading, compilation, and solid 64-bit support. If you want the first one, rethink whether the fork model works. If you want the second think about embedding an interpreter. If you need the third I suggest getting used to opening pipes to and from programs that can handle large files...
A "cool feature" that was discussed (I have ignored the Perl development list for the last half year so I don't know if it is in) was embedding Perl and a directory structure in a zip format. Imagine shipping an executable which had an encrypted zip appended which was Perl, with your scripts, and a directory structure of all of the modules your script used...:-)
I believe that there never was a limit in the filesystem code. I don't know if the OS limitations have been lifted (I suspect they have). But a lot of applications won't "just work" and they won't "just work" on 64-bit machines either.
The problem is that to fix the 2GB limit you need to change every program to understand that they cannot just seek to an integer (or long) location. This kind of type change simply cannot be easily done, there are too many problems that can arise. Therefore even on 64-bit machines many programs only use 32-bit constructs and will require workarounds.
A sample problem? Perl programmers on 64-bit machines are advised not to open large files directly in Perl, but rather to open pipes to and from processes that can read and write the files. Fixing that requires compiling perl (the program is lower case) with still-experimental 64-bit support. There is nothing that could possibly be done at the OS level about this - the issues are internal to how perl was written.
Cheers, Ben
Reminds me of an old story
on
LonelyNet
·
· Score: 2
Friend of mine met someone in a newsgroup. Needed my help to get a chat set up. A few months later he took a vacation, met her. Not long after that they got married.
It was strange meeting her and saying, "You know I was the guy that showed your husband how to use newsgroups, and then how to use chat?"
BTW you are the only person that I have seen describe a past long-term live-in boyfriend as, "ex-common-law husband".
Cheers, Ben
PS Good luck on your marriage. I would try to think of some good advice, but I remember how much that sort of thing irritated me a decade ago next Tuesday..and yes, there is a reason that I can name that date so easily...:-)
The problems were not in Samba, they were in the Linux TCP-IP stack being a bottle-neck with 4 network cards. And Solaris has problems with slow file-systems. Samba itself performed just fine.
The same company was used a few days earlier by Microsoft. Microsoft won those tests. OTOH those tests were chosen by Microsoft and did not include any "contains" searches, the NT box was optimized, etc.
As Jeremy Allison said, everybody knows ahead of time who will win a particular test, and nobody will participate if they don't honestly think they are going to win. He said that when Linux' IP stack gets optimized and Solaris' file-system gets improved that you will see him repeat the Mindcraft benchmarks - but not until...
Everyone and their dog has shown that/.ers actually understand basic statistics. With a 1/37 million chance of a match between two people, and 660,000 people in the database, the odds of eventually coming up with a false positive eventually become quite high.
What not so many have pointed out is that the true odds are probably lower than 1/37 million. That figure is based on the contents of each loci being independently distributed. (With about 1/18 of a match at each loci.) Well we know that is strictly not true - after all a sibling of yours will have 1/64 of getting the same loci from the same source that you did. But are there any larger effects?
The answer is that there is. Suppose that some of the loci have a different distributions in frequency between anglo-saxons, Celts, and East Indians. Then the chance of finding a match between 2 East Indians could be far higher than they estimate. For instance if that 1/18 figure was changed to around 1/9, the chance of matching 2 East Indians now becomes about 1/530,000. Even if your database has only 50,000 East Indians in it, if an East Indian committed the crime, the chance of a false positive is around 10%. Much higher than you would expect. (I am using East Indians because I understand that they are a disliked racial minority in England. Substitute your favorite group if you wish.)
So the moral of the story? Not only is the technique going to inevitably produce false positives, but it is likely to do so in a racially biased manner!
What do you think about setting up an ongoing distributed scanning effort, to identify compromisable machines, and to get the owners to lock them down?
I would like your opinion both on whether this is doable and whether it would likely prove useful.
They have changed the story so often that I don't know what the current version is.
It is no secret that the top brass wants to kill the 9x line, they just have not been able to execute it. (And anything they can use to squeeze out more OS revenue seems to wind up taking precedence over long-term strategy...)
Here is a list of things I have seen, what am I missing?
Microsoft has a security patch for it (that breaks something of course)
Microsoft's benchmarks comparing 2000 to NT 4.0 have turned out to be bogus
The EU has opened an anti-trust investigation against Microsoft over some of the "features" in Windows 2000
Network administrators are being advised to not allow *ANY* Windows 2K clients on networks using a Unix-based DNS system. (The client tries to take over. Can you say "food fight"?)
Novell has devoted an entire section of its website to refuting Microsoft's claims about Windows 2K
Microsoft has lost a few more top executives
The Windows 9x line will have Yet Another Rev. This is claimed to be the last rev. Again.
Gee, when it comes out things could get very interesting...
Upon occasion I have needed to ask him direct questions or point things out. He has always answered me with direct, to the point, answers. Sure, they are short. But considering how many he must answer, I am astounded that he would continue to answer them.
Additionally go look through the Perl documentation. Tom has been working on that for years. He still is. That is patience.
As for being humble, if you ever find an occasion where Tom is wrong he admits it. Sincerely. Takes it to heart. Learns from it. Despite his many strongly-held positions, he has the humbleness to accept his mistakes and learn from them.
OK, so he is an excellent programmer. His hubris and pride are obvious. But exactly as Larry said, he also manages to be humble and patient.
It just isn't the sort of humbleness and patience that people would sometimes like to see from him...
In fact there is even a port of VB to Linux. See, for instance, Gnumeric.
OTOH VB itself is a language that I hate. I can understand how someone who had never dealt with a real language could be impressed by it, but personally for scripting I am much happier with Perl or Python than I ever was with VB.
Think of them as VB except easier to really learn, cross-platform, faster,...
Slashdot Mirror
One of the most ironic things about C++ is that it has made people aware that ++C is better.
:-)
Why?
Because if C has a constructor, then a C++ compiler has to create a copy, and to do that it has to call the constructor on the copy made by the C++ call in case there are side-effects. Which can be expensive But ++C does not create a copy.
Cheers,
Ben
HD vs RAM is what counts, and HD speed and density is improving faster than RAM.
Cheers,
Ben
I also don't see the static connection.
But the temperatures reached in manufacturing the material are very different from the temperatures that they need to subject the entire craft to. If you don't believe me consider what temperatures steel is made at and ask if they ever have to heat the entire plane to that temperature...
And about hard drives. Moore's law is faster for them than for other components. If current trends continue the in the next decade it will become reasonable to replace RAM with miniature hard drives!
Cheers,
Ben
I should fix that.
Cheers,
Ben
Not that implementation (clearly) but the same program works. It is quite fast per prime found. In fact it is so fast that storing long lists of primes is not done any more - it is faster to calculate them than to read them out of storage!
The barrier is that the number of primes out to n is about n/log(n), and so no matter how quickly you list primes, there are just too many primes to list.
So it is utterly useless for cryptographic purposes.
Cheers,
Ben
As a point of comparison, standard general-purpose math programs such as Mathematica can factor ~20 digit numbers (e 70 bits) on commodity hardware in a fraction of a second.
If you cannot come within shouting range of that, your algorithm is not likely to be interesting. If it does then it would be interesting is to know how your algorithm scales to, say, 30 digit numbers...
Ben
It isn't very hard. Finding primes has little to do with factoring though...
Cheers,
Ben
PS Here is a moderately efficient algorithm in an unefficient language:
#!/usr/bin/perl -w
# primes - generate primes
# Written for the PPT initiative by Jonathan Feinberg.
# The algorithm was substantially modified by Benjamin Tilly.
# See docs for license.
use strict;
#use integer; # faster, but cuts the maxint down
$|++;
my @primes = (2, 3, 5, 7, 11); # None have been tested
my @next_primes = (); # Avoid redoing work
my $VERSION = '1.002';
END {
close STDOUT || die "$0: can't close stdout: $!\n";
$? = 1 if $? == 255; # from die
}
chomp(my $start = @ARGV ? $ARGV[0] : <STDIN>);
my $end = $ARGV[1] || 2**32 - 1;
for ($start, $end) {
s/^\s*\+?(\d{1,10}).*/$1/ || die "$0: $_: illegal numeric format\n";
$_ > 2**32 - 1 && die "$0: $_: Numerical result out of range\n";
}
primes ($start, $end);
exit 0;
sub primes {
my ($start, $end) = @_;
return if $end <= $start;
if ($start <= 2 and 2 < $end) {
print "2\n";
}
$start = 3 if $start == 1; # Don't report 1 as a prime
$end--; # Reindex
# Initialize the list of primes
&more_primes($primes[-1]+1, int(2 * sqrt($end)));
while (scalar @next_primes) {
push @primes, @next_primes;
# Careful, we need to ensure that
# we get a prime past sqrt($end)...
&more_primes($primes[-1]+1, int(2 * sqrt($end)));
}
my $from = $start-1;
my $to = $from;
until ($to == $end) {
$from = $to + 1;
$to = $from + 99999; # By default do 100,000
$to = $end if $end < $to; # Unless I can finish in one pass
&more_primes($from, $to);
print map {"$_\n"} @next_primes; # Print primes
}
}
sub more_primes {
# This adds to the list of primes until it reaches $max
# or the square of the largest current prime (assumed odd)
my $base = shift;
my $max = shift;
my $square = $primes[-1] * $primes[-1];
$max = $square if $square < $max; # Determine what to find primes to
$base++ unless $base % 2; # Make the base odd
$max-- unless $max %2; # Make the max odd
$max = ($max - $base)/2; # Make $max into a count of odds
return @next_primes = () if $max < 0; # Sanity check
my @more = map {0} 0..$max; # Initialize array of 0's for the
# odd numbers in our range
shift @primes; # Remove 2
foreach my $p (@primes) {
my $start;
if ($base < $p * $p) {
$start = ($p * $p - $base)/2; # Start at the square
if ($max < $start) { # Rest of primes don't matter!
last;
}
}
else { # Start at first odd it divides
$start = $base % $p; # Find remainder
$start = $p - $start if $start; # Distance to first thing it divides
$start += $p if $start %2; # Distance to first odd it divides
$start = $start/2; # Reindex for counting over odd!
}
for (my $i = $start; $i <= $max; $i += $p) {
$more[$i] = 1;
}
}
unshift @primes, 2; # Replace 2
# Read off list of primes
@next_primes = map {$_ + $_ + $base} grep {$more[$_] == 0} 0..$max;
}
__END__
=head1 NAME
B<primes> - generate primes
=head1 SYNOPSIS
B<primes> [I<start> [I<stop>]]
=head1 DESCRIPTION
The B<primes> utility prints primes in ascending order, one per line,
starting at or above I<start> and continuing until, but not including
I<stop>. The I<start> value must be at least 0 and not greater than
stop. The I<stop> value must not be greater than 4294967295. The
default value of I<stop> is 4294967295.
When the primes utility is invoked with no arguments, I<start> is read
from standard input. I<stop> is taken to be 4294967295. The I<start>
value may be preceded by a single C<+>. The I<start> value is
terminated by a non-digit character (such as a newline).
=head1 BUGS
B<primes> has no known bugs.
=head1 AUTHOR
The Perl implementation of I<factor> was written by Jonathan Feinberg,
I<jdf@pobox.com> and Benjamin Tilly, I<ben.tilly@alumni.dartmouth.org>.
=head1 COPYRIGHT and LICENSE
This program is copyright (c) Jonathan Feinberg and Benjamin Tilly (1999).
This program is free and open software. You may use, modify, distribute,
and sell this program (and any modified variants) in any way you wish,
provided you do not restrict others from doing the same.
So if you need to store formatted documents for archival purposes in a system where you may later need to output the documents in a different form, you should look at TeX...
Cheers,
Ben
As was pointed out there are a number of changes. This is not just a bug-fix. The biggest new item is Unicode support. If you have to do things like match patterns in multi-byte character sets, this will be really cool. If you don't it will still be a nice feature since a lot of things (eg the web, file-systems, etc) are moving towards Unicode as internationalization becomes more and more important.
:-)
The biggest "missing features" continue to be solid multi-threading, compilation, and solid 64-bit support. If you want the first one, rethink whether the fork model works. If you want the second think about embedding an interpreter. If you need the third I suggest getting used to opening pipes to and from programs that can handle large files...
A "cool feature" that was discussed (I have ignored the Perl development list for the last half year so I don't know if it is in) was embedding Perl and a directory structure in a zip format. Imagine shipping an executable which had an encrypted zip appended which was Perl, with your scripts, and a directory structure of all of the modules your script used...
Cheers,
Ben
I believe that there never was a limit in the filesystem code. I don't know if the OS limitations have been lifted (I suspect they have). But a lot of applications won't "just work" and they won't "just work" on 64-bit machines either.
The problem is that to fix the 2GB limit you need to change every program to understand that they cannot just seek to an integer (or long) location. This kind of type change simply cannot be easily done, there are too many problems that can arise. Therefore even on 64-bit machines many programs only use 32-bit constructs and will require workarounds.
A sample problem? Perl programmers on 64-bit machines are advised not to open large files directly in Perl, but rather to open pipes to and from processes that can read and write the files. Fixing that requires compiling perl (the program is lower case) with still-experimental 64-bit support. There is nothing that could possibly be done at the OS level about this - the issues are internal to how perl was written.
Cheers,
Ben
Friend of mine met someone in a newsgroup. Needed my help to get a chat set up. A few months later he took a vacation, met her. Not long after that they got married.
:-)
It was strange meeting her and saying, "You know I was the guy that showed your husband how to use newsgroups, and then how to use chat?"
BTW you are the only person that I have seen describe a past long-term live-in boyfriend as, "ex-common-law husband".
Cheers,
Ben
PS Good luck on your marriage. I would try to think of some good advice, but I remember how much that sort of thing irritated me a decade ago next Tuesday..and yes, there is a reason that I can name that date so easily...
What evidence do you have for that?
Mindcraft?
The problems were not in Samba, they were in the Linux TCP-IP stack being a bottle-neck with 4 network cards. And Solaris has problems with slow file-systems. Samba itself performed just fine.
Regards,
Ben
The same company was used a few days earlier by Microsoft. Microsoft won those tests. OTOH those tests were chosen by Microsoft and did not include any "contains" searches, the NT box was optimized, etc.
As Jeremy Allison said, everybody knows ahead of time who will win a particular test, and nobody will participate if they don't honestly think they are going to win. He said that when Linux' IP stack gets optimized and Solaris' file-system gets improved that you will see him repeat the Mindcraft benchmarks - but not until...
Cheers,
Ben
Anyone who has not read it, should read How to Lie With Statistics. Highly recommended for becoming alert to a lot of tricks like this one.
Cheers,
Ben
When the second release of BO was GPLed, the Cult of the Dead Cow presentation involved someone running from the room yelling, "Open sores!"
So no, Bob didn't invent that phrase.
Cheers,
Ben
PS OTOH I expect in time to see tyop show up in a dictionary....
Everyone and their dog has shown that /.ers actually understand basic statistics. With a 1/37 million chance of a match between two people, and 660,000 people in the database, the odds of eventually coming up with a false positive eventually become quite high.
What not so many have pointed out is that the true odds are probably lower than 1/37 million. That figure is based on the contents of each loci being independently distributed. (With about 1/18 of a match at each loci.) Well we know that is strictly not true - after all a sibling of yours will have 1/64 of getting the same loci from the same source that you did. But are there any larger effects?
The answer is that there is. Suppose that some of the loci have a different distributions in frequency between anglo-saxons, Celts, and East Indians. Then the chance of finding a match between 2 East Indians could be far higher than they estimate. For instance if that 1/18 figure was changed to around 1/9, the chance of matching 2 East Indians now becomes about 1/530,000. Even if your database has only 50,000 East Indians in it, if an East Indian committed the crime, the chance of a false positive is around 10%. Much higher than you would expect. (I am using East Indians because I understand that they are a disliked racial minority in England. Substitute your favorite group if you wish.)
So the moral of the story? Not only is the technique going to inevitably produce false positives, but it is likely to do so in a racially biased manner!
Regards,
Ben
We have every reason to believe that once this hits production use, many more will be discovered. How many? No idea.
Also Microsoft has a history of saying that things anyone else would call a bug is not a bug.
Glad I am not planning to use this...
Cheers,
Ben
What do you think about setting up an ongoing distributed scanning effort, to identify compromisable machines, and to get the owners to lock them down?
I would like your opinion both on whether this is doable and whether it would likely prove useful.
Thanks,
Ben
That is the new standard in reliability they are setting.
Cheers,
Ben
They have changed the story so often that I don't know what the current version is.
It is no secret that the top brass wants to kill the 9x line, they just have not been able to execute it. (And anything they can use to squeeze out more OS revenue seems to wind up taking precedence over long-term strategy...)
Cheers,
Ben
Here is what Novell has to say on this.
Cheers,
Ben
Gee, when it comes out things could get very interesting...
Ben
Take another look at its tail...
Cheers,
Ben
Seriously.
Upon occasion I have needed to ask him direct questions or point things out. He has always answered me with direct, to the point, answers. Sure, they are short. But considering how many he must answer, I am astounded that he would continue to answer them.
Additionally go look through the Perl documentation. Tom has been working on that for years. He still is. That is patience.
As for being humble, if you ever find an occasion where Tom is wrong he admits it. Sincerely. Takes it to heart. Learns from it. Despite his many strongly-held positions, he has the humbleness to accept his mistakes and learn from them.
OK, so he is an excellent programmer. His hubris and pride are obvious. But exactly as Larry said, he also manages to be humble and patient.
It just isn't the sort of humbleness and patience that people would sometimes like to see from him...
Cheers,
Ben
In fact there is even a port of VB to Linux. See, for instance, Gnumeric.
...
OTOH VB itself is a language that I hate. I can understand how someone who had never dealt with a real language could be impressed by it, but personally for scripting I am much happier with Perl or Python than I ever was with VB.
Think of them as VB except easier to really learn, cross-platform, faster,
Cheers,
Ben