3 ms·

There is a calculational school of programming in which algorithms are derived from specifications in a presentation of first-order logic adapted to program der

There is a calculational school of programming in which algorithms are derived from specifications in a presentation of first-order logic adapted to program derivation. It does not seem to be popular on HN. "Programming: the derivation of algorithms" by Anne Kaldewaij is a good source for this. A derivation of an efficient algorithm to compute Fibonacci numbers is given, as well as for me the most memorable implementation of binary search. Miller should have used Kaldewaij's O(log(N)) algorithm to compute the n-th Fibonacci number, given below. def fib(n): """Lifted from Kaldewaij.""" a,b,x,y = 0,1,0,1 while n != 0: if n % 2 == 0: a,b = a * a + b * b, 2 * a * b + b * b n = n // 2 else: x,y = a * x + b * y, b * x + a * y + b * y n -= 1 return x As Kaldewaij remarks, the algorithm is harder to understand without its derivation. Of course there is TAOCP by Knuth, who added a supplement on probability to the mathematical preliminaries. Miller's suggestion that programmers should know calculus, statistics and linear algebra is sound, though perhaps pedestrian. There is no end to the mathematics one might apply. The article omits logic and dependent type theory. The Curry-Haskell-Lambek isomorphism theorem on the equivalence between the category of cartesian closed categories and functors and the category of simply-typed lambda calculi and translations is basic in the study of functional programming languages. Ramsey's theorem has been applied to program termination. I myself am interested in applications of game theory--though I am not giving away my secrets.

yetanotherphd 13y ago
That algorithm can be de-obfuscated (see my top level post for the intuition). The above is equivalent to calculating a power of a 2x2 matrix, and since matrix multiplication is associative, we can use the squaring trick. In python (I left out the code for matrix multiplication for brevity) this becomes def nth_power_assoc(comp, f, n): """Reduce n copies of f with associative operation comp (short for composition, not compare).""" if n < 1: raise ValueError if n == 1: return f if n % 2 == 1: return comp(nth_power_assoc(comp, f, n - 1), f) else: g = nth_power_assoc(comp, f, n / 2) return comp(g, g) def fib(n): M = ((1, 1), (1, 0)) M_n = nth_power_assoc(mmul, M, n) return M_n[0][0]
- ChristianMarks 13y ago
  Yes, of course, that's how the algorithm is derived. I have to say I prefer the "un-de-obfuscated" version, though it wasn't intentionally obfuscated--the code is the way it is in Kaldewaij's derivation from a matrix multiplication.

yetanotherphd 13y ago

That algorithm can be de-obfuscated (see my top level post for the intuition). The above is equivalent to calculating a power of a 2x2 matrix, and since matrix multiplication is associative, we can use the squaring trick. In python (I left out the code for matrix multiplication for brevity) this becomes def nth_power_assoc(comp, f, n): """Reduce n copies of f with associative operation comp (short for composition, not compare).""" if n < 1: raise ValueError if n == 1: return f if n % 2 == 1: return comp(nth_power_assoc(comp, f, n - 1), f) else: g = nth_power_assoc(comp, f, n / 2) return comp(g, g) def fib(n): M = ((1, 1), (1, 0)) M_n = nth_power_assoc(mmul, M, n) return M_n[0][0]

ChristianMarks 13y ago
Yes, of course, that's how the algorithm is derived. I have to say I prefer the "un-de-obfuscated" version, though it wasn't intentionally obfuscated--the code is the way it is in Kaldewaij's derivation from a matrix multiplication.