Math For Programmers

In ProgrammerMathSkills, it is lamented that many programmers lack training (or have forgotten all about it as part of the usual MindWipe that occurs shortly after graduation). This page, which contains some material ReFactored from that page, lists the math skills that programmers ought to have. Or so the collective we think....

Things suggested: Discussion below.

Counting (from zero, from one, forwards, and backwards) to avoid OffByOne errors
Addition, subtraction, multiplication, and division
CheckBySubstitution?
LinearAlgebra
GraphTheory
combinatorics
probability theory & statistics
basic applied math skills (estimation, modeling, etc.)
BooleanAlgebra
Predicate logic/FirstOrderLogic
LambdaCalculus
ChomskyHierarchy and TheoryOfComputation?
NumericalAnalysis (everyone uses some floating point)
ConcreteMathematics for analysis of programs (see also TheArtOfComputerProgramming)

This page starts in a rather disjoined ThreadMode; perhaps we can distill some DocumentMode out of it:

You do bring up a good point though; Perhaps this direction of discussion is more fruitful. I expect that a professional programmer would have an elementary understanding of the following areas of mathematics:

linear algebra
graph theory
combinatorics
differential and integral calculus & perhaps OrdinaryDifferentialEquations?
probability theory & statistics
basic applied maths skills (estimation, modeling, etc.)

further more, she should be able to effectively perform the following analytical tasks:

effective back-of-the-envelope estimates
simulation and numerical experiments
analytic complexity analysis - both to analyse simple algorithms, and to understand the analysis of complex ones if it is handed to you
numerical/empirical complexity analysis - how to effectively test an algorithm you can't analyse (i.e., most except the simplest)

These, to me, represent bare minimum requirements. All of the mathematics above is understood to be at the elementary level (e.g. 1st or 2nd year at most colleges). Further exposure is undoubtedly helpful. For particular areas (numerical methods, dynamical systems, scientific programming, games programming, etc.), significantly more background is needed as a starting point.

I am sure to have missed some points in haste. Comments are appreciated!

How about Boolean algebra and predicate logic? This is usually in the beginning CS/CE/EE curriculum and helps greatly when analysing and refactoring conditionals. Personally, I think the second list is more widely applicable than the first. I consider items in the first list knowledge required to solve particular domain problems rather than general programming problems.

The math skills I use every day are arithmetic, regular algebra, and Boolean algebra. The CS math skills I have used to fix bugs and solve performance issues are complexity analysis, simulation, and the ScientificMethod. For particular problems at specific jobs, I have had to dip into numerical analysis, trigonometry, and linear algebra. However, it was just as important in those cases that I know where to go to refresh my skills as it was to have those skills in the first place. -- IanOsgood

Let's not forget numerical analysis. After all, the floating point number system is not the real number system, but just an approximation. Sometimes programmers don't understand this, and sometimes their managers don't understand this.

Sure, the problems with floating point operation are well known, if not well understood by the average programmer. However, many programmers rarely use FP. Above, I mentioned numerical analysis (methods) as one of the special cases that needs more background.

For example, consider the quadratic equation ax^2 + bx + c = 0. I'll assume the discriminant is positive, so as to avoid any domain problems. The standard way to solve this (in pseudo-code) is:

  discriminant := b*b - 4*a*c
  discr_root   := sqrt(discriminant)
  r1           := (-b + discr_root) / (2*a)
  r2           := (-b - discr_root) / (2*a)
  return (r1, r2)

This is not the correct method, because when b*b is much bigger than 4*a*c, discr_root is very close to abs(b), and the calculation of either r1 or r2 will result in catastrophic round-off error. (See ReadLikeMath)

However, some programmers for NASA in the 1980s tried to rewrite their quadratic solver to do it the correct way, but their managers refused to allow that. They remembered the quadratic formula from their high school days, and by G-d they would use it. Is this documented?

The correct method is, by the way:

  discriminant := b*b - 4*a*c
  discr_root   := sqrt(discriminant)
  factor       := - b - sign(b)*discr_root
  r1           := factor / (2*a)
  r2           := (2*c) / factor
  return (r1, r2)

This converts the nasty subtraction to a benign addition and division. -- EricJablow

And here I was despairing because my skills in such things as the LambdaCalculus, FirstOrderLogic, and other such and sundry are a bit weak...

In many schools, a math minor is made a computer science major requirement. Ironically, the same is not true of electrical engineering. I imagine this is done to pad the degree and bring in more money for the school. I can't say that it is to help the computer science student, as most math classes skip over (or barely touch) the things important to computer science like 3d graphics, set theory, automata, etc.

What's ironic about that? You can't understand the EE curriculum without some moderately serious math background. If you can't handle Fourier Transforms and Laplace Transforms, then you're not going to get an EE degree. Conversely, the areas of math that are essential to EE are rarely critical to most areas of CS, and vice-versa. An EE cares about finite state automata, but usually only trivial ones, he doesn't need to know about the equivalence with the Chomsky hierarchy of grammars.

