The Mathematical Hacker (2012)

> But rarely in these discussions will you find relevant mathematical considerations. If the goal is to compute a Fibonacci number or a factorial, the proper solution is not a recursive function, but rather knowledge of mathematics.

If you want precise results for large sizes, then the integer-arithmetic recurrence is faster than computing the square root of 5 to very high precision and raising it to the nth power.

The author’s “proper solution” might better be named the “naive undergraduate introductory linear algebra student solution”. Or maybe “18th century analytic solution ignorant of computer number formats”.

> They run in constant [...] time

If we are going to artificially limit ourselves to numbers smaller than the precision of e.g. double precision floats, then the integer algorithms might just as well be considered “constant time”, where the constant is just whatever it takes to compute the largest value we are considering.

Or alternately we can just precompute and cache the entire set of them if we want. There are only 78.

Here’s a Javascript implementation

  const fibcache = [
    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
    377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
    28657, 46368, 75025, 121393, 196418, 317811, 514229,
    832040, 1346269, 2178309, 3524578, 5702887, 9227465,
    14930352, 24157817, 39088169, 63245986, 102334155, 
    165580141, 267914296, 433494437, 701408733, 1134903170,
    1836311903, 2971215073, 4807526976, 7778742049, 
    12586269025, 20365011074, 32951280099, 53316291173, 
    86267571272, 139583862445, 225851433717, 365435296162, 
    591286729879, 956722026041, 1548008755920, 
    2504730781961, 4052739537881, 6557470319842, 
    10610209857723, 17167680177565, 27777890035288, 
    44945570212853, 72723460248141, 117669030460994,
    190392490709135, 308061521170129, 498454011879264, 
    806515533049393, 1304969544928657, 2111485077978050, 
    3416454622906707, 5527939700884757, 8944394323791464];

  const fibonacci = (n) => fibcache[n];

Let's just accept that there are different kinds of math and people are interested in different kinds of math. The lisp school may especially like the beauty of recursion (recursion theory, aka computability theory is a branch of math), and the fortran school may like the beauty of calculus and numeric computing. This isn't necessarily exclusive. I can write a naïve recursive function for Fibonacci numbers, or I can derive the "constant-time" formula using generating functions on the fly. Or I can find a method better than both using matrix exponentiation. These are all math. There's no need to denigrate one school over another, just like there's no need to denigrate one branch of math over another.

I agree with his main point.

Programming will become true engineering soon. In a few decades, we will be building mainstream software with formal guarantees. And for that, there's tons of abstract algebra needed as a foundation, once you try to digest [1-6] and whatever replaces them in the future.

It's tragic most CS programs do not emphasize this a bit more.

[1] https://www.elsevier.com/books/lectures-on-the-curry-howard-...

[2] https://softwarefoundations.cis.upenn.edu/

[3] https://www.cis.upenn.edu/~bcpierce/tapl/

[4] https://www.springer.com/gb/book/9783540654100

[5] http://www.concrete-semantics.org/

[6] http://adam.chlipala.net/frap/

I think the greatest link is aesthetic, the instinct for power and simplicity. Mathematics and programming are both the creation of weightless structures that are limited only by their tractability by human intellect.

Of course that perspective ignores two important things: physical constraints on performance, and the relationship of data to facts in the real world. From these constraints programming also takes on the characteristics of natural science and engineering. These considerations come into play as well, but so often the limiting resource is human time and intellectual bandwidth, requiring a simpler, easier solution.

In mathematics, the scale can be much grander than anything yet produced in computing. Calculus is just breathtaking -- the signature accomplishment of the greatest mathematicians of their time, refined over hundreds of years into a tool that can be wielded by ordinary teenagers. It might seem shallow to compare such a sweeping achievement to mundane programming tasks such as writing enterprise business logic. Yet, if you ignore scale and universality, the intellectual task is the same: to take something that requires careful thought and close familiarity with the product requirements today, and boil it down to something that can be understand at a glance six months from now by someone who was not involved in the initial development. To distill patterns of thought internalized via close familiarity with the motivating problems into easily defined and digested concepts.

Leslie Lamport (of Paxos, LaTeX, and TLA+ fame) has been making this point for years. Basically that in order to design a piece of software, you need to be able to create a spec, and the best way of doing that is through mathematics.

E.g.

- https://lamport.azurewebsites.net/tla/math-knowledge.html

- https://youtu.be/-4Yp3j_jk8Q

This question of the relationship between math and CS always boggles my mind. Computers are, in a very real sense, automatic math machines. Programmers are, in a very real sense, telling the automatic math machines what math to do.

Now we've built ourselves a large number of layers of abstraction in an attempt to forget these things. And with those abstraction layers, programmers can be reasonably productive without having to think about their problems in terms of the math that the underlying math machine is doing. But in my mind, if someone wants to call themselves a computer scientist, they are necessarily concerned with the underlying math being done.

