QM,
My latest obsession is with Perl internals, improving my C skills. Inline::C is a great way to do both, so I figured I would translate my previous code (minus the %seen cache). It actually loses when checking just one number, but running it in a loop of a lot of numbers it wins hands down.
#!/usr/bin/perl
use strict;
use warnings;
use Inline 'C';
use Math::Pari qw/factorint PARImat/;
my $num = $ARGV[0];
print nearest_sqrt($num, prime_factors( $num ) ) || 'prime';
sub prime_factors {
my $num = shift;
my %p_fact = PARImat( factorint( $num ) ) =~ /(\d+)/g;
return [ map { ($_) x $p_fact{$_} } keys %p_fact ];
}
__END__
__C__
int nearest_sqrt (double num, SV* input) {
int len = av_len((AV *)SvRV(input));
int tot = len + 1;
int i = 0;
double list[ tot ];
int position[ tot ];
int stop[ tot ];
double offset = -1;
int end_pos;
int done = 0;
int winner = 0;
int by = 0;
int next = 1;
while ( i <= len ) {
list[ i ] = SvNV(* av_fetch((AV *)SvRV(input), i, 0));
++i;
}
while ( done == 0 ) {
int j;
int cur;
double factor;
double diff;
if ( next == 1 ) {
int c = 0;
int p = 0;
int s = 0;
++by;
if ( by > tot ) break;
if ( by >= 2 ) {
for (p = 0; p <= by - 2; ++p) {
position[ p ] = p;
}
}
position[ p ] = by - 2;
end_pos = p;
for ( s = tot - by; s <= len; ++s ) {
stop[ c ] = s;
++c;
}
next = 0;
}
cur = end_pos;
while ( 1 ) {
if ( ++position[ cur ] > stop[ cur ] ) {
int k;
int new_pos;
position[ --cur ]++;
if ( position[ cur ] > stop[ cur ] ) continue;
new_pos = position[ cur ];
for (k = cur; k <= end_pos; ++k) {
position[ k ] = new_pos++;
}
}
break;
}
if ( position[0] == stop[0] ) {
if ( position[0] == tot ) {
done = 1;
}
else {
next = 1;
}
}
factor = 1;
for (j = 0; j <= end_pos; ++j) {
factor *= list[ position[ j ] ];
}
diff = (num / factor) - factor;
if ( diff >= 0 && (offset == -1 || diff < offset) ) {
winner = factor;
offset = diff;
}
}
return( winner );
}
I am sure someone more knowledgeable could make the C cleaner if not faster.
Updated - copy/paste fixed as sleepingsquirrel pointed out below
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|