3 years of computing... the palindrome quest | Hacker News Reader

3 years of computing... the palindrome quest

fourmilab.ch

48 pointsbootload19 comments

BTW, in case you missed it, this message is from 1990.

As of 2006 the 300 million digit mark has been reached.

Very interesting, heard about it before.

For anyone interested on today's state of knowledge, according to Wikipedia, there is still no known proof, but someone has reached the 13 Million digit mark without finding a palindrome:

"By May 1, 2006, VanLandingham had reached the 300 million digit mark (at a rate of one million digits every 5 to 7 days). A palindrome has yet to be found."

http://en.wikipedia.org/wiki/Lychrel_number

Maybe I did something wrong, but I've compiled and run the original code and it crunches 1.7 million digits per hour on an not too old Opteron. Did I miss something?

It probably takes longer when there are more digits.

For fun, I re-ran his million-digit calculation last night. What took three years starting in 1987 took 2:21:09 (2 hours, 21 minutes) on a 2006-vintage PC* and 1:38:55 on a 2010 laptop.

I got the same termination message (pass 2415836).

* Intel Core 2 Duo, model E6420, 80386 execution model. Intel Core/i7 Q720, x86-64 execution model.

Your numbers are in near-perfect agreement with Moore's Law, if we take it to mean computation time should halve every 1.5 years.

Your 2006 PC is about 20 years newer than the 1987 PC, which means it should calculate it (3 years)/2^(20/1.5) amount of time. That is, based on his computation time, and the amount of time elapsed to the building of your computer, we'd expect your computer take 153 minutes, or 2:32. That's only 11 minutes off of the actual result!

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.

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

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)

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.

For those who like programming challenges, there is a interesting Project Euler problem about Palindromes (Lychrel Number).

http://projecteuler.net/index.php?section=problems&id=55

Isn't the result of this undefined?

while (i--)

    *fp++ = *fp >> 4;

I'm sure he tested it and it does the right thing on his compiler/computer, but for anyone thinking of picking up the challenge...

The rule you're alluding to is that you mustn't modify the same value more than once between sequence points. I don't think that rule applies here, as it's modifying fp (a pointer value) and then the memory location at the address of fp's original value: the increment operator has higher precedence than dereferencing (which is of course an arbitrary rule I happen to have memorised, and many have not). The right hand side has no side effects.

It's certainly confusing code, but I'm fairly sure the outcome is well-defined. That doesn't mean it's good code: I'd never write it like that. I find this far easier to understand, and that's how I'd write it in practice:

  *fp >>= 4;
  ++fp;

The postfix while condition isn't one of my favourites either, but not quite as confusing.

I had to try it just because I wanted to know. With -Wall GCC says: pquest.c:279: warning: operation on 'fp' may be undefined

Not sure what 'may' means though

EDIT:

So to clarify, my suspicion is that the expression could mean either:

    *fp = *fp >> 4;
    *fp++;

    *fp = *(fp+1) >> 4;
    *fp++;

It is not the addressed value which is being incremented, but the pointer itself. There is no ambiguity.

I never claimed that the addressed value would be incremented, and that is not what is being discussed here, even though that too would have been a problem.

The thing is, at some point the compiler must calculate the address where to store the value. The question is then if there is a sequence point between calculating the data to store and the address which to store to. Otherwise there is ambiguity and the result is undefined.

According to http://en.wikipedia.org/wiki/Sequence_point there is no sequence point because of assignment (only initialization which this is not)

Btw was it you that downvoted my comment?

No, this is the same as:

  *fp = *fp >> 4;
  fp++;

http://c-faq.com/ptrs/unopprec2.html for details.

EDIT: formatting

You're right; it is.

According to the Standard: "Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be accessed only to determine the value to be stored."

What the second sentence says, is this: if an object is written to within a full expression, any and all accesses to it within the same expression must be directly involved in the computation of the value to be written. This rule effectively constrains legal expressions to those in which the accesses demonstrably precede the modification. For example, the old standby i = i + 1 is allowed, because the access of i is used to determine i's final value. The example

        *(fp++) = *fp >> 4; /* redundant parentheses */

is disallowed because one of the accesses of fp (the one in *fp) has nothing to do with the value which ends up being stored in fp (which happens over in fp++), and so there's no good way to define - either for our understanding or the compiler's - whether the access should take place before or after the modified value is stored.

Hence, the quoted statement does invoke undefined behaviour.

off-topic, but his little comment about interstellar travel is wrong. Even with exponential growth in propulsion technology, there is an optimal departure time for arriving earliest.

http://en.wikipedia.org/wiki/Wait_Calculation

(that equation was published long after this article was written though)

Reply on news.ycombinator.com