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.

### My Blog Links

### Recent Entries

### Recent Comments

### Search My Blog

### 0 user(s) viewing

**0**Guests

**0**member(s)

**0**anonymous member(s)