11
$\begingroup$

I'm trying to find a differentiable approximation of the "fract" function, which returns the fractional portion of a real number.

$y = x-\lfloor x\rfloor$

enter image description here

I have something that works "ok", that I got by adapting a bandlimited saw wave.

$y=0.5-\frac{sin(2\pi x)+sin(4\pi x)/2+sin(6\pi x)/3+sin(8\pi x)/4+sin(10\pi x)/5}{\pi}$

enter image description here

I can add more harmonics to make the band limited saw wave closer to the actual "fract" function, but for my usage case, all these trig function calls are getting pretty expensive.

I was curious, are there other (better quality / lower computational complexity) ways to differentiably approximate this function?

$\endgroup$
  • $\begingroup$ If you know fourier series, you can probably run a low pass filter on it for example. $\endgroup$ – mathreadler Dec 26 '17 at 22:22
  • 1
    $\begingroup$ Do you need only differentiability, that is a continuous first derivative, or you need a smooth function? $\endgroup$ – lisyarus Dec 26 '17 at 22:22
  • 2
    $\begingroup$ As $\frac d{dx}(x - \lfloor x\rfloor)$ is almost everywhere defined (and equals 1 when), for some applications it could be taken as exactly 1 everywhere. What is the application? $\endgroup$ – arseniiv Dec 26 '17 at 22:26
  • $\begingroup$ i only need a continuous first derivative. I'm using this for part of a process I'm going to be doing gradient descent on. $\endgroup$ – Alan Wolfe Dec 26 '17 at 22:49
  • 2
    $\begingroup$ @AlanWolfe What are you trying to minimize? I think you're going to have serious trouble using gradient descent on anything with the fractional part function (that is, the function - or any approximation thereof - is inherently badly natured for that kind of method) $\endgroup$ – Milo Brandt Dec 27 '17 at 3:16
23
$\begingroup$

A function like

$$x-\frac{x^n}{1+x^n}$$

well approximates $x-\lfloor x \rfloor$ on the interval $[0, 2]$ for large $n$. If we take it on the interval $\left[{1 \over 2}, {3 \over 2}\right]$ and periodically repeat it, we get a nice almost differentiable approximation. $x^n$ can be efficiently calculated using the binary exponentiation algorithm (thus it would be handy if $n=2^k$).

NB: I said almost differentiable, since in the boundary points the derivatives on different sides are $\approx 1 - \frac{n}{2^{n-1}}$ and $1-\frac{n}{(3/2)^{n+1}}$, so, if $n$ is suitably large, the derivative is $\approx 1$ from practical perspective.

A live example on desmos.

enter image description here

$\endgroup$
11
$\begingroup$

Assume $x\to f(x)$ is the discontinous function you want to get smoother/more regular. Then, for example the local mean value integral $$F(x) = \frac{1}{2\Delta_x}\int_{x-\Delta_x}^{x+\Delta_x}f(\varphi)d\varphi \hspace{1cm} \text{(local averaging)}$$ will be differentiable for any $\Delta_x\in \mathbb R^+$ (why?) You can estimate this as a discrete sum (low pass filter) or you can calculate an explicit expression for it analytically as a continuous time convolution since $f(x)$ is so nice in this example. A slightly smoother and more complicated one is if we iterate it: $$F_2(x) = \frac{1}{2\Delta_x}\int_{x-\Delta_x}^{x+\Delta_x}F(\varphi)d\varphi \hspace{1cm} \text{(linear interpolation)}$$

enter image description here

$\endgroup$
5
$\begingroup$

Let $\{ x \}$ mean $x - \lfloor x \rfloor$. Given your goal of having the derivative be cheaply computable by computer, you should use a piecewise defined function:

$$ f(x) = \begin{cases} \{ x \} & \epsilon \leq \{ x \} \leq 1 - \epsilon \\ g(x) & 0 \leq \{ x \} < \epsilon \\ h(x) & 1 - \epsilon < \{ x \} < 1 \end{cases} $$

where $g$ and $h$ are any easily computed functions (e.g. quadratic polynomials) that satisfy the conditions listed below, and $\epsilon$ is a small positive number.

The point being that for most values of $x$, you have $f'(x) = 1$ so there is very little work in computing the derivative.


The conditions for $f$ to be differentiable are:

  • $g(0) = h(1)$
  • $g(\epsilon) = \epsilon$
  • $h(1-\epsilon) = 1 - \epsilon$
  • $g'(0) = h'(1)$
  • $g'(\epsilon) = 1$
  • $h'(1 - \epsilon) = 1$

For symmetry, you probably want $h(x) = 1 - g(1-x)$. Then the conditions reduce to

  • $g(0) = 1/2$
  • $g(\epsilon) = \epsilon$
  • $g'(\epsilon) = 1$
$\endgroup$
2
$\begingroup$

Here is a differentiable one. Just repeat $f$ every unit interval.

$f(x) = x + \dfrac{(\frac12-x)c(1+c)}{(x+c)(1-x+c)}$ for every $x \in [0,1]$, with parameter $c \to 0^+$.

The gradient also tends to $1$ at the midpoint as $c \to 0^+$.

The main advantage is that no exponentiation is needed; just pure arithmetic.

Example with $c=0.001$.

enter image description here][1

$\endgroup$
  • $\begingroup$ Doesn't look infinitely differentiable at integer values. $\endgroup$ – Hurkyl Dec 27 '17 at 14:19
  • $\begingroup$ @Hurkyl: You are right; it's only once differentiable. I've edited. Now it makes me wonder what is a computationally efficient function that when repeated is infinitely differentiable. $\endgroup$ – user21820 Dec 27 '17 at 14:57

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.