how to find out the square root of the sum of the first 500 fibonacci number ?

,

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. :slight_smile:

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 ??

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

Oh sorry. Well you can use the BigInteger class then, as mentioned by shivam217

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?

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.

In fact, there are just 3 known Fibonacci squares: link

2 Likes

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.

@j0inedup,

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

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.

//