This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
printf("%3d :%25llu \n",count,fibn);
fib0 = fib1;
fib1 = fibn;
count++;
}
return ;
}
int main(void)
{
unsigned long temp = 0;
puts("Fibonacci Numbers");
fibonacci(100); /*Print the first 100 Fibonacci Numbers*/
return 0;
}
This is a part of the output :
Fibonacci Numbers
...snip...
90 : 1779979416004714189
91 : 2880067194370816120
92 : 4660046610375530309
93 : 7540113804746346429
94 : 12200160415121876738
95 : 1293530146158671551
96 : 13493690561280548289
97 : 14787220707439219840
98 : 9834167195010216513
99 : 6174643828739884737
100 : 16008811023750101250
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
17  7506 
Tarique wrote:
) <snip>
) unsigned long long fibn = 1; /*Nth Fibonacci Number*/
) <snip>
) if((fibn < 0) || (fibn ULLONG_MAX)){
This can never happen.
Some compilers would even warn about an if condition never being true,
or about unreachable code, or something similar.
) puts("\nOverflow\n");
) <snip>
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Tarique wrote:
This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
Why do you treat fib1 as long long when it is declared as unsigned long
long?
while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
How can 'fibn' be less than zero when it is an unsigned type? Also how
can it be greater than ULLONG_MAX?
One method would be:
if (ULLONG_MAX - fib1 < fib0) { puts("Overflow."); break; }
printf("%3d :%25llu \n",count,fibn);
Why the precision specifiers?
fib0 = fib1;
fib1 = fibn;
count++;
}
return ;
}
int main(void)
{
unsigned long temp = 0;
puts("Fibonacci Numbers");
fibonacci(100); /*Print the first 100 Fibonacci Numbers*/
return 0;
}
This is a part of the output :
Fibonacci Numbers
...snip...
90 : 1779979416004714189
91 : 2880067194370816120
92 : 4660046610375530309
93 : 7540113804746346429
94 : 12200160415121876738
95 : 1293530146158671551
96 : 13493690561280548289
97 : 14787220707439219840
98 : 9834167195010216513
99 : 6174643828739884737
100 : 16008811023750101250
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Are you sure about the output?
"Tarique" <pe*****@yahoo.comwrote in message
This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
Here you need if(fibn < fib0 || fibn < fib1)
unsigned numbers wrap silently.
You need a huge integer library to calculate high Fibonacci numbers
effectively.
--
Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm
Tarique wrote:
This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
printf("%3d :%25llu \n",count,fibn);
fib0 = fib1;
fib1 = fibn;
count++;
}
return ;
}
int main(void)
{
unsigned long temp = 0;
puts("Fibonacci Numbers");
fibonacci(100); /*Print the first 100 Fibonacci Numbers*/
return 0;
}
This is a part of the output :
Fibonacci Numbers
...snip...
90 : 1779979416004714189
91 : 2880067194370816120
92 : 4660046610375530309
93 : 7540113804746346429
94 : 12200160415121876738
95 : 1293530146158671551
96 : 13493690561280548289
97 : 14787220707439219840
98 : 9834167195010216513
99 : 6174643828739884737
100 : 16008811023750101250
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Try this modification:
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25llu \n",fib0,fib1);
while(count <= n )
{
fibn = fib0 + fib1 ;
/*
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
*/
if (ULLONG_MAX - fib1 < fib0) { puts("Overflow!"); break; }
printf("%3d :%25llu \n",count,fibn);
fib0 = fib1;
fib1 = fibn;
count++;
}
return ;
}
int main(void)
{
unsigned long temp = 0;
puts("Fibonacci Numbers");
fibonacci(100); /*Print the first 100 Fibonacci Numbers*/
return 0;
}
Relavant output is:
88 : 679891637638612258
89 : 1100087778366101931
90 : 1779979416004714189
91 : 2880067194370816120
92 : 4660046610375530309
93 : 7540113804746346429
94 : 12200160415121876738
Overflow!
santosh wrote:
Tarique wrote:
>This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
Why do you treat fib1 as long long when it is declared as unsigned long
long?
Overlooked that..changed it
>while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
How can 'fibn' be less than zero when it is an unsigned type? Also how
can it be greater than ULLONG_MAX?
Initially i was using a long long integer,but then changed it to
unsigned int.
Did not remove the fibn < 0 check.
Since i was getting -ve numbers as output(some of them..which was
obviously due to overflow),it seemed to be at least a temporary fix!
>
One method would be:
if (ULLONG_MAX - fib1 < fib0) { puts("Overflow."); break; }
>printf("%3d :%25llu \n",count,fibn);
Why the precision specifiers?
It's a little easier to actually add any two numbers in the output when
they are right aligned!
>
>fib0 = fib1;
fib1 = fibn;
count++;
}
return ;
}
int main(void)
{
unsigned long temp = 0;
puts("Fibonacci Numbers");
fibonacci(100); /*Print the first 100 Fibonacci Numbers*/
return 0;
}
This is a part of the output :
Fibonacci Numbers
...snip...
90 : 1779979416004714189
91 : 2880067194370816120
92 : 4660046610375530309
93 : 7540113804746346429
94 : 12200160415121876738
95 : 1293530146158671551
96 : 13493690561280548289
97 : 14787220707439219840
98 : 9834167195010216513
99 : 6174643828739884737
100 : 16008811023750101250
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Are you sure about the output?
Well yes.I did check the numbers prior to 90,the smaller ones are easier
to check...did some random checks with larger numbers.
The 95th one is obviously wrong! It is smaller than the 94th one.
Willem wrote:
Tarique wrote:
) <snip>
) unsigned long long fibn = 1; /*Nth Fibonacci Number*/
) <snip>
) if((fibn < 0) || (fibn ULLONG_MAX)){
This can never happen.
Some compilers would even warn about an if condition never being true,
or about unreachable code, or something similar.
Yes. The compiler did not warn.Lint did!
Tarique wrote:
santosh wrote:
>Tarique wrote:
>>This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
#include<stdio.h>
#include<limits.h>
void fibonacci(int n)
{
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
int count = 3; /*Hold Count*/
printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1);
Why do you treat fib1 as long long when it is declared as unsigned
long long?
Overlooked that..changed it
>>while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
How can 'fibn' be less than zero when it is an unsigned type? Also
how can it be greater than ULLONG_MAX?
Initially i was using a long long integer,but then changed it to
unsigned int.
Did not remove the fibn < 0 check.
Since i was getting -ve numbers as output(some of them..which was
obviously due to overflow),it seemed to be at least a temporary fix!
<snip>
Unsigned numbers cannot overflow in C. As for signed values, you must
check for possible overflow /before/ the suspect calculation. Once
overflow has occured the behaviour of your program is undefined.
Some compilers have an option to enable overflow detection. This might
be easier than doing so manually before every calculation.
Umm..I am combining two questions together.
These were the suggestions :
1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean
2. if (ULLONG_MAX - fib1 < fib0) from Santosh
Can you please explain the logic ?
"Tarique" <pe*****@yahoo.comwrote in message news:fo**********@aioe.org...
Umm..I am combining two questions together.
These were the suggestions :
1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean
2. if (ULLONG_MAX - fib1 < fib0) from Santosh
Can you please explain the logic ?
fibn is set to fib0 + fib1. So if fibn is less than either, some overflow
must have occurred. If greater than either, there cannot be overflow. This
holds true for any two positive integers represented by a fixed number of
bits.
Santosh is saying effectively the same thing. The overflow occurs if fib1 +
fib0 ULLONG_MAX. However we cannot sum fib0 and fib1, because that in
itself woyuld give overflow. So he rearranges the equation.
--
Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm
Tarique wrote:
) Umm..I am combining two questions together.
)
) These were the suggestions :
) 1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean
Actually, if(fibn < fib0) is enough.
If overflow occurs, then fibn will be like this:
fibn = (fib0 + fib1) - (ULLONG_MAX + 1)
You can algebraically rewrite this to:
fibn = fib0 - (ULLONG_MAX+1 - fib1)
Knowing that fib1 is smaller than ULLONG_MAX+1, you can deduce
that if overflow occurs, fibn < fib0.
Same holds for fibn < fib1, symmetrically.
) 2. if (ULLONG_MAX - fib1 < fib0) from Santosh
You really want to check: if ((fib0 + fib1) ULLONG_MAX)
But that will not work because of overflow.
If you rewrite it algebraically, you get the above comparison.
(Move fib1 to the right of the comparator.)
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Tarique wrote:
Umm..I am combining two questions together.
These were the suggestions :
1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean
2. if (ULLONG_MAX - fib1 < fib0) from Santosh
Can you please explain the logic ?
In addition to Malcolm's and Willem's explanations also note that method
one is used after the concerned calculation while method 2 can be used
before. But this doesn't matter for unsigned calculations.
santosh wrote:
Tarique wrote:
>Umm..I am combining two questions together.
These were the suggestions :
1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean
2. if (ULLONG_MAX - fib1 < fib0) from Santosh
Can you please explain the logic ?
In addition to Malcolm's and Willem's explanations also note that method
one is used after the concerned calculation while method 2 can be used
before. But this doesn't matter for unsigned calculations.
Thank You everyone.
"Tarique" <pe*****@yahoo.comwrote in message news:fo**********@aioe.org...
This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Apparently the C standard says that unsigned arithmetic does not overflow,
therefore the problem in your code is nothing to do with overflow. Even
though the problem in your code clearly *is* to do with overflowing the
range of your datatype.
In this case, I think you can test for overflow by making the sure each
successive fibonacci number is the previous number.
If you are particularly interesting in calculating big fibonaccis, try using
double datatype. These will be approximate.
--
Bart
Bartc said:
>
"Tarique" <pe*****@yahoo.comwrote in message
news:fo**********@aioe.org...
>This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
>Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Apparently the C standard says that unsigned arithmetic does not
overflow, therefore the problem in your code is nothing to do with
overflow.
Right. It is, instead, to do with the OP's apparent belief that standard
integer types are infinitely wide.
Even though the problem in your code clearly *is* to do with
overflowing the range of your datatype.
No, unsigned integer arithmetic doesn't overflow, any more than a clock
overflows at midnight.
>
In this case, I think you can test for overflow by making the sure each
successive fibonacci number is the previous number.
If you are particularly interesting in calculating big fibonaccis, try
using double datatype. These will be approximate.
Or use, or even write and then use, a bignum library.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Richard Heathfield wrote:
Bartc said:
>"Tarique" <pe*****@yahoo.comwrote in message
news:fo**********@aioe.org...
>>This program was compiled on MS Visual C++ 08
/*Fibonacci Numbers*/
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
Apparently the C standard says that unsigned arithmetic does not
overflow, therefore the problem in your code is nothing to do with
overflow.
It is, instead, to do with the OP's apparent belief that standard
integer types are infinitely wide.
I would like to differ here. If i believed that standard integer types
are infinitely wide,i would not have bothered to at least try to check
if bounds were transgressed.
The problem was that I was using (signed) long long integer instead,as I
have mentioned earlier in the thread.When i changed that to unsigned
type,i should have changed the *failure* condition.
>Even though the problem in your code clearly *is* to do with
overflowing the range of your datatype.
No, unsigned integer arithmetic doesn't overflow, any more than a clock
overflows at midnight.
I definitely learned it today!
Tarique wrote:
[...]
unsigned long long fib0 = 0; /*First Fibonacci Number*/
unsigned long long fib1 = 1; /*Second Fibonacci Number*/
unsigned long long fibn = 1; /*Nth Fibonacci Number*/
while(count <= n )
{
fibn = fib0 + fib1 ;
if((fibn < 0) || (fibn ULLONG_MAX)){
puts("\nOverflow\n");
break;
}
Why are the numbers after 95th Fibonacci numbers (including it) wrong?
[...]
Because you test for overflow after the overflow has occured.
Note that fibn is unsigned so (fibn < 0) can never be true, and
fibn is an unsigned long long so (fibn ULLONG_MAX) can never be
true,
so your test amounts to
if (0)
{
/* dead code */
}
Consider how your test differs from this
while(count <= n )
{
if(fib1 ULLONG_MAX - fib0)
{
puts("\nOverflow\n");
break;
}
fibn = fib0 + fib1 ;
where fib0 must be less than or equal to ULLONG_MAX (since
it is an unsigned long long), so
ULLONG_MAX - fib0 always has a defined value for which
the test against fib1 makes sense.
Remember that
fib1 ULLONG_MAX - fib0 (which can be true)
and
fib1 + fib0 ULLONG_MAX (which can never be true)
do not mean the same thing.
On Feb 8, 3:48*pm, "Malcolm McLean" <regniz...@btinternet.comwrote:
Here you need if(fibn < fib0 || fibn < fib1)
unsigned numbers wrap silently.
Actually, if you want to check an addition c = a + b for wrapping, you
only need to check _either_ (c < a) _or_ (c < b). You don't need to
check both. If one is true then the other must be true. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jatinder |
last post by:
I found these questions on a web site and wish to share with all of u
out there,Can SomeOne Solve these Porgramming puzzles.
Programming Puzzles
Some companies certainly ask for these...
|
by: Andy |
last post by:
Hi,
Are 1 through 4 defined behaviors in C?
unsigned short i;
unsigned long li; /* 32-bit wide */
1. i = 65535 + 3;
2. i = 1 - 3;
3. li = (unsigned long)0xFFFFFFFF + 3;
4. li = 1...
|
by: Neil Zanella |
last post by:
Hello,
Often I happen to be dealing with nonnegative integers and since I know I won't
need negative numbers here I declare them as unsigned simply to make the program
somewhat clearer....
|
by: TTroy |
last post by:
Hello, I'm relatively new to C and have gone through more than 4 books
on it. None mentioned anything about integral promotion, arithmetic
conversion, value preserving and unsigned preserving. ...
|
by: Mike Miller |
last post by:
What is the best way to convert a managed unsigned int64 to an
unsigned long? Basically I need to do the following:
System::UInt64 managedInt = 10;
unsigned long unmanagedInt;
unmanagedInt =...
|
by: jeff |
last post by:
unsigned long a = ...;
long b = (long)a;
while a overflows, what is the result of b?
Thank you.
|
by: linq936 |
last post by:
I have some algorithm dealing with unsigned int calculation a lot, I am
trying to add some check for overflow. The initial thinking was very
easy, just do something like this,
int...
|
by: John Harrison |
last post by:
I have a problem. I want to compare an integral value, n, against three
half open ranges as follows
[-A, 0) // range 1
[0, B) // range 2
[B, C} // range 3
Each range corresponds to a...
|
by: Keith Thompson |
last post by:
pereges <Broli00@gmail.comwrites:
These types already have perfectly good names already. Why give them
new ones?
If you must rename them for some reason, use typedefs, not macros.
--
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |
