Pi and Irrational Numbers

[wexer9]

Pi is an irrational number, meaning it never ends.
It's infinitely long, therefore it must contain every possible combination of numbers an infinite amount of times.
Does this mean pi contains every piece of software (in 0's and 1's) ever written? And if we could reduce genetic code to numbers, would it contain the genetic code for every possible human being?
It's mind-blowing stuff, if I've got it right.

[Thabiguy]

Pi is an irrational number, meaning it never ends.
It's infinitely long, therefore it must contain every possible combination of numbers an infinite amount of times.
Almost surely.
Does this mean pi contains every piece of software (in 0's and 1's) ever written? And if we could reduce genetic code to numbers, would it contain the genetic code for every possible human being?
Almost surely.
It's mind-blowing stuff, if I've got it right.
It is, isn't it? Now consider that there are infinitely many other numbers that also contain all that; in fact, there's infinitely many times more of them than natural numbers...

[Alkatran]

Pi is an irrational number, meaning it never ends.
It's infinitely long, therefore it must contain every possible combination of numbers an infinite amount of times.
Does this mean pi contains every piece of software (in 0's and 1's) ever written? And if we could reduce genetic code to numbers, would it contain the genetic code for every possible human being?
It's mind-blowing stuff, if I've got it right.

Just being infinitely long doesn't mean it contains every possible combination of digits. There are infinitely many odd numbers, but none of them are 16. It is actually unknown whether or not the particular sequence that makes up pi contains every possible finite sequence. It's generally believed that this is the case.

But let's keep the "contains the genetic code of every possible human being" talk in perspective. Start counting. Congratulations, you've started a process which will enumerate all possible genetic codes, computer programs, you name it. You just won't get to many of them before a century has gone by and you can't count anymore because you're dead.

[shadron]

Pi is an irrational number, meaning it never ends.
It's infinitely long, therefore it must contain every possible combination of numbers an infinite amount of times.

No. It might, and in pi's case it very well might, but it is not a necessity for all irrational numbers. For example, suppose you had an irrational number that expanded into a random sequence of only ones and zeros (there has to be one - rather, an infinity of them -, right?). That certainly would not create the digit sequence '7', right?

Does this mean pi contains every piece of software (in 0's and 1's) ever written? And if we could reduce genetic code to numbers, would it contain the genetic code for every possible human being?

Yup - with their social security numbers attached, as well.

[Tim Thompson]

Pi is an irrational number, meaning it never ends.
No, "irrational" means that it cannot be expressed as a ratio of integers, hence "irrational". 1/3 Is a rational number, but its decimal equivalent is 0.333333333333333 ... forever. It never ends either, but it is not irrational.

[Perpetual Student]

\pi is a transcendental number (which is a subset of the irrationals). Basically that means it cannot be the solution to a polynomial equation with rational coefficients.
No regularly repeating patterns have been discovered. The numbers generated by \pi appear to be totally random. In the first six billion decimal places of \pi, each of the digits from 0 through 9 appears about six hundred million times, which would be expected if the digits were random. However, that does not prove it is is totally random and to my knowledge that proof has not yet been done.
So the answer to your questions is a qualified yes, it appears that way.
Here is an interesting link, showing the appearance of sequences of numbers within \pi:

http://www.angio.net/pi/piquery (Try your birthdate.)

[JoeTheJuggler]

I'm experiencing deja vu.

Wasn't there just recently a thread on almost this exact topic? I remember I mentioned Carl Sagan's Contact and posted this link (http://www.angio.net/pi/piquery) to a page where you can search the first 200 million digits of pi.

I didn't see the thread title on the first page of this forum, but it seems to me it was active within the last week or thereabouts.

ETA: D'oh--I see Perpetual Student already posted the same link here.

[GreyICE]

When you add it to infinity it makes infinity bigger too!

Not joking.

Well... not really.

[Dave Rogers]

I explained recently to my daughter that, if you choose a coding scheme and look far enough along the digits of pi, eventually you probably really will find a series of digits that decodes to the message "Help, I'm trapped in a universe factory!"

http://xkcd.com/10/

Dave

[orange31]

Pi has been computed to over a trillion digits without repeating a pattern.

I thought that was impressive until I became aware of a non-repeating number computed to over 11 trillion digits.

It's called the US national debt, and yes I'd call it an irrational number ;).

http://zfacts.com/p/461.html

[HansMustermann]

