### Re^2: Triangle Numbers Revisited

by Limbic~Region (Chancellor)
 on Oct 14, 2004 at 04:54 UTC ( #399106=note: print w/replies, xml ) Need Help??

in reply to Re: Triangle Numbers Revisited

FoxtrotUniform,
I couldn't sleep as I had several optimizations pop into my head I just had to try. I played around with caching known triangular numbers as well as results of known non-triangular numbers. I only got a marginal speed increase which I guessed would be the case earlier in the CB. Moving away from caching, I tried a combination of my method and your method with dramatic results:
```#!/usr/bin/perl
use strict;
use warnings;

my \$file = \$ARGV[0] || 'targets.txt';
open (INPUT, '<', \$file) or die "Unable to open \$file for reading : \$!
+";

while ( <INPUT> ) {
chomp;
get_three( \$_ );
}

sub get_three {
my \$num = shift;
my \$prev = p_tri( \$num );

return (\$num, 0, 0) if ! \$prev;

while ( \$prev ) {
my \$tri_1 = (\$prev * \$prev + \$prev) / 2;
my \$target = \$num - \$tri_1;
my \$next = gen_tri();
my \$tri_2 = \$next->();
while ( \$tri_2 <= \$target / 2 ) {
my \$tri_3 = \$target - \$tri_2;
return \$tri_1, \$tri_2, \$tri_3 if ! p_tri( \$tri_3 );
\$tri_2 = \$next->();
}
--\$prev;
}
die "Something went horribly wrong : \$num\n";
}

sub p_tri {
my \$num = shift;
my \$x = ( sqrt( 8 * \$num + 1 ) + 1 )/ 2;
my \$t = int \$x;
return \$t == \$x ? 0 : --\$t;
}

sub gen_tri {
my \$tri = 0;
my \$sum;
return sub { \$sum += \$tri++; return \$sum };
}
__END__

real    0m3.393s
user    0m3.344s
sys     0m0.050s
From 1 minute to just over 3 seconds.

Cheers - L~R

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2018-03-25 00:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (299 votes). Check out past polls.

Notices?