Here is one way to make it 30x 150x faster using your 5000 random number bench. Kinda cheating of course and still room for more optimisation.
[root@devel3 root]# time ./trinum.pl >out
real 0m41.310s
user 0m41.310s
sys 0m0.000s
[root@devel3 root]# time ./trinum_c2.pl >out
real 0m0.276s
user 0m0.280s
sys 0m0.000s
[root@devel3 root]# more trinum_c2.pl
#!/usr/bin/perl
use Inline 'C';
my $file = $ARGV[0] || 'targets.txt';
open (INPUT, '<', $file) or die "Unable to open $file for reading : $!
+";
while ( <INPUT> ) {
chomp;
get_three( $_ );
}
__END__
__C__
#include <math.h>
#define TRI(i) (i*(i+1)/2)
int get_three ( int num ) {
register max,target,i,j;
max = (int)sqrt((double)(2*num));
while ( max != 0 ) {
target = num - TRI(max);
for( i=0;TRI(i)<=target;i++ ) {
for( j=0;j<=i;j++ ) {
if ( target == (int)(TRI(i)+TRI(j)) ) {
printf( "%d, %d, %d\n", TRI(max), TRI(i), TRI(j) )
+;
return 1;
}
}
}
max--;
}
printf( "Something went horribly wrong : %d\n", num );
return 0;
}
[root@devel3 root]#
This was the original try which was only 30x faster and took over a whole second to run :-)
[root@devel3 root]# time ./trinum_c.pl >out_c
real 0m1.158s
user 0m1.150s
sys 0m0.000s
[root@devel3 root]# cat trinum_c.pl
#!/usr/bin/perl
use Inline 'C';
my $file = $ARGV[0] || 'targets.txt';
open (INPUT, '<', $file) or die "Unable to open $file for reading : $!
+";
while ( <INPUT> ) {
chomp;
get_three( $_ );
}
__END__
__C__
#include <math.h>
int p_tri( int num ) {
double x;
int t;
x = ( sqrt( 8 * (double)num + 1 ) + 1 )/ 2;
t = (int)x;
return (double)t == x ? 0 : t;
}
int get_three ( int num ) {
register prev,i,j,tri;
if ( ! (prev = p_tri( num )) ) {
printf( "%d, 0, 0\n", num );
return 1;
}
while ( --prev ) {
for( tri=prev*(prev+1)/2,i=0,j=num-tri; j>=i; j--,i++ ) {
if ( 0==p_tri(i) && 0==p_tri(j) ) {
printf( "%d, %d, %d\n", tri, i, j );
return 1;
}
}
}
printf( "Something went horribly wrong : %d\n", num );
return 0;
}
[root@devel3 root]#