Write an algorithm that compute the Euler's number until

Question

My professor from Algorithms course gave me the following homework:

Write a C/C++ program that calculates the value of the Euler's number (e) with a given accuracy of eps > 0.

Hint: The number e = 1 + 1/1! +1/2! + ... + 1 / n! + ... = 2.7172 ... can be calculated as the sum of elements of the sequence x_0, x_1, x_2, ..., where x_0 = 1, x_1 = 1+ 1/1 !, x_2 = 1 + 1/1! +1/2 !, ..., the summation continues as long as the condition |x_(i+1) - x_i| >= eps is valid.

As he further explained, eps is the precision of the algorithm. For example, the precision could be 1/100 |x_(i + 1) - x_i| = absolute value of ( x_(i+1) - x_i )

Currently, my program looks in the following way:

#include<iostream>
#include<cstdlib>
#include<math.h>
#include<vector>

// Euler's number

using namespace std;

double factorial(double n)
{
    double result = 1;
    for(double i = 1; i <= n; i++)
    {
        result = result*i;

    }
    return result;
}

int main()
{
    long double euler = 2;
    long double counter = 2;
    float epsilon = 2;
    do
    {
        euler+= pow(factorial(counter), -1);
        counter++;
    }
    while( (euler+1) - euler >= epsilon);
    cout << euler << endl;
    return 0;
}

The problem comes when I implement the stop condition |x_(i+1) - x_i| > = eps (line where is while( (euler+1) - euler >= epsilon);) The output is 2.5 instead of 2.71828

