Section 11/9/99
For homework #3,
1. No need to write out any functions. You should be able to do the assignment with just a for loop.
2. No need to worry about lengths <= 1
Why am I having errors on inputs larger than 45?
Remember that with 2 bits, the largest number we can represent is (2^2)-1 = 3
With 3 bits, the largest number we can represent is (2^3)-1 = 7.
In visual C++, int’s are 4 bytes. Each byte is 8 bits, and so each int is 4*8 = 32 bits.
The last leftmost 31st bit is used to determine the sign of the int.
The formula for determining the base ten value of a signed integer is as follows (xi means the ith bit of x:
(x31 * -231) + (x30 * 230) + (x29 * 229) + ... + (x1 * 21) + (x0 * 20)
For example.
1111 1111 1111 1111 1111 1111 1111 1100two
is –4ten.
So really there are only 31 bits that we can use to specify integers and the greatest positive integer we can represent is 2^31-1 = 2,147,483,647
So given an input of 46 in your Fibonacci, your output might be
.
.
.
701408733
1134903170
1836311903
-1323752223
The last number should be 2971215073 instead of -1323752223.
However, since this 2971215073 greater than (2^31)-1 (= 2147483647), it’s bit representation (1...blah, blah) is interpreted as a negative number instead.
So if we assume that the Fibonacci sum is always nonnegative, the 31st sign bit is kind of a waste. In order to used that 31st bit, we can change our int type, which is signed by default, to an unsigned int type. In addition to changing
int var;
to
unsigned int var;
we need to change our printf that originally printed a signed integer to print out an unsigned integer. We do this by changing the %d in:
printf “(%d\n”, var);
to
printf (“%u\n”, var);
to %u.
Now, if we enter the length as 46, the last few lines of the output will be:
.
.
.
701408733
1134903170
1836311903
2971215073
Of course, we still have a bound on the integers that we can represent but the upper bound for unsigned int’s ((2^32)-1) is higher than that of the signed int ((2^31)-1).
Notice that the next number in the Fibonacci sequence (4807526976) is greater that (2^32-1). So using unsigned int’s wasn’t much help.
Make sure your inputs work on everything less than or equal to 45.
scanf
You may be wondering what the following lines do:
printf ("Enter length: ");
scanf ("%d", &length);
Scanf reads from standard input, which is the console in our case, and return the values to the caller (e.g. the function that invoked the scanf). In order to read from standard input into an int we do two things.
Firstly, we specify that the data from standard input will be converted into an int by using the %d sign.
Secondly, we specify the address (denoted by the ‘&’ character in front of the variable length) in memory to which data will be written.
Why do we specify the address of length instead of just the length itself?
The reason is that we want scanf to modify the value held by length variable, and this can only be done using length’s address.
For example, suppose I want to deliver a couch to Bob’s house. In order to do so, I need to know the address of Bob’s house. Knowing the previous contents of Bob’s house is irrelevant. For example, knowing that Bob had a TV or an aquarium previously in his house won’t be much help for getting that couch to his house. What I need is the address of Bob’s house to be able to deliver that couch to its correct location.
Analogously, we need to know the address of the length variable in order to change its contents. The actual value residing in the length variable is irrelevant.