Mismatch in exercise “approximately e”

[cionx]

In the exercise “approximately e”, we want to approximate the exponential function by approximating the series $\sum{k = 0}^∞ x^k / k!$ with a partial sum $\sum{k = 0}^n x^k / k!$, for a sufficiently large number of summands $n + 1$. The number $n$ depend both on $x$ and some notion of “accuracy” $ε > 0$, and there are at least two approaches for choosing it:

• Consider only a single summand $x^n / n!$, and require that $|x^n / n!| < ε$.

• Consider all remaining summands, and require that $| \sum_{k = n+1}^∞ x^k / k! | < ε$.

The exercise seems to be designed to implement the first choice, and this is also what happens in the official solution.

However, the exercise actually asks for the second choice:

https://github.com/cs3110/textbook/blob/97e0237190012891d66f19ce213395e6c0d33cc6/src/chapters/ds/exercises.md?plain=1#L356-L357

So there is a mismatch:

• The overall exercise builds towards a (relatively simple) solution for the first choice.[^1]

[^1]: The resulting function e is a bit weird. For example, if we choose eps > abs_float x, then e x eps will always evaluate to 1. +. x. This works fine for smaller values of x, but utterly fails for larger values of x. Of course, this example is a bit pathological and can be avoided by making a sensible choice for eps. But it is still a failure of what e is supposed to do.

• But then the exercise asks for a solution for the second choice instead.

  (Such a solution can actually be build from the auxiliary functions constructed in the previous parts of the exercise. But this uses more mathematics than the rest of the book ever requires from its reader.)

[clarksmr]

Thank you!

Hm, I think the official solution is actually computing something different than your first or second choice? Let's define $\hat{e}$ to approximate the exponential function as follows: $$\hat{e}^xn = \sum{k=0}^{n} \frac{x^k}{k!}$$

Then the solution computes e x eps by returning $\hat{e}^x_n$ for the smallest $n$ such that: $$\hat{e}^xn - \hat{e}^x{n-1} \lt \epsilon$$

What do you think?

If I've got that right, then I think the exercise could do a better job of explaining what "within a tolerance" means. I will go ahead and add that while leaving this issue open.

[clarksmr]

Actually I think this "hint" might have been the culprit, or at least was misleading:

https://github.com/cs3110/textbook/blob/1794fcf096d1dbe51c0d075c30f7b9f2695564bd/src/chapters/ds/exercises.md?plain=1#L358-L360

That is not how the solution works. It takes a sum before using within.

[clarksmr]

See these commits (also linked above)

https://github.com/cs3110/textbook/commit/0aef42a2926b64d647f33a9e667f0fdd8c06a574

https://github.com/cs3110/textbook-solutions/commit/593cd86c68866819f94c3e96fac4094238c34ab3

[cionx]

Let's define $\hat{e}$ to approximate the exponential function as follows:

  \hat{e}^x_n = \sum_{k = 0}^n \frac{x^k}{k!}

Then the solution computes e x eps by returning $\hat{e}^x_n$ for the smallest $n$ such that:

\hat{e}^x_n − \hat{e}^x_{n - 1} < \epsilon

I agree, except for one minor detail: the helper function within_helper uses abs_float to compare successive values.

let rec within_helper (eps: float) (prev: float) (s: float sequence): float =
  match s with
  | Cons(h, tf) -> (
      if (abs_float (prev -. h)) < eps then h
      else within_helper eps h (tf ())
    )

So I think the estimate should actually be

|\hat{e}^x_n − \hat{e}^x_{n - 1}| < \epsilon \,.

Hm, I think the official solution is actually computing something different than your first or second choice?

We have

| \hat{e}^x_n − \hat{e}^x_{n - 1} |
=
\left|\frac{x^n}{n!}\right| ,

so the above inequality $|\hat{e}^xn − \hat{e}^x{n - 1}| < \epsilon$ becomes $|x^n / n!| < \epsilon$. This is the first choice.

If I've got that right, then I think the exercise could do a better job of explaining what "within a tolerance" means.

[…]

See these commits (also linked above)

https://github.com/cs3110/textbook/commit/0aef42a2926b64d647f33a9e667f0fdd8c06a574 https://github.com/cs3110/textbook-solutions/commit/593cd86c68866819f94c3e96fac4094238c34ab3

I think that the new explanation makes it clear when the approximation is supposed to end (i.e., what was originally meant by “within a tolerance”). And I agree that the solution implements this behaviour.

So unless I’m missing something, I believe that this issue is resolved.