News for hackers. Stuff that matters.
Re:From scratch: reverse-mode automatic differentiation (in ... by martincmartin on Sunday June 14, 2020 @03:40PM (#23520667)
There's a straight forward algorithm for automatic differentiation. You can think of it like long division: tedious to do, but you can easily program a computer to do it.

Integration is a whole different ball game. It's essentially a puzzle: what function, when differentiated, produces this result? There are various heuristics you can apply, e.g. integration by parts. And there are some databases of common integrals. But in the end, there's no algorithm, integration requires ingenuity to solve.

Re:From scratch: reverse-mode automatic differentiation (in ... by Someone on Sunday June 14, 2020 @06:07PM (#23521782)
It’s slightly better. https://en.wikipedia.org/wiki/Risch_algorithm: “The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷)”

That algorithm isn’t easily programmed, though, and will fail in the many cases where the integral cannot be expressed in elementary functions.

Worse, according to that page, it needs the ability to check whether expressions are zero (https://en.wikipedia.org/wiki/Constant_problem), and that, in general, is undecidable if I understand that page correctly.

https://mathworld.wolfram.com/RischAlgorithm.html seems a tiny bit more optimistic about the limitations of this approach, but https://link.springer.com/chapter/10.1007/978-3-319-00894-3_... seems, to me, in line with what Wikipedia says.

Re:From scratch: reverse-mode automatic differentiation (in ... by pkaye on Sunday June 14, 2020 @11:43PM (#23523568)
There is also an open source rule based integrator that I came across.

https://rulebasedintegration.org/

Re:From scratch: reverse-mode automatic differentiation (in ... by adamnemecek on Sunday June 14, 2020 @05:27PM (#23521545)
No, with automatic integration you presumably would not get the integrated function, the same way you don't with dual number autodiff.
Re:From scratch: reverse-mode automatic differentiation (in ... by IngoBlechschmid on Sunday June 14, 2020 @05:30PM (#23521563)
Exactly.

Automatic differentiation works because we have the chain rule (f . g)'(x) = f'(g(x)) g'(x), telling us how to differentiate functions which are composed from simpler building blocks. But there is no analogous rule for integration.

Re:From scratch: reverse-mode automatic differentiation (in ... by a1369209993 on Monday June 15, 2020 @03:00AM (#23524567)
Technically there is:

  D f = f' <=> S f' = f  # inverse
  
  # chain rule
  D (f . g) x = D f (g x) * D g x
  # divide by D g x
  D (f . g) x / D g x = (D f) (g x)
  # S vs D inverse
  D (S f' . g) x / D g x = (f' . g) x
  # commute = and integrate both sides
  S (f' . g) x = S \x( D (S f' . g) x / D g x ) x
  # rename and drop argument
  S (f . g) = S \x( D (S f . g) x / D g x )
The problem is that the RHS is, in the general case, not any less complex (and often much more) than the LHS.

Edit: Note that (S f . g) is integrating only f, then composing with g, which is what you want; it's the S \x(...) that causes problems.

Re:From scratch: reverse-mode automatic differentiation (in ... by IngoBlechschmid on Monday June 15, 2020 @04:16AM (#23525054)
Nice observation, thank you for sharing!