What is ironic is that it isn't required - Obviously EE's need a lot of math, so why isn't a minor required as it is for CS?
Because it isn't necessary to formally require something that is already implicitly required. Think about it. An EE needs to take a class on signal processing or filter design or something because it is a core requirement for his major. However, a prerequisite for the course is a mastery of Fourier theory. If he doesn't have the prerequisite, then he isn't allowed to take his core class (or he is allowed, but he flunks). The EE perforce must learn quite a bit of difficult math, or else he won't get his degree. There is thus no irony.
- I don't understand the logic here. Isn't the situation the same for CS students? CS students need the prerequisite math to take advanced classes also, so why is it different for EE? I think the logic is exactly the same, and that therefore CS majors should not be required to minor in Math. Like EE majors, they should merely be required to know the appropriate math, which is a different issue. . . .We have achieved agreement.
Besides which, it actually isn't even sufficient to require a math minor for an EE, because the minor might be in the wrong areas of math.
- I could buy that argument, except that the CS students are forced to take math in the wrong areas also. Well, schools aren't always strictly logical about their requirements.
It's also not clear to me that a math minor is all that common a requirement for CS majors, although it's easy to believe that such a thing is required at a minority of schools, and for similar reasons.
- True, I have only anecdotal evidence, but everywhere I've looked at CS majors, they required a math minor (everywhere in Alabama at least) - specifically UAH. It used not to be required for the C.S. program at, e.g., CalBerkeley; I haven't checked recently. Certain other first-tier universities have traditionally required something like it because it got grandfathered in: in the 1960s and 1970s, CS was usually part of the math department.
  - That explains a lot! I always felt like the math department was jealous of the CS department. Typically the math depts are contemptuous of the subject matter of the CS dept but jealous of the funding. :-)
- Typically, in less science-oriented state universities (like Florida State), and possibly most non-technical schools, the CS department sits under the College of Arts and Sciences, or some similarly general flag. A lot of the extra classes CS students have to take - calculus, physics - are due to accreditation concerns, in addition to the idea of math breeding CS.
To be clear here, I don't hate math, I hate that I'm being forced to take certain courses while the ones I really need to advance in both CS and software development aren't included
- Interesting. Switch schools. They are definitely not all alike in what they require. Yeah. . . not really an option - at least UAH is the best school in the area.
- Well, when given lemons, make lemonade... which math courses do you object to, and which would you prefer to take instead?

In an ideal world, the universities would set up the curriculum to help the students. In the real world, things like money and MicroSoft do a lot of damage to ComputerScience students. Not to mention academic politics and a whole host of other AntiPatterns.

That's for sure, yep yep, definitely agree.

Challenged:

Reasons to learn DifferentialCalculus?, IntegralCalculus?, and the OrdinaryDifferentialEquations? used to solve the ReynoldsTransportTheorem or any of its special cases (such as KirchoffsCurrentLaw?, KirchoffsVoltageLaw?, et cetera):

If you do programming for business, calculus comes up often for optimization, cost and margin analysis, queueing theory. Differential equations (part of calculus) also apply to many fields - physics, biology, chemistry as well as economics and business. Calculus is useful for some kinds of programming. There is such a thing as applied mathematics, not just pure mathematics.

[Most of these uses of DifferentialEquations? are special cases of the ReynoldsTransportTheorem. It is easier to learn these various differential equations if one is aware that they all follow the same pattern.]

Though GeneralSystems?, ControlTheory? concepts and patterns may help, there is no way you are going to learn DifferentialEquations without calculus.

I'm quite sure no one meant to suggest otherwise; that would be utterly foolish on the face of it. So if you see a phrasing that you think does imply that, correct it. The thrust of the point is that neither calculus nor diffeq tend to be used by most programmers, even though they are valuable to have learned as background, and even though they sometimes come up in a number of speciality fields.

The ReynoldsTransportTheorem and its special cases describe fundamental aspects of the real world. Using these laws is good training for programming, because they require systematic description of:

system interfaces
boundary conditions
flows into and out of a system.

Arguments that these topics have nothing in particular to do with programming:

Unless you're programming calculus, you're unlikely to need calculus to understand anything you're doing in programming.

That's like saying English is necessary because everyone should document. It's not hard to find reasons for every other subject, too. So, we all believe in a well-rounded education, and its future value, yes. Does that make it a core subject for programming? Certainly not.

I've never heard of Reynolds before today. I've certainly heard of Kirchoff's laws (having an EE degree), but wouldn't list them as requirements for programmers.
You are correct, Reynolds and Kirchoffs have nothing whatsoever to do with programming, unless you're doing e.g. a physics simulation, in which case they still have nothing to do with programming. But calculus doesn't come up very often (never, in many sub-areas), so maybe he just means it's good for the soul to learn these before turning to programming. Like Latin and Greek. I don't think it belongs on the list.

