4 ms·

> How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as the

by chime 12y ago

> How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as they put in some time apparently, but was just curious. Zeller's Congruence is an algorithm. This is a formula. It made it to the front page because it was a clever hack and people like me love those.

thaumasiotes 12y ago
Zeller's Congruence is a formula as well (well, more than one depending on which calendar you want to use). Go look at the wikipedia article. More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. What distinction are you trying to draw?
- JadeNB 12y ago
  > More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. For example, what is the formula for the algorithm "on input `n`, output the first position in the decimal expansion of `pi` at which a copy of the decimal expansion of `n` begins"?
  - thaumasiotes 12y ago
    The fact that I can't tell you a formula doesn't mean there isn't one. For example, it's trivial for me to come up with input for that problem that you (or anyone else in the world) would be unable to solve. When the answers are unknown, I don't find it all that surprising that it's difficult to list or otherwise classify them. If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.
    - JadeNB 12y ago
      > If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. If you allow a formula to be an infinite look-up table, then the statement "every [always halting] algorithm is a fixed formula" becomes true, but, I think, almost meaningless—it just says that the algorithm produces an output for every input. This is what I meant by saying: This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. > On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose. No 'may' about it—it is possible to find the hexadecimal (and thus binary, 'quaternary', or octal, but not higher) digits using this algorithm. However, the discoverers explicitly disclaim its utility for finding decimal digits of pi in this way, and, indeed, say that no such 'look-ahead' algorithm is known (see p. 55 of http://link.springer.com/article/10.1007%2FBF03024340 http://link.springer.com/article/10.1007%2FBF03024340).
      - thaumasiotes 12y ago
        What do you mean, but not higher? If you want a base-256 digit, calculate the two base-16 digits that make it up. That's actually a simpler process than you'd have to go through for the nth octal digit (compare -- the second octal digit of pi is composed of, as high bit, the low bit of the first hex digit, followed by the two high bits of the second hex digit. But the 8th 256-ary digit of pi is just the concatenation of the 15th and 16th hex digits). In general, since you can calculate any adjacent 4 bits of the binary expansion, you can then aggregate those bits however you like, making it easy to get the nth digit in any power of two. The only complication is that, since you generate bits in blocks of four, you may end up having calculated as many as 6 bits that you didn't need. You object to my characterizing the pi-reading function you describe as an infinite lookup table. But it can't be implemented as an "intuitive" algorithm either. No matter how you code a function to solve that problem, it will always be trivial to provide input that your function cannot handle (if you have a representation of pi that you search, then you're relying on an infinite lookup table. If you calculate pi on the fly, you won't be able to handle large numbers as input). So I don't see why a defective (because you don't have enough time, or space, to run it) algorithm tranforming into a defective (because you don't have enough space to store it, but hey, time is no longer a concern) formula is a big problem for the equivalence between algorithms and formulae. Also, I have to note that you've referred to the following mathematical result: pi = \sum_{k=0}^\infty (16^{-k} * [4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6)]) as an "algorithm" instead of a "formula" ;)

by chime 12y ago

thaumasiotes 12y ago

Zeller's Congruence is a formula as well (well, more than one depending on which calendar you want to use). Go look at the wikipedia article. More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. What distinction are you trying to draw?

JadeNB 12y ago
> More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. For example, what is the formula for the algorithm "on input `n`, output the first position in the decimal expansion of `pi` at which a copy of the decimal expansion of `n` begins"?
- thaumasiotes 12y ago
  The fact that I can't tell you a formula doesn't mean there isn't one. For example, it's trivial for me to come up with input for that problem that you (or anyone else in the world) would be unable to solve. When the answers are unknown, I don't find it all that surprising that it's difficult to list or otherwise classify them. If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.
  - JadeNB 12y ago
    > If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. If you allow a formula to be an infinite look-up table, then the statement "every [always halting] algorithm is a fixed formula" becomes true, but, I think, almost meaningless—it just says that the algorithm produces an output for every input. This is what I meant by saying: This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. > On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose. No 'may' about it—it is possible to find the hexadecimal (and thus binary, 'quaternary', or octal, but not higher) digits using this algorithm. However, the discoverers explicitly disclaim its utility for finding decimal digits of pi in this way, and, indeed, say that no such 'look-ahead' algorithm is known (see p. 55 of http://link.springer.com/article/10.1007%2FBF03024340 http://link.springer.com/article/10.1007%2FBF03024340).
    - thaumasiotes 12y ago
      What do you mean, but not higher? If you want a base-256 digit, calculate the two base-16 digits that make it up. That's actually a simpler process than you'd have to go through for the nth octal digit (compare -- the second octal digit of pi is composed of, as high bit, the low bit of the first hex digit, followed by the two high bits of the second hex digit. But the 8th 256-ary digit of pi is just the concatenation of the 15th and 16th hex digits). In general, since you can calculate any adjacent 4 bits of the binary expansion, you can then aggregate those bits however you like, making it easy to get the nth digit in any power of two. The only complication is that, since you generate bits in blocks of four, you may end up having calculated as many as 6 bits that you didn't need. You object to my characterizing the pi-reading function you describe as an infinite lookup table. But it can't be implemented as an "intuitive" algorithm either. No matter how you code a function to solve that problem, it will always be trivial to provide input that your function cannot handle (if you have a representation of pi that you search, then you're relying on an infinite lookup table. If you calculate pi on the fly, you won't be able to handle large numbers as input). So I don't see why a defective (because you don't have enough time, or space, to run it) algorithm tranforming into a defective (because you don't have enough space to store it, but hey, time is no longer a concern) formula is a big problem for the equivalence between algorithms and formulae. Also, I have to note that you've referred to the following mathematical result: pi = \sum_{k=0}^\infty (16^{-k} * [4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6)]) as an "algorithm" instead of a "formula" ;)