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
milleja46
20 September 2011 - 07:03 AM
Well, I knew it was important i just didn't think it was this important...well now i know
dreamincodehamza
10 November 2011 - 09:48 PM
great artical
i also have a misconception about this topic.
i also have a misconception about this topic.
Beach_Coder
13 November 2011 - 03:51 PM
"If only I had more mathematics." - Albert Einstein
Although a lot of problems are solved without mathematics, or at least without the explicit use of math, I would argue that there is no problem that cannot be solved with mathematics. Further, or perhaps to the point, solving any truly complex problem requires the use of mathematics.
Although a lot of problems are solved without mathematics, or at least without the explicit use of math, I would argue that there is no problem that cannot be solved with mathematics. Further, or perhaps to the point, solving any truly complex problem requires the use of mathematics.
pablo9891
20 November 2011 - 02:34 PMQuote
Although a lot of problems are solved without mathematics, or at least without the explicit use of math, I would argue that there is no problem that cannot be solved with mathematics. Further, or perhaps to the point, solving any truly complex problem requires the use of mathematics.
I'm totally agree with you in that we can't forget that we are in some way (and this is the idea i have about what computing is) trying to emulate the reality, just look at how facebook emulates comunication between people or look how real is the new Call of duty is. Maths in some way were born with the same purpose by trying to emulate the whole universal structure there's no way in which these concepts could by any mean be separate.
nuclearfroggy
21 November 2011 - 01:23 PM
Great article, I can see in this example how much of a difference this could make to efficiency. My only question is, you say it's O(1) time, but how costly is it to calculate x^n where n is really large - does the processor do a bit of clever maths itself?
linuxnut
10 December 2011 - 04:25 PM
Math is a toolbox for your programming. This thread has already given a lot of great examples. Once, I worked on a manufacturing robotics project. The problem was that the previous programmer could not understand coordinate math/kinematics of the robot arm.
I was glad that my school required 6 math classes:
- Calculus 1, 2
- Statistics 1, 2
- Discrete Math
- Linear Algebra & Differential Equations
If you want to get paid for graphical/scientific/financial, then math is gonna be your best friend.
I was glad that my school required 6 math classes:
- Calculus 1, 2
- Statistics 1, 2
- Discrete Math
- Linear Algebra & Differential Equations
If you want to get paid for graphical/scientific/financial, then math is gonna be your best friend.
noorahmad
13 February 2013 - 03:05 AM
I don't like math because I have to study more to pass the exam
AnthonyMcqueen21
08 July 2015 - 11:45 AM
I agree having a good concept on Algebra and some Calculus will help in programming when developing complex algorithms matrices and other programming architecture.
← March 2018 →
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
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)