Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
YuckFoo once asked if there was a more efficient way to verify that any non-negative whole integer could be represented as the sum of 3 triangular numbers. particle came up with a pretty cool solution using bit strings. While fast, it blew up when I asked it for 987654321.
My usual approach to these kind of problems is to translate how I would solve the problem with a pencil and paper in code, make any obvious performance changes, and see if it is fast enough. I usually don't start thinking about more efficient algorithms unless it is a "challenge" or my initial approach was just plain abysmal. Here was my go at it:
#!/usr/bin/perl use strict; use warnings; my $target = defined $ARGV[0] ? $ARGV[0] : 987654321; print join ', ' , get_three( $target ); sub get_three { my $num = shift; my $prev = p_tri( $num ); return ($num, 0, 0) if ! $prev; while ( $prev ) { my $p_tri = ($prev * $prev + $prev) / 2; my $i = 0; my $j = $num - $p_tri; while ( $j >= $i ) { return $p_tri, $i, $j if ! p_tri( $i ) && ! p_tri( $j ); ++$i; --$j; } --$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; }
Now without explaining how this works*, I will ask the same question as YuckFoo - Any suggestions to optimize the search method?
Cheers - L~R
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Triangle Numbers Revisited
by FoxtrotUniform (Prior) on Oct 13, 2004 at 23:54 UTC | |
Just off the top of my head: In the inner while loop, it looks like you're testing each $i, $j to see if it's triangular (although I must confess, I don't really understand p_tri). Since we can enumerate triangle numbers (if Jobby is to be believed), why not iterate through those?
Edit 2: Oh, I get it, p_tri returns the rank of the previous triangular number, not the number itself... although it returns zero when given a triangular number, which is weird but useful. Edit 3: Here's the start of an implementation. It's not as fast as the code posted above (by about a factor of two, if Unix time is to be trusted), probably because it calculates a lot of trinums and makes a lot of function calls. I'm posting it more or less as a proof of concept. Edit 4: Inlining the calls to &trinum results in slightly faster code than Limbic~Region's. Code updated, benchmarks added. Read more... (2 kB)
-- | [reply] [Watch: Dir/Any] [d/l] [select] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 00:09 UTC | |
In HTML comments, I have provided a spoiler explanation of how the code works. Update: 2013-10-24 When I first wrote this node, we didn't have spoiler tags. The HTML comments remain but I have also added spoiler for those who don't want to view the source. <Reveal this spoiler or all in this thread>
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 02:34 UTC | |
The trouble with selecting a single number to benchmark from is that it may favor one method over the other. With this in mind, I created another rudimentary benchmark that shows the two methods are fairly equal: Read more... (2 kB)
I haven't spent any time thinking about optimizations, but if I come up with any tomorrow I will post it along with a "real" benchmark.
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] [select] |
by FoxtrotUniform (Prior) on Oct 14, 2004 at 04:43 UTC | |
The trouble with selecting a single number to benchmark from is that it may favor one method over the other. Good catch. Another problem I ran into was that the load on my test system was varying (lab machine, someone was logged in remotely doing a bunch of matlab foolery), so I ended up getting quite different "real" time results with the same input... which is probably what a casual reader would check. It would be interesting to know what kinds of inputs favour whose method, and (ideally) why. -- | [reply] [Watch: Dir/Any] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 04:54 UTC | |
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: Read more... (1365 Bytes)
From 1 minute to just over 3 seconds.
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
Re: Triangle Numbers Revisited
by tachyon (Chancellor) on Oct 14, 2004 at 06:53 UTC | |
Here is one way to make it
Read more... (2 kB) | [reply] [Watch: Dir/Any] [d/l] [select] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 13:21 UTC | |
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. | [reply] [Watch: Dir/Any] |
Re: Triangle Numbers Revisited
by hv (Prior) on Oct 14, 2004 at 12:47 UTC | |
I'm not sure quite how you might take advantage of it for optimisation, but the possible decompositions are restricted by the mod 3 equivalences. That is: so if we split the T_n sequence into A_n (== 0) and B_n (== 1) the possible decompositions are restricted such that:
You can get similar restrictions by considering other prime moduli, but 3 is likely to be the most beneficial because it has a shorter than possible cycle in T_n. Also, a word of warning on your p_tri() routine - the final result relies on comparing a floating point number for equality, normally considered a bad idea. It would be preferable to do the test instead by calculating from $t back up to the last known integer value, something like:
Hugo | [reply] [Watch: Dir/Any] [d/l] [select] |
Re: Triangle Numbers Revisited
by TedPride (Priest) on Oct 14, 2004 at 10:25 UTC | |
This is blazingly fast with numbers even several orders of magnitude larger than 987654321, and requires almost no memory to run. | [reply] [Watch: Dir/Any] [d/l] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 11:29 UTC | |
This is blazingly fast... I wanted to see just how fast, so I modified your code to fit into the benchmark FoxtrotUniform and I were playing with. It turns out your code is only about half as fast as my second version and it has a bug I didn't bother to track down. To see the bug, try entering 3133756 with your code. I say your code is only about half as fast because it got less than halfway through (line 2235 of 5000) when it blew up and it took approximately the same amount of time (3.619 seconds) to get there. In case you want to run some more tests yourself, take a look at gen_targets.pl and then use this modified code: Read more... (989 Bytes)
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
by TedPride (Priest) on Oct 14, 2004 at 11:52 UTC | |
| [reply] [Watch: Dir/Any] |
Re: Triangle Numbers Revisited
by tall_man (Parson) on Oct 14, 2004 at 18:09 UTC | |
The computation starts with a bigger number, but the calculations might be easier this way. I'll try it when I get a chance. Update: Here is code that takes advantage of a few things that are known about Diophantine quadratic problems. For example, it can convert multiples of two into smaller problems. It also screens out a few factors which would make a solution impossible. In many cases, it should be faster than the brute-force triangular number search.
| [reply] [Watch: Dir/Any] [d/l] [select] |
by tmoertel (Chaplain) on Oct 15, 2004 at 19:09 UTC | |
Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder | [reply] [Watch: Dir/Any] |
by tall_man (Parson) on Oct 15, 2004 at 19:30 UTC | |
There are choices for k that don't work. I want to eliminate them quickly and move on to the next k in the loop instead of spending time trying all combinations of i and j. Eventually I will find an answer, but that choice of k won't be part of it. For example, if N is a multiple of an odd power of 3, the quadratic problem can't be solved in integers. So I can eliminate about 1/3 of the possible choices for k. | [reply] [Watch: Dir/Any] [d/l] |
by tilly (Archbishop) on Oct 15, 2004 at 19:44 UTC | |
| [reply] [Watch: Dir/Any] |
by Limbic~Region (Chancellor) on Oct 15, 2004 at 22:27 UTC | |
Wow! It took a bit to make your code with my benchmark, but the results were quite impressive (25_000 random targets between 1 .. 9_999_999
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
Re: Triangle Numbers Revisited
by TedPride (Priest) on Oct 14, 2004 at 11:21 UTC | |
EDIT: Just needed a slight change to the first line after BING to prevent tget calls for 0: Incidently, I ran a looped version of this for all numbers 3-100000, and only the following could not be made with sums of three triangles: 4, 6, 11, 20, 29 As far as I can tell, all integers after 29 can be made with at least one sum of three triangles. The number of sums increases as you go along. | [reply] [Watch: Dir/Any] [d/l] |
by Limbic~Region (Chancellor) on Oct 14, 2004 at 12:53 UTC | |
Good catch! I didn't have time to track it down myself this morning as I was supposed to be getting ready for work. For the purposes of the original thread, it appears that 0 was being allowed as a triangular number. With that allowance, all numbers can indeed be the sum of 3 triangles.
As far as speed, you are right that this is quite fast. If it was not fast enough in a real problem you would likely use C as tachyon, the cheater, did ;-)
Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
Re: Triangle Numbers Revisited
by Limbic~Region (Chancellor) on Oct 14, 2004 at 20:49 UTC | |
I was having a conversation with blokhead in the CB concerning the most efficient solution to this problem. Not having any idea how to determine the big O notation, I ran a few tests to see how well my solution scaled. The first thing I noticed was the average number of guesses doubled every time I increased the search group by a factor of 10. Then I noticed something really cool - it also corresponded to a power of 2. This allowed me to calculate the average case scenario for any number Read more... (651 Bytes)
So for 12_345 you can expect 16.42, and for 123_456_789 you can expect 262.67 As you can see this scales quite well. While this is the average case, the worst case scenario should still scale reasonably well. Cheers - L~R | [reply] [Watch: Dir/Any] [d/l] |
Re: Triangle Numbers Revisited
by tall_man (Parson) on Oct 19, 2004 at 18:33 UTC | |
| [reply] [Watch: Dir/Any] [d/l] |
Re: Triangle Numbers Revisited
by ambrus (Abbot) on Oct 24, 2013 at 15:30 UTC | |
See also the later thread Write any natural number as sum of three triangular numbers. | [reply] [Watch: Dir/Any] |