From Friday, April 19th (11:00 PM CDT) through Saturday, April 20th (2:00 PM CDT), 2024, ni.com will undergo system upgrades that may result in temporary service interruption.
We appreciate your patience as we improve our online experience.
BreakPoint
Code Miniatures!
Sorry, I can only test on my ancient laptop (~2006) at the moment, but here are some approximate times and solutions.
can ayone verify if these solutions are correct? (The longer solutions use I64 of course)
size time solution 06 129us 906609 08 60us 99000099 10 115ms 9966006699 12 30ms 999000000999 14 35s 99956644665999 16 6s 9999000000009999
@Jacobson-ni wrote:
That was a fun little puzzle. I ended up using the same amount of primitive functions as Altenbach did but only ended up sharing 2/11 primitives which I thought was pretty interesting.
Yours seems to be a few orders of magnitude slower, but you are using a completely different algorithm overall. 😄
@John_P1 wrote:
Mine is faster (for higher order cases anyway) when the answer does not include the maximum number in the range (e.g. 9998017 * 9997647). I'm doing the check like this:
Yes, there are many ways to roll the numbers and it depends where the solution is. I start both numbers from the top, but stop the current train once the product is less than the best found so far.
Here are the current numbers on my 3.1GHz Xeon. A current generation I7 would probably be quite a bit faster)
size time solution 06 35us 906609 08 13us 99000099 10 25ms 9966006699 12 7ms 999000000999 14 13s 99956644665999 16 2s 9999000000009999
@Jacobson-ni wrote:
Wouldn't this method possibly skip over the correct answer if we are looking for the largest number?
Well, we just need to keep the current largest and keep going until there are no larger products possible anymore.
The full search is
999999 * 999999
999999 * 999998
999999 * 999997
999999 * 999996
etc...
999998 * 999998
999998 * 999997
999998 * 999996
etc.
999997 * 999997
999997 * 999996
999997 * 999995
etc,
We terminate the inner loop if the product is less than the currently best. And terminate the outer loop (and the search!) if the square of the first number is less than the currently best.
@Jacobson-ni wrote:
Wouldn't this method possibly skip over the correct answer if we are looking for the largest number?
All numbers are tested in either algorithm (like Altenbach's, I move on to the next set once the product is below the best found palindromic number).
The space of products you have to check looks like this (e.g. the 2 digit case -- I blacked out the duplicates in the bottom left half of the graph):
Both algorithms start in the top left corner.
Altenbach's moves from left to right, moving down to the next row after each row is completed (or the exit criteria is met).
Mine moves from top to bottom, moving over to the next column after each column is completed (or the exit criteria is met).
My reason for slicing it this way is that the higher value products will mostly be tested first (e.g. checking 99*10 before checking 98*98 seems inefficient to me). As it turns out though, it is fairly common for the answer to fall on the top row so Altenbach's algorithm wins out in those cases. I think he also has some additional tricks to his that I am lacking (e.g. I'm still using the string conversion) that improve his performance.
Best Regards,
I was rewriting mine in terms of Jacobsons algorithm (Checking 6 digit numbers for palinomicity :D), then see if there is a product of two 3 digit numbers. Takes about 1ms for the original 6 digit problem. Probably could be improved.
Yes, your oder seems different but there is no clear winner.
Here are my preliminary times on the 3.1GHz Xeon for your input ordering. Still need to polish up the code....
size time solution 06 20us 906609 08 24us 99000099 10 2ms 9966006699 12 15ms 999000000999 14 520ms 99956644665999 16 7s 9999000000009999
A better way might be to sweep in a somewhat radial diagonal pattern such that the first one found is also the largest. 😄
