09-30-2008 01:22 AM - edited 09-30-2008 01:29 AM
Actually, it would be much better to search the pairs in transposed order, else the computation time depends strongly on the "upper limit" input. For example, with an upper limit of 100, we need to look at 766 sums before finding the first number and with an upper limit of 1000, its 7965 inspections. In addition, if the upper limit is set too high, we get false solutions due to overflow of the I32 cube calculation.
With the following code, the numbers are searched in a better order and the solution is found after only 57 sums, irrespecitve of the "upper limit" setting.
Both find the same solution. Still, both algorithms are theoretically flawed, because they both don't generate potential solutions in strictly ascending order, so how do we know that we really have the lowest of all potential solutions if we stop after the first match? For example if we set the upper limit at 1000 and generate all numbers that can be represented at least two ways as a sum of two cubes (1593 solutions), we can see that they are not found in sorted order. My transposed solutions is much better though, while my original solution is all over the place. Here are the candidates in the order found (the right panel is zoomed to for first 101 candidates, with the y axis mapped logarithmically).
09-30-2008 07:10 AM - edited 09-30-2008 07:10 AM
09-30-2008 10:05 AM
09-30-2008 10:28 AM
ShotSimon wrote:Would you like to choose the next puzzle challenge?
Taxicab(3) numbers are number that can be expressed three ways as a sum of two cubes.
Write a program that finds such a number number and displays it, including the three possible input pairs.
I would guess that your code style might take a long time, so we need something a bit faster.
4143 + 2553 = 87539319
4233 + 2283 = 87539319
4363 + 1673 = 87539319
Write a program that finds this solution and also displays the three pairs of factors.
We are looking for speed. The fastest code wins! 🙂
(A few trivial modifications of my solution will do this in well under 1 minute. So let's see who can do it the fastest :))
09-30-2008 11:32 AM
09-30-2008 12:00 PM
altenbach wrote:
Bonus problem: Write a program that finds all taxicab(3) numbers where the factors are all below 1000.
Just to raise the bar a bit, I wrote some simple LabVIEW code that finds all 8 solutions in under one second. 😄 Can you beat that?
(Yes, my solution can be improved quite a bit! There is a lot of slack left. ;))
09-30-2008 12:37 PM
I'm with you Altenbach, it runs in under 1 second on but I guess I could still improve it. I'll try to find a solution to remove the "Sort 1D" array from the process.
Olivier
09-30-2008 12:52 PM - edited 09-30-2008 12:53 PM
altenbach,
While all your previous solutions use a very small amount of code I'm having a hard time figuring out how to extract the numbers that came about generating the taxi number to begin with. The last pair is easy but the first pair is lost in the array as a sum
Also for your new problem I wanted to know if you count the time it takes to create a constant array of say all cubed values from 1 to 1000 towards the total time?
-SS
09-30-2008 12:54 PM - edited 09-30-2008 12:58 PM
You can do whatever you want als long as it is pure LabVIEW and honest code (no dll, no folded algorithm, i.e. upper limit must be a control).
And no, I don't precompute the cubes.
The totla time is everything, from start of the code to the result.
09-30-2008 07:54 PM - edited 09-30-2008 07:55 PM
OlivierL wrote:I'm with you Altenbach, it runs in under 1 second on but I guess I could still improve it. I'll try to find a solution to remove the "Sort 1D" array from the process.
I timed my version on an ancient Athlon XP 3200 that I had sitting around in the lab and it did it in about 275ms. Haven't tried on my core 2 Duo, but should be faster, even though the code is not optimized to use more than one core....
(I can switch it to give all taxicab(2) numbers (for all factors >1000) instead, which takes about the same amount of time).