Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

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

Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://399106]
help
Chatterbox?
[ambrus]: MLX: if it's a work email, then it's probably not Uncle Sam that matters, but what the account managing server at work thinks your name is. Those can differ. For example, we've had two co-workers with identical real name at one point,
[ambrus]: so one got a stupid suffix in the email account (people have email address based on their real name here usually).

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (11)
As of 2017-01-19 14:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you watch meteor showers?




    Results (170 votes). Check out past polls.