3 ms·
Computing e to thousands of decimal places is an interesting exercise for the mathematically inclined students in a beginning programming class. If you use the
by tzs 7y ago
Computing e to thousands of decimal places is an interesting exercise for the mathematically inclined students in a beginning programming class. If you use the ∑1/n! series you can fairly easily do it even in a language that does not have built in arbitrary precision or an arbitrary precision library.
Let's say you want to deal with numbers to 1000 decimal places. Pick a base that is a power of 10, such as 10000. Represent a number as an array of 251 base 10000 digits, with the first item of the array being the integer part, and the remaining 250 being 250 base 10000 "decimal" digits.
You need two of these arrays. One represents 1/n!, and the other is the cumulative sum of the series so far.
You need two large precision operations. To go from 1/n! to 1/(n+1)! involves simply dividing by n+1. As long as we limit n+1 to under 10000, we only have to handle division with a single digit denominator. Limiting n thusly is not a problem--it's enough to actually support calculating e to over 35000 decimal places, so our modest goal of 1000 is no problem.
Implement the division exactly like you would do division by a single digit with pencil and paper. The only thing you have to worry about is dealing with carry. You can have intermediate values as large as the carry x the base + base - 1, and since carry can be as large as base - 1, this means you can have intermediate values as large as base^2 - 1. Just pick base (10000 in my example) so that base^2 - 1 doesn't overflow the basic integer type of the language you are using.
The other large precision operation you need is addition, to accumulate the result from the division into the sum. Same as with division--just write it using the same algorithm you would use with pencil and paper. Add digits right to left, with carry.
By using a base that is a power of 10, it is easy to figure out the base 10 representation of the final result for printing.