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$
9
  • $\begingroup$ If you know fourier series, you can probably run a low pass filter on it for example. $\endgroup$ 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$ 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$
2
  • $\begingroup$ Doesn't look infinitely differentiable at integer values. $\endgroup$
    – user14972
    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
0
$\begingroup$

The other answers require you to copy the function over the entire range of input values x. Instead, one can use trigonometric and inverse trigonometric functions to produce exactly the desired behavior.

Desiderata

  • $x \in \mathbb{R}$
  • $f\left(x\right) \approx \mathrm{mod}\left(x\right)$
  • No copying of function across input space
  • Differentiable

Solution

For the range $\left[0, 2\pi\right]$, the function $$ f\left(x\right) = \mathrm{arctan}\left(-\frac{1}{\mathrm{tan}\left(x\right)}\right) + \frac{\pi}{2}$$ is identical to $\mathrm{mod}\left(x\right)$, however it has discontinuities at $\pi$ and $2\pi$ (as it should). This produces

modulo versus differentiable modulo

Differentiability

I'm assuming the differentiability is needed for some mechanics of a neural network, as is often the case when people are searching for differentiable functions. As such, I'm posting torch code which proves that this function is equivalent to modulo, and that it is differentiable:

import torch
import pytest
import numpy as np

def diff_mod(x, x_low, x_high):
    """Differentiable modulo function between x_low
    and x_high."""
    if not isinstance(x, torch.Tensor):
        x = torch.tensor(x)
    x = np.pi / (x_high - x_low) * (x - x_low)
    y = torch.arctan(-1.0 / (torch.tan(x))) + 0.5 * np.pi
    y = (x_high - x_low) / np.pi * y + x_low
    return y

# show that this is the same at a few test points
m0 = diff_mod(37.0, 0.0, 25.0)
assert torch.allclose(m0, torch.tensor(12.0))
m1 = diff_mod(3.5, -1.0, 1.0)
assert torch.allclose(m1, torch.tensor(-0.5))

# use pytorch's autodiff to prove this is at least
# approximately differentiable (torch certainly uses
# approximations at pi and 2pi for the derivative of
# tan)
ysum = y.sum()
with not pytest.raises():
    ysum.backward()
$\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.