Sorry for the confusion, Given series : http://oeis.org/A032263/list How to get the nth number of the series in O(log(n)) ?
Regards, Shady On Mon, Jan 10, 2011 at 12:36 AM, shady <[email protected]> wrote: > thanks that was a very nice tutorial..... > but i am still stuck with > > > S(n,3) = A(n+3) = 6*A(n+2) - 11*A(n+1) + 6*A(n) ------------------- 1 > > S(n+1,4)=S(n,3)+4*S(n,4) -------------------- 2nd stirling number > > 3*S(n+1,4) = 0, 0, 3, 30, 195, 1050, 5103, 23310........ > > what will be the matrix for the second sequence > i know how to solve the first recurrence, but how to solve the second > one............ > > On Sun, Jan 9, 2011 at 6:13 PM, radha krishnan < > [email protected]> wrote: > >> You find this so useful .... >> http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html >> >> On Sun, Jan 9, 2011 at 6:10 PM, shady <[email protected]> wrote: >> > I am not familiar with such techniques, can you please refer to some >> article >> > where such techniques are explained, ... >> > Regards, >> > Shady >> > >> > On Sun, Jan 9, 2011 at 5:44 PM, juver++ <[email protected]> wrote: >> >> >> >> There is very useful technique for this kind of problem. >> >> A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). >> >> Let's introduce matrix B: >> >> C1 -C2 C3 >> >> 1 0 0 >> >> 0 1 0. >> >> A(n-1) A(n) >> >> B x A(n-2) = A(n-1) >> >> A(n-3) A(n-2) >> >> and so on.. >> >> So to find A(n) you should muultiply matrix B^n by initial vector (A2, >> A1, >> >> A0). >> >> B^n can be calculated using fast exponention algorithm. >> >> Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]<algogeeks%[email protected]> >> . >> >> For more options, visit this group at >> >> http://groups.google.com/group/algogeeks?hl=en. >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > For more options, visit this group at >> > http://groups.google.com/group/algogeeks?hl=en. >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
