Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
- A problem with Math::Prime::XS
- 02-14-2006
posted on
February 14, 2006, 5:35 pm
February 14, 2006, 5:35 pm
I don't know what exactly the problem is with this module.
But watch this:
1st program:
---------------------------------------------------------
#!/usr/bin/perl
use warnings;
use strict;
use Math::Prime::XS qw( is_prime );
die( 'please specify a number' ) unless ( @ARGV == 1 );
my $num = $ARGV[0];
if ( is_prime( $num ) ) {
print "$num is prime.\n";
} else {
print "$num is not prime.\n";
}
---------------------------------------------------------
2nd program:
---------------------------------------------------------
#!/usr/bin/perl
use warnings;
use strict;
use bigint;
die( 'please specify a number' ) unless ( @ARGV == 1 );
my $num = $ARGV[0];
if ( is_prime( $num ) ) {
print "$num is prime.\n";
} else {
print "$num is not prime.\n";
}
sub is_prime {
my ( $num ) = @_;
if ( ( ( $num % 2 ) == 0 ) || ( $num <= 3 ) || ( $num !~ /^\d+$/ )
) {
return 0;
}
for ( my $check_num = 3; $check_num <= int( sqrt( $num ) );
$check_num+=2 ) {
if ( ( $check_num % 5 ) == 0 ) {
next;
} elsif ( ( $num % $check_num ) == 0 ) {
return 0;
}
}
return 1;
}
---------------------------------------------------------
I know that the script I wrote is not very good or very smart. But take
a look in the results:
ofer@nettux:~/scripts/prime_numbers$ time ./prime_using_xs.pl 123456
123456 is not prime.
real 0m9.196s
user 0m8.837s
sys 0m0.008s
ofer@nettux:~/scripts/prime_numbers$ time ./my_prime_check.pl 123456
123456 is not prime.
real 0m0.064s
user 0m0.052s
sys 0m0.012s
ofer@nettux:~/scripts/prime_numbers$ time ./prime_using_xs.pl 1234567
Segmentation fault
real 0m0.015s
user 0m0.012s
sys 0m0.004s
ofer@nettux:~/scripts/prime_numbers$ ./my_prime_check.pl 1234567
1234567 is not prime.
Anybody knows what is wrong with Math::Prime::XS?
Re: A problem with Math::Prime::XS
Also sprach ofer@ilunix.org:
It's broken beyond repair.
The module is doing extremely stupid things. Here's something funny from
its PODs:
[ some benchmarks ]
Bear in mind, that these results are not too reliable as the author
could neither increase the number nor the iteration count provided,
because if he attempted to do so, perl would report "Out of
memory!", which was most likely caused by the Sieve of Eratosthenes
algorithm, which is rather memory exhaustive by implementation.
No, it's not caused at all by that but rather by this:
void
xs_is_prime(number)
long number
PROTOTYPE: $
INIT:
long primes[number], psum[number];
long i, n, pcount, square_root;
bool is_prime;
For your input of 1234567, this will try to create two arrays 'primes'
and 'psum' of longs, each 1234567 elements long on the stack! This
hurts.
And if the author of that package isn't able to come up with an
implementation of the Sieve of Eratosthenes that gets away with only a
few megabytes at most, then he is not to be trusted.
With the exception of mod_primes, all functions in that module behave
abnormally with respect to runtime and memory consumption. I'd stay away
from that module.
Tassilo
--
use bigint;
$n=71423350343770280161397026330337371139054411854220053437565440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
Re: A problem with Math::Prime::XS
Also sprach ofer@ilunix.org:
[...]
I wouldn't bother with trying to fix the module. A prime number test can
easily be written unless you are dealing with very big numbers.
use Inline C => <<'EOC';
int is_prime (double number) {
long long i;
long long bound = sqrt(num);
long long num = number;
for (i = 2; i <= bound; ++i) {
if (num % i == 0)
return 0;
}
return 1;
}
EOC
for ($_ = (1<<31)-1; $_ ; $_--) {
print "$_ is prime\n" if is_prime($_);
}
__END__
2147483647 is prime
2147483629 is prime
2147483587 is prime
2147483579 is prime
2147483563 is prime
2147483549 is prime
...
So for a given number in the 32bit range the above is_prime is
reasonably fast. Numbers in the 48bit range already take a few seconds
to compute here. There is probably a threshold at which you want to
start using a more sophisticated (indeterministic) method, such as
Miller-Rabin.
Tassilo
--
use bigint;
$n=71423350343770280161397026330337371139054411854220053437565440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
Re: A problem with Math::Prime::XS
Also sprach Ilya Zakharevich:
Yes, it is in C99 (the arrays will be allocated using alloca(3)). Are
you merely asking or implying that code like the above should be
endorsed because it is in the standard now? I hope you were just asking.
:-)
To me this is a feature that I am sure will be abused to shoot oneself
in the foot to an unbearable extent. Just as we've seen here. I am just
waiting for something like that to appear in actual code:
char* convenient_malloc (unsigned int n) {
char ary[n];
return ary;
}
Tassilo
--
use bigint;
$n=71423350343770280161397026330337371139054411854220053437565440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
Re: A problem with Math::Prime::XS
[A complimentary Cc of this posting was sent to
Tassilo v. Parseval
a) Since this construct is not in previous standards, a module using
such a construct is of questionable portability.
b) I did not know that it actually is C99 (given that I do not know in
which cases C99 is guaranteed to be supported, I never bothered to
be sure what it changed)
Com'on, we all saw code much worse than this... ;-)
Yours,
Ilya
Site Timeline
- » WWW::Mechanize cannot find the form.
- — Next thread in » PERL Modules Announcements
- » postscript and charting/graphing
- — Previous thread in » PERL Modules Announcements
- » Updating the hash across the files
- — Newest thread in » PERL Modules Announcements
- » HTML 5 validation software?
- — The site's Newest Thread. Posted in » HTML Authoring Forum