Actually, I think that the wording you're looking for is that it's a normal number. That's what makes it basically as good as an infinite sequence of random digits.

[drkitten]

Pi has been computed to over a trillion digits without repeating a pattern.

I thought that was impressive until I became aware of a non-repeating number computed to over 11 trillion digits.

It's called the US national debt, and yes I'd call it an irrational number ;).

http://zfacts.com/p/461.html


There are eleven trillion digits in the national debt?

Hmm. So, you're not only a political neanderthal, and incapable of following a thread -- but you're innumerate as well.

[Myriad]

Whether or not the expansion of pi (in whatever specified base) can ever be proven to contain every possible finite sequence of digits, irrational numbers exist that are guaranteed to contain every possible finite sequence of digits. For instance, the number

0.12345678910111213141516171819202122...

It's odd to think that this number is merely a single specific quantity, and yet it contains all the books in Borges' Babylon Library, and infinitely more.

I think it tends to support Wolfram's notion that even though it's generally thought that numbers, that is the quantities that numerals represent, are fundamental entities in mathematics while the symbols (such as digit sequences) that we use to represent them are barely adequate artificial contrivances, it might make more sense to think of that the other way around. Mathematics might actually be about the behavior of sequences of symbols under various rules, while the question of what numbers "actually are" might be beyond any possible understanding.

Respectfully,
Myriad

[Solitaire]