Besides the question of whether the Fibonacci sequence is a good or bad example, here’s a different objection to the author’s thesis:

If software development is ripe for a mathematics-driven leap forward, just like logistics and baseball, why hasn’t it happened yet?

If software developers and baseball coaches were both sitting next to low-hanging fruit that merely required a bit of mathematical knowledge and spreadsheet-wrangling to exploit, I would have expected the people already using computers -- the software developers -- to find it first. What’s different, and why?

It could be that software is inherently less amenable to statistical and numeric approaches than baseball, and that’s just the way it is. When you look at baseball the right way, you have a great mass of data with fairly simple and consistent rules, ideal for a statistical approach. When you look at a typical software system, you have a mass of special-case business logic, with no real simplifying assumption to be found.

In cases where “big data” is available, successful companies are using statistics to exploit regularities in the system.

So maybe what the author is arguing for is already happening, albeit on an somewhat smaller and slower scale, and maybe this is inherent in the nature of software.

Applied mathematics, basically calculus, is great but it can’t do everything. The author seems to be ignoring discrete mathematics (which a lot of the “Lisp hacks” he dismisses would fall under). Then there are sociological issues, such as documentation, unit testing, debugging, modularity, maintenance of legacy systems.

Plenty of researchers have tried applying a data-driven approach to testing and debugging, and I think it’s safe to say no-one has completely cracked it yet. If another recent paper posted here is to be believed, we don’t even know if there’s a significant difference in bug rates between static and dynamic typing.

Article misses the point on recursion. It isn't about solving the study questions. They were only chosen as self-contained examples. A better example is navigating tree structures or divide and conquer algorithms but that requires more context. Math is useful because it's a common language we expect to have been exposed to before programming.

> Lisp-school essayists [...] spend their time worrying about how to make code more abstract. This kind of thinking may lead to compact, powerful code bases, but in the language of economics, there is an opportunity cost. If you’re thinking about your code, you’re not thinking about the world outside, and the equations that might best describe it.

Another way of saying the same thing in a positive light is to say that these things have already been thought about and can be applied to take advantage of opportunities where applicable.

> Although the early years in the twenty-first century seem to be favoring the Lisp-school philosophy, I predict the balance of the century will belong to the Fortran-school programmers

This part does seem to be happening. Just look at Apache Storm v2 port from Clojure to Java:

"While Storm’s Clojure implementation served it well for many years, it was often cited as a barrier for entry to new contributors. Storm’s codebase is now more accessible to developers who don’t want to learn Clojure in order to contribute."[0]

[0] https://www.dm4r.com/tech/apache-storm-v2-0-porting-from-clo...

The Fibonacci example is interesting. If you want arbitrary precision, then the naive recursive method is exponential in $n$ to compute $F_n$. The loop method (recursive method with cache) is in $O(n^2)$. Indeed you only have $n$ steps in the loop, but at step $k$ you add $F_k$ and $F_{k+1}$ which have $O(k)$ bits so the total costs is $O(n^2)$. Finally the matrix/formal \sqrt{5} algorithm costs $O(n log n)$.

Indeed, using fast exponentiations, you only need $O(log n) matrix multiplications. But the dominant cost is actually at the last step, where you multiply two numbers of size $O(n)$ bits for a total cost of $O(n log n)$.

Speaking of mathematics in programming: I find it remarkable that the recent convergence of async programming into the use of promises and async/await (in python, js, rust...) is a weak form of the continuation monad. And the continuation monad is a form of the 'not not' Lawrere topology!

Not to say anything about the central thesis of the post, but the two examples of how deeper mathematical knowledge can lead to better programming are just terrible examples. As someone whose background was originally mathematics and starting programming relatively late, I can very much relate to thinking Binet's formula for Fibonacci numbers or gamma function for factorials might be faster than recursive methods. But when you actually learn about how ints, floats and their arithmetic is implemented at a low level, how cache and memory works etc, you realise that recursive methods for those two problems are actually your best bet, both for speed and accuracy. So ironically, these are examples where knowing much about low level coding and computing architecture helps you more than knowing more advanced mathematics.

No mention of Hoare triples, predicate transformers, loop invariants, or any of the other formal machinery that was discovered 50 years ago and thoroughly solves the problem. The author means well, but this is completely uninformative.

Dijkstra was trained as a Mathematical Engineer for example. Fact is, if astronomers had the mindset of most programmers, they'd call their field Telescope Science.

2013: https://news.ycombinator.com/item?id=6953774

2012: https://news.ycombinator.com/item?id=4915328

> the Lisp hacker is more likely to ask the irrelevant question: how can I reduce these two functions down to one function?

Except... mathematicians are very frequently going to be doing the same thing: asking if there is some generalization that covers two seemingly independent cases. Otherwise, the author should/would probably be talking about Stirling's approximation instead of the log gamma function in that piece.

More knowledge of mathematics relevant to a given domain an application is written for might often be a good thing -- I think that's an overarching point worth examining.

