Click here to get back home

A problem with Math::Prime::XS
 Home | NewsGroups | Search | About
Login Password
Register Now!
 comp.lang.perl.modules    Post an article   get this group's latest topics as an RSS feed add this group's latest topics to your My MSN content add this group's latest topics to your My Yahoo content
Subject Author Date
A problem with Math::Prime::XS ofer 02-14-2006
Posted by ofer on February 14, 2006, 12:35 pm
Please log in for more thread options

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?


Posted by Tassilo v. Parseval on February 14, 2006, 3:07 pm
Please log in for more thread options

Also sprach ofer@ilunix.org:

> I don't know what exactly the problem is with this module.

It's broken beyond repair.

> 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";
> }

> ofer@nettux:~/scripts/prime_numbers$ time ./prime_using_xs.pl 1234567
> Segmentation fault
>
> real 0m0.015s
> user 0m0.012s
> sys 0m0.004s

> Anybody knows what is wrong with Math::Prime::XS?

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);

Posted by ofer on February 15, 2006, 9:34 am
Please log in for more thread options



Tassilo v. Parseval wrote:
> Also sprach ofer@ilunix.org:
>
> > I don't know what exactly the problem is with this module.
>
> It's broken beyond repair.
>
> > 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";
> > }
>
> > ofer@nettux:~/scripts/prime_numbers$ time ./prime_using_xs.pl 1234567
> > Segmentation fault
> >
> > real 0m0.015s
> > user 0m0.012s
> > sys 0m0.004s
>
> > Anybody knows what is wrong with Math::Prime::XS?
>
> 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);

Heh okay I understand... Thank you for your answer.
Should I try and rewrite it so it will work better? Maybe other module
can perform this test?


Posted by Tassilo v. Parseval on February 15, 2006, 11:33 am
Please log in for more thread options


Also sprach ofer@ilunix.org:

> Tassilo v. Parseval wrote:
>> Also sprach ofer@ilunix.org:
>>
>> > I don't know what exactly the problem is with this module.

[...]

>> 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.

> Heh okay I understand... Thank you for your answer.
> Should I try and rewrite it so it will work better? Maybe other module
> can perform this test?

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);

Posted by ofer on February 15, 2006, 3:33 pm
Please log in for more thread options


Got it :) Thank you!


Similar ThreadsPosted
problem when installing Math::BigInt::GMP ... March 12, 2007, 6:55 pm
problem installing MATH::MATLAB module August 28, 2006, 10:50 am
GMP::Math ...PLEASE HELP!! February 7, 2005, 11:02 am
Math::TrulyRandom May 22, 2006, 9:56 pm
Help with Math::GMP compile on AIX 5.3 September 11, 2007, 4:47 pm
Math-Random-MT-Auto-4.08.00.tar.gz September 18, 2005, 12:16 am
Math::Macopt version 0.01 available January 9, 2006, 9:21 pm
Math::Pari headaches August 15, 2006, 1:50 pm
Memory Leak in Math::Pari December 16, 2004, 6:21 am
proposal for new module -- Math::TriangularNumbers February 21, 2005, 10:19 pm

Our other projects:

Art Dolls, Fairies and Mermaids - Sunnyfaces.net

Roy's Linux, Programming and Search Engines messages

1-Script XML SitemapXML Sitemap