Skip to main content

Q Matrix... Dynamic is not always the solution...

Alsalam alikom wa ra7mat allah wa barakatoh

Today I'm going to speak about a useful (I hope) piece of algorithm, that makes ur life easier ;)..

Let's re-visit the Fibonacci Series, F(n) = F(n-1) + F(n-2)

Till yesterday, I knew only the dynamic solution for it (Top Down and Bottom Up)

long long fib(unsigned int index) {
if (index < 0)
return 0;
if (sol[index] != -1)
return sol[index];
return fib(index - 1) + fib(index - 2);
}
looks neat, huh!!
so, what if I ask u to give me the answer of fib(1000000000) ?
this will require in the best case to have 1000000000 iterations which is O(n), mmmm bad!!

Let's see the second solution (using Q-Matrix)
Some math first :
Q: What do you need to calculate fib(n) ?
A: fib(n-1) & fib(n-2)

so, if we re-wrote the relation between inputs and output like this :
[fib(n-1), fib(n-2)] * [1, 1] = [fib(n-1) + fib(n-2), fib(n-1)] which is [fib(n), fib(n-1)]
[1, 0]

that last vector is suitable to get the next fib(n+1) if we multiplied it by the same matrix, right ? ok,... good,
now the idea :
let's call the matrix M, the vector V so Vn * M = Vn+1
if we did this : Vn * M^3, what will be the result ?
this will iterate 3 times and give us Vn+3 (in one step)
Q: How many matrix multiplications do you need to get M^1000000000 ?
A: lg(1000000000)
Q: How ?
A: M*M = M^2, M^2 * M^2 = M^4, M^4 * M^4 = M^8..... and so on, the powers goes this fast :2, 4, 8, 16, 32....... powers of 2 ;)

The code to do this multiplication goes like this :
Matrix power(int n)
{
if (n <= 1)
return *this;
int i;
Matrix res = *this;
for(i = 2; i < n; i += i)
res = res * res;
i /= 2;
return res.power(n - i);
}
When you are sure you understand this, try to solve this nice problem : http://acm.uva.es/p/v107/10743.html

That's it for today...
C u soon In Shaa Allah,

Alsalam alikom wa ra7mat allah wa barakatoh

Comments

Popular posts from this blog

Windows7 adds Math Input Panel

Alsalam alikom wa ra7mat Allah wa barakatoh… I was reading a windows team post about Input Panels improvements in Windows7 [ here ]. When at the end I saw a very interesting –intuitive if you wish- new thing… which is, as you guessed, the Math Input Panel… Yes, that crappy font is mine… I “drew” that by mouse as I don’t have a tablet pen/pc. You can then paste it directly into word and it’ll recognize it as an editable equation… During my tests, the output panel (the top part) hanged, but I liked that the drawing panel was still responsive and I could still write/erase… till the top one started to respond again… One other thing to know, after you click Insert (that button down there) it copies the equation in MathML [ Wikipedia link ] format.. which is a standard way of representing equations and hence any application that recognizes the format can insert it not as an image but as a nice editable equation… If you think it recognized something wrong, you can click “Sele

Microsoft Web Platform Installer… coming near you

The Microsoft Web Platform Installer 2.0 (Web PI) is a free tool that makes it simple to download, install and keep up-to-date with the latest components of the Microsoft Web Platform, including Internet Information Services (IIS), SQL Server Express, .NET Framework and Visual Web Developer. In addition, install popular open source ASP.NET and PHP web apps with the Web PI. Here is the code snippet if you want to spread the word :) < a href ="http://go.microsoft.com/fwlink/?LinkId=146503" title=" Get the Microsoft Web Platform " > < img src ="http://www.microsoft.com/web/media/badge/get_microsoft_web_platform.png" alt ="Get the Microsoft Web Platform" border ="0" /> </ a >

Visual Studio 2008 Not saving changes or project properties?

Alsalam alikom wa ra7mat Allah wa barakatoh (Peace upon you) I’ve recently ran into problems with VS 2008. Summarized here: When you try to edit the project properties (specially C++ projects) you are faced with a little nice message saying “Exception from HRESULT: 0xF9F0F308”. Sometimes when you are editing a file (specially large ones), VS doesn’t recognize you’ve made changes (ie doesn’t display that ‘*’ in the files tabs) hence, when you save, nothing actually gets saved. For those 2 problems, a friend explained the problem and a work around (till they officially release a fix)… Open up a Visual Studio 2008 Command Prompt Run cd "C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\IDE" Make a backup copy of devenv.exe in case something does not work right. ie. copy devenv.exe devenv.exe.bak Run editbin /largeaddressaware:no devenv.exe Happy VSing… :)