4 ms·

I suspect that since every step is dependent on the previous one, it would not parallelize very well.

• pmjordan 16y ago
  Checking whether the current result is a palindrome will parallelise (split digit groups among processors), and you'd have to experiment with optimising the carry propagation for addition. My first guess would be to look at the last digits of the previous chunk, and if it's not clear whether they will produce a carry (i.e. if they sum to 9), calculate both possibilities in parallel until they converge. Once the information is available, fix up the indeterminate pieces. Intuitively, it seems like decimal representation actually is better than binary for this as the probability of producing large sequences of 9s is lower than that of large binary 1 sequences, although only by a constant factor of ln(2)/ln(10) ~ 0.3. It's certainly not trivial and requires a lot of communication between processors. The longer the numbers, the better, though. 300 million digits sounds like a suitable data set. (~150M bytes packed BCD, 4 copies of this will fit nicely into the currently tyical 1GB of graphics memory)
  • PassTheAmmo 16y ago
    Just keep them as BCD and add / xor them in parallel, as show here (under Packed BCD Arithmetic / addition): http://www.cs.uiowa.edu/~jones/bcd/bcd.html#packed http://www.cs.uiowa.edu/~jones/bcd/bcd.html#packed Then just keep track if at least one carry was generated instead of checking if the resulting number was a palindrome separately. Should be very fast.