The code presented in the question does not implement the stop condition your professor specified. You can algebraically cancel the two appearances of `euler` from yours, leaving just `1 >= epsilon`. You are supposed to test the difference between the estimation of `e` at the end of one iteration and the estimation of *e* after the next iteration. — John Bollinger, Jan 12 '21 at 18:02
Note that your code is not very efficient. You could calculate the factorial recursively, from one iteration to the next one, instead to recalculate it from the beginning at each iteration — Damien, Jan 12 '21 at 18:04
"Recursively" is the wrong term for that, @Damien, but yes, it would be more efficient to keep a running factorial than to recompute each factorial from scratch. Also, using `pow(x, -1)` is abominable. Simple `1 / x` would be much better. — John Bollinger, Jan 12 '21 at 18:06
@JohnBollinger The term may not be good. My concern was to use the recursive relation `fact = n*previous_fact`. I agree that `pow()` use is an abomination. Simpler `term \= counter` and test `term > eps`, where `term` is the inverse of the factorial — Damien, Jan 12 '21 at 18:11
@Damien how can I factorize on the fly? How the code would look like. thx — max, Jan 12 '21 at 18:39
Look at my previous comment. Note that you must take `eps=0.00001`. And `xi -x(i-1) = 1/fact(i)` I call term this inverse of fact — Damien, Jan 12 '21 at 19:11
@Damien sorry, I lost track. Please, look at the code and tell what and where I should alter — max, Jan 12 '21 at 21:17
Don't edit your changes and new issue into this question, thereby invalidating answers. New problem, New question... — JHBonarius, Jan 12 '21 at 21:52
@JHBonarius my new question got closed because they labeled it as the duplicate of the current question even though my code was updated over there. Moreover, I can post one question per 90 minutes. How am I supposed to update the current code on this question then??? — max, Jan 12 '21 at 23:03
The new issue you encounter is about formatting of the output stream. Anyhow Some moderators are too fast in closing issues. I see you deleted the question. I cannot do anything about it then. — JHBonarius, Jan 13 '21 at 07:00
About the number of digits in the outputted number, please take a look at [`std::setprecision`](https://en.cppreference.com/w/cpp/io/manip/setprecision). — Bob__, Jan 13 '21 at 07:32
@Bob__ good point. Also, how can I optimize the algorithm of finding Euler's number? I know, I can rid off the function and calculate the Euler's value on the fly, but after each attempt to do that, I receive other errors. — max, Jan 13 '21 at 08:37

score 2 · Accepted Answer · answered Jan 12 '21 at 18:02

2

|x_(i+1) - x_i| > = eps means "the distance between the next value of x (x_(i+1)) and the current value of x (x_i) is greater or equal to epsilon".

Your code is adding one to x and checking a very different condition:

(euler+1) - euler >= epsilon

This means: "iterate until euler + 1 (not the next value of euler!) minus the current value is...", which is very different from the original condition. Also, (euler+1) - euler == 1, so you're checking whether epsilon is less than a constant 1.

answered Jan 12 '21 at 18:02

ForceBru

43,482
10
63
98

ok. I have added the edit. It seems to do what you have suggested, but it also produces the other issues – max Jan 12 '21 at 18:38
`pow(factorial(counter+1), -1)` is still not the next value of `euler`, though. That would be `euler + pow(factorial(counter+1), -1)`. And `pow(factorial(counter), -1)` is not the current value of `euler` either. – ForceBru Jan 12 '21 at 18:41
alright. I have changed to while((euler + pow(factorial(counter+1), -1) - euler) > epsilon); – max Jan 12 '21 at 21:03
Do I fulfill the condition then? – max Jan 12 '21 at 21:15
@max, I think so. Also, `pow(factorial(counter+1), -1)` is the same as `1 / factorial(counter+1)`, which might be easier to read and a bit faster to compute. – ForceBru Jan 13 '21 at 05:54
thx. also, it seems my epsilon value does not work properly. It is supposed to control the precision. For example, when I wish precision of 5 digits, I initialize it to 1.0/10000, and it outputs 3 digits before they get truncated after 8 (.718). How can I fix it? – max Jan 13 '21 at 08:35
@max, there must be some math to calculate the value of epsilon necessary to get the precision you need. You could ask your prof about that. – ForceBru Jan 13 '21 at 09:07

Bob__ · Answer 2 · 2021-01-13T09:57:54.870

There are a couple of things that the OP missed in both their attempted implementations.

the summation continues as long as the condition |x_i+1 - x_i| >= eps is valid.

Now, if we consider the posted series, what that difference looks like?

x₀ = 1, x₁ = 1 + 1 / 1!, x₂ = 1 + 1/1! +1/2!, ...
|x₁ - x₀| = 1 / 1!, |x₂ - x₁| = 1 / 2!, ..., |x_i - x_{i - 1}| = 1 / i!

So that the condition becomes 1 / i! >= eps
The function factorial is called at every iteration, multiple times, while we can easily calculate the new approximation of the Euler number with a couple of operations

term /= ++i
euler += term

When a floating point number is outputted via operator<<, it is represented with a default number of digits. To view more of them, we can use an input/output manipulator like std::setprecision. This won't affect the internal representation of that number nor the actual precision of any calculation involving it, it's just a format specifier.

The precision (and range) of a floating point type like double is limited, while the factorial grows pretty fast. At some point, 1/i! will be so small that euler += 1/i! will be numerically equivalent to the previous value of euler. See e.g. the following results, obtained using double variables

 1   2
 2   2.5
 3   2.666666666666666518636930049979127943515777587890625
 4   2.70833333333333303727386009995825588703155517578125
 5   2.716666666666666341001246109954081475734710693359375
 6   2.718055555555555447000415369984693825244903564453125
 7   2.71825396825396836675281520001590251922607421875
 8   2.718278769841270037233016410027630627155303955078125
 9   2.71828152557319224769116772222332656383514404296875
10   2.718281801146384513145903838449157774448394775390625
11   2.71828182619849290091451621265150606632232666015625
12   2.71828182828616871091753637301735579967498779296875
13   2.718281828446759362805096316151320934295654296875
14   2.71828182845823018709552343352697789669036865234375
15   2.718281828458994908714885241352021694183349609375
16   2.7182818284590428703495490481145679950714111328125
17   2.71828182845904553488480814849026501178741455078125
18   2.71828182845904553488480814849026501178741455078125
19   2.71828182845904553488480814849026501178741455078125
20   2.71828182845904553488480814849026501178741455078125

     2.718281828459045090795598298427648842334747314453125    <--- std::numbers::e

Note that the difference between the calculated value and std::numbers::e is roughly +4.4e-16 (it's actually the next representable double value).

The complete code (with all the needed initializations) is left to the reader to write.

Write an algorithm that compute the Euler's number until

2 Answers2

Linked