68
$\begingroup$

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!

$\endgroup$
15
  • 13
    $\begingroup$ I double majored at university. Mathematics and engineering. Im a pure mathematician before Im an engineer. I breezed through the engineering program because the associated mathematics was most peoples biggest hurtle. But one thing that always threw me off were the odd-ball discontinuous or non-differentiable functions that were "assigned" meaning in all violation of mathematics. Through fiat alone, a derivative was given to it, an integral, etc. Never mind the lack of mathematical rigor; just appreciate the mathematical self-consistency and the practicality and approximation it yields. $\endgroup$ Aug 30 '20 at 21:54
  • 8
    $\begingroup$ An answer to a different question: it always surprises me how seldom people use the natural way to optimize a function of an integer variable—namely, just look at the discrete difference $E(n,k+1)-E(n,k)$, whose sign tells us whether the function is increasing or decreasing just like a derivative does for continuous functions. (Sometimes the discrete quotient works better than the discrete difference.) $\endgroup$ Aug 31 '20 at 6:16
  • 5
    $\begingroup$ @CogitoErgoCogitoSum. Similar experience here. Majored in physics, work as an engineer. First thing that came into my head when I saw the title was "They don't care if it's correct or not. No, it's not correct, but they still don't care as long as it seems to work" $\endgroup$ Aug 31 '20 at 15:28
  • 17
    $\begingroup$ An Engineer doesn't care whether a method is "correct" as long as it gives the right answer within machine tolerances. $\endgroup$
    – OrangeDog
    Aug 31 '20 at 16:51
  • 4
    $\begingroup$ Physicists and engineers pay functions better than mathematicians and functions work harder for them (apologies to Lewis Caroll) All the functions in physics and engineering are uniformly continuous and in this case low pass filtered so that samples at the integers are sufficient. If it is properly filtered, the maximum at an integer will be one side or the other of the global maximum of the version extended from the integers to the reals. $\endgroup$ Sep 1 '20 at 3:25
114
$\begingroup$

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!

$\endgroup$
2
  • 22
    $\begingroup$ It's a good point that convexity actually makes the method pretty rigorous, but it should also be mentioned that it often gives good results even for grossly non-convex functions. You could argue this then assumes that the function is still locally convex in a sufficiently big region, but physicists or engineers may not bother proving this kind of thing. $\endgroup$ Aug 31 '20 at 8:20
  • 5
    $\begingroup$ @leftaroundabout Your last sentence is precisely the sentiment I tried to capture in my last paragraph. Understanding when the method does or doesn't work is valuable but quite difficult. I guess the key takeaway is that the general method is very convenient for finding good candidates for optima. $\endgroup$
    – Servaes
    Aug 31 '20 at 8:29
39
$\begingroup$

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.

$\endgroup$
1
  • 11
    $\begingroup$ I would like to add that using standard mathematical terminology (which may differ from High School terminology) any function $'maths N\to\mathbb R$ is continuous. (There is no appropriate concept of differentiation, though,) $\endgroup$
    – Carsten S
    Aug 31 '20 at 10:55
14
$\begingroup$

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".

$\endgroup$
1
  • 3
    $\begingroup$ I completely agree with your last paragraph, but I also think that we should take into consideration the rigorous mathematical arguments, because looking at graphs not always show the whole picture and things we may take by obvious may not be right with small variations. $\endgroup$ Aug 31 '20 at 14:09
8
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Yes, that's what I was thinking about, but the fact that the function is discontinuous bothers me for some reason. Is there any reason/exception why we can do this? $\endgroup$ Aug 30 '20 at 20:37
  • $\begingroup$ Hmm yeah they must be using an approx like this - but in general for optimization it does not need to be the case that simply rounding and getting a whole value is optimal over the whole numbers, right? Especially if the function is steep at the Maxima $\endgroup$ Aug 30 '20 at 20:39
  • 1
    $\begingroup$ @Riemann'sPointyNose Yes I agree in general the method do not guarantee for an extrema point. $\endgroup$
    – user
    Aug 30 '20 at 20:44
  • 1
    $\begingroup$ @SantiagoPardal Assuming $k$ continuous "relax" the problem in an easier form. Once we have the solution for the continuous case we can easily find the integer value nearest to that optimal value. See also Relaxation (approximation). $\endgroup$
    – user
    Aug 30 '20 at 20:45
  • 1
    $\begingroup$ @Riemann'sPointyNose Thanks, feel free to add more observation also in an answer if you like! Bye $\endgroup$
    – user
    Aug 30 '20 at 20:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.