A problem with Math::Prime::XS

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:

> 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=714233503437702801613970263303373711390544118542200534375 65440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);

Re: A problem with Math::Prime::XS

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=714233503437702801613970263303373711390544118542200534375 65440;
> $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?

Re: A problem with Math::Prime::XS

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=714233503437702801613970263303373711390544118542200534375 65440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);

Re: A problem with Math::Prime::XS

Got it :) Thank you!

Re: A problem with Math::Prime::XS

[A complimentary Cc of this posting was sent to
Tassilo v. Parseval
], who wrote in article <45erkeF6esajU1@news.dfncis.de>:

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

Wow? Is it in C99, or what?

Thank,
Ilya

Re: A problem with Math::Prime::XS

Also sprach Ilya Zakharevich:

> [A complimentary Cc of this posting was sent to
> Tassilo v. Parseval
>], who wrote in article <45erkeF6esajU1@news.dfncis.de>:
>
>> 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!
>
> Wow? Is it in C99, or what?

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=714233503437702801613970263303373711390544118542200534375 65440;
$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
], who wrote in article <45itn3F6ptofU1@news.dfncis.de>:
> Also sprach Ilya Zakharevich:
>
> > [A complimentary Cc of this posting was sent to
> > Tassilo v. Parseval
> >], who wrote in article <45erkeF6esajU1@news.dfncis.de>:
> >
> >> 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!
> >
> > Wow? Is it in C99, or what?
>
> 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.
> :-)

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)

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

Com'on, we all saw code much worse than this... ;-)

Yours,
Ilya