An argument over mathematical nomenclature. (http://images.intl.shopping.msn.com/au/img/8/61/47/22658959.jpg)

[CapelDodger]

Does this mean pi contains every piece of software (in 0's and 1's) ever written? And if we could reduce genetic code to numbers, would it contain the genetic code for every possible human being?

As Thabiguy said, almost certainly. Also Moby Dick or the complete works of Shakespeare; much cheaper and less messy than an infinite number of chimps banging away on keyboards.

For any particular sequence you could certainly never be sure that it isn't in there. Unless I'm wrong, of course.

[sol invictus]

I think it tends to support Wolfram's notion that even though it's generally thought that numbers, that is the quantities that numerals represent, are fundamental entities in mathematics while the symbols (such as digit sequences) that we use to represent them are barely adequate artificial contrivances, it might make more sense to think of that the other way around. Mathematics might actually be about the behavior of sequences of symbols under various rules, while the question of what numbers "actually are" might be beyond any possible understanding.

But there are ways to define numbers using (say) geometry that have nothing to do with symbols... pi as a geometrical ratio, 0 as the genus of a torus, 1 as the generator of the 3rd homotopy group of a 3-sphere, etc.

I think mathematics is discovered, not invented... and numbers are a fundamental part of that. Our notation for them, not so much.

[orange31]

There are eleven trillion digits in the national debt?

Hmm. So, you're not only a political neanderthal, and incapable of following a thread -- but you're innumerate as well.

LOL! You're right about my math skills, only 14 digits so far in the national debt.
(It just seems like 11 trillion).

However, I don't think your quote about 'my politics' is fair....
to the neanderthal.

[drkitten]

As Thabiguy said, almost certainly. Also Moby Dick or the complete works of Shakespeare; much cheaper and less messy than an infinite number of chimps banging away on keyboards.

For any particular sequence you could certainly never be sure that it isn't in there. Unless I'm wrong, of course.

Actually, there's enough regularity in pi that it wouldn't astonish me to learn that pi is not, in fact, "normal" and you could prove things didn't appear in it.

For example, there's a theorem from the mid 90s that allows you to compute the x'th digit of pi without computing the previous (x-1) digits. The trick is that it only works in hexadecimal (base 16), not in base 10. But this suggests to me that pi might not be normal in base 16, meaning, of course, that it might not be normal is base-2, either.

[sol invictus]

For example, there's a theorem from the mid 90s that allows you to compute the x'th digit of pi without computing the previous (x-1) digits. The trick is that it only works in hexadecimal (base 16), not in base 10. But this suggests to me that pi might not be normal in base 16, meaning, of course, that it might not be normal is base-2, either.

Really?

What's the theorem?

[drkitten]

What's the theorem?

http://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml

Neat, huh?

[Bob Klase]

Here is an interesting link, showing the appearance of sequences of numbers within \pi:

http://www.angio.net/pi/piquery (Try your birthdate.)

Oh crap. Not only did it find my birthdate, it also knows my social security number, my address, and all of my credit card numbers. It's only a matter of time until identity thieves discover that site and they'll have all our information!

[Perpetual Student]

I think mathematics is discovered, not invented... and numbers are a fundamental part of that. Our notation for them, not so much.

A good example of this is the concept of continuity, which is so easily comprehended and quite intuitive for most people (which I would argue is a mathematical "discovery"). Yet the definitions developed (example: for continuous functions) took a long time historically, are laden with notation and are not easily understood by laymen.

[sol invictus]

Neat, huh?

Very.

Thank you.

[ravdin]

No, "irrational" means that it cannot be expressed as a ratio of integers, hence "irrational". 1/3 Is a rational number, but its decimal equivalent is 0.333333333333333 ... forever. It never ends either, but it is not irrational.

Exactly. If you think about it, all rational numbers have a nonterminating sequence when expressed in decimal form- the equivalent of 1/2 is 0.500000000...

The difference with an irrational number is that the sequence does not repeat itself. If it did, you could express it as the ratio of two integers.

[edd]

Actually, there's enough regularity in pi that it wouldn't astonish me to learn that pi is not, in fact, "normal" and you could prove things didn't appear in it.

For example, there's a theorem from the mid 90s that allows you to compute the x'th digit of pi without computing the previous (x-1) digits. The trick is that it only works in hexadecimal (base 16), not in base 10. But this suggests to me that pi might not be normal in base 16, meaning, of course, that it might not be normal is base-2, either.

I'm not that willing to follow that connection between the base-16 generating formula and normality myself. Although of course "might not be normal" is a pretty weak statement ;)

A brief look around also brings up this interesting paper which hints at pi being base-2 normal.

http://crd.lbl.gov/~dhbailey/dhbpapers/baicran.pdf

[wexer9]

No, "irrational" means that it cannot be expressed as a ratio of integers, hence "irrational". 1/3 Is a rational number, but its decimal equivalent is 0.333333333333333 ... forever. It never ends either, but it is not irrational.
Thank you for the clarification.

[drkitten]

I'm not that willing to follow that connection between the base-16 generating formula and normality myself. Although of course "might not be normal" is a pretty weak statement ;)

It was intended to (be a pretty weak statement). My argument is merely along the lines of "there is a surprisingly strong pattern in the base 16 digits, threfore it wouldn't astonish me to learn there was another surprisingly strong pattern," along with the idea that examining THIS pattern might be a good start to finding THAT one.

If I actually had a firm argument that pi was not normal to base 16, I wouldn't burn it here; there are better number theory journals than the JREF. :D

[CapelDodger]

Oh crap. Not only did it find my birthdate, it also knows my social security number, my address, and all of my credit card numbers. It's only a matter of time until identity thieves discover that site and they'll have all our information!

Not only that - they'll have all our future information! Before it's even happened!

What chance do we have against that?

[CapelDodger]

It was intended to (be a pretty weak statement). My argument is merely along the lines of "there is a surprisingly strong pattern in the base 16 digits, threfore it wouldn't astonish me to learn there was another surprisingly strong pattern," along with the idea that examining THIS pattern might be a good start to finding THAT one.

Where infinity is involved, any weakness is terminal.

If I actually had a firm argument that pi was not normal to base 16, I wouldn't burn it here; there are better number theory journals than the JREF. :D

I used to spend a lot of time in number theory lectures musing on the better things I could be doing with my time ...

All the same, a Pass was necessary and I really don't buy this special-base idea. I recall seeing it demolished : the details escape me (decades have passed), but it was a sound demolition. It's hardly a new idea, after all. I was probably getting it at fifth-generation pithiness.

[CapelDodger]

http://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml

Neat, huh?

But wrong.

... the numerator decreases very quickly as k gets large so that terms become negligible

This is where infinity and continuity kick in. There is no neglible in infinity; rounding error is always there, and you don't know what it is.

[69dodge]

But wrong.

This is where infinity and continuity kick in. There is no neglible in infinity; rounding error is always there, and you don't know what it is.

I'm not sure what you're trying to say here.

It's certainly possible, sometimes, to know an upper bound on rounding error, and often that's good enough.

There is no doubt, for example, that the first six digits of pi are 3.14159.

[sol invictus]

But wrong.


Certainly not. You can check in three lines that that sum equals pi.


This is where infinity and continuity kick in. There is no neglible in infinity; rounding error is always there, and you don't know what it is.

Again, not so. It's trivial to show that the error is bounded. Therefore if you want to compute the Nth digit, you only need to compute a finite number of terms (which turns out to be order N in this case).

[Almo]

No, "irrational" means that it cannot be expressed as a ratio of integers, hence "irrational". 1/3 Is a rational number, but its decimal equivalent is 0.333333333333333 ... forever. It never ends either, but it is not irrational.

0.333333333333333 approaches 1/3 as a limit as the number of digits increases. With an infinite number of digits, it is in fact = 1/3.

Irrationals can't be expressed as repeating decimals.

[cyborg]

0.12345678910111213141516171819202122...

Which could be expressed as the concatenation of the symbols in the set of integers in base 10. And of course any other normal number in base 10 would be some permutation of this set.

And I'm pretty sure determining the permutation is incomputable - since the permutation could have infinite entropy.

Adding in the task of having to check this for every possible integer base... well, it's just a staggeringly huge task to say the least.

It's odd to think that this number is merely a single specific quantity, and yet it contains all the books in Borges' Babylon Library, and infinitely more.

The problem is extracting this information of course.

[Myriad]

But there are ways to define numbers using (say) geometry that have nothing to do with symbols... pi as a geometrical ratio, 0 as the genus of a torus, 1 as the generator of the 3rd homotopy group of a 3-sphere, etc.


True, but it works both ways. Pi as a geometrical ratio seems very simple in concept has a complex numerical expression. On the other hand, the binary number 0.101100111000111100001111100000... has a very simple numerical expression, but I very much doubt that it can be expressed as any property of simple geometric objects.

I think mathematics is discovered, not invented... and numbers are a fundamental part of that. Our notation for them, not so much.


Our specific notation systems and axiom systems are of course invented. But what is being discovered (not invented; no one designed this behavior or even expected to find it) is that they all behave fundamentally the same. Some are sufficiently limited so as to have only rather simple behavior (e.g. the two-body problem), and the rest have behavior that becomes intractably complex when given inputs outside specifically constrained domains (e.g. the three-body problem). Of the latter type, a large number have been proven to be computationally equivalent -- that is, transformable into known computationally universal systems such as Turing machines, proofs from the axioms of arithmetic, lambda calculus, symbolic logic, solvability of Diophantine equations, the Rule 110 cellular automaton, and everyday computers (when idealized to have infinite memory), all of which are capable of emulating one another and are therefore fundamentally equivalent.

It remains to be seen whether any systems with complex behavior will turn out to be exceptions. For instance, gravitational movement of three bodies in space has not yet been proven to be computationally universal, but it's looking very likely that it eventually will be, and that would explain (or at least put into a more consistent context) the surprising complexity of the behavior of arbitrary three-body systems.

Numbers are looking less fundamental than they used to.

Respectfully,
Myriad

[Alkatran]

Which could be expressed as the concatenation of the symbols in the set of integers in base 10. And of course any other normal number in base 10 would be some permutation of this set.

And I'm pretty sure determining the permutation is incomputable - since the permutation could have infinite entropy.

Adding in the task of having to check this for every possible integer base... well, it's just a staggeringly huge task to say the least.



The problem is extracting this information of course.

In binary you can permute any irrational number into any other irrational number. If you need a 1 you just scan ahead for the next 1, then swap and go to the next bit. Do the same for 0. Because the number is irrational there will always be a 1 or 0 left to choose from.

I'm defining permute as the limit of permuting more and more of the bits, with the constraint that each bit's destination must eventually become fixed [otherwise you can turn any irrational binary number into any real number, but not vice versa].

[IMST]

Oh crap. Not only did it find my birthdate, it also knows my social security number, my address, and all of my credit card numbers. It's only a matter of time until identity thieves discover that site and they'll have all our information!

Actually, that site doesn't have anything to do with pi at all. It just collects sensitive information for future identity theft because humans naturally put that kind of stuff in first.

joking, of course. Though that would be a decent scam

[cyborg]

In binary you can permute any irrational number into any other irrational number.

This would imply all binary infinite sequences are normal.

ETA: On second though it wouldn't. 101101110111101111101111110... wouldn't be normal but the set of 1's would have the same cardinality as the set of 0's since you could map all the zeros to all the 1's. I'm a little unsure at this point.

[linusrichard]

0.333333333333333 approaches 1/3 as a limit as the number of digits increases. With an infinite number of digits, it is in fact = 1/3.

Or with a finite number of digits and three dots after them, thus:
.33...
Or with a finite number of digits and a horizontal line over the last one.

[CapelDodger]

Certainly not. You can check in three lines that that sum equals pi.

I wasn't referring to the formula, but to the line I quoted

"... the numerator decreases very quickly as k gets large so that terms become negligible "

I'm not sure that follows.

Again, not so. It's trivial to show that the error is bounded.

Trivially, it's bounded by the difference between the current estimate and pi. The problem arises when the bound - which is itself indeterminate - coincides closely enough with a digit-boundary that it never delivers a definite answer. Which is to say, the pi-digit problem has merely been replaced with the error-bound-digit problem. Which is no great help.

Therefore if you want to compute the Nth digit, you only need to compute a finite number of terms (which turns out to be order N in this case).

I'm not yet convinced.

[sol invictus]

I wasn't referring to the formula, but to the line I quoted

The line was "Neat, huh?"

Soooo.... huh?


I'm not sure that follows.

It does. It's obvious. Would you like me to prove it?


Trivially, it's bounded by the difference between the current estimate and pi. The problem arises when the bound - which is itself indeterminate - coincides closely enough with a digit-boundary that it never delivers a definite answer. Which is to say, the pi-digit problem has merely been replaced with the error-bound-digit problem. Which is no great help.

The only way that could be a problem is if the digit you are computing (say in base 10 for ease) turns out to be 9, followed by 9, followed by 9, etc. I suppose it's true that sequences of 9's of arbitrary length do in fact occur in pi, and therefore one can find digits for which this technique would require many more than N terms to compute. But they are extremely rare, and irrelevant to the claim that the typical Nth digit requires of order N operations to compute.


I'm not yet convinced.

There is a paper, published in a mathematical journal, which proves the statements presented on that page. That paper has not only stood the test of nearly 20 years, it has become the basis for a set of similar algorithms for computing digits of other irrational numbers.

It's a little hard to think of something more convincing - particularly when a glance at the formulas makes it obvious why it works. But I suppose if that doesn't convince you, neither will I - so I'll stop here.

[ddt]

I'm not sure that follows.

Trivially, it's bounded by the difference between the current estimate and pi. The problem arises when the bound - which is itself indeterminate - coincides closely enough with a digit-boundary that it never delivers a definite answer. Which is to say, the pi-digit problem has merely been replaced with the error-bound-digit problem. Which is no great help.

I'm not yet convinced.
The terms in the infinite sum are

16^-k * [ 4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6) ]

