i am trying but fail to find out that…i am trying in c (GCC 4.2.1)…i want to solve it in c only…
The sum of first n fibonacci numbers is infact the (n+2)th fibonacci number minus one:
f(1)+f(2)+…+f(n)=f(n+2)-1.
So what you need to do is find the sqrt of f(n+2)-1. That is trivial. 
You can handle very large numbers easily in Java or Python. But in C/C++ ,you would have to implement it through Big Integer class.
2 Likes
simplest thing you could use is floating point to store the fibonacci numbers - the square root of a fibonacci number doesn’t need to be an integer so you’re throwing away precision when you take the sqrt anyway.
fib(500) fits into a double
e.g.
#include <stdio.h>
#include <math.h>
double iminus1=1,iminus2=1, i;
int j=3;
main()
{
printf("N\tfib\tsqrt\n");
printf("%d\t%g\t%g\n",1,1.0,sqrt(1));
printf("%d\t%g\t%g\n",2,1.0,sqrt(1));
for (;j<=500;j++)
{
i=iminus1+iminus2;
printf("%d\t%g\t%g\n",j,i,sqrt(i));
iminus2=iminus1;
iminus1=i;
}
return 0;
}@amul_patel - if you are ultimately finding square root then there is a high chance it will be irrational, so a double would suit the requirement! And fibo(n+2) can be calculated in O(log(n)) normally with double! Problem solved?
How does fib(500) fits into a double?
I believe it gives precision errors, as expected:
In Python (correct, checked online):
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
Wrong using double in C (obviously):
139423224561697698330489613862193018947914545343780323868775030943672596190605867771863846635039486902272
So, how can that ever work?
I’m confused that’s all
Bruno
no buddy here the idea is that you can’t store the more than 20 digit in c programming…and in this problem the sum is even exeed then 30 digit…so which logic apply to doing that thing ??
Oh sorry. Well you can use the BigInteger class then, as mentioned by shivam217
not sure whether it would lead to right answer:
sqrt(a)=b
, binary search on
b
and check whether
b^2==a
.
10^18*10^18=10^36
, so
long long
might help you in handling
b
. keep
a
in array.
no buddyy…if i use the double then it can store around the 16 digit number…so it will not work…if you have any idea then post here code…i will appreciate your help…thanks
hai buddyy sorry to ask one thing here is that…the answer in the double is printing in this form: 1.39423e+104
so how to convert this one in the regular form like 11232323 without e …how to done here…help me out
ya i know but which data type i have to use here ??? give me the code which is working properly for this problem in c…thanks your feedback yar…
#include
using namespace std;
#include<stdio.h>
int main()
{
double x= 1.39423e+104;
// cout<<x<<endl;
printf("%.0f",x);
}
this is how to convert it to regular form…
as i mentioned in the above code… double can take as large values as possible… even 10^104(>100 dgt no) … only issue will be precision!! but it will be quite accurate as you never really need that large precision… if it does matter, then kindly switch to matlab or python!! they can handle large numbers without loss of precisions… hope this helps!
if this mathod to see the regular form then the code given above may be wrong…@joinedup
C’s built in maths uses fixed size representations of numbers - there are two different types of representation, integer types (char, short, int, long, long long) which can store whole numbers with perfect precision and floating point types (float and double) which can store a greater range of values but with a possible loss of precision… they can chop of the least significant digits (but often this is not really important)
neither is right or wrong, it’s up to you as a coder to select which is most appropriate for the task you’re trying to solve.
it fits but with precision loss. you wouldn’t use a double if you needed perfect precision - changing the format in printf doesn’t bring back the precision you’ve lost by using a floating point representation.
The OP’s application is taking the square root which isn’t going to be an integer in the majority of cases as xellos showed earlier.
in a lot of practical applications you’re happy enough to know the answer is 1.3942322456169E+104 to 14 significant figures - but if that isn’t the case you’d use a bigint library or a language with built in support.