Code Miniatures!

[GregSands]

Yes it's faster, though that mostly arises from being able to represent the "half" number as an I32, and do the reversal in I32 representation. Creating the "half" number (dividing by 10^digits) is relatively slow.

After a bit more thought I'd actually ended up with this palindrome check which is faster again, if written using I32s, but slower using I64. 

[GregSands]

Are you sure about 2ns for 3 digits?  Using I32s I still get ~40ns to check one number and 600ns to find the solution. For 4 digits I get 1.2us with I32s, but for I64s I get around 3.3us, and right up to 9 digits, I get times just less than twice as slow as yours.  

I don't have a problem with folding due to counting the number of checks that are made, but yes, that is something to watch for.

[altenbach]

---

@GregSands wrote:

Are you sure about 2ns for 3 digits?

---

Sotty, I mistyped. 2us.

[altenbach]

Yes, the Q&R on 64bit is slow, so it pays to do split once and do the rest in 32bit.

Here's a new version. (eliminating the repetition loop, but keeping the fastest time for each size).

(Old Core2 Quad)

digits size time   solution

   2    04    0ns   9009
   3    06  819ns   906609
   4    08  1.2us   99000099
   5    10   11us   9966006699
   6    12  108us   999000000999
   7    14   29ms   99956644665999
   8    16   12ms   9999000000009999
   9    18   5.4s   999900665566009999

And here are the times on my Xeon

digits size time   solution

   2    04    0ns   9009
   3    06  330ns   906609
   4    08  660ns   99000099
   5    10  6.9us   9966006699
   6    12   73us   999000000999
   7    14   19ms   99956644665999
   8    16    8ms   9999000000009999
   9    18   3.5s   999900665566009999

[GregSands]

---

@altenbach wrote:

Yes, the Q&R on 64bit is slow, so it pays to do split once and do the rest in 32bit.

Here's a new version. (eliminating the repetition loop, but keeping the fastest time for each size).

---

I'm very impressed.  It's been good fun trying to optimize a "simple" coding problem like this, both for code size and for speed - a lot of progress from the first attempts.  Even learnt a few things along the way - using Split Number instead of ToU32 is new to me.  And it's now very obvious that both String and Array comparisons are significantly slower - and by the same amount, which is perhaps not too surprising.

I don't think there are too many speed optimization possibilities left -- perhaps a parallel version of the inner loop?

Anyhow, looking forward to the next challenge...

[altenbach]

In just what a pianist would call "Fingerübungen", I had fun coding the brute force vertical, horizontal, and diagonal scans. Might come in handy in the future. 😄 For example if we would re-state the problem to "find all 2N digit palidromic products of two N digit numbers".

I also had really fast version that use lookup tables. For example for the 6 digit case, we need a table containing all elements where index array with a 3digit index would return the reversed number. Of course that gets unmanagable for more than 8 digits, unless we have unlimited RAM and LabVIEW 128 bit (:o). For the larger numbers we could e.g. split the 16 digit number into four 4-digit numbers, look them up, and compare them pairwise, etc.

The lookup tables can be included as diagram constants for ultimate speed, but code could be sped up even if always generating the table from scratch: Since the the brute force search algorithm looks at more elements than the lookup table contains, it is faster to generate the lookup table on the fly (and even include in the timing), than to use the reversal algorithm inside the main loops.

Yes, the substitution of split number (vs. to U32) was a new idea (for me). It does do less but is safe here because we don't care about the other part.

It was fun. I even learned something about the compiler as discussed elsewhere: A seemingly pointless wire forcing a different data dependency sped certain code up by over 6x. Ah, the secret art of code optimization! 😄

[altenbach]

Of course another interesting variations of the problem would be to find palindromic hexadecimally formatted numbers in the same way. That would allow significantly faster code of course because we can operate more lowlevel. No Q&R needed, for example. 😄