Register to reply 
On the complexity of pi, eby Newtime
Tags: complexity 
Share this thread: 
#1
Jul1610, 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. 


#2
Jul1710, 11:40 AM

HW Helper
P: 3,352

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^225, x^57[/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 byproduct while dealing with e. 


#3
Jul1710, 12:39 PM

P: 348




#4
Jul1710, 01:11 PM

HW Helper
P: 3,352

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.



#5
Jul1710, 01:15 PM

P: 348




#6
Jul1810, 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?



#7
Jul1810, 06:31 PM

Sci Advisor
HW Helper
P: 3,684

1. Set n = 1. 2. Calculate the number to a certain precision, say 1/10^(n+100). 3. Output the nth 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 nth 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). 


#8
Jul1910, 11:12 AM

Sci Advisor
HW Helper
P: 3,684

Better reference: V.Kh. Salikhov, Russ. Math. Surv. 63, No. 3, 570572 (2008).



#9
Jul1910, 09:43 PM

P: 96

Hi Newtime,
This seems to be an irrationality measure like what your looking for. http://mathworld.wolfram.com/IrrationalityMeasure.html It's the "LiouvilleRoth 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. 362386, 1987. 


#10
Jul1910, 10:31 PM

Sci Advisor
HW Helper
P: 3,684




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 