But if you're going really to look to mathematics as a guiding light, it's not going to be super useful in criticizing the drive for abstraction.

While we’re talking about metaphors: this reminds me of the distinction between craft and art. Where one is the creation or something elegant and functional (craft, lisp), the other treats more important the ideas being put into practice (art, fortran).

I think the article’s artificially limiting its point to mathematics - there are plenty of other disciplines where we can find well-tread useful metaphors, etc.

This is an excellent article. It motivated me to adopt a more Fortran morality, where my assumptions or so function first on underlying scientific principles, when I search for practical problems to solve.

Unfortunately I have to strongly disagree with the author's central thesis.

> But I think that most programmers who are serious about what they do should know calculus (the real kind), linear algebra, and statistics. The reason has nothing to do with programming per se — compilers, data structures, and all that — but rather the role of programming in the economy...One way to read the history of business in the twentieth century is a series of transformations whereby industries that “didn’t need math” suddenly found themselves critically depending on it.

There are two ways to interpret the claim that more programmers should know advanced math. One of them, which the author preempts, is the idea that programmers will improve their own work through significant mathematical maturity. It seems the author and I already agree that isn't the case, so I won't address this interpretation. But I still consider this interpretation to be more defensible than the other one.

The other way to interpret it, which the author seems to be explicitly pushing, is that programmers with a strong mathematical background will be better situated to proactively find fertile areas of the economy which can be improved through a combination of computing and advanced math. I don't believe this is realistic. None of the author's specific examples - control theory, optimization, linear programming, econometrics, or Black-Scholes - were pioneered by generalist engineers with a strong grounding in mathematics. They were just applied mathematicians (and in a few of those cases, repurposed pure mathematicians).

Likewise the bar is constantly rising. Knowing calculus, linear algebra and statistics won't empower you to make significant, groundbreaking improvements to any major field. That knowledge is necessary but insufficient. What's considered low hanging fruit these days is something that could be conceivably noticed and tackled by a postdoc. Mathematics itself is ossifying as a field of specialists, to the point where prominent researchers within subfields like algebraic geometry can be unfamiliar with each other's principal work.

This is really why find the appeal to economic advancement less than convincing - every advancement the author mentions has an implicit foundation in specialization. Historically, the most notable advancements in technology have come about through division of labor and cross-pollination. You would be better served by having two collaborating teams of mathematicians and engineers than by a team of engineers who know undergraduate math. It's already common for applied mathematicians to be able to program competently; they dominate the authorship of fast, low level math libraries. If you need them, hire them.

Conversely, I would argue we should actually reduce the education for more developers, not add even more material to it. Most developers already don't need to learn a significant amount of the material in a standard computer science degree. Piling on math courses isn't going to be a fundamental improvement for the vast majority of engineers working on real world software.

Fast forward a few years, now with the demand of learning-based software, there is no doubt that mathematics is indeed a requirement for data-driven software.

Although you may not need to know the math to build such software, given the tools that we have available. However you would need to know the math in order to understand the limitations, pros/cons of a particular ML algorithm for a given application (at the very least).

Theoretical fluid dynamicist here. I'm fairly decent with math, or at least solving differential equations. Related to the essay, I've always found it odd how many people with a CS background tend to "compute first, ask questions later." My experience has been that analyzing a problem first is generally a good idea, but CS folks typically don't in my experience. Exact or good approximate solutions to problems often exist, perhaps only for relatively simple problems, but still.

Sometimes computation is necessary, but that doesn't mean you'll save time by avoiding analysis entirely. When mathematical analysis succeeds, the time saved can be considerable. And you can combine both, e.g., recently I sped up a non-linear algebraic equation solver for my work by using an ansatz that I derived using the perturbation method. (Also probably helps the solver converge to the right solution.)

One possible explanation: https://en.wiktionary.org/wiki/if_all_you_have_is_a_hammer,_...

A huge 3rd category of programmers is entirely missing: those that don't care about abstraction at all, be it mathematical or linguistic. I think the priority for our industry is to get those on board, then we can discuss what tools for abstraction they should specialize in.

just doing a double click on the Fibonacci Solution :hypothetically speaking, can a compiler take the recursive solution and optimize it to the Binet's formula in machine code? . and obviously apply that technique to other similar problems?.

Just wrote an article about the same topic:

https://gist.github.com/justinmeiners/f7d08f99e7e9b8b84f0183...

I agree with the point that the author brings up but I think there is a broader point to discuss with regards to a mathematical focus in education. China, for example, is putting a large focus on applying a mathematical modeling perspective to their K-12 education, just look at the results of the MCM of the past few years. [1] I was lucky to be exposed to that frame of thinking in high school and I think it will become ever the more important in all areas, not just hacking, for people to have some sort of training in that respect.

[1] https://www.comap.com/undergraduate/contests/mcm/contests/20...

Knuth is one of the few authors that shows the derivation of the Binet's formula for Fibonacci numbers.