Caclulation of e

doc has asked for the wisdom of the Perl Monks concerning the following question:

OK so Google wants you to find a prime in e, so lots of people are into e at the moment. Given I can get a couple of million digits of e online (and I've already answered both quiz questions just to see where it led) I am interested in why/how the algorithms at e actually work.

Euler's original equation e = 1 + 1/1! + 1/2! + 1/3! .... is obviously limited in accuracy by the size of the floating point value you can work with. To calculate a lot of digits, an alternative approach is needed which is not limited by the accuracy of the floating point you can work with. Now you can express e as e=1+1+1/2(1+1/3(1+1/4(1+1/5(1+.....)))) which means that when you work from the inside out the calculations only use small integer division. I presume that this is what is being done at e with the reverse walking and a carry up the integer array. The thing is I simply don't get it? Anyone able to enlighten me or provide a reference? This looks simple enough.....

sub e{
    @e=(1)x pop;
    for(1..@e){
        for(reverse(1..$#e)){
            $e[$_-1]+=$e[$_]/$_;
            $e[$_]=10*($e[$_]%$_)
        }
        print int $e[0];
        $e[0]=0
    }
}
[download]

Mazal tov.

Comment on Caclulation of e Select or Download Code

Replies are listed 'Best First'.
Re: Caclulation of e by tachyon (Chancellor) on Jul 17, 2004 at 10:40 UTC
Does this help? `use Data::Dumper; # print "2718281828459045235360287471352662497757247093699\n"; sub e{ @e=(1)x pop; for(1..@e){ print "Before: ", Dumper \@e; for(reverse(1..$#e)){ printf "Add %3.3f/%d(%3.3f) to \$e[%d] (now %3.3f); ", $e[$_],$_, $e[$_]/$_, $_-1, ($e[$_-1]+ $e[$_]/$_); $e[$_-1]+=$e[$_]/$_; printf "Set \$e[%d] = %d (10(%d%%%d))\n", $_, 10($e[$_]%$_), $e[$_], $_; $e[$_]=10*($e[$_]%$_); } print "After: ", Dumper \@e; printf "Printing: %d\n\n", $e[0]; $e[0]=0 } } e(5);` [download] Read more... (6 kB)	[reply] [d/l] [select]
Re^2: Caclulation of e by jdalbec (Deacon) on Jul 17, 2004 at 14:52 UTC
Read more... (549 Bytes)	[reply]
Re: Caclulation of e by Dr. Mu (Hermit) on Jul 18, 2004 at 04:48 UTC
According to this site, the number of primes between 0000000000 and 9999999999 is 455052511, or about 4.55 percent of them. If you were to throw all 10¹⁰ of these integers into a hat and draw them out at random (with replacement), how many would you have to draw before being 99.99 percent sure that at least one of them was prime? Well, the probability of not getting a prime in one draw is 1 - 0.0455 = 0.9545. So the probability of getting no primes in n draws is 0.9545ⁿ. We want to draw enough times to reduce this probability to 0.0001, so we need to solve 0.9545ⁿ = 0.0001. This is the same as saying n log 0.9545 = log 0.0001, or n = log 0.0001 / log 0.9545 = 197.78. What's the point of all this? It's simply to show that you don't need a million digits of e to find a 10-digit prime embedded in them. 207 (198 + 9) are probably (i.e. with 99.99% assurance) enough. This assumes, of course, that sets of consecutively overlapping 10-digit subsequences in the decimal expansion of e represent independent, random samples from the integers between 0000000000 and 9999999999. That may or may not be true.	[reply]
Re^2: Caclulation of e by tachyon (Chancellor) on Jul 18, 2004 at 11:00 UTC
Think about the problem. How hard do you think they made it? What is the significance of 10 digit (>2**32? perhaps)....Is there an easy way to answer it? If you can't do Q1 you are not going to like Q2	[reply]
Re^2: Caclulation of e by bageler (Hermit) on Jul 19, 2004 at 01:42 UTC
but we're not looking for primes in that range, we're looking for primes between 1 000 000 000 and 9 999 999 999, since any leading zeroes would make the number less than ten digits.	[reply]
Re: Caclulation of e by pg (Canon) on Jul 17, 2004 at 23:45 UTC
As how to resolve the puzzle, you started with the wrong direction. What expression of e to use is much less significant, than the way numbers should be stored, and how the basic math operations like plus and minus should be performed to ensure precision. The bottom line is that it is impossible for you to resolve this kind of problem by using the conventional math operations as you are using here. The usual implementation of math operation does not target this kind of precision. You are forced to to implement even things like plus, minus, mutiply ... by yourself. Of course first you have to have your own way of store numbers. Most likely, you will have to store numbers as strings. The performance of your computer and your implementation of basic operations will become the key factor of your success.	[reply]
Re: Caclulation of e by fredopalus (Friar) on Jul 18, 2004 at 03:09 UTC
How about Deriving pi and e?	[reply]
Re: Caclulation of e by ambrus (Abbot) on Jul 21, 2004 at 10:03 UTC
`bc -l <<<'scale=500;e(1)'` [download] gievs the first 500 digits fast (you might need to recompile bc if it's compiled with a too small max precision). I've tried with `bc -l <<<'scale=500;e(1)' \| tr -dc 0-9 \| ruby -we 's = gets; (0...(s.l +ength-10)).each {\|k\| puts s[k,10];};' \| factor \| grep -v ' .* '` [download] and found that there are about 17 10-digit primes in the first 500 digits.	[reply] [d/l] [select]