Register to reply

On the complexity of pi, e

by Newtime
Tags: complexity
Share this thread:
Newtime
#1
Jul16-10, 10:20 AM
P: 348
I was reading a book on number theory, and there was an interesting dicussion about pi and e. It state that it took about one third less time to compute e to 100,000 places when compare to pi. Additionally, it stated that no "simple" partial fraction (that is, one in which all numerators are 1's) exists for pi, but one exists for e. I'm no number theorist, and certainly am not up to date with any research, but has there been any results proving that pi is, in a sense a deeper, more complex irrational number than e, in the same vein as the statements in the book I was reading? Thanks.

Note: the book is called "Excursions in Number Theory" and was published in 1966.

edit: Oops. Thought I was posting this in the number theory section. If a mod would move it, I would appreciate it.
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
Gib Z
#2
Jul17-10, 11:40 AM
HW Helper
Gib Z's Avatar
P: 3,348
For a special class of numbers, that many irrational numbers are, there is a certain measure of "complexity" (I say "many" in a loose everyday sense, it turns out that almost all irrational numbers are in fact not in this class). This class is called the Algebraic Numbers, and these are the set of numbers that are solutions to some polynomial equation with integer coefficients. For example, [itex] \sqrt{5} [/itex] and [itex]7^{1/5}[/itex] are algebraic as they are roots of [itex]x^2-25, x^5-7[/itex] respectively. We say an algebraic number is of degree n if n is the smallest degree a polynomial must be to have the number as a solution. In our examples, the numbers are of degree 2 and 5 respectively. We can regard lower degree algebraic numbers as "simpler" and "less irrational" in some sense to higher degree algebraic numbers. For example, the set of algebraic numbers of degree 1 is the set of solutions to ax + b = 0, where a and b are integers, ie the rational numbers. It is only from degree 2 onwards we "step up" a level and get to irrational numbers (or imaginary numbers).

If the number is not the solution of any polynomial with integer coefficients, we call them transcendental numbers (they "transcend" algebraic equations). Since all rational numbers are algebraic numbers (of degree 1), all real transcendental numbers are immediately irrational, but not all irrational numbers are transcendental. Examples of numbers in the latter class are [itex]\pi[/itex] and e. From this we can already reason that these two constants are "more complex" than the other irrational numbers mentioned here previously, so your question is not a foolish one to ask. However, there is no longer a quantitative comparison like we had for algebraic numbers.

e comes about very naturally when doing Calculus, Differential Equations or Complex Analysis (I've probably missed others), and then one finds by investigation of the exponential function that it has a period of [itex]2\pi i[/itex]. When [itex]\pi[/itex] finds a reason to pop up somewhere, often its because the exponential function has found a way to pop up somewhere, often disguised as a trigonometric function or some other alias. For example, a circle in the complex plane is traced out by a full period of [itex]e^{it}[/itex], and because we call this period [itex]2\pi i[/itex], we've already linked [itex]\pi[/itex] into all of our circular geometry. So in a purely subjective sense, I would say that e is the more fundamental number while [itex]\pi[/itex] arises as a by-product while dealing with e.
Newtime
#3
Jul17-10, 12:39 PM
P: 348
Quote Quote by Gib Z View Post
For a special class of numbers, that many irrational numbers are, there is a certain measure of "complexity" (I say "many" in a loose everyday sense, it turns out that almost all irrational numbers are in fact not in this class). This class is called the Algebraic Numbers, and these are the set of numbers that are solutions to some polynomial equation with integer coefficients. For example, [itex] \sqrt{5} [/itex] and [itex]7^{1/5}[/itex] are algebraic as they are roots of [itex]x^2-25, x^5-7[/itex] respectively. We say an algebraic number is of degree n if n is the smallest degree a polynomial must be to have the number as a solution. In our examples, the numbers are of degree 2 and 5 respectively. We can regard lower degree algebraic numbers as "simpler" and "less irrational" in some sense to higher degree algebraic numbers. For example, the set of algebraic numbers of degree 1 is the set of solutions to ax + b = 0, where a and b are integers, ie the rational numbers. It is only from degree 2 onwards we "step up" a level and get to irrational numbers (or imaginary numbers).

If the number is not the solution of any polynomial with integer coefficients, we call them transcendental numbers (they "transcend" algebraic equations). Since all rational numbers are algebraic numbers (of degree 1), all real transcendental numbers are immediately irrational, but not all irrational numbers are transcendental. Examples of numbers in the latter class are [itex]\pi[/itex] and e. From this we can already reason that these two constants are "more complex" than the other irrational numbers mentioned here previously, so your question is not a foolish one to ask. However, there is no longer a quantitative comparison like we had for algebraic numbers.

e comes about very naturally when doing Calculus, Differential Equations or Complex Analysis (I've probably missed others), and then one finds by investigation of the exponential function that it has a period of [itex]2\pi i[/itex]. When [itex]\pi[/itex] finds a reason to pop up somewhere, often its because the exponential function has found a way to pop up somewhere, often disguised as a trigonometric function or some other alias. For example, a circle in the complex plane is traced out by a full period of [itex]e^{it}[/itex], and because we call this period [itex]2\pi i[/itex], we've already linked [itex]\pi[/itex] into all of our circular geometry. So in a purely subjective sense, I would say that e is the more fundamental number while [itex]\pi[/itex] arises as a by-product while dealing with e.
I'm not concerned with the qualitative idea of which is more fundamental, although you bring up interesting points. I'm more interested in which is more quantitatively complex and in particular if such a method for determining or even defining the "complexity" of such numbers exists.

Gib Z
#4
Jul17-10, 01:11 PM
HW Helper
Gib Z's Avatar
P: 3,348
On the complexity of pi, e

Well as I said before, there isn't a way of ordering pi and e in terms of "complexity", but it seems you are interested in computational difficulty, in which case it is more about the efficiency of the specific algorithm being used, rather than the constants themselves. As far as I know there is no theorem concerning algorithms which compute pi and e in terms of theoretical maximum computational efficiency. So when the book said it took less time to calculate e than pi, it's saying the algorithm used to compute e was more efficient than the one that computed pi. Note that there are many possible algorithms that compute e, and some would have been slower than the one that computed pi in this instance.
Newtime
#5
Jul17-10, 01:15 PM
P: 348
Quote Quote by Gib Z View Post
Well as I said before, there isn't a way of ordering pi and e in terms of "complexity", but it seems you are interested in computational difficulty, in which case it is more about the efficiency of the specific algorithm being used, rather than the constants themselves. As far as I know there is no theorem concerning algorithms which compute pi and e in terms of theoretical maximum computational efficiency. So when the book said it took less time to calculate e than pi, it's saying the algorithm used to compute e was more efficient than the one that computed pi. Note that there are many possible algorithms that compute e, and some would have been slower than the one that computed pi in this instance.
You're right: I think computational efficiency is indeed what I'm interested in since it seems the best way to determine the complexity of these numbers. You're also right about the algorithms. But this brings up another question: can it be proven that some algorithm for computing pi or e is the most efficient? If not, can it be shown that one will always require more computation than the other? I suppose this is getting more into complexity theory than number theory though...
Justin Kirk
#6
Jul18-10, 02:52 PM
P: 11
I take irrational to mean the digits in pi follow no order. 3 is rational because its digits follow an order, that is 3 then 0,0,0,0,0,0 and so on. What I am trying to ask is, is there an algorithm which would give each digit in pi, which would give the 3, give the 1, give the 4 and so forth depending on how long you want to have the number be?
CRGreathouse
#7
Jul18-10, 06:31 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by Justin Kirk View Post
I take irrational to mean the digits in pi follow no order. 3 is rational because its digits follow an order, that is 3 then 0,0,0,0,0,0 and so on. What I am trying to ask is, is there an algorithm which would give each digit in pi, which would give the 3, give the 1, give the 4 and so forth depending on how long you want to have the number be?
Sure. For a general number, you might expect such an algorithm to be:
1. Set n = 1.
2. Calculate the number to a certain precision, say 1/10^(n+100).
3. Output the n-th decimal digit of the approximation.
4. Increment n and go to step 2.

Of course this algorithm fails eventually for most numbers, since eventually you may come across a portion where there are (in this case) over 100 consecutive 0s or 9s, so that you could be within the desired precision but not have the right digit. But it happens that there are theorems (say, Baker's effective version of Roth's theorem) that show that pi cannot have too good of a rational approximation, so using those there is an effectively computable function C(n) such that an approximation to within 1/10^(n+C(n)) will have the same n-th decimal place as pi.

Now, the theorem's constants are weak; this may require you to calculate a million decimal places of pi to get 3.14 for all I know.

Of course, practically you just calculate pi to n+1000 decimal places using any desired algorithm and check that the last thousand aren't too close to all 0s or 9s (in which case you recompute).
CRGreathouse
#8
Jul19-10, 11:12 AM
Sci Advisor
HW Helper
P: 3,684
Better reference: V.Kh. Salikhov, Russ. Math. Surv. 63, No. 3, 570-572 (2008).
dimitri151
#9
Jul19-10, 09:43 PM
P: 99
Hi Newtime,

This seems to be an irrationality measure like what your looking for.
http://mathworld.wolfram.com/IrrationalityMeasure.html
It's the "Liouville-Roth constant or irrationality exponent, ...defined as the threshold at which Liouville's approximation theorem kicks in and is no longer approximable by rational numbers.."
For e it is 2, for pi it seems there is no exact number but an upper bound 7.6304 which would seem to suggest that pi is more irrational.

Justin, There are algorithms that give blocks of pi as far in as you like. You can even calculate a single digit of pi's expansionwithout calculating any of the preceding expansion. I can't find the reference but I know I read the article some years back. Here:
http://www.eurekalert.org/features/d...-atd062002.php
Borwein seems to be the authority.
Borwein, J. M. and Borwein, P. B. "Irrationality Measures." 11.3 in Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, pp. 362-386, 1987.
CRGreathouse
#10
Jul19-10, 10:31 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by dimitri151 View Post
You can even calculate a single digit of pi's expansionwithout calculating any of the preceding expansion. I can't find the reference but I know I read the article some years back. Here:
http://www.eurekalert.org/features/d...-atd062002.php
Borwein seems to be the authority.
Borwein, J. M. and Borwein, P. B. "Irrationality Measures." 11.3 in Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, pp. 362-386, 1987.
That's Plouffe's algorithm (the so-called "BBP algorithm"). But it only works in hexadecimal (or more generally in bases that are a power of two) and the question was about decimal.


Register to reply

Related Discussions
Help with algorithm complexity Engineering, Comp Sci, & Technology Homework 0
Complexity Economics? Academic Guidance 0
Complexity Class General Math 1
I'm sure there are lots of way to define complexity in different General Math 3
Computational complexity General Math 3