News for hackers. Stuff that matters.
Re:3 years of computing... the palindrome quest by pmjordan on Monday July 19, 2010 @07:21AM (#1528264)
Interesting; it's the first code I've seen in a long time that uses BCD (binary coded decimal) representation, and it actually makes sense in this case.

I don't know how widely this is known, but the x86 instruction set actually has native support for BCD(!). AMD removed the instructions in x86_64 to free up some valuable short opcodes.

In any case, it'd be interesting how fast this sort of search would be on a GPU, using OpenCL or so. Vectorising arbitrary-precision BCD arithmetic could be a fun puzzle.

Re:3 years of computing... the palindrome quest by afhof on Monday July 19, 2010 @08:53AM (#1528459)
I suspect that since every step is dependent on the previous one, it would not parallelize very well.
Re:3 years of computing... the palindrome quest by pmjordan on Monday July 19, 2010 @09:22AM (#1528535)
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)

Re:3 years of computing... the palindrome quest by PassTheAmmo on Monday July 19, 2010 @09:53AM (#1528615)
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

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.