Why do engineers use derivatives in discontinuous functions? Is it correct?

I am a Software Engineering student and this year I learned about how CPUs work, it turns out that electronic engineers and I also see it a lot in my field, we do use derivatives with discontinuous functions. For instance in order to calculate the optimal amount of ripple adders so as to minimise the execution time of the addition process:

$$\text{ExecutionTime}(n, k) = \Delta(4k+\frac{2n}{k}-4)$$ $$\frac{d\,\text{ExecutionTime}(n, k)}{dk}=4\Delta-\frac{2n\Delta}{k^2}=0$$ $$k= \sqrt{\frac{n}{2}}$$

where $n$ is the number of bits in the numbers to add, $k$ is the amount of adders in ripple and $\Delta$ is the "delta gate" (the time that takes to a gate to operate).

Clearly you can see that the execution time function is not continuous at all because $k$ is a natural number and so is $n$. This is driving me crazy because on the one hand I understand that I can analyse the function as a continuous one and get results in that way, and indeed I think that's what we do ("I think", that's why I am asking), but my intuition and knowledge about mathematical analysis tells me that this is completely wrong, because the truth is that the function is not continuous and will never be and because of that, the derivative with respect to $k$ or $n$ does not exist because there is no rate of change.

If someone could explain me if my first guess is correct or not and why, I'd appreciate it a lot, thanks for reading and helping!

Solution 1:

In general, computing the extrema of a continuous function and rounding them to integers does not yield the extrema of the restriction of that function to the integers. It is not hard to construct examples.

However, your particular function is convex on the domain $k>0$. In this case the extremum is at one or both of the two integers nearest to the unique extremum of the continuous function.

It would have been nice to explicitly state this fact when determining the minimum by this method, as it is really not obvious, but unfortunately such subtleties are often forgotten (or never known in the first place) in such applied fields. So I commend you for noticing the problem and asking!

Solution 2:

The main question here seems to be "why can we differentiate a function only defined on integers?". The proper answer, as divined by the OP, is that we can't--there is no unique way to define such a derivative, because we can interpolate the function in many different ways. However, in the cases that you are seeing, what we are really interested in is not the derivative of the function, per se, but rather the extrema of the function. The derivative is just a tool used to find the extrema.

So what's really going on here is that we start out with a function $f:\mathbb{N}\rightarrow \mathbb{R}$ defined only on positive integers, and we implicitly extend $f$ to another function $\tilde{f}:\mathbb{R}\rightarrow\mathbb{R}$ defined on all real numbers. By "extend" we mean that values of $\tilde{f}$ coincide with those of $f$ on the integers. Now, here's the crux of the matter: If we can show that there is some integer $n$ such that $\tilde{f}(n)\geq \tilde{f}(m)$ for all integers $m$, i.e. $n$ is a maximum of $\tilde{f}$ over the integers, then we know the same is true for $f$, our original function. The advantage of doing this is that now can use calculus and derivatives to analyze $\tilde{f}$. It doesn't matter how we extend $f$ to $\tilde{f}$, because at the end of the day we're are only using $\tilde{f}$ as a tool to find properties of $f$, like maxima.

In many cases, there is a natural way to extend $f$ to $\tilde{f}$. In your case, $f=\text{ExecutionTime}$, and to extend it you just take the formula $\Delta \left(4k + \frac{2n}{k} - 4\right)$ and allow $n$ and $k$ to be real-valued instead of integer-valued. You could have extended it a different way--e.g. $\Delta \left(4k + \frac{2n}{k} - 4\right) + \sin(2\pi k)$ is also a valid extension of $\text{ExecutionTime}(n,k)$, but this is not as convenient. And all we are trying to do is find a convenient way to analyze the original, integer-valued function, so if there's a straightforward way to do it we might as well use it.

As an illustrative example, an interesting (and non-trivial) case of this idea of extending an integer-valued function to a continuous-valued one is the gamma function $\Gamma$, which is a continuous extension of the integer-valued factorial function. $\Gamma$ is not the only way to extend the factorial function, but it is for most purposes (in fact, all purposes that I know of) the most convenient.

Solution 3:

You are confusing a mathematical model of the system with the system itself. The map is not the territory.

Obviously in the real system both $n$ and $k$ must be integers. On the other hand, the math formula for the execution time is a perfectly good function for any real (or even complex!) values of $n$ and $k$ except when $k = 0$.

So you can certainly find the minimum value if $k$ according to the math model, even though the answer $k = \sqrt{(n/2)}$ gives a fractional value of $k$ for most integer values of $n$.

If you want to make the math more rigorous, since the function is convex you can then say that

For any integer $k \ge \sqrt{n/2}$, $E(n,k+1) > E(n,k)$, and

For any integer $k \le \sqrt{n/2}$ and $k > 1$, $E(n,k-1) > E(n,k)$.

Therefore, the minimum value of $E$ when $k$ is an integer is one of the (one or two) integers in the range $\sqrt{n/2} - 1 < k < \sqrt{n/2} + 1$.

On the other hand, engineers are interested in getting results, not doing rigorous math, and if you sketch a graph of the general shape of $E(n,k)$ this rigorous mathematical argument is "obvious".

Solution 4:

The continuous solution $k= \sqrt{\frac{n}{2}}$ gives in general an approximation for the extrema point, then we can estimate the optimal value by the integer part

$$ k_1=\left\lfloor \sqrt{\frac{n}{2}}\right\rfloor \le\sqrt{\frac{n}{2}} \le \left\lfloor \sqrt{\frac{n}{2}}\right\rfloor +1=k_2$$

such that ExecutionTime$(n, k)$ is minimum.

As noticed by Servaes in this particular case convexity guarantees that the minimum value given by $k_1$ or $k_2$ is the optimal integr value for the given function.

Solution 5:

If you consider that k and n are continuous variables, you obtain a continuous function that may be derivated and is entangled to the initial discontinuous function. The real problem is if the extreme point of this function can approximate the extreme point of the discontinuous one. The error may be evaluated with the Cauchy reminder formula for Newton or Lagrange interpolation which has a k! in the denominator and may be tolerable if k is enough big.