Note that the numerators in the four fractions add to 0, while the denominators are of the same magnitude. This should give you a hint that the part within the square brackets is very small.

When you rewrite the part between the square brackets to one fraction, you'll see that in the numerator, the k^3 terms cancel each other out, so you get k^2 as the highest power of k; while in the denominator, you'll have k^4 as the highest power. (and I'm too lazy and too prone to make errors with it to write the whole thing out). But in effect, the term is of O(k^-2), which is enough for the "decreases very quickly" in this context.

[CapelDodger]

The only way that could be a problem is if the digit you are computing (say in base 10 for ease) turns out to be 9, followed by 9, followed by 9, etc. I suppose it's true that sequences of 9's of arbitrary length do in fact occur in pi, and therefore one can find digits for which this technique would require many more than N terms to compute. But they are extremely rare, and irrelevant to the claim that the typical Nth digit requires of order N operations to compute.

This is, I think, the problem : I've been considering the case of any N, not of a typical N. I read the case too strongly.

In the any N case it doesn't matter that the non-typical N's are extremely rare, it's enough that they exist, there are an infinite number of them, and there's no way of predicting where they are. Not in any base.

There is a paper, published in a mathematical journal, which proves the statements presented on that page. That paper has not only stood the test of nearly 20 years, it has become the basis for a set of similar algorithms for computing digits of other irrational numbers.

It's a little hard to think of something more convincing - particularly when a glance at the formulas makes it obvious why it works. But I suppose if that doesn't convince you, neither will I - so I'll stop here.

As I say, my mistake was in the strength of the case being made.

[CapelDodger]

The terms in the infinite sum are

16^-k * [ 4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6) ]