You work for a telecom company (a not uncommon vocation for programmers). Your PointyHairedBoss wants you to write a program to help him manage prices and capacity. He has come up with a formula for 3 distinct demands for the company's service:

  Weekends: Q1=a1-b1*P1
  Holidays: Q2=a2-b2*P2
  Nights:   Q3=a3-b3*P3

TC=j+k*Q where Q=Q1+Q2+Q3 and TC is TotalCost?, P is Price, Q is quantity of minutes demanded by subscribers. a,b,j,k are constants they determine by data mining. What formula will your program use for the button that says "Show Profit Maximizing Output" and the one that says "Show Profit Maximizing Price"? (He expects you to come up with that formula).

Domain Issue

Isn't this a domain issue? Different domains will require different math skills, some very few. Rather than try to load up on a bunch of different kinds of math when we are young and hope to remember it for a long time without use, some kind of JustInTime training would perhaps be more effective.

Most of this discussion seems to be missing the point. Math for programmers is like progressive weight training for athletes. Not every athlete is going to be a weight-lifter - virtually none of them are - and yet virtually all athletes do progressive weight training. Why? Because it gives them one component of a well-rounded athlete. Sport specific training is then added to this fundamentally sound basis.

Mathematics does the same thing for your mind. It gives you some knowledge, yes, but much more important is the skills that come with it. Analysis, abstraction, manipulation, attention to detail while retaining the whole picture, are all skills acquired and hone by doing mathematics.

But there are other ways and topics to expand one's mind. In my opinion, the best way to expand yourself is force yourself to do what you least like or are the least good at. For many geeks, this is improving social and diplomacy skills.

Maybe it's not the only way, but the best programmers I've worked with and for have all had strong mathematical backgrounds. I don't believe that to be one way. I believe that further study in mathematics will make you a better programmer, provided it's used as an enhancement of domain specific skills.

Perhaps, but what I find is that what the boss rewards and what personally impresses me of other's work often differs greatly. Perhaps we should make a distinction between personal enlightenment and keeping our wallets happy.

Moved from BadStuffWeLearnInSchool

Re: Math and science are overemphasized

Hey, if that was true I wouldn't have met so many incompetent programmers, you wouldn't complain so much about H1Bs and L1s (those seem to be on another level altogether than the average US born programmer) and >50% of graduate tech students being foreigners. Blaming it all on globalization when there are many more deep causes is handwaving. From my private perspective, the intelligent kids receive an utterly incompetent training in Math. Somebody with A's all over the place could not derive for me ln x, a year after getting A in calculus. I landed here in 2000, the then gov of California declared that the "strategic goal" to have all high-school graduates be able to write read and do basic math (mostly arithmetic, that is, because otherwise I already saw two shop attendants who had problems calculating in their head a 10% discount). To argue for further de-emphasizing of science and math is pure unadulterated idiocy.

Students are ignoring math because in the US, math does not pay. The high-end of the field has almost always been filled with foreigners because, first, it is more socially acceptable to be a math nerd in other countries, and second, it is easier for foreigners to learn math than other subjects due to language and cultural barriers. Thus, they gravitate that way, pushing down the US value of such a skill relative to other skills. If the US government wants more citizen math whizzes, it would probably have to subsidize the field to compete with these factors. Also, in the business domains, high-end math is not used that often at all. It is hard to know which domain one will end up in when in school. Business domains are probably growing faster than other domains due to offshoring of manufacturing and physical research. The laws of nature are constant across the globe, but the laws of business are not.

Some obvious comments:

