@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't
mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$,
and your function returned double or float instead of an integer type such as int
or floatlong, you would see that the result is incorrect due to floating-point errors.
Here's an illustration of how incorrect the result would be:
@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't
mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$,
and your function returned double or float instead of an integer type such as int
or float, you would see that the result is incorrect due to floating-point errors.
Here's an illustration of how incorrect the result would be:
@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't
mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$,
and your function returned double or float instead of an integer type such as int
or long, you would see that the result is incorrect due to floating-point errors.
Here's an illustration of how incorrect the result would be:
\498ドル\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous ternterm \308ドル\ 061\ 521\ 170\ 129\$.
This is not a problem in thisour scenario, since we only need Fibonacci numbers which are less
or equal to \4ドル\ 000\ 000\$. Moreover the function given above returns an int, for which can
only hold thethe maximum possible value ofis \2ドル^{31}-1\$, which is \2ドル\ 147\ 483\ 647\$ — well out of danger.
\498ドル\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous tern \308ドル\ 061\ 521\ 170\ 129\$.
This is not a problem in this scenario, since we only need Fibonacci numbers which are less
or equal to \4ドル\ 000\ 000\$. Moreover the function given above returns an int, which can
only hold the maximum value of \2ドル^{31}-1\$, which is \2ドル\ 147\ 483\ 647\$ — well out of danger.
\498ドル\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous term \308ドル\ 061\ 521\ 170\ 129\$.
This is not a problem in our scenario, since we only need Fibonacci numbers which are less
or equal to \4ドル\ 000\ 000\$. Moreover the function given above returns an int, for which
the maximum possible value is \2ドル^{31}-1\$, which is \2ドル\ 147\ 483\ 647\$ — well out of danger.
EDIT
@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't
mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$,
and your function returned double or float instead of an integer type such as int
or float, you would see that the result is incorrect due to floating-point errors.
Here's an illustration of how incorrect the result would be:
actual value [long] Binet's formula [double]
3 3.0000000000000004
5 5.000000000000001
8 8.000000000000002
⋮ ⋮
498454011879264 498454011879265.2
\498ドル\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous tern \308ドル\ 061\ 521\ 170\ 129\$.
This is not a problem in this scenario, since we only need Fibonacci numbers which are less
or equal to \4ドル\ 000\ 000\$. Moreover the function given above returns an int, which can
only hold the maximum value of \2ドル^{31}-1\$, which is \2ドル\ 147\ 483\ 647\$ — well out of danger.
I would post a link to a now-classical paper by David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic. But since it's not just some easy wikipedia-style reading, I doubt anybody would actually read it. It's no problem to google it if you're interested.
So now we know how to calculate the index of the last Fibonacci number in our sum. Note
Note that \1ドル\$ occurs in the sequence twice, but obviously this method can produce only one index.
So now we know how to calculate the index of the last Fibonacci number in our sum. Note that \1ドル\$ occurs in the sequence twice, but obviously this method can produce only one index.
EDIT
@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't
mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$,
and your function returned double or float instead of an integer type such as int
or float, you would see that the result is incorrect due to floating-point errors.
Here's an illustration of how incorrect the result would be:
actual value [long] Binet's formula [double]
3 3.0000000000000004
5 5.000000000000001
8 8.000000000000002
⋮ ⋮
498454011879264 498454011879265.2
\498ドル\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous tern \308ドル\ 061\ 521\ 170\ 129\$.
This is not a problem in this scenario, since we only need Fibonacci numbers which are less
or equal to \4ドル\ 000\ 000\$. Moreover the function given above returns an int, which can
only hold the maximum value of \2ドル^{31}-1\$, which is \2ドル\ 147\ 483\ 647\$ — well out of danger.
I would post a link to a now-classical paper by David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic. But since it's not just some easy wikipedia-style reading, I doubt anybody would actually read it. It's no problem to google it if you're interested.
So now we know how to calculate the index of the last Fibonacci number in our sum.
Note that \1ドル\$ occurs in the sequence twice, but obviously this method can produce only one index.