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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|