nerds are less than popular all over the world
- I disagree. In Asia they are much more revered than in the US.
The average US kid who likes math or other science faces the extremely high probability of meeting an incompetent teacher following from a bad manual and a bad curriculum. Results speak for themselves. The rest is handwaving.
- I think the problem is that there is a kind of stark decision choice between "alpha-geek" jobs and "regular cubicle jobs" (RCJ). Sending an upcoming math-whiz off to Math Camp may indeed improve his/her chances for the fewer alpha-geek positions, but harm their RCJ chances by removing exposure to "normal" people. Europe generally has chosen to take the alpha path of risk, while the US seems to take the RCJ route. Being that globalism has turned brains into a commodity, the RCJ route appears the more practical.
- The math camp is a StrawMan. Somebody who cannot compute 10% of something in my home country will not make it past the 6th grade (yes they will be failed the year and forced to repeat the 6th grade until they get it, or until a decision is taken that the poor kid is retarded and then sent to a special school). In US, the same student will very likely be "socially promoted" and finish with a high school diploma. This is not just bad because that person cannot compute 10% of something, but it is bad because the brain muscle suffers severe atrophy as a result of not being exercised.
- I am not sure what your point is. People often learn such stuff but later forget. Refresher courses are perhaps the solution. JIT education.
- Now really, if you can explain to me how one forgets to calculate 10% after receiving a competent education.The point was that their brains grow under-developed and this is a severe handicap they have to live with for the rest of their lives. No JIT education can recover that.
- I don't share such as Boolean view of education. Anyhow, I was mostly talking about the better students, not those near the bottom.
- And those near the top don't fare much better, because they also receive less than competent education, and also a lot of their potential is wasted during the high-school years. You don't need to share any boolean view you just have to search for quantifiable results. And the quantifiable results are that the US education in primary to high school years ranks amongst the worse in developed nations. If Tony Blair declared the same strategic goal for the British education system as the governor of California did, he would have been laughed all the way out of parliament.
- Someone once said, "The real world is more like high-school than college". I don't know who said it, but over the years I found that to be so true. Continued in DilbertianVsMeritView.
No subsidies can alleviate a less than competent workforce. In any case it's not the business of US government to decide what activities should US citizens be encouraged to pursue. This approach reminds us of Gorbachev asking Thatcher how she saw to it that the people in London get fed. For the culturally puzzled, socialist countries had an economic planning agencies that decided what farm grows wheat and what farm grows potatoes and what truck state company delivers how much of those to a particular city. Of course the plans never quite worked anywhere, but the strong conviction that there must be a plan could not be shuttered.
Competent software engineers still make a very nice living in US.
- I have seen people I consider "competent" struggle. The HR filtering process is hardly optimum, filtering out otherwise good people. Also, I have been rejected for positions because my competition had better people skills. They admitted that to the agency that represented me. My admitted insufficient people skills has hurt me career-wise far more often than lacking math or technical skills. It was usually not any blunt violation, just small things that add up. For example, during lunches I gravitate toward geeky topics, such as robots, while everyone else talks about movies, baseball, or their favorite foods.
- Still, on average, competent software engineers still make a very nice living. FYI: you can always claim to have good people skills especially with agents and agencies. They expect you to.
- Competent factory workers can also make a good living. But I would not recommend it as a career choice. Speaking of "people skills", phrases such as "straw man" and "unadulterated idiocy" are not an example of them.
- I know an unadulterated idiocy when I see one, and I can speak up about it when and where appropriate. This is integral to my people's skills. You may be less than thrilled with your career choice, but there's no apparent reason to believe that the average competent software engineer out there could have made a better choice.
- Glad to know that you are the God of Truth. I bow down to your isolated greatness. I am just a mere mortal who hallucinates observations about the work world. I would not know they were just hallucinations if not cleared up by your limitless wisdom. By the way, what did you mean by "better choice"?
- Now if I have a claim to being able to recognize idiocies - a lot of people can claim that, it doesn't follow in any way shape or form that I implied that I was the "God of Truth". Using such cheap rhetoric is another idiocy that I can recognize quite easily. Now if you made some anecdotal observations about your workplace, drawing from there that de-emphasizing math education in America would be a good idea, well, that is way beyond a defendable logical position.
- I suspect this wide disagreement is a difference in our DilbertianVsMeritView.

My highly opinionated two cents...

I think the most important reason for programmers to learn (a least a bit more) mathematics is for a more general skill: reasoning skills.

We are bestowed with brains that work in some way. Never mind if they are always right or not: it is what we have, and what we are bound by. We have some intuitive notions of what makes sense and what doesn't, and we often find that we agree with others about what those things are.

Logic is simply an abstraction of our common and agreed ways of reasoning. It provides us with a way of formalising and communicating our intuitive reasoning. We don't know if it is absolutely reliable, but we have been using it a while now and it seems to serve well. If, someday, we find a part of logic that doesn't fit the real world very well, then we will probably dump it. Hence, I would say that logic is the science of human reasoning.

The way I look at mathematics is that it is an application of logic to things we can measure (or quantify, whatever). And it just so happens that a lot of real-world phenomena, and a lot of other things we would like to analyse, tend to be measurable. And a whole bunch of people have tried to formalise the things we commonly measure as different fields of mathematics.

So, which fields of maths you study depends on what real-world phenomena are important to you. For example, if you concern yourself with chance, then probability is dead handy. If you concern yourself with finding patterns and trends in seemingly random data, then statistics is worth a look. If you want to build things in the real world that involve taking up space (architecture, landscape design, all sorts) then geometry is a must-have. If you are interested in how changing one measurable thing can affect another measurable thing, the differential calculus is a lot of help. (Okay, I think you probably see my point.)

If you concern yourself with software development... well, I suppose it depends on what you are developing!

I am no great mathematician; in fact, I don't have any qualifications at all. But the above is how maths has helped me. So maybe it could help a bunch of other people too.

CategoryMath