|Just another Perl shrine|
Triangle Numbers Revisitedby Limbic~Region (Chancellor)
|on Oct 13, 2004 at 23:37 UTC||Need Help??|
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:
Now without explaining how this works*, I will ask the same question as YuckFoo - Any suggestions to optimize the search method?
* If anyone wants to know, feel free to ask. If anyone wants to offer their own explanation, feel free to post.
Cheers - L~R