Note that the numerators in the four fractions add to 0, while the denominators are of the same magnitude. This should give you a hint that the part within the square brackets is very small.

k being consistently below the line, and k going to infinity, does rather convey that.

When you rewrite the part between the square brackets to one fraction ...

Why on earth would you do that?

The point is the rate of decay as k gets larger - does it increase, or decrease? In this case it decreases, which means it is not trivial that terms become negligible.

[69dodge]

In the any N case it doesn't matter that the non-typical N's are extremely rare, it's enough that they exist, there are an infinite number of them, and there's no way of predicting where they are.

I still can't figure out what you're saying.

Imagine that we're computing pi by adding terms of the series, one by one.

Are you saying that, for some digits of pi, it's never possible to know with certainty what that digit is, because maybe it will change if enough further terms are added?

Or are you just saying that, for some digits, many more terms than usual will need to be added before we're sure what that digit is?

[69dodge]

k being consistently below the line, and k going to infinity, does rather convey that.

No, I think you misunderstand. He meant that it is small, even relative to 1/k.

The point is the rate of decay as k gets larger - does it increase, or decrease? In this case it decreases, which means it is not trivial that terms become negligible.

Are you forgetting that the whole thing is anyway multiplied by 1/16k, which decays quite rapidly all by itself?

[ddt]

