5 ms·

3 years of computing... the palindrome quest

48 points by bootload 16y ago

edanm 16y ago
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 http://en.wikipedia.org/wiki/Lychrel_number
- wazoox 16y ago
  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?
  - ars 16y ago
    It probably takes longer when there are more digits.
DuoSRX 16y ago
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 http://projecteuler.net/index.php?section=problems&id=55
PassTheAmmo 16y ago
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...
- pmjordan 16y ago
  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.
  - PassTheAmmo 16y ago
    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: 1) *fp = *fp >> 4; *fp++; or 2) *fp = *(fp+1) >> 4; *fp++;
    - BrandonM 16y ago
      It is not the addressed value which is being incremented, but the pointer itself. There is no ambiguity.
      - PassTheAmmo 16y ago
        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 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?
pmjordan 16y ago
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.
- afhof 16y ago
  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.
ars 16y ago
BTW, in case you missed it, this message is from 1990. As of 2006 the 300 million digit mark has been reached.
kbob 16y ago
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.
- photon_off 16y ago
  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!
sushibowl 16y ago
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 http://en.wikipedia.org/wiki/Wait_Calculation (that equation was published long after this article was written though)

48 points by bootload 16y ago

edanm 16y ago

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 http://en.wikipedia.org/wiki/Lychrel_number

wazoox 16y ago
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?
- ars 16y ago
  It probably takes longer when there are more digits.

DuoSRX 16y ago

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 http://projecteuler.net/index.php?section=problems&id=55

PassTheAmmo 16y ago

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...

pmjordan 16y ago
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.
- PassTheAmmo 16y ago
  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: 1) *fp = *fp >> 4; *fp++; or 2) *fp = *(fp+1) >> 4; *fp++;
  - BrandonM 16y ago
    It is not the addressed value which is being incremented, but the pointer itself. There is no ambiguity.
    - PassTheAmmo 16y ago
      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 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?

pmjordan 16y ago

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.

afhof 16y ago
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.

ars 16y ago

BTW, in case you missed it, this message is from 1990. As of 2006 the 300 million digit mark has been reached.

kbob 16y ago

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.

photon_off 16y ago
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!

sushibowl 16y ago

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 http://en.wikipedia.org/wiki/Wait_Calculation (that equation was published long after this article was written though)