The other day while helping out in Java, I came across this thread, which illustrates why math can be useful to programmers. Math does not always come in the form of trig equations or evaluating an integral. In this case, we go back to Discrete Math, for solving linear recurrences.
The problem in the above thread is to find an efficient way to calculate large fibonacci numbers. Using recursion, this can take hours because in order to generate the next fibonacci number, the program must generate the previous two. Instead, solving the recurrence mathematically first will give us a function that can generate the nth fibonacci number in O(1) time.
Let's start by setting up our recurrence: F(n) = F(n-1) + F(n-2). We can simplify this as such: F(n) - F(n-1) - F(n-2) = 0. If you have taken a Differential Equations class, you might recognize this form as well: y"- y' - y = 0.
As with our differential equations, we set up the recurrence as a quadratic: r^2 - r - 1 = 0. Solving the quadratic gives us: r = [1 +- sqrt(5)]/2.
We now plug in those roots to our standard form equation for distinct roots:
Plugging in our base cases, we can solve a system of equations for A and B. When we do this, we get A = sqrt(5)/5 and B = -sqrt(5)/5.
Now we have an equation that we can solve for Fibonacci numbers in O(1) time. If we plug in F(10), we get 55, the 10th Fibonacci number in practically no time at all. See what doing a little math on the front-end can do for performance?
The problem in the above thread is to find an efficient way to calculate large fibonacci numbers. Using recursion, this can take hours because in order to generate the next fibonacci number, the program must generate the previous two. Instead, solving the recurrence mathematically first will give us a function that can generate the nth fibonacci number in O(1) time.
Let's start by setting up our recurrence: F(n) = F(n-1) + F(n-2). We can simplify this as such: F(n) - F(n-1) - F(n-2) = 0. If you have taken a Differential Equations class, you might recognize this form as well: y"- y' - y = 0.
As with our differential equations, we set up the recurrence as a quadratic: r^2 - r - 1 = 0. Solving the quadratic gives us: r = [1 +- sqrt(5)]/2.
We now plug in those roots to our standard form equation for distinct roots:
F(n) = A * root1^n + B * root2^n F(n) = A * [(1+sqrt(5))/2]^n + B * [(1-sqrt(5))/2]^n
Plugging in our base cases, we can solve a system of equations for A and B. When we do this, we get A = sqrt(5)/5 and B = -sqrt(5)/5.
F(0) = 0 = A + B F(1) = 1 = A(1+sqrt(5))/2 + B(1-sqrt(5))/2
Now we have an equation that we can solve for Fibonacci numbers in O(1) time. If we plug in F(10), we get 55, the 10th Fibonacci number in practically no time at all. See what doing a little math on the front-end can do for performance?
28 Comments On This Entry
marinus
17 April 2011 - 02:59 AMQuote
Why Math Is Important for Programmers
Its a requirement in 3D game programming
Taibah
17 April 2011 - 04:02 AM
Math is only important for only game programming because it works mostly with cordinates and more.
Hiram
17 April 2011 - 04:34 AM
I'd definitely agree that being able to work with mathematics is integral for graphics programming. I'm doing a graphics programming course at my university at the moment, and because I'm not the best with maths, it's grueling to say the least.
However, tying back to the original post. When I studied discrete mathematics I felt the course was useless while I was doing it. "I just want to program, who cares about maths!". Of course, I learnt about sets, and with that, common set operations, like intersections, unions etc. Knowledge of these operations has been infinitely useful for me, especially for communicating problems to other programmers. For example, I'm teaching now, and just the other day a student said to me "I have two arrays, and I want all the elements that are common to both, how can I do that?" and I told him to look up intersections. Before completing the mathematics course, I would have told them something very complicated, involving a lot of pseudocode and probably a few mistakes.
I think mathematics is important for programmers in an entirely different way as well. They're both logical concepts that can be explained and tested algorithmically (i.e. step by step). Being able to work efficiently with mathematics can do nothing but help your programming ability.
The main problem I have with mathematics now, is that I want to improve my knowledge but I'm not sure what areas I should start with. I'd say there are quite a few programmers out there who are the same.
However, tying back to the original post. When I studied discrete mathematics I felt the course was useless while I was doing it. "I just want to program, who cares about maths!". Of course, I learnt about sets, and with that, common set operations, like intersections, unions etc. Knowledge of these operations has been infinitely useful for me, especially for communicating problems to other programmers. For example, I'm teaching now, and just the other day a student said to me "I have two arrays, and I want all the elements that are common to both, how can I do that?" and I told him to look up intersections. Before completing the mathematics course, I would have told them something very complicated, involving a lot of pseudocode and probably a few mistakes.
I think mathematics is important for programmers in an entirely different way as well. They're both logical concepts that can be explained and tested algorithmically (i.e. step by step). Being able to work efficiently with mathematics can do nothing but help your programming ability.
The main problem I have with mathematics now, is that I want to improve my knowledge but I'm not sure what areas I should start with. I'd say there are quite a few programmers out there who are the same.
Martyr2
17 April 2011 - 09:00 AM
Great article and some of these comments prove that their is a large misconception about math's role in much of the programming world. You will run into math in more than just game programming or graphics programming. You have to ask yourself what type of systems do we typically find ourselves creating in industry?
Financial systems - have to know about interest, calculate mortgages, return on investment formulas, break event points, calculating charts, probability, etc
Science systems - scientists use programs which model things they are studying. Formulas for balancing chemical equations, sequencing the human genome, calculating distance to stars, aerodynamics for planes, fluid motion weather and other physics etc
Algorithms - the various functions you use in the .NET framework to sort an array itself is based on previous work done in mathematics. Finding efficient ways to find something, calculate an answer, cut problem sets down without going into exponential growth all is based on math.
As I have always told people, math is not always 100% needed in programming and you can go pretty far without knowing large complex formulas. However, to be a productive programmer in industry you do have to know how to USE math and how to apply a given formula. Just knowing that a formula exists, where to find it, what the variables in it mean and being able to plug them in can get you even farther. To know that, you do need to know a bit of math.
Macosxnerd, as well as myself, know how many times we have had to help people with just the math let alone the code. Sometimes the answer is purely a math one than the programming. Don't let yourself be falsely convinced that math only appears purely in graphics programming or games. There are many more areas.
Financial systems - have to know about interest, calculate mortgages, return on investment formulas, break event points, calculating charts, probability, etc
Science systems - scientists use programs which model things they are studying. Formulas for balancing chemical equations, sequencing the human genome, calculating distance to stars, aerodynamics for planes, fluid motion weather and other physics etc
Algorithms - the various functions you use in the .NET framework to sort an array itself is based on previous work done in mathematics. Finding efficient ways to find something, calculate an answer, cut problem sets down without going into exponential growth all is based on math.
As I have always told people, math is not always 100% needed in programming and you can go pretty far without knowing large complex formulas. However, to be a productive programmer in industry you do have to know how to USE math and how to apply a given formula. Just knowing that a formula exists, where to find it, what the variables in it mean and being able to plug them in can get you even farther. To know that, you do need to know a bit of math.
Macosxnerd, as well as myself, know how many times we have had to help people with just the math let alone the code. Sometimes the answer is purely a math one than the programming. Don't let yourself be falsely convinced that math only appears purely in graphics programming or games. There are many more areas.
pandaman
17 April 2011 - 09:34 AM
Interesting points macosnerd101 and I agree with you about how it helps improve efficiency(I told you about my Project Euler problem). However, I think that it's not the math directly that's important, rather it's the thought process that happens when doing math. Kinda like it's more important to learn how to prove something rather than just memorizing formulas.
e_i_pi
17 April 2011 - 04:48 PM
There's a lot more maths in programming than first meets the eye, maths is not just numbers as a lot of people think. When I was in final year at University, I rarely wrote down numbers in exams. I was studying Complex Algebra, Data Mining, Knowledge Discovery, Set Theory, and Cryptography. Here are some programming - maths techniques that are comparable in some way or another:
- Boolean Algebra - Mathematical Logic
- Object Inheritance - Set Theory
- Functions - Category Theory
- Regex - Markov Algorithm
- Pathfinding - Combinatorics
- Hash Functions - Cryptography
- Arrays - Group Theory
- Terrain Generation - Fractal Geometry
- Business Intelligence - Statistics
- AI - Game Theory
- MVC - Control Theory
Jstall
18 April 2011 - 06:09 AM
I recently read an interesting blog post on the subject of math and programming. warning it's a bit of a long read .
The author does touch on some interesting points including how he believes math is generally not being taught correctly in schools, and that someone who is weak in math but learns programming concepts can find it much easier to pick up more complex math in the future. That is, knowing programming can make it easier to learn math.
I look at math like another tool to be used in software development, just like OOP design and relational database theory. Being able to use this tool effectively will help in many aspects of a developers career.
I feel math is a weak spot for me, I would love to take a few courses to broaden my skill set and make myself more marketable. I just haven't had the time as of late, life/work hectic. I really want to take something in the near future though, I know it's an important skill to have.
The author does touch on some interesting points including how he believes math is generally not being taught correctly in schools, and that someone who is weak in math but learns programming concepts can find it much easier to pick up more complex math in the future. That is, knowing programming can make it easier to learn math.
I look at math like another tool to be used in software development, just like OOP design and relational database theory. Being able to use this tool effectively will help in many aspects of a developers career.
I feel math is a weak spot for me, I would love to take a few courses to broaden my skill set and make myself more marketable. I just haven't had the time as of late, life/work hectic. I really want to take something in the near future though, I know it's an important skill to have.
sunil.gandhi007
18 April 2011 - 01:00 PM
Nice article....Maths holds applications in alll parts of learning and day to day life...
its good to be good at it...
its good to be good at it...
e_i_pi
18 April 2011 - 10:54 PMJstall, on 18 April 2011 - 07:09 AM, said:
I recently read an interesting blog post on the subject of math and programming. warning it's a bit of a long read :).
Nice link, and while I read it, it reminded me of another similarity between maths and programming. In programming, there is no strict right or wrong for a solution, and that applies in maths too. If you look at the Wikipedia entry for Pythagoras' Theorem, it names a book that has 370 distinct proofs for the Theorem.
When I was in 2nd year Uni, a Differential Equations exam I took had a total of 5 questions. I could solve two questions, so I knew I had at least 35-40% score, but the other three questions were giving me no end of trouble. They each involved finding either the volume of a 3D space, or the length of a curve. I never turned up to the 2-3 lessons we had on those topics, so I thought I was screwed. After stressing about it for around an hour, I gave up - looked away from the paper and let my eyes wander the room. After about 30 minutes, with 20 minutes left on the clock, I thought "I may as well have one more look". I studied the questions again, and what little work I had already done to solve them. My fresh eyes saw that I could solve every single question by using one simple proof - that the area of a circle is pi * radius * radius. Sounds too simple? Well, it involved me transforming from cartesian to polar co-ordinates, in 2 and 3 dimensions, something I'd learnt in a completely different subject, but that I could apply to these problems. It was never taught in Differential Equations, it was taught in Fundamentals of Mathematics! There's always more than one way to solve a problem... :)
lockon777
05 May 2011 - 05:50 PM
Maby i should learn pre cal befor i try to do more complated things
RetardedGenius
19 May 2011 - 07:32 AM
This is an excellent post, that clearly demonstrates how a knowledge of maths can dramatically improve the efficiency of a computation. Many people dismiss maths as not being to important for programming, however a knowledge of maths can often be the difference between using an O(n^{2}) and an O(n*log(n)) computation! :)
v0rtex
21 May 2011 - 03:08 PM
I totally agree with you and a very nice post however I do think that whilst it is important and fundamental to be comfortable with maths in many areas of programming there are also areas where it is not too important. My brother does web design with HTML and CSS,PHP etc... And atleast for HIM its not a big issue. Nice Post!
hockey97
27 May 2011 - 04:23 PM
Hi, can you guys give me some resources online or some books I might find at the local library to brush up on my math skills.
I am in college but going for accounting and finance. Ever since I was in 6th grade I been learning programming online and threw books.
I learn better by reading books or learning online for any subject. It's because I can take my own time to try and full master the concepts taught where college forces you to move your butt... which if you didn't understand some concepts fully it will haunt you down the road.
I would like good resources to look at that can bring me up from basic algbra all the way to calculus.
I have stopped at algbra 2 or you should say algbra intermediate where they teach you about imaginary numbers.
This fall I be taking a business calculus class. Since it's been 2 to 3 years ago that I took a math class. I need to brush up my math before taking such a math class.
I asked here since your on topic as to why math is important. It's good to know but I am sure most of us looking at this article may suck at math or not very good with it. So I think the question here is where can we find resources to brush up our math skills without having to take a math class at our local college.
I am in college but going for accounting and finance. Ever since I was in 6th grade I been learning programming online and threw books.
I learn better by reading books or learning online for any subject. It's because I can take my own time to try and full master the concepts taught where college forces you to move your butt... which if you didn't understand some concepts fully it will haunt you down the road.
I would like good resources to look at that can bring me up from basic algbra all the way to calculus.
I have stopped at algbra 2 or you should say algbra intermediate where they teach you about imaginary numbers.
This fall I be taking a business calculus class. Since it's been 2 to 3 years ago that I took a math class. I need to brush up my math before taking such a math class.
I asked here since your on topic as to why math is important. It's good to know but I am sure most of us looking at this article may suck at math or not very good with it. So I think the question here is where can we find resources to brush up our math skills without having to take a math class at our local college.
trevster344
13 June 2011 - 07:45 PM
To assume math is only used in game programming is foolish. It's extremely important and math does not only come in the form of numbers.
jon.kiparsky
21 June 2011 - 10:19 AM
I'm sunk pretty deep in a few texts, working through them all in parallel, which is sort of how I work.
One is Knuth's The Art of Computer Programming - a big, dense book, beautifully written, that i've been meaning to get to for a few years, and finally realized that would only get to it by getting to it. He starts out with mathematical foundations - it's a pretty take-no-prisoners approach, but if you don't get it from reading Knuth you'll have a pretty good idea of what it is you need to read up on.
I'm also looking at Rosenbloom's Elements of Mathematical Logic. Pretty good stuff, and reasonably clear, for a mathematical text.
Joseph Breuer's Introduction to the Theory of Sets is a pretty good and pretty basic intro to set theory.
The Knuth is not cheap, but the other two are available from Dover for peanuts ($10 or $15).
Otherwise: I agree with all of the sensible comments posted here, and I disagree vehemently with the non-sensible ones.
One is Knuth's The Art of Computer Programming - a big, dense book, beautifully written, that i've been meaning to get to for a few years, and finally realized that would only get to it by getting to it. He starts out with mathematical foundations - it's a pretty take-no-prisoners approach, but if you don't get it from reading Knuth you'll have a pretty good idea of what it is you need to read up on.
I'm also looking at Rosenbloom's Elements of Mathematical Logic. Pretty good stuff, and reasonably clear, for a mathematical text.
Joseph Breuer's Introduction to the Theory of Sets is a pretty good and pretty basic intro to set theory.
The Knuth is not cheap, but the other two are available from Dover for peanuts ($10 or $15).
Otherwise: I agree with all of the sensible comments posted here, and I disagree vehemently with the non-sensible ones.
hockey97
22 August 2011 - 02:12 AM
Anyone got good resources to brush up on your math skills????
I haven't been good in math since 1st to 12th grade. I mean I was average.. not the best and not the dumbest in math.
I started to learn programming at 6th grade. I started off reading a c++ book since I heard c++ was used to make games... before opening this book I thought binary was an alien language or a math language where you need to be a math major to understand it. This changed after learning about programming and binary and Boolean etc. I tried to learn c++ in 6th grade and wanted to make some neat games. well... you could guess what happened... I ended up getting a headach and didn't understand what is X notice examples showing x = this. The book said it was to store something in memory. I thought hmm... must be how you store something in ram. well eventually went online and talked with many programmers. I then started to learn C language and learned html,css,php. I learned html,css,php first before going into C. Then C was a breeze... and finally started to learn c++ in 10th grade. Overall... by that time I knew after reading many example code in c++ for games and many other programs. I knew how important is math and knew some of the stuff how I could apply what I learn from the classroom to my programs. Like the matrix multiplication etc.
This opened my eyes to why you need math and how important it is to make the next best piece of software. I got interested but realized that in highschool and college. They don't actually explain how you can use these math formulas and what is the goal using these.
I now think math is fun but still feel math class is pointless. I mean the explain you how to do the problems with the equation or formula but won't tell you why you need to use it and what is the purpose... what is the goal of using it. Makes you feel like math is useless... but in reality it's not but you can't understand how to apply it to real world problems. This makes you feel like why would someone use this in their life.
For Instance I remember in school they gave us a math problem. we are putting a fence in our garden. they tell use the footage of each piece of fence. They ask you now find the area that is inside the fence for our garden. Now I was a kid back at that time. So I thought it was pointless... it was like who cares... just put a fence and just have the plan of where you want to put it and just build the fence there and your done.
if each side is 5feet then it be 5*5= 25feet of area. width times height.
well, I mean at the time we as kids can't really understand why you need to know the area... I mean who cares.. just go and build the fence. later on in highschool. many kids ask why we learned that and why it keeps coming back up... after learning that math there were other areas you can figure out like an area of a triangle...etc. In highschool the teacher said well if your installing an air conditional.... you will need to know how much space or area you need to cool down in order to know exactly what A/C unit you need to install to cool down your house... that made sense... but took them in highschool to give us some real world problems that you can solve by using these kinds of math.
I think not just programmers need math but mostly every field of work needs to know math to solve complex problems.
For instance building a space shuttle. You mix science and math to build such a thing. Yet, it costs lots of money and via just paper you have to know exactly that your designs will work flawlessly... you can't make mistakes... because small mistakes may cost millions. In those areas... you need math and science to help you design something of that nature and know exactly that it will work or at least be in the ball park. You will never know 100% weather something will work 100% usually there are small bugs or issues that occur and very rarely big issues occur.
your just using math and science as tools. To solve problems you face in the real world.
If you learn the theory of math and you have a big box full of math tools... but don't know how you can use the tools to solve your problem you face today... then those tools are useless and won't be used and you will use very very hard complex ways to try and solve your problem and you will most likely never solve them or would take you months or years whereas if you used those mat tools you could of solved the problem in one day or two.
So math is important in every profession. Even when barbers give you a haircut... some may not realize it but you do need to know math... but I am sure you don't need the same math as a rocket scientist needs. Since the problems they face would be different then the problems the rocket scientists face.
I ask here, instead of saying math is important.. you should be telling us some resources on what we can do to better our math skills. what should we be looking at.
Me, I am in college going for accounting and finance. I won't be taking advance math classes but I do want to expand my math knowledge so I can write more better programs in the future.
I think math is only fun when you can actually use it to solve many problems you face and you then realize if you didn't know that math you wouldn't of been able to solve such problems.
So what math should I be learning to help me make better software.
I haven't been good in math since 1st to 12th grade. I mean I was average.. not the best and not the dumbest in math.
I started to learn programming at 6th grade. I started off reading a c++ book since I heard c++ was used to make games... before opening this book I thought binary was an alien language or a math language where you need to be a math major to understand it. This changed after learning about programming and binary and Boolean etc. I tried to learn c++ in 6th grade and wanted to make some neat games. well... you could guess what happened... I ended up getting a headach and didn't understand what is X notice examples showing x = this. The book said it was to store something in memory. I thought hmm... must be how you store something in ram. well eventually went online and talked with many programmers. I then started to learn C language and learned html,css,php. I learned html,css,php first before going into C. Then C was a breeze... and finally started to learn c++ in 10th grade. Overall... by that time I knew after reading many example code in c++ for games and many other programs. I knew how important is math and knew some of the stuff how I could apply what I learn from the classroom to my programs. Like the matrix multiplication etc.
This opened my eyes to why you need math and how important it is to make the next best piece of software. I got interested but realized that in highschool and college. They don't actually explain how you can use these math formulas and what is the goal using these.
I now think math is fun but still feel math class is pointless. I mean the explain you how to do the problems with the equation or formula but won't tell you why you need to use it and what is the purpose... what is the goal of using it. Makes you feel like math is useless... but in reality it's not but you can't understand how to apply it to real world problems. This makes you feel like why would someone use this in their life.
For Instance I remember in school they gave us a math problem. we are putting a fence in our garden. they tell use the footage of each piece of fence. They ask you now find the area that is inside the fence for our garden. Now I was a kid back at that time. So I thought it was pointless... it was like who cares... just put a fence and just have the plan of where you want to put it and just build the fence there and your done.
if each side is 5feet then it be 5*5= 25feet of area. width times height.
well, I mean at the time we as kids can't really understand why you need to know the area... I mean who cares.. just go and build the fence. later on in highschool. many kids ask why we learned that and why it keeps coming back up... after learning that math there were other areas you can figure out like an area of a triangle...etc. In highschool the teacher said well if your installing an air conditional.... you will need to know how much space or area you need to cool down in order to know exactly what A/C unit you need to install to cool down your house... that made sense... but took them in highschool to give us some real world problems that you can solve by using these kinds of math.
I think not just programmers need math but mostly every field of work needs to know math to solve complex problems.
For instance building a space shuttle. You mix science and math to build such a thing. Yet, it costs lots of money and via just paper you have to know exactly that your designs will work flawlessly... you can't make mistakes... because small mistakes may cost millions. In those areas... you need math and science to help you design something of that nature and know exactly that it will work or at least be in the ball park. You will never know 100% weather something will work 100% usually there are small bugs or issues that occur and very rarely big issues occur.
your just using math and science as tools. To solve problems you face in the real world.
If you learn the theory of math and you have a big box full of math tools... but don't know how you can use the tools to solve your problem you face today... then those tools are useless and won't be used and you will use very very hard complex ways to try and solve your problem and you will most likely never solve them or would take you months or years whereas if you used those mat tools you could of solved the problem in one day or two.
So math is important in every profession. Even when barbers give you a haircut... some may not realize it but you do need to know math... but I am sure you don't need the same math as a rocket scientist needs. Since the problems they face would be different then the problems the rocket scientists face.
I ask here, instead of saying math is important.. you should be telling us some resources on what we can do to better our math skills. what should we be looking at.
Me, I am in college going for accounting and finance. I won't be taking advance math classes but I do want to expand my math knowledge so I can write more better programs in the future.
I think math is only fun when you can actually use it to solve many problems you face and you then realize if you didn't know that math you wouldn't of been able to solve such problems.
So what math should I be learning to help me make better software.
← January 2021 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
My Blog Links
Recent Entries
Recent Comments
Search My Blog
1 user(s) viewing
1 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)