baez@x.ucr.edu (john baez) (02/08/90)
In article <Cw-w0q2@cs.psu.edu> callahan@cs.psu.edu (Paul B. Callahan) writes: > >Getting to more pragmatic examples, it seems that most numerical >approximations to real values assume that to compute the digit >at the ith position we have already computed all the digits preceding it. >It would be nice to see a counterexample to this. For example, rather >than seeing 50,000 digits of e, it would be interesting to see a >program that could compute the correct digit at any position specified. >The advantage to a method which does not need the preceding digits >is that one could claim to "know," perhaps 10^1000 digits of e. I recall reading two interesteing articles on topics like this in recent American Mathematical Monthlies... one on a surprising thing about computing some digits of a number without computing all the previous ones, and one on optimal algorithms for computing numbers. The latter went vaguely like this (I solicit more accurate information!). Rather shockingly, it hasn't been proved that one cannot multiply two numbers in a number of steps proportional to the number of digits (linear time). I believe it can be done in O(n log n) (or perhaps a bit slower??) Using this fact one can show that the first n digits of any algebraic number can be computed in O(n log n) time (again, I may be off here). The best known algorithm for pi is slower. Thus it is possible that there could be a computational complexity proof that pi is transcendental: i.e., that it is transcendental because it can't be computed fast enough!! I don't recall them saying anything about how long it takes to compute digits of e , but it's possible (and would be interesting) that it can be computed faster than pi, which would make it "more complicated" in a precise sense. Please, if anyone knows the facts, inquiring minds, want to know!