Replying to my own posting! Even better, since it replaces the
relatively slow modulus operation with a comparison and subtraction:
long long int n;
int a = 1, b = 2, c;
for(i = 0; i < n, i++)
{
c = a + b;
a = b;
b = c < 1000000007 ? c : c - 1000000007;
}
// b is the result
Dave
On May 23, 7:30 pm, Dave <[email protected]> wrote:
> @Akshata: Actually, you only need to find the n+3rd Fibonacci number,
> modulus 1000000007. This saves you from having to deal with big
> integers. Something like this should do for the calculation, assuming
> that long long int is 64 bits:
>
> long long int n;
> int a = 1, b = 2, c;
> for(i = 0; i < n, i++)
> {
> c = a+b % 1000000007;
> a = b;
> b = c}
>
> // c is the result
>
> Dave
>
> On May 23, 12:36 am, Akshata Sharma <[email protected]> wrote:
>
>
>
> > It appers that the problem is just to find the (N+3)th fibonacci number for
> > given N. Since N is very large, how to find nth fibonaci number for such a
> > large n??
>
> > On Mon, May 23, 2011 at 7:51 AM, tec <[email protected]> wrote:
> > > Try thinking backwards.
> > > (0,1),(1,2),(2,3),(3,5),(5,8),(8,13),...
>
> > > 2011/5/22 shady <[email protected]>:
> > > > Hey,
> > > > Can anyone tell how to solve this problem in Spoj ? I went through
> > > > some material but there all they were discussing was on complexity and
> > > > not on actual number of iterations.
> > > >http://www.spoj.pl/problems/MAIN74/
>
> > > > Thanks.
>
> > > > --
> > > > 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.
>
> > > --
> > > __________________________________________________
>
> > > --
> > > 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.-Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
--
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.
