News for hackers. Stuff that matters.
Re:A Formula for the Number of Days in Each Month by thaumasiotes on Tuesday December 09, 2014 @10:36AM (#8723293)
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" ;)
Re:A Formula for the Number of Days in Each Month by JadeNB on Wednesday December 10, 2014 @02:15PM (#8731048)
> What do you mean, but not higher? If you want a base-256 digit, calculate the two base-16 digits that make it up.

I'm sorry; you're quite right, and I was wrong.

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

I'm not sure why you say that I won't be able to handle large numbers as input. It might take a long time (like, a universe-endingly long time), but so would printing out the decimal expansion of 10↑↑10 (https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation), and I don't think that anyone would claim that that means that exponentiation algorithms "can't handle" this kind of exponentiation. (I dunno; maybe people would claim that.)

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

My problem is that I think that there is no such equivalence, unless the definition of 'formula' is made so broad as to be essentially synonymous with 'algorithm'—at which point it's true but un-interesting. All I am arguing is (as a constructivist would) that it is worthwhile to maintain meaningful distinctions.

> Also, I have to note that you've referred to the following mathematical result `pi = [elided]` as an "algorithm" instead of a "formula" ;)

I did not mean to do that; I was referring to the process of using that formula (which is, as it were, an 'inert' object) to produce hexadecimal digits as an algorithm.