The Mathematical Hacker (2012)(evanmiller.org)
evanmiller.org
The Mathematical Hacker (2012)
https://www.evanmiller.org/mathematical-hacker.html
87 comments
I want to make the same objections (among others) but... interestingly, all of these actually reinforce the author's overarching point, which is less that everyone should be using closed forms for fibonacci and factorial computations, and more that an analytical understanding of conceptual model and computing implementations often matters more than the due generally given. You're able to make the critical evaluation of closed-form solutions using doubles vs other options precisely because you're practicing the approach he's recommending (albeit, apparently, a little bit better!).
The GP demonstrates that the mathematics alone cannot produce a good software and does not necessarily refute the OP.
You need to know a lot more computers than mathematics to know that floating point numbers are nothing like real numbers, neither are machine implemented integers.
Not necessarily. Error analysis with floating point numbers is closely related to the mathematics, you have no other way. You can use several heuristics, like avoiding catastrophic cancellations or better summation algorithms, to improve error bounds and there is even an automatic approach like Herbie [1], but ultimately you can't be as sure without error analysis. (Note that the interval arithmetics or unum or posit or whatever are crude but useful approximations to the proper error analysis.)
[1] https://herbie.uwplse.org/
[1] https://herbie.uwplse.org/
> Note that the interval arithmetics or unum or posit or whatever are crude but useful approximations to the proper error analysis.
"crude but useful approximations" is such a strange view. The purpose of machine-controlled error arithmetics is to give the programmer a powerful language construct that enables evaluation of a function or algorithm for arbitrarily small margin of error, using automatically revised accuracy in the intermediate steps. Error analysis is a math subject that gives us better algorithms. One needs both for hitting that desired margin of error with certainty within as short time as possible.
"crude but useful approximations" is such a strange view. The purpose of machine-controlled error arithmetics is to give the programmer a powerful language construct that enables evaluation of a function or algorithm for arbitrarily small margin of error, using automatically revised accuracy in the intermediate steps. Error analysis is a math subject that gives us better algorithms. One needs both for hitting that desired margin of error with certainty within as short time as possible.
> a powerful language construct that enables evaluation of a function or algorithm for arbitrarily small margin of error, using automatically revised accuracy in the intermediate steps.
AIUI, this is what "constructive (or 'exact') real numbers" give you, and it's quite computationally-intensive. Error arithmetic/interval arithmetic/etc. are only approximations to it. In many cases people don't even bother with the real deal because they're computing way more than one single result, so roundoff errors can be thought of as just one additional source of noise that is going to be averaged out over many 'steps'.
AIUI, this is what "constructive (or 'exact') real numbers" give you, and it's quite computationally-intensive. Error arithmetic/interval arithmetic/etc. are only approximations to it. In many cases people don't even bother with the real deal because they're computing way more than one single result, so roundoff errors can be thought of as just one additional source of noise that is going to be averaged out over many 'steps'.
I agree, interval arithmetics/unums/$other_fancy_number_concept is just a start, not the end of getting reliable results. However, the roundoff errors that FPU generates are hardly controllable. In general they are not just a simple noise that cancels out on averaging. And some calculations do not do averaging at all.
Moreover, the C implementation quoted in the article will give a negative -1323752223 after the 46th number (1836311903). So while I understand the author's point, I think this particular example is not a really good choice.
AIUI, you don't need to "compute" sqrt5 to high precision in order to use that closed form! Just "adjoin" it to Q and compute symbolically over Q(sqrt5).
Yes, and that symbolic computation is the same arithmetic as the original algorithm the author was complaining about.
Personally I like the version better where you explicitly work in terms of integers like a + bφ or rational numbers like (a + bφ)/c. https://observablehq.com/@jrus/zome-arithmetic very handy when working with the symmetry system of the icosahedron. https://observablehq.com/d/cae3fea57d7cf2d4
Personally I like the version better where you explicitly work in terms of integers like a + bφ or rational numbers like (a + bφ)/c. https://observablehq.com/@jrus/zome-arithmetic very handy when working with the symmetry system of the icosahedron. https://observablehq.com/d/cae3fea57d7cf2d4
Nice. Thanks for that.
The computation over Q(sqrt(5)) is essentially identical to the matrix form.
> 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.
Know what's even faster? Exponentiating a 2x2 matrix of integer coefficients. And again, that's what a bit of math tells you, so I think the point of the author holds.
Know what's even faster? Exponentiating a 2x2 matrix of integer coefficients. And again, that's what a bit of math tells you, so I think the point of the author holds.
Those are two ways of saying the same thing. If you want to use a fancier algorithm, then fine.
Then I might have misunderstood what you meant by "integer-arithmetic recurrence"; my understanding of it was that it was the traditional recursive implementation of Fibonacci, which has much worse complexity than matrix exponentiation, and is not the same algorithm at all.
There are several ways we might try to optimize this calculation. Really depends on the context/constraints.
Since the recurrence is always the same we can e.g. use the identities F_{m+n-1} = F_mF_n + F_{m-1}F_{n-1} and F_{m+n} = F_mF_n + F_mF_{n-1} + F_{m-1}F_n to precompute and cache all of the terms for 2^{n-1} and 2^{n}, and then multiply the appropriate ones together to find whatever value we need based on a binary expansion of the index we want to find a fibonacci number for.
This is the same idea as fast matrix exponentiation but saves low-level arithmetic and half of the space, because two of the terms in the matrix are basically redundant.
Since the recurrence is always the same we can e.g. use the identities F_{m+n-1} = F_mF_n + F_{m-1}F_{n-1} and F_{m+n} = F_mF_n + F_mF_{n-1} + F_{m-1}F_n to precompute and cache all of the terms for 2^{n-1} and 2^{n}, and then multiply the appropriate ones together to find whatever value we need based on a binary expansion of the index we want to find a fibonacci number for.
This is the same idea as fast matrix exponentiation but saves low-level arithmetic and half of the space, because two of the terms in the matrix are basically redundant.
I am wondering if all three methods (sqrt(5) method, 2x2 matrix exponentiation, and jacobolus's power of two method) take approximately the same amount of time --- slightly less than O( log(F_n)*log(F_n)^2) (using Fürer's algorithm for integer multiplication.)
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/
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/
In the future, I really don't think the vast majority of software engineers will need to know any abstract algebra in order to use or write software with strong formal guarantees. The history of software engineering (and most engineering disciplines in general) is a narrative in which practitioners need to know less theory as time goes on.
I expect that formal methods will become another specialization that most engineers don't need to directly work with, alongside things like cryptography and low level arithmetic.
I expect that formal methods will become another specialization that most engineers don't need to directly work with, alongside things like cryptography and low level arithmetic.
Yes.
Nowadays it is mostly about tools/frameworks. You don't even need to master the programming language that you are using.
I work mainly with Java stack and see so many devs with 10+ years of experience who know nothing about Java internals, who know nothing about how Java's hashmap works...heck, many of them can't even explain what some _keywords_ do: volatile, transient.
Nevertheless, they 'successfully' close their JIRA tickets and deliver.
Nowadays it is mostly about tools/frameworks. You don't even need to master the programming language that you are using.
I work mainly with Java stack and see so many devs with 10+ years of experience who know nothing about Java internals, who know nothing about how Java's hashmap works...heck, many of them can't even explain what some _keywords_ do: volatile, transient.
Nevertheless, they 'successfully' close their JIRA tickets and deliver.
> Nevertheless, they 'successfully' close their JIRA tickets and deliver.
Leave those quotes away and I agree. If they know enough Java to finish those tickets in a way that the bug is actually fixed and the fix itself does not impose more technical debt than needed, then those developers know exactly enough java and close their tickets successfully indeed.
I wrote my own compiler for a subset of Java (including inheritance and overriding) to MIPS in uni, among the top in class, and am currently looking to compile Haskell to a very neat kind of calculus (check out "Formality-Core"). It was a really fun experience, but I feel that compilers are immensely overhyped. I guess that is because it is a hard topic and for many people, the investment is huge, so they exagerate the benefits they percieve to reap.
Being proud of understanding something or admitting that a topic is hard is all fine, but I am absolutely allergic to elitism where it isn't just. And no, in 2019, knowing all about parsing and register allocation won't unlock superpowers anymore.
Leave those quotes away and I agree. If they know enough Java to finish those tickets in a way that the bug is actually fixed and the fix itself does not impose more technical debt than needed, then those developers know exactly enough java and close their tickets successfully indeed.
I wrote my own compiler for a subset of Java (including inheritance and overriding) to MIPS in uni, among the top in class, and am currently looking to compile Haskell to a very neat kind of calculus (check out "Formality-Core"). It was a really fun experience, but I feel that compilers are immensely overhyped. I guess that is because it is a hard topic and for many people, the investment is huge, so they exagerate the benefits they percieve to reap.
Being proud of understanding something or admitting that a topic is hard is all fine, but I am absolutely allergic to elitism where it isn't just. And no, in 2019, knowing all about parsing and register allocation won't unlock superpowers anymore.
That’s true. And that’s the artifact of the difference between software engineering and computer science. One can be a successful software engineer, consistently delivering useful code that just works. Does it have to be the best design and best code ever. Maybe, maybe not. Does it really matter? Maybe, maybe not. Real computer scientists would be more concerned over design and efficiency. Any important software development project would benefit from both types of professionals.
Yes. It is more understanding which library to choose or which eco.
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.
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
E.g.
- https://lamport.azurewebsites.net/tla/math-knowledge.html
- https://youtu.be/-4Yp3j_jk8Q
I agree in principle, but there’s a rather fundamental problem here: writing the spec has to be easier than writing the program. Otherwise,we should just write a compiler for the spec language and save ourselves a step, or blunder on by writing the program without a spec, as is usually done.
I think if you're doing your spec as a combination of high level set theory or algebra and some prose, then it should be easier than writing the program itself (assuming you know a bit about math and how to write a spec).
The question is how much time is it worth putting into writing a detailed spec. I think the answer is that it really depends on the size and complexity of your software.
I think the idea is that programmers have to be comfortable with writing something down, even if it's not perfect. A half-baked spec is better than no spec, basically. Otherwise you will likely end up with spaghetti code that needs to be rewritten or scrapped.
The question is how much time is it worth putting into writing a detailed spec. I think the answer is that it really depends on the size and complexity of your software.
I think the idea is that programmers have to be comfortable with writing something down, even if it's not perfect. A half-baked spec is better than no spec, basically. Otherwise you will likely end up with spaghetti code that needs to be rewritten or scrapped.
I already write my specs as a combination of math and prose. It’s just that the math portion is empty. /s
Seriously, though, that prose portion is where the vast majority of the bugs will be.
Seriously, though, that prose portion is where the vast majority of the bugs will be.
Writing a useful TLA+ spec will usually be easier than writing an operational program with the functionality the spec describes, because it lets you abstract over the uninteresting parts.
That seems like it just pushes all the bugs into the “uninteresting” parts.
It pushes the bugs to things that are easier to test. You write tests for things like "we properly error on a malformed input" and write TLA+ specs for things like "there are no awful concurrency bugs spanning three servers in two regions."
Not really. Some parts are harder to reason about than others, especially interactions between components of a distributed system.
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.
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.
A fruit picker is doing math all the time: calculating distance to fruit, using inverse kinematics to move limbs in order to pick a fruit and put it in a basket in a way that does not deform or damage the fruit... and the list goes on and on. There's math in everything.
The fruit picker does not have to think about that math or understand it, just like most programmers do not have to understand what happens at the low level.
The fruit picker does not have to think about that math or understand it, just like most programmers do not have to understand what happens at the low level.
Except the programs that programmers write very directly correspond to mathematics. The formal semantics of programming languages maps expressions in programming languages to mathematical expressions.
As such, all ordinary programmers are demonstrably writing mathematics - just with syntax, semantics, and applications that are unlike those of more traditional math.
As such, all ordinary programmers are demonstrably writing mathematics - just with syntax, semantics, and applications that are unlike those of more traditional math.
I don't disagree with you, but I think your statement is roughly like: all ordinary composers are writing music theory, or all ordinary language users are doing linguistics.
Math is a way to add structure and understand the activity that programmers are engaged in. A lot of programming languages and computer architectures have been developed without the math in mind. There is still a lot of mathematical structure to be discovered in what an ordinary programmer does, I think. But yes, much of computer science, programming, etc feels very close to math, even compared to physics, linguistics, music theory, etc.
Math is a way to add structure and understand the activity that programmers are engaged in. A lot of programming languages and computer architectures have been developed without the math in mind. There is still a lot of mathematical structure to be discovered in what an ordinary programmer does, I think. But yes, much of computer science, programming, etc feels very close to math, even compared to physics, linguistics, music theory, etc.
The difference is that programming languages are formal languages. They simply have a different syntax and semantics from traditional mathematics. The mapping between them is isomorphic.
> A lot of programming languages and computer architectures have been developed without the math in mind.
They're still formal systems. In a broad definition, they're mathematics themselves. In a narrower definition, they map isomorphically to more rigorous mathematics.
> A lot of programming languages and computer architectures have been developed without the math in mind.
They're still formal systems. In a broad definition, they're mathematics themselves. In a narrower definition, they map isomorphically to more rigorous mathematics.
I look at https://en.wikipedia.org/wiki/Formal_system and I don't really see much resemblance to how mainstream programming languages are defined.
Some mainstream programming languages do not even a formal grammar for their syntax. Valid syntax is whatever is accepted by the parsing program. Much more commonly there isn't a formal specification of the semantics. The semantics are similarly defined by the implementation.
I think you might be arguing that the implementation is itself part of a formal system, involving the processor. I don't think I feel the same way. The CPUs operation can be described precisely in terms of rules, in the same way that Newtonian physics can, with the difference that digital systems are more robust to modeling errors. This is what the Strawberry picker example above, I believe, was meant to touch on. Just because math is used to model something doesn't mean the thing is math.
Some aspects of computational sciences feel like they are math. Other aspects seem like they're just modeled by math.
Some mainstream programming languages do not even a formal grammar for their syntax. Valid syntax is whatever is accepted by the parsing program. Much more commonly there isn't a formal specification of the semantics. The semantics are similarly defined by the implementation.
I think you might be arguing that the implementation is itself part of a formal system, involving the processor. I don't think I feel the same way. The CPUs operation can be described precisely in terms of rules, in the same way that Newtonian physics can, with the difference that digital systems are more robust to modeling errors. This is what the Strawberry picker example above, I believe, was meant to touch on. Just because math is used to model something doesn't mean the thing is math.
Some aspects of computational sciences feel like they are math. Other aspects seem like they're just modeled by math.
> The formal semantics of programming languages maps expressions in programming languages to mathematical expressions.
Which mathematical expressions do memcpy, fork, and putchar map to?
Which mathematical expressions do memcpy, fork, and putchar map to?
memcpy is trivially modeled as an operation on an underlying store. Such stores are a basic feature of any programming language semantics.
Putchar is easily modeled in terms of something like a state monad. In earlier semantics, such as the original denotational semantics, it was just modeled directly as a store that was threaded through a program, i.e. passed to every function.
Fork is modeled by process calculi.
If you think programming languages somehow can't be modeled by mathematics, you're essentially taking the position that they're doing something supernatural.
Putchar is easily modeled in terms of something like a state monad. In earlier semantics, such as the original denotational semantics, it was just modeled directly as a store that was threaded through a program, i.e. passed to every function.
Fork is modeled by process calculi.
If you think programming languages somehow can't be modeled by mathematics, you're essentially taking the position that they're doing something supernatural.
Library functions are not part of the formal semantics of programming languages.
Only a small fraction of programmers deal with math beyond basic arithmetic and simple Boolean logic.
The point is that by writing a program in a programming language, you're doing math whether you know it or not, because all existing programming languages have a direct, isomorphic mapping to mathematical expressions.
It goes well beyond "basic arithmetic and simple Boolean logic". One of the comment semantic descriptions of imperative programming languages involves a stack of monads representing the various effects that programming language support.
While most programmers may not be aware of this, they're still writing working expressions in a formal language which is equivalent to this.
It goes well beyond "basic arithmetic and simple Boolean logic". One of the comment semantic descriptions of imperative programming languages involves a stack of monads representing the various effects that programming language support.
While most programmers may not be aware of this, they're still writing working expressions in a formal language which is equivalent to this.
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.
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...
> 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!
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.
Is recursion really that good? It seems calculating those once and storing results in array and then only accessing the array would be best.
Sure, if you need to continually access the same values then you'd want to save them but whether you need to reuse the same values or just do a one off calculation, you still need to compute the value the first time in some way.
For Fibonacci numbers, expressing terms of the sequence as a 2x2 matrix exponentiatied and then exponentiating by repeated squaring let's you get the n-th Fibonacci number in O(log n) multiplications. It's straightforward, if you get an input n and handle arbitrary precision integer arithmetic, you can calculate F_1000 quickly and without much hassle. Compare that to Binet's formula: How many digits of precision will you need to compute the golden ratio to ensure your result from Binet's formula is correct? And how will you compute it to that many digits? And that's not even worrying about the fact that floating point multiplication doesn't correspond exactly to multiplication of real numbers, so you may need to switch to arbitrary precision floating point arithmetic.
For Fibonacci numbers, expressing terms of the sequence as a 2x2 matrix exponentiatied and then exponentiating by repeated squaring let's you get the n-th Fibonacci number in O(log n) multiplications. It's straightforward, if you get an input n and handle arbitrary precision integer arithmetic, you can calculate F_1000 quickly and without much hassle. Compare that to Binet's formula: How many digits of precision will you need to compute the golden ratio to ensure your result from Binet's formula is correct? And how will you compute it to that many digits? And that's not even worrying about the fact that floating point multiplication doesn't correspond exactly to multiplication of real numbers, so you may need to switch to arbitrary precision floating point arithmetic.
I don't think it's too hard to get the sqrt(5) to a high enough degree of precision. (Probably could use Newton-Raphson.) On my computer it takes about 0.05 seconds to compute sqrt(5) to one million digits. It takes about 0.01 seconds to multiply two 500,000 digit integers. If you want to computer F_n using Binet's formula I think you need about (log(F_n)/log(10) + 10) digits for sqrt(5).
I computed Fibonacci(20*10^6) using Binet's formula. The answer has 4179753 digits. I computed sqrt(5) to 4179753 digits and applied the formula. The result was correct.
The time to compute sqrt(5) was 0.23 sec. The time compute the formula (I dropped the insignificant 1-sqrt(5) term) was 2.8 seconds. When I used the built in Mathematica function to compute the Fibonacci number, it took 0.12 seconds.
The time to compute sqrt(5) was 0.23 sec. The time compute the formula (I dropped the insignificant 1-sqrt(5) term) was 2.8 seconds. When I used the built in Mathematica function to compute the Fibonacci number, it took 0.12 seconds.
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.
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.
> Dijkstra was trained as a Mathematical Engineer for example.
"Mathematical engineering" looks like a modern invention. In any case, his undergraduate degree was in physics.
"Mathematical engineering" looks like a modern invention. In any case, his undergraduate degree was in physics.
Dijkstra appears to have thought otherwise: "I worked at the time at the Department of Mathematics of the Eindhoven University of Technology in the Netherlands, and told at that conference that the official academic title our graduates earned was 'Mathematical Engineer', and most of the Americans began to laugh, because for them it sounded as a contradiction in terms, mathematics being sophisticated and unpractical, engineering being straightforward and practical."[1]
Before quibbling, note I said he was trained as a Mathematical Engineer, not that he had a degree in Mathematical Engineering.
[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD11xx/E...
Before quibbling, note I said he was trained as a Mathematical Engineer, not that he had a degree in Mathematical Engineering.
[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD11xx/E...
Not so modern an invention then. Thanks for the pointer.
(Anyway, participating in the training of "mathematical engineers" and being trained as one are not necessarily the same thing.)
(Anyway, participating in the training of "mathematical engineers" and being trained as one are not necessarily the same thing.)
I've heard this analogy several times, but I've never met an astronomer who didn't know how a telescope works.
That analogy would only make sense if you built the universe inside the telescope.
No: telescopes are tools to study the universe, just as computers are tools for studying computation.
I don't look at computers as tools for studying computation. Instead, they are tools for performing computation.
"A scientist builds in order to learn; an engineer learns in order to build." - Fred Brooks
perhaps performing computations is to studying computation as observing the universe through a telescope is to studying it.
> perhaps performing computations is to studying computation as observing the universe through a telescope is to studying it.
This is an interesting thought, but the two seem fundamentally different in nature (active vs passive).
This is an interesting thought, but the two seem fundamentally different in nature (active vs passive).
Yes, and to a certain extent, you can study computation without a digital computer. Computation can be abstracted away from the devices that perform it. You can, for example, study Big O notation and theoretical computational complexity of algorithms without actually using a computer.
> 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.
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.
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.
> 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.
I feel as though you have it backwards. Would you care to explain your rationale for fortran as art compared to lisp as craft?
> 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.
I feel as though you have it backwards. Would you care to explain your rationale for fortran as art compared to lisp as craft?
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.
> 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.
> 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).
With regards to control theory, whilst some key people like Bode [0] had mathematics degrees, others such as Kalman [1], Nyquist [2], and Black [3] had electrical engineering degrees. Claude Shannon had a bachelor's degree in both electrical engineering and mathematics.
[0]: https://en.wikipedia.org/wiki/Hendrik_Wade_Bode
[1]: https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n
[2]: https://en.wikipedia.org/wiki/Harry_Nyquist
[3]: https://en.wikipedia.org/wiki/Harold_Stephen_Black
With regards to control theory, whilst some key people like Bode [0] had mathematics degrees, others such as Kalman [1], Nyquist [2], and Black [3] had electrical engineering degrees. Claude Shannon had a bachelor's degree in both electrical engineering and mathematics.
[0]: https://en.wikipedia.org/wiki/Hendrik_Wade_Bode
[1]: https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n
[2]: https://en.wikipedia.org/wiki/Harry_Nyquist
[3]: https://en.wikipedia.org/wiki/Harold_Stephen_Black
I think I agree with a lot of your post, but do you really think something isn't worth learning just because other people are going to know it better? Will hyper-specialization make better developers? Or would developers be better if their education was more general?
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).
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,_...
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,_...
[deleted]
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?.
In the general case (for values of n bigger than double precision floats support), the Binet formula is slower.
The author’s proposed solution only works up to n = 78. If you want to speed up the calculation for small values, just cache them all.
The author’s proposed solution only works up to n = 78. If you want to speed up the calculation for small values, just cache them all.
ofc, but it is possible for compiler to be smart enough to"discover" this? and use similar heuristics for other similar problems?
In this particular case, it would not be useful.
Personally I don’t ever want a compiler trying to replace straight-forward integer algorithms with floating point formulas. YMMV.
Personally I don’t ever want a compiler trying to replace straight-forward integer algorithms with floating point formulas. YMMV.
No (and no time soon unless it's a special case coded in manually), but some simpler things are possible, see e.g. https://news.ycombinator.com/item?id=16259157.
Just wrote an article about the same topic:
https://gist.github.com/justinmeiners/f7d08f99e7e9b8b84f0183...
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...
[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.
Do you mean "one of the few computer science authors"?
We did this as whilst studying difference equations in first year undergraduate mathematics. I imagine most books dealing with the subject will include the Fibonacci equation as an example.
We did this as whilst studying difference equations in first year undergraduate mathematics. I imagine most books dealing with the subject will include the Fibonacci equation as an example.
ot: there's a really nice derivation in the first couple chapters of generatingfunctionology[0].
[0]: https://www.math.upenn.edu/~wilf/DownldGF.html
[0]: https://www.math.upenn.edu/~wilf/DownldGF.html
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