Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Triangle Numbers Revisited

by tachyon (Chancellor)
on Oct 14, 2004 at 06:53 UTC ( [id://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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://399118]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (5)
As of 2024-03-29 07:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found