in reply to
Re: Triangle Numbers Revisited

in thread 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.