The stupid question is the question not asked PerlMonks

### Re: Triangle Numbers Revisited

by tachyon (Chancellor)
 on Oct 14, 2004 at 06:53 UTC ( #399118=note: print w/replies, xml ) Need Help??

in reply to Triangle Numbers Revisited

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

cheers

tachyon

Replies are listed 'Best First'.
Re^2: Triangle Numbers Revisited
by Limbic~Region (Chancellor) on Oct 14, 2004 at 13:21 UTC
tachyon,
Nice, but since you decided to cheat, I am going to make you pay for it (compile time). I changed the gen_targets.pl to 10_000 random targets ranging from 1 .. 999_999_999. My solution completed in 25 seconds while yours took a whopping 36 seconds. I realize you only pay the compiling penalty once unless you change the code or run it from a different directory, but hey - I had to level the playing field some how. Incidently, your code ran in 10 seconds the second time around and would still win with the compiling penalty if the number of targets was large enough. Good Job.

Cheers - L~R

Update: If you want to go up to a billion, you are going to need to change the C code. I thought I was doing really well until I realized what was going on.

Create A New User
Node Status?
node history
Node Type: note [id://399118]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (2)
As of 2017-08-19 01:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (310 votes). Check out past polls.

Notices?