k being consistently below the line, and k going to infinity, does rather convey that.
Yes, but only being of O(1/k) is not enough - the harmonic series is divergent.


Why on earth would you do that?

The point is the rate of decay as k gets larger - does it increase, or decrease? In this case it decreases, which means it is not trivial that terms become negligible.
That's precisely the point of the rewrite. The single fraction, after rewriting, has a k^2 in the numerator and a k^4 in the denominator. So the whole fraction is of O(1/k^2), which means that all those fractions can be summed and the sum is smaller than pi^2/6 times some constant.

That whole point is moot anyway, as 69dodge rightly notes:

Are you forgetting that the whole thing is anyway multiplied by 1/16k, which decays quite rapidly all by itself?
which means that we only have to establish that all terms

[ 4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6) ]

are bounded by some constant, say c. Then each term

16^-k * [ 4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6) ]

is smaller than 16^-k * c and the infinite sum for k=m..infinity is

16^-m * 16/15 * c

so we have an upper bound for the sum of each tail of the series, and thus can calculate for which m, we have an accuracy of 16^-N.

[sol invictus]

I think the point was this. Using hex notation, somewhere in the expansion of pi there is ...0FFFFFFFFF...., with any arbitrary number of Fs. Somewhere else there's ...1000000000... So suppose you compute 0F as the Nth and (N+1)st digits. To distinguish that from 10, you have to compute the next digit. But if you get F, you must compute the next, etc.

So I guess it's true that there exist Ns for which the time to compute the Nth digit of pi is any arbitrary multiple of N. Of course those Ns are exponentially rare, since a sequence of m Fs has a probability of 16^{-m}. So this doesn't affect the typical time.

[Molinaro]

JREF in ASCII code is 74 82 69 70 and that sequence first occurs starting at the 10,969,623rd digit after the decimal in PI.

[ddt]

I think the point was this. Using hex notation, somewhere in the expansion of pi there is ...0FFFFFFFFF...., with any arbitrary number of Fs. Somewhere else there's ...1000000000... So suppose you compute 0F as the Nth and (N+1)st digits. To distinguish that from 10, you have to compute the next digit. But if you get F, you must compute the next, etc.

So I guess it's true that there exist Ns for which the time to compute the Nth digit of pi is any arbitrary multiple of N. Of course those Ns are exponentially rare, since a sequence of m Fs has a probability of 16^{-m}. So this doesn't affect the typical time.

Agreed. The algorithm is on estimate linear in time, but the worst case behaviour is unbounded.

[CapelDodger]

Are you forgetting that the whole thing is anyway multiplied by 1/16k, which decays quite rapidly all by itself?

I think that's cancelled by the fact that each digit represents 1/16 of the previous one. In the construct that sol invictus described (which is what I was thinking of) this merely pushes the uncertainty further along the sequence.

My thinking has been about exceptions, and the arbitrarily long string of hexF seemed a good one. As ddt so excellently puts it, the worst case is unbounded. Not that there is a worst case, of course; for every arbitrarily long string there is an arbitrarily longer one.

[portlandatheist]

Actually, that site doesn't have anything to do with pi at all. It just collects sensitive information for future identity theft because humans naturally put that kind of stuff in first.

joking, of course. Though that would be a decent scam
LOL, I was going to make a similar comment after I realized I was volunteering personal information on that website. I'd love to see the source code! What a cool utility.