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]#
[download]

[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]#
[download]