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

Exploiting Double Free Vulnerabilities...

Alsalam alikom wa ra7mat Allah wa barakatoh



Huh!! that's what I said when I first saw that title... but let me explain...


Double Free means that you try to free a pointer two times (which is logically can't work).
Actually windows SP2 and later (even Vista) this can be done (in somehow) and can actually corrupt the heap (Vista will shout at your face if u did) and that can make you able to use and browse the heap as you want..

Facts to know about how Windows frees your pointers:
- There is something called Lookaside buffer (fast access, small size) and another thing is FreeList(slower access, the whole memory).
- Chunk is an object of the DataStructure that holds mainly 2 things: pointer to where the next free Chunk is and pointer to the previous free one (think about it like a node in a linked list)
- The first 4 bytes of the Chunk is the BLink (BackLink) and the second 4 bytes is the FLink
- delete ptr1;
delete ptr2;
Windows takes your Chunk (for ptr1) and puts it in the Lookaside s…

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 “Select and Correct” then draw …

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… :)