Automatic differentiation

In programming, one of the covenants is not to duplicate functionality. Otherwise, we get a code in which some areas are nontrivially dependent on others. When implementing some of the tasks, this principle is easy to follow, but others have problems: consider software that uses not very clever mathematical algorithms that require working with functions and their derivatives.

f(a : double ) : double
{
a*a + 3 * a
}

df(a : double ) : double
{
2*a + 3
}


It is obvious that, at a minimum, the code f and df are functionally dependent, and, perhaps, we are seeing duplication of functionality. The situation can be corrected if we recall the definition of the derivative and, accordingly, correct the df code:

df(a : double ) : double
{
def delta = 0.1;
(f(a+delta)-f(a))/delta
}

In this case, we got rid of duplication of functionality, but paid off with the accuracy of the program, since the optimal value of the delta parameter does not exist.

Serious engineers can solve this problem by programming, for example, in matlab and further code generation into their favorite programming language. But there is an opinion that code generation is evil, so I will talk about a different method.
')
The imaginary unit i is assumed by solving the equation x ² +1 = 0. By analogy, we introduce another imaginary unit d, which will solve the equation x ² = 0 and not equal to zero. Then we recall the decomposition of the function in a Taylor series:


If we substitute our imaginary unit as h and use the fact that d ² = 0, we get:

Thus, to find out the value of the derivative of the function f at the point x, it suffices to take the coefficient at the imaginary part of the number f (x + d). In modern languages, it is not a problem to define a class, for working with complex numbers, it is just as easy to define a class for working with these extended numbers. Below is an example translated into Nemerle:

public class Dual
{
public this (real : double , imaginary : double )
{
this .real = real;
this .imaginary = imaginary;
}

real : double ;
imaginary : double ;

public Real : double { get { real } }
public Imaginary : double { get { imaginary } }

public static @+(a : Dual, b : Dual) : Dual
{
Dual(a.real + b.real, a.imaginary + b.imaginary)
}

public static @-(a : Dual, b : Dual) : Dual
{
Dual(a.real - b.real, a.imaginary - b.imaginary)
}

public static @*(a : Dual, b : Dual) : Dual
{
Dual(a.real * b.real, a.real * b.imaginary + a.imaginary * b.real)
}

public static @/(a : Dual, b : Dual) : Dual
{
a*Dual(1/b.real, - b.imaginary / (b.real*b.real))
}

public static @:(k : double ) : Dual
{
Dual(k,0)
}
}


Now you can rewrite the example from the beginning of the article:

f(a : Dual) : Dual
{
a*a + 3.0 * a
}

f(a : double ) : double
{
f(Dual(a,0)).Real
}

df(a : double ) : double
{
f(Dual(a,1)).Imaginary
}

Obviously, we get the code for the derivative for free. The disadvantage of this approach is that it is necessary to redefine the elementary functions for working with dual numbers, but thanks to the resulting formula it is not difficult, the sinus overload is shown below:

public Sin(a : Dual) : Dual
{
Dual( Math .Sin(a.Real), Math .Cos(a.Real)*a.Imaginary)
}

I want more:

	Automatic differentiation
	Dual numbers
	Automatic Differentiation
	Automatic Di ff erentiation, C ++ Templates and Photogrammetry
	Nemerle

I wanted to create a Computer Science blog and put this post there, but on Habré, I hope that temporarily, you can’t create new blogs, so I’m posting Abnormal Programming on the blog. Computer Science blog was planned to be a place where you can write retellings, translations, annotations to articles falling under the definition of Computer Science, links to pdf and so on. Anyone who would like to write articles in this blog I advise you not to wait for it to open, but to write in “Abnormal programming” with the tag “to computer science”.