11 ms·

Mathematics for Programmers [pdf]

589 points by signa11 6y ago

DanielMcLaury 6y ago
One subject that's pretty useful for programmers to understand reasonably well is numerical analysis, even if it's at a fairly basic level. It's amazing how quickly you run into problems in practice as soon as you try to do anything with floating point numbers. I didn't carefully read through the section on modular arithmetic, so maybe this is already there, but one thing worth noting that bites a lot of people is that using modular arithmetic for integer representations means that addition, subtraction, and multiplication work the same for signed and unsigned integers. This means that you can typically write arithmetic expressions involving these operations without worrying too much about whether things are being regarded as signed or unsigned at intermediate steps. As soon as you introduce division into the mix, though, the whole thing falls apart, and you have to be very careful about how the language is interpreting each subexpression.
- enchiridion 6y ago
  I'm not sure understand what you're saying with mod arithmetic. Can you provide an example?
  - macmmajor 6y ago
    You can think of it as applying a mod operator after each operation. Say we wanted to work with mod 5 Then 6 + 8 = 14 = 4 mod 5
    - eru 6y ago
      Doesn't work for division. At least not in general in a naive fashion.
  - BearsAreCool 6y ago
    Not OP, but I'll give it a shot. At a low level pretty much all standard integer math is mod arithmetic, typically mod 2^32 or 2^64 depending on if a computer is 32 or 64 bit. This means that when a number goes above this limit it "overflows" and only the part left after dividing by the mod size is left. Additionally, negative numbers are stored by essentially counting down from the maximum number that can be stored + 1, in scholarly terms this is the twos complement. For instance on a 32 bit system -7 as a signed integer would be stored identically to the unsigned integer (2^32)-7. For anyone new to programming, unsigned meaning an integer variable that can only be positive and signed being an integer variable that could be positive or negative. Now all of this combines to make addition, subtraction, and even multiplication essentially identical for signed and unsigned numbers. On an 8 bit system (so integers can be between 0 to 255 inclusive) you could be trying to add the signed number 40 and the unsigned number 200. Naturally, this is 200+40 or 240. Now inside the computer, 240 is stored in the exact same way that -16 is so it is important that the software knows the correct way to handle the variable. This is equivalent to subtracting 56 from 40, and the signed integer -56 is represented in the exact same way as the unsigned integer 200. Now this is where it starts to get crazy. What if you add the signed integer -5 (represented by 251 in the unsigned world) and the unsigned integer 100? Well it is equivalent to 251 + 100 = 351. However, now we encounter modular arithmetic, because this is an 8 bit system and the maximum value for an integer is 255 we calculate everythihg mod 256, so ar left with 351 % 256 = 95. You can mentally view this as the calculation occurring with 1s and 0s, where everytime a 1 is added to a 1, there is a single bit carried and the last bit is dropped, which is exactly how full and half adders work in a processor! This also works for multiplication! If we multiply -5 by 5, we get -25 easily. But for computers we do 251 * 5 = 1255. The modulo math starts to get tricky for us puny humans but for a computer it is trivial, 1255 % 256 = 231. As a signed integer that is equal to -25, as it is equivalent to (255+1-25). For division, everything is just crazy. 250/5 is way different than -5/5, no amount if mod arithmetic will save it. Unsigned 50 and signed -1 have completely different representations, and this is even an example without fractions and rounding. I may have went long winded, but hopefully this helps someone!
    - fmi11 6y ago
      You're a cool bear! Thanks for the detailed explanation!
    - eru 6y ago
      Purely on the mathematical side, you can define division as the inverse of multiplication, and then when you are working modulo a prime number, division works just fine. (But computers usually don't implement it that way.) As an example when working modulo 17 and you want to work out what division by 3 means. You want to solve equations like: x * 3 = 10 (mod 17). For this case, x = 9; because 9 * 3 = 27 = 10 (mod 17). In general when working modulo 17, 6 is the multiplicative inverse of 3. Ie 6 * 3 = 1. Thanks to Fermat's Little Theorem you can find multiplicative inverses very easily, y^(p-2) mod p gives you the inverse of y. (Most programming languages won't know that you are going to apply a mod afterwards, so they just give you eg rounded or truncated integer division. Which is completely different in general.)
      - Tainnor 6y ago
        Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.
        threatofrain 6y ago
        Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.
        Tainnor 6y ago
        Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
  - alblue 6y ago
    You probably do this all the time with time without realising it. If it’s 11 o’clock and we agree to meet in two hours, you instinctively know I’m talking about 1 o’clock. But what you’ve just done is add two numbers mod(ulus) 12. In effect your brain added 11+2 to get 13, then took away 12 to make it fit, and came up with the modulus (or remainder) of 1. Modulus arithmetic is therefore sometimes known as clock arithmetic.
    - mbeex 6y ago
      > In effect your brain added 11+2 to get 13, then took away 12 to make it fit Not my German brain. But mod 24, I'm with you again :) And don't let me start with the Russians, they did it in hardware: https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/File:Raketa-24h-ghiera-ore.jpg https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/Fil...
- eru 6y ago
  If you are using C or C++, you need to be extremely careful with signed integers, even when working modulo. Their overflow is undefined.
  - boston_clone 6y ago
    Is that due to the division taking place like the parent mentions, or something else?
    - eru 6y ago
      Due to how C and C++ are defined in their standards. The reason behind that is so that the compiler is allowed to assume that expressions like (x + 1 > x) are true, and thus can optimise more.
curuinor 6y ago
My impression after a quick once-over is that there's an order of magnitude too little linear algebra in this. Can't have 3D video games without it, can't do large parts of machine learning and statistics without it, etc etc.
- gavinray 6y ago
  It says it's an early draft, and the lack of a coherent path in the Linear Algebra section (currently final section) plus only two sub-chapters makes me think it's under work atm. I also have not a clue what I'm talking about with math (sub-highschool understanding) so I could be very mistaken about the path thing.
- gautamcgoel 6y ago
  Came here to say this. I think he is focusing on the math that "typical" coders need without any emphasis on what ML practicioners need. Nevertheless I agree more linear algebra should be included.
- mhh__ 6y ago
  I think that a course like this should really prepare you to be able to go and look things up yourself i.e. you only need enough linear algebra to recognise what it looks like, then you can go and read one of many excellent linear algebra books. If you want to do video games you'll need to read something else anyway, so better to get into the habit now.
cole-k 6y ago
Unlike the other comments so far, I have a link that is in my opinion NOT generally useful for most programmers. I figured it is worth a share for the programmer who knows all of the math in this post and wants to learn yet more: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p... Other people can debate category theory's utility: I have no expert insight of my own to lend.
- hlava 6y ago
  playlist from the same author: https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_ https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbm...
- gabcoh 6y ago
  Does anyone have any opinion on this book as an introduction to category theory compared to something like Category Theory by Steve Awodey (https://books.google.com/books/about/Category_Theory.html?id=zLs8BAAAQBAJ https://books.google.com/books/about/Category_Theory.html?id...) or Seven Sketches in Compositionality (http://math.mit.edu/~dspivak/teaching/sp18/ http://math.mit.edu/~dspivak/teaching/sp18/)? I'm interested in learning about category theory in general just to get a feel for the subject, but I also want to have a better concrete understanding of the category theory that is put to use in Haskell.
  - AlexSW 6y ago
    Category Theory by Steve Awodey is great, but in my opinion only for a graduate mathematician wanting to do more mathematics and understand category theory in an abstract sense. Preferably one will have done some algebraic topology when reading it. Category Theory for Programmers is just that, for programmers. In fact, if I recall correctly its preface explicitly answers the question 'Why write this when Category Theory by Steve Awodey exists?', with the answer being what I summarise above. If you're a computer scientist, programmer, or otherwise a non-mathematician first, Awodey is not for you and this book I believe should serve you very well instead. I haven't read it, mind. I haven't come across Seven Sketches in Compositionality, but hopefully that helps compare the other two. It's mostly about your intention (e.g. theoretical mathematics vs practical application) and background.
gavinray 6y ago
At first glance, this is actually a refreshing take on "teach math to coders". There are 1-2 other books constantly recommend here, which are (probably) fantastic but throw you off the deep end with assumptions that you understand algebra, trigonometry, fundamental calculus, and statistics. Essentially, that you finished school and paid attention. Which is a well-founded assumption. And I don't necessarily expect an author to assume responsibility for covering fundamentals, but it's nice if there are authors willing to do this.
- gge 6y ago
  What are the 1-2 books that are constantly recommended here?
  - gavinray 6y ago
    "A Programmer's Introduction to Mathematics", by Jeremy Kun is the one you'll see a lot https://pimbook.org/ https://pimbook.org/ The other one is in web format, it's something along the lines of "Visual Linear Algebra". Really unsure of title, but it's centered around visualizations of the math. On my laptop I would post bookmark but I'm in bed on phone, sorry =/ Edit: Here https://textbooks.math.gatech.edu/ila/ https://textbooks.math.gatech.edu/ila/ http://immersivemath.com/ila/index.html http://immersivemath.com/ila/index.html
    - captn3m0 6y ago
      there's also Intro to mathematical thinking: https://www.coursera.org/learn/mathematical-thinking/home/welcome https://www.coursera.org/learn/mathematical-thinking/home/we... and mathematics for machine learning: https://mml-book.github.io/ https://mml-book.github.io/
  - vram22 6y ago
    MCS - Mathematics for Computer Science - is one. From MIT, free. A google should find it.
    - 6y ago
nickponline 6y ago
I would also recommend Concrete Mathematics by Donald Knuth, Oren Patashnik, and Ronald Graham as another refreshing approach.
- eru 6y ago
  I really like Concrete Mathematics, but I fear it's a bit too heavy as an intro for most programmers. (Whoever can stomach it, should give the book a try. It's awesome and fun!)
bogomipz 6y ago
This looks great. I'm looking forward to reading future revisions. I hope you'll post it here when a final draft is available. Keep up the good work. Cheers.
remarkEon 6y ago
These kinds of things pop up a lot on HN, so I want to ask: are they helpful to people? I save basically every single one, planning to come back to them (I studied math and economics in college, and do a little programming now but not enough to call myself a developer), but can’t find time between work and everything else to dive in and actually advance my skills. So maybe what I’m asking for is this: is there a “refresh your math, sharpen your sword” resource that exists that one could tune to what they do today?
- _hl_ 6y ago
  If you studied math, or if you have any kind of respect for the mere concept of rigorous proofs, then these kinds of resources will leave you deeply dissatisfied. If you want to refresh your math, take an elementary result of any particular discipline, e.g. existance and multiplicity of eigenvalues in linear algebra, or uncomputability of the halting problem, and see if you can prove it yourself from what you still recall. You will have to look up on definitions and theorems on the way there, refreshing your skills.
fmi11 6y ago
I think it would be awesome if OP open-sourced this. That way we could make suggestions via pull request.
- blewboarwastake 6y ago
  https://yurichev.com/news/20191207_github/ https://yurichev.com/news/20191207_github/
tskmngr 6y ago
I’m in the middle of speed running khan academy’s entire math section. This’ll compliment my task well. Thanks for sharing.
- deleted 6y ago
  [deleted]
susam 6y ago
For all the mathematics enthusiasts and scholars out here, we have Slack and Freenode IRC channels[1][2] to discuss mathematics and computer science literature like this. It is a reading and discussion group that focuses on math and CS books, articles, and papers, as well as using software tools like Python, WolframAlpha, Desmos, etc. to explore new concepts we come across. As an example of what we discuss in this forum, see "From Vector Spaces to Periodic Functions"[3] that was a result of one of the discussions in this forum. We plan to discuss Munchausen numbers[4] next. If this sounds interesting to you, please join us. [1]: https://bit.ly/euclidslack https://bit.ly/euclidslack [2]: https://webchat.freenode.net/#euclidpoint https://webchat.freenode.net/#euclidpoint [3]: https://susam.in/blog/from-vector-spaces-to-periodic-functions/ https://susam.in/blog/from-vector-spaces-to-periodic-functio... [4]: https://arxiv.org/pdf/0911.3038.pdf https://arxiv.org/pdf/0911.3038.pdf
- sussid 6y ago
  Thanks for this! As fresh IT Dev student, this will help me out!
- Abhinav2000 6y ago
  Thanks, will join
- creative-coder 6y ago
  Just a suggestion: Why not add a Discord link too ?
  - plazmatic 6y ago
    Discord? What is this, high school? Move along, son.
  - AlphENsign_Tech 6y ago
    I think Slack is better suited for information oriented conversation
    - AlchemistCamp 6y ago
andykx 6y ago
In my opinion, the only type of mathematics that is useful to ALL programmers is discrete math. This is applied math that barely resembles the kind of math that you learned in high school, but it’s easy to see how these thoughts lead to the creation of computers. Other types of math are relevant depending on what you’re interested in, but I think students should learn discrete math before diving into writing any serious code.
- onion2k 6y ago
  There's a decent series of "Math for programmers"[1] on YouTube from FreeCodeCamp that covers the basics of discrete math. I've been recommending it to people who want to learn to code for a little while and it seems to go down well. [1] https://www.youtube.com/playlist?list=PLWKjhJtqVAbndUuYBE5sVViMIvyzp_dB1 https://www.youtube.com/playlist?list=PLWKjhJtqVAbndUuYBE5sV...
- eru 6y ago
  Category theory is also very relevant to programming. But, curiously enough, learning and practicing programming is probably a better intro to eventually get to category theory, than the more usual approaches mathematicians take. Discrete math is lots of fun, but less applicable to the kind of glue code many people write most often. (Category theory is in some sense exactly the theory of glue code. But it's also generalised abstract nonsense.)
  - whytaka 6y ago
    > Category theory is in some sense exactly the theory of glue code. If you can explain this to the satisfaction of my understanding, I would like to subscribe to your newsletter.
    - eru 6y ago
      First a qualification: Category Theory doesn't teach you how to write glue code, but it can be seen as a theory to organizing some of our understanding of glue code. One simple example would just be a discussion around the different use cases of Functor, Applicative Functor, Arrows and Monads. And how they relate to common programming constructs like functions, tuples, arrays, Maybes, futures, whatever's happening in react, etc. Category theory won't help you learn those concepts, but once you know those concepts, even a superficial understanding of some category theory, can help you organize your thoughts. As a genuine application of category theory, whenever you find a useful abstraction (like eg functors or monads again), you can have a look at its dual, and see whether that's another interesting structure you haven't seen yet. Just like tuples and Either are duals of each other. (As an analogy, dualizing is also a concept in linear programming. Linear programming can help solve many interesting algorithmic problems, like sorting or matching or assignment or median selection, basically almost anything that's in P, and if you allow integer linear programming than you can solve what's in NP. However, I wouldn't recommend anyone who wants to learn about algorithms and data structures to start with linear programming. But once you know a bunch of algorithms, you can re-express the problems they are solving in terms of linear programming, and see whether you get anything interesting out of looking at their duals.)
mehrdadn 6y ago
Also see Matters Computational (the fxtbook): https://www.jjj.de/fxt/ https://www.jjj.de/fxt/
- MrXOR 6y ago
  Jörg Arndt (jj) also wrote an awesome book about π. https://www.maa.org/press/maa-reviews/pi-unleashed https://www.maa.org/press/maa-reviews/pi-unleashed
xvilka 6y ago
See also Category Theory for Programmers[1] book. [1] https://github.com/hmemcpy/milewski-ctfp-pdf https://github.com/hmemcpy/milewski-ctfp-pdf
reagent_finder 6y ago
Nice. What I want is their latex/pdf setup. I've messed around with it enough to know I'm no good at it and this seems like it would be a great base.
- xenihn 6y ago
  Also interested, I would love to be able to use it.
- SeeDoubleYou 6y ago
  Oh yeah, would love to have a go at it as well. Yet, it is an early draft so they may have some things planned. In my experience, books, presentations, really everything that tries to convey information, works better when looking "good". And "good" is prone to opinion, but some general rules doe apply. I think that the writer has chosen not to bother with styling all to much until the content is set in stone, which is smart.
- jimhefferon 6y ago
  I bet you could write the author. A brief, polite, note will almost always get a reply.
fedlarm 6y ago
As a frontend developer I also encounter I need Geometry from time to time. I used it a lot in my days as a flash developer drawing vector graphics programmatically. I feel that its missing from this list. I rarely see geometry mentioned on these kinds of lists?
- eru 6y ago
  You can do a lot of geometry with linear algebra. (And that's more or less what you'll have to do on a computer anyway. Ruler and compass approaches won't cut it.) I quite like geometry for itself, but it's probably more of a niche for most programmers?
jmiskovic 6y ago
I jumped straight to chapter on graphs and I found it quite weak. It basically documented author's attempts to query few datasets for cliques, using Mathematica. Who is the target audience for this content?
- blewboarwastake 6y ago
  The author says in the first page that it is an early draft, and I think he has a long ways to go still, being less than 100 pages.
jhncls 6y ago
Dennis Yurichev also wrote an awesome free book about creating SMT/SAT code to solve real-world (and less real-world) problems. [0] https://sat-smt.codes/ https://sat-smt.codes/
- mhh__ 6y ago
  That's where I recognised the name from then. Very illuminating book. Turning coffee into SAT solver is found in most CS books, using SAT to buy more coffee less so.
_0o6v 6y ago
My favourite: https://pimbook.org/ https://pimbook.org/ by Jeremy Kun. It's a great read!
- smusamashah 6y ago
  It has way too much text when compared with the shared book which jumps straight to the point.
smusamashah 6y ago
Unlike almost other books recommended in this thread, this jumps straight to the point without a lot of text. From the very start it makes a point and continue without delving into too much intro or background or other plain (useless) text. I find Effective Java an easy read for the exact same reason, it makes a point from the very start without telling so many stories.
jrib 6y ago
In the IRC network social graph section, it was interesting to see my nick pop up in there along with a lot of regulars from when I was active on #ubuntu
mpw92 6y ago
You lost me at: "Let’s find a first 5 prime numbers, each number for each character" <BR/> "first 5 prime number" - I would need to leave your text to figure out what that is.
- jodrellblank 6y ago
  It’s “the first 5 prime numbers”, native speakers of Eastern European languages often get “a” and “the” swapped around or left out completely in English. What prime numbers are was explained earlier in it, and what first 5 is ... probably assumed that was clear enough?
nwsm 6y ago
I have "A Programmer's Introduction to Mathematics" (2018) by Jeremy Kun [0] and can recommend it. HN thread for this book: [1]. The OP looks good as well, a bit more applied it seems. [0] https://pimbook.org/ https://pimbook.org/ [1] https://news.ycombinator.com/item?id=18579076 https://news.ycombinator.com/item?id=18579076
jhallenworld 6y ago
Should add quadratic reciprocity to the modular arithmetic section.. https://www.youtube.com/watch?v=X63MWZIN3gM https://www.youtube.com/watch?v=X63MWZIN3gM
GuB-42 6y ago
Really nice, thank you I'm keeping it. One section that may be added would be about interpolations. I think the formula I implemented the most is a * p + b * (1.0-p), i.e. a simple linear interpolation, which is also an extrapolation when p is not in [0..1]. Obviously useful in graphics and animation but also every time you want to give the user a non-binary choice. A lot can be said on that topic: bilinear, cubic, smoothstep, etc...
iainctduncan 6y ago
Oh wow, this led me to the author's book on reverse engineering to assembly, and it is fierce. Damn!
woxinguangming 6y ago
Great

589 points by signa11 6y ago

One subject that's pretty useful for programmers to understand reasonably well is numerical analysis, even if it's at a fairly basic level. It's amazing how quickly you run into problems in practice as soon as you try to do anything with floating point numbers. I didn't carefully read through the section on modular arithmetic, so maybe this is already there, but one thing worth noting that bites a lot of people is that using modular arithmetic for integer representations means that addition, subtraction, and multiplication work the same for signed and unsigned integers. This means that you can typically write arithmetic expressions involving these operations without worrying too much about whether things are being regarded as signed or unsigned at intermediate steps. As soon as you introduce division into the mix, though, the whole thing falls apart, and you have to be very careful about how the language is interpreting each subexpression.

enchiridion 6y ago
I'm not sure understand what you're saying with mod arithmetic. Can you provide an example?
- macmmajor 6y ago
  You can think of it as applying a mod operator after each operation. Say we wanted to work with mod 5 Then 6 + 8 = 14 = 4 mod 5
  - eru 6y ago
    Doesn't work for division. At least not in general in a naive fashion.
- BearsAreCool 6y ago
  Not OP, but I'll give it a shot. At a low level pretty much all standard integer math is mod arithmetic, typically mod 2^32 or 2^64 depending on if a computer is 32 or 64 bit. This means that when a number goes above this limit it "overflows" and only the part left after dividing by the mod size is left. Additionally, negative numbers are stored by essentially counting down from the maximum number that can be stored + 1, in scholarly terms this is the twos complement. For instance on a 32 bit system -7 as a signed integer would be stored identically to the unsigned integer (2^32)-7. For anyone new to programming, unsigned meaning an integer variable that can only be positive and signed being an integer variable that could be positive or negative. Now all of this combines to make addition, subtraction, and even multiplication essentially identical for signed and unsigned numbers. On an 8 bit system (so integers can be between 0 to 255 inclusive) you could be trying to add the signed number 40 and the unsigned number 200. Naturally, this is 200+40 or 240. Now inside the computer, 240 is stored in the exact same way that -16 is so it is important that the software knows the correct way to handle the variable. This is equivalent to subtracting 56 from 40, and the signed integer -56 is represented in the exact same way as the unsigned integer 200. Now this is where it starts to get crazy. What if you add the signed integer -5 (represented by 251 in the unsigned world) and the unsigned integer 100? Well it is equivalent to 251 + 100 = 351. However, now we encounter modular arithmetic, because this is an 8 bit system and the maximum value for an integer is 255 we calculate everythihg mod 256, so ar left with 351 % 256 = 95. You can mentally view this as the calculation occurring with 1s and 0s, where everytime a 1 is added to a 1, there is a single bit carried and the last bit is dropped, which is exactly how full and half adders work in a processor! This also works for multiplication! If we multiply -5 by 5, we get -25 easily. But for computers we do 251 * 5 = 1255. The modulo math starts to get tricky for us puny humans but for a computer it is trivial, 1255 % 256 = 231. As a signed integer that is equal to -25, as it is equivalent to (255+1-25). For division, everything is just crazy. 250/5 is way different than -5/5, no amount if mod arithmetic will save it. Unsigned 50 and signed -1 have completely different representations, and this is even an example without fractions and rounding. I may have went long winded, but hopefully this helps someone!
  - fmi11 6y ago
    You're a cool bear! Thanks for the detailed explanation!
  - eru 6y ago
    Purely on the mathematical side, you can define division as the inverse of multiplication, and then when you are working modulo a prime number, division works just fine. (But computers usually don't implement it that way.) As an example when working modulo 17 and you want to work out what division by 3 means. You want to solve equations like: x * 3 = 10 (mod 17). For this case, x = 9; because 9 * 3 = 27 = 10 (mod 17). In general when working modulo 17, 6 is the multiplicative inverse of 3. Ie 6 * 3 = 1. Thanks to Fermat's Little Theorem you can find multiplicative inverses very easily, y^(p-2) mod p gives you the inverse of y. (Most programming languages won't know that you are going to apply a mod afterwards, so they just give you eg rounded or truncated integer division. Which is completely different in general.)
    - Tainnor 6y ago
      Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.
      - threatofrain 6y ago
        Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.
        Tainnor 6y ago
        Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
- alblue 6y ago
  You probably do this all the time with time without realising it. If it’s 11 o’clock and we agree to meet in two hours, you instinctively know I’m talking about 1 o’clock. But what you’ve just done is add two numbers mod(ulus) 12. In effect your brain added 11+2 to get 13, then took away 12 to make it fit, and came up with the modulus (or remainder) of 1. Modulus arithmetic is therefore sometimes known as clock arithmetic.
  - mbeex 6y ago
    > In effect your brain added 11+2 to get 13, then took away 12 to make it fit Not my German brain. But mod 24, I'm with you again :) And don't let me start with the Russians, they did it in hardware: https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/File:Raketa-24h-ghiera-ore.jpg https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/Fil...
eru 6y ago
If you are using C or C++, you need to be extremely careful with signed integers, even when working modulo. Their overflow is undefined.
- boston_clone 6y ago
  Is that due to the division taking place like the parent mentions, or something else?
  - eru 6y ago
    Due to how C and C++ are defined in their standards. The reason behind that is so that the compiler is allowed to assume that expressions like (x + 1 > x) are true, and thus can optimise more.

curuinor 6y ago

My impression after a quick once-over is that there's an order of magnitude too little linear algebra in this. Can't have 3D video games without it, can't do large parts of machine learning and statistics without it, etc etc.

gavinray 6y ago
It says it's an early draft, and the lack of a coherent path in the Linear Algebra section (currently final section) plus only two sub-chapters makes me think it's under work atm. I also have not a clue what I'm talking about with math (sub-highschool understanding) so I could be very mistaken about the path thing.
gautamcgoel 6y ago
Came here to say this. I think he is focusing on the math that "typical" coders need without any emphasis on what ML practicioners need. Nevertheless I agree more linear algebra should be included.
mhh__ 6y ago
I think that a course like this should really prepare you to be able to go and look things up yourself i.e. you only need enough linear algebra to recognise what it looks like, then you can go and read one of many excellent linear algebra books. If you want to do video games you'll need to read something else anyway, so better to get into the habit now.

cole-k 6y ago

Unlike the other comments so far, I have a link that is in my opinion NOT generally useful for most programmers. I figured it is worth a share for the programmer who knows all of the math in this post and wants to learn yet more: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p... Other people can debate category theory's utility: I have no expert insight of my own to lend.

hlava 6y ago
playlist from the same author: https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_ https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbm...
gabcoh 6y ago
Does anyone have any opinion on this book as an introduction to category theory compared to something like Category Theory by Steve Awodey (https://books.google.com/books/about/Category_Theory.html?id=zLs8BAAAQBAJ https://books.google.com/books/about/Category_Theory.html?id...) or Seven Sketches in Compositionality (http://math.mit.edu/~dspivak/teaching/sp18/ http://math.mit.edu/~dspivak/teaching/sp18/)? I'm interested in learning about category theory in general just to get a feel for the subject, but I also want to have a better concrete understanding of the category theory that is put to use in Haskell.
- AlexSW 6y ago
  Category Theory by Steve Awodey is great, but in my opinion only for a graduate mathematician wanting to do more mathematics and understand category theory in an abstract sense. Preferably one will have done some algebraic topology when reading it. Category Theory for Programmers is just that, for programmers. In fact, if I recall correctly its preface explicitly answers the question 'Why write this when Category Theory by Steve Awodey exists?', with the answer being what I summarise above. If you're a computer scientist, programmer, or otherwise a non-mathematician first, Awodey is not for you and this book I believe should serve you very well instead. I haven't read it, mind. I haven't come across Seven Sketches in Compositionality, but hopefully that helps compare the other two. It's mostly about your intention (e.g. theoretical mathematics vs practical application) and background.

gavinray 6y ago

At first glance, this is actually a refreshing take on "teach math to coders". There are 1-2 other books constantly recommend here, which are (probably) fantastic but throw you off the deep end with assumptions that you understand algebra, trigonometry, fundamental calculus, and statistics. Essentially, that you finished school and paid attention. Which is a well-founded assumption. And I don't necessarily expect an author to assume responsibility for covering fundamentals, but it's nice if there are authors willing to do this.

gge 6y ago
What are the 1-2 books that are constantly recommended here?
- gavinray 6y ago
  "A Programmer's Introduction to Mathematics", by Jeremy Kun is the one you'll see a lot https://pimbook.org/ https://pimbook.org/ The other one is in web format, it's something along the lines of "Visual Linear Algebra". Really unsure of title, but it's centered around visualizations of the math. On my laptop I would post bookmark but I'm in bed on phone, sorry =/ Edit: Here https://textbooks.math.gatech.edu/ila/ https://textbooks.math.gatech.edu/ila/ http://immersivemath.com/ila/index.html http://immersivemath.com/ila/index.html
  - captn3m0 6y ago
    there's also Intro to mathematical thinking: https://www.coursera.org/learn/mathematical-thinking/home/welcome https://www.coursera.org/learn/mathematical-thinking/home/we... and mathematics for machine learning: https://mml-book.github.io/ https://mml-book.github.io/
- vram22 6y ago
  MCS - Mathematics for Computer Science - is one. From MIT, free. A google should find it.
  - 6y ago

nickponline 6y ago

I would also recommend Concrete Mathematics by Donald Knuth, Oren Patashnik, and Ronald Graham as another refreshing approach.

eru 6y ago
I really like Concrete Mathematics, but I fear it's a bit too heavy as an intro for most programmers. (Whoever can stomach it, should give the book a try. It's awesome and fun!)

bogomipz 6y ago

This looks great. I'm looking forward to reading future revisions. I hope you'll post it here when a final draft is available. Keep up the good work. Cheers.

remarkEon 6y ago

These kinds of things pop up a lot on HN, so I want to ask: are they helpful to people? I save basically every single one, planning to come back to them (I studied math and economics in college, and do a little programming now but not enough to call myself a developer), but can’t find time between work and everything else to dive in and actually advance my skills. So maybe what I’m asking for is this: is there a “refresh your math, sharpen your sword” resource that exists that one could tune to what they do today?

_hl_ 6y ago
If you studied math, or if you have any kind of respect for the mere concept of rigorous proofs, then these kinds of resources will leave you deeply dissatisfied. If you want to refresh your math, take an elementary result of any particular discipline, e.g. existance and multiplicity of eigenvalues in linear algebra, or uncomputability of the halting problem, and see if you can prove it yourself from what you still recall. You will have to look up on definitions and theorems on the way there, refreshing your skills.

fmi11 6y ago

I think it would be awesome if OP open-sourced this. That way we could make suggestions via pull request.

blewboarwastake 6y ago
https://yurichev.com/news/20191207_github/ https://yurichev.com/news/20191207_github/

tskmngr 6y ago

I’m in the middle of speed running khan academy’s entire math section. This’ll compliment my task well. Thanks for sharing.

deleted 6y ago
[deleted]

susam 6y ago

For all the mathematics enthusiasts and scholars out here, we have Slack and Freenode IRC channels[1][2] to discuss mathematics and computer science literature like this. It is a reading and discussion group that focuses on math and CS books, articles, and papers, as well as using software tools like Python, WolframAlpha, Desmos, etc. to explore new concepts we come across. As an example of what we discuss in this forum, see "From Vector Spaces to Periodic Functions"[3] that was a result of one of the discussions in this forum. We plan to discuss Munchausen numbers[4] next. If this sounds interesting to you, please join us. [1]: https://bit.ly/euclidslack https://bit.ly/euclidslack [2]: https://webchat.freenode.net/#euclidpoint https://webchat.freenode.net/#euclidpoint [3]: https://susam.in/blog/from-vector-spaces-to-periodic-functions/ https://susam.in/blog/from-vector-spaces-to-periodic-functio... [4]: https://arxiv.org/pdf/0911.3038.pdf https://arxiv.org/pdf/0911.3038.pdf

sussid 6y ago
Thanks for this! As fresh IT Dev student, this will help me out!
Abhinav2000 6y ago
Thanks, will join
creative-coder 6y ago
Just a suggestion: Why not add a Discord link too ?
- plazmatic 6y ago
  Discord? What is this, high school? Move along, son.
- AlphENsign_Tech 6y ago
  I think Slack is better suited for information oriented conversation
  - AlchemistCamp 6y ago

andykx 6y ago

In my opinion, the only type of mathematics that is useful to ALL programmers is discrete math. This is applied math that barely resembles the kind of math that you learned in high school, but it’s easy to see how these thoughts lead to the creation of computers. Other types of math are relevant depending on what you’re interested in, but I think students should learn discrete math before diving into writing any serious code.

onion2k 6y ago
There's a decent series of "Math for programmers"[1] on YouTube from FreeCodeCamp that covers the basics of discrete math. I've been recommending it to people who want to learn to code for a little while and it seems to go down well. [1] https://www.youtube.com/playlist?list=PLWKjhJtqVAbndUuYBE5sVViMIvyzp_dB1 https://www.youtube.com/playlist?list=PLWKjhJtqVAbndUuYBE5sV...
eru 6y ago
Category theory is also very relevant to programming. But, curiously enough, learning and practicing programming is probably a better intro to eventually get to category theory, than the more usual approaches mathematicians take. Discrete math is lots of fun, but less applicable to the kind of glue code many people write most often. (Category theory is in some sense exactly the theory of glue code. But it's also generalised abstract nonsense.)
- whytaka 6y ago
  > Category theory is in some sense exactly the theory of glue code. If you can explain this to the satisfaction of my understanding, I would like to subscribe to your newsletter.
  - eru 6y ago
    First a qualification: Category Theory doesn't teach you how to write glue code, but it can be seen as a theory to organizing some of our understanding of glue code. One simple example would just be a discussion around the different use cases of Functor, Applicative Functor, Arrows and Monads. And how they relate to common programming constructs like functions, tuples, arrays, Maybes, futures, whatever's happening in react, etc. Category theory won't help you learn those concepts, but once you know those concepts, even a superficial understanding of some category theory, can help you organize your thoughts. As a genuine application of category theory, whenever you find a useful abstraction (like eg functors or monads again), you can have a look at its dual, and see whether that's another interesting structure you haven't seen yet. Just like tuples and Either are duals of each other. (As an analogy, dualizing is also a concept in linear programming. Linear programming can help solve many interesting algorithmic problems, like sorting or matching or assignment or median selection, basically almost anything that's in P, and if you allow integer linear programming than you can solve what's in NP. However, I wouldn't recommend anyone who wants to learn about algorithms and data structures to start with linear programming. But once you know a bunch of algorithms, you can re-express the problems they are solving in terms of linear programming, and see whether you get anything interesting out of looking at their duals.)

mehrdadn 6y ago

Also see Matters Computational (the fxtbook): https://www.jjj.de/fxt/ https://www.jjj.de/fxt/

MrXOR 6y ago
Jörg Arndt (jj) also wrote an awesome book about π. https://www.maa.org/press/maa-reviews/pi-unleashed https://www.maa.org/press/maa-reviews/pi-unleashed

xvilka 6y ago

See also Category Theory for Programmers[1] book. [1] https://github.com/hmemcpy/milewski-ctfp-pdf https://github.com/hmemcpy/milewski-ctfp-pdf

reagent_finder 6y ago

Nice. What I want is their latex/pdf setup. I've messed around with it enough to know I'm no good at it and this seems like it would be a great base.

xenihn 6y ago
Also interested, I would love to be able to use it.
SeeDoubleYou 6y ago
Oh yeah, would love to have a go at it as well. Yet, it is an early draft so they may have some things planned. In my experience, books, presentations, really everything that tries to convey information, works better when looking "good". And "good" is prone to opinion, but some general rules doe apply. I think that the writer has chosen not to bother with styling all to much until the content is set in stone, which is smart.
jimhefferon 6y ago
I bet you could write the author. A brief, polite, note will almost always get a reply.

fedlarm 6y ago

As a frontend developer I also encounter I need Geometry from time to time. I used it a lot in my days as a flash developer drawing vector graphics programmatically. I feel that its missing from this list. I rarely see geometry mentioned on these kinds of lists?

eru 6y ago
You can do a lot of geometry with linear algebra. (And that's more or less what you'll have to do on a computer anyway. Ruler and compass approaches won't cut it.) I quite like geometry for itself, but it's probably more of a niche for most programmers?

jmiskovic 6y ago

I jumped straight to chapter on graphs and I found it quite weak. It basically documented author's attempts to query few datasets for cliques, using Mathematica. Who is the target audience for this content?

blewboarwastake 6y ago
The author says in the first page that it is an early draft, and I think he has a long ways to go still, being less than 100 pages.

jhncls 6y ago

Dennis Yurichev also wrote an awesome free book about creating SMT/SAT code to solve real-world (and less real-world) problems. [0] https://sat-smt.codes/ https://sat-smt.codes/

mhh__ 6y ago
That's where I recognised the name from then. Very illuminating book. Turning coffee into SAT solver is found in most CS books, using SAT to buy more coffee less so.

_0o6v 6y ago

My favourite: https://pimbook.org/ https://pimbook.org/ by Jeremy Kun. It's a great read!

smusamashah 6y ago
It has way too much text when compared with the shared book which jumps straight to the point.

smusamashah 6y ago

Unlike almost other books recommended in this thread, this jumps straight to the point without a lot of text. From the very start it makes a point and continue without delving into too much intro or background or other plain (useless) text. I find Effective Java an easy read for the exact same reason, it makes a point from the very start without telling so many stories.

jrib 6y ago

In the IRC network social graph section, it was interesting to see my nick pop up in there along with a lot of regulars from when I was active on #ubuntu

mpw92 6y ago

You lost me at: "Let’s find a first 5 prime numbers, each number for each character" <BR/> "first 5 prime number" - I would need to leave your text to figure out what that is.

jodrellblank 6y ago
It’s “the first 5 prime numbers”, native speakers of Eastern European languages often get “a” and “the” swapped around or left out completely in English. What prime numbers are was explained earlier in it, and what first 5 is ... probably assumed that was clear enough?

nwsm 6y ago

I have "A Programmer's Introduction to Mathematics" (2018) by Jeremy Kun [0] and can recommend it. HN thread for this book: [1]. The OP looks good as well, a bit more applied it seems. [0] https://pimbook.org/ https://pimbook.org/ [1] https://news.ycombinator.com/item?id=18579076 https://news.ycombinator.com/item?id=18579076

jhallenworld 6y ago

Should add quadratic reciprocity to the modular arithmetic section.. https://www.youtube.com/watch?v=X63MWZIN3gM https://www.youtube.com/watch?v=X63MWZIN3gM

GuB-42 6y ago

Really nice, thank you I'm keeping it. One section that may be added would be about interpolations. I think the formula I implemented the most is a * p + b * (1.0-p), i.e. a simple linear interpolation, which is also an extrapolation when p is not in [0..1]. Obviously useful in graphics and animation but also every time you want to give the user a non-binary choice. A lot can be said on that topic: bilinear, cubic, smoothstep, etc...

iainctduncan 6y ago

Oh wow, this led me to the author's book on reverse engineering to assembly, and it is fierce. Damn!

woxinguangming 6y ago

Great