CSC231 Homework 6 2015

--D. Thiebaut (talk) 10:46, 4 November 2015 (EST)

---

This homework is due on Wednesday 11/11/15, at 23:55 p.m.

Problem #1

Same problem as we did in class. Below is the mystery program. Its output is listed in the header of the program.

/* mystery.cpp
// D. T.
// mystery program
// To compile and run this program:
//
//     g++ mystery.cpp
//     ./a.out
//
// The output of the program is the following
//
// 2000000001
// -1294967294
//
// With what positive values were x and y initialized
// at the beginning of the program.  Explain why.
// An int contains 32 bits and is coded in 2's complement.
*/

#include <iostream>

using namespace std;

int main( int argc, char* argv[] ) {

    int x = ?????;
    int y = ?????;


    x = x+y;
    cout << x << endl;

    x = x+y;
    cout << x << endl;

    return 0;
}

What two positive numbers are stored in x and y to create the output listed in the header?

Explain your answer.

Problem #2

Assume that we want to compute the Fibonacci series with a compiled program written in a language that supports signed and unsigned ints, in 8-, 16-, 32-, and 64-bit length.

• How many terms can we correctly display if we use unsigned chars (8 bits) to store the Fibonacci terms?

• How many terms if we use unsigned short ints (16 bits)?

• How many terms if we use unsigned ints (32 bits)?

• How many terms if we use long unsigned ints of 64 bits?

• Repeat the same four questions for signed ints of 8, 16, 32, and 64-bit length.

Explain carefully how you derive your answers. Preferred answers are answers that contain a program (in the language of your choice) demonstrating/illustrating in one way or another the answers to the various questions.

Problem #3

class PowersOf2 {

    public static void main( String args[] ) {
        int x = 1;  

        while ( x != 0 ) { 
            System.out.println (  x ); 
            x = x * 2; 
        }
    }
}

• Why is the loop not an infinite loop?

• How many times does it go through? Why?

• What is the last number displayed by the loop? Why? Is it a valid power of 2?

• Assume now that we are interested in printing powers of 3, so we replace the multiplication line by "x = x * 3;" Is the loop infinite? Why or why not? If not infinite, what is the last number printed by the program?

Moodle Submission

• Submit your answers in 3 different pdf files in the HW 6 PB 1, PB 2, and PB 3 sections on Moodle.

<showafterdate after="20151112 00:00" before="20151231 00:00">

Solution Answers

Problem 1

Sabrina Sayasith
11/9/15
HW 6 PB 1
OUTPUT: x=x+y -->
x = 1000000000
y = 1000000001
x = x + y --> // -1294967294
// 2000000001

When the 32 bit signed integer’s positive value goes over
the largest positive value it can hold (in this case,
2,147,483,647), instead of going to
2,147,483,648...2,147,483,649...2,147,483,650 and so on like we
would in natural counting, it goes to -2,147,483,648
because of two’s complement’s form. Adding more positive
numbers causes our largest negative number to become more
positive/increase in value:
-2,147,483,648 --> -2,147,483,647 --> -2,147,483,646 ->... and
so on
We know in the second x = x + y, the starting value of x is
what we stored in x from the last operation. X =
2000000001. We know the second x = x + y is equivalent to
-1,294,967,294 = 2,000,000,001 + y.
2,147,483,647 - 2,000,000,001 = 147,483,646 //the number
needed to be added to 2,000,000,001 to reach the positive
cap.
2,147,483,648 – 1,294,967,294 = 852,516,354 //the positive
number that needs to be added to the largest negative
number to get to -1,294,967,294.
Y = 147,483,646 + 852,516,354 + 1(the +1 it takes to switch from positive to negative) = 1000000001
Then we can figure out x from the first x = x + y.
2000000001 = x + 1000000001 x = 1000000000

Problem 2

Sabrina Sayasith HW 6 PB 2 Fibonacci Numbers
F0 = 0, F1 = 1, F2 = 1, F3 = 2....
How many terms can we correctly display if we use unsigned chars (8 bits) to store the Fibonacci terms?
 Unsigned chars (8 bits) gives us a maximum value of 1111 1111 in binary or 255 in decimal. We have a range of 0 to 255 to work with. Fibonacci number 13 is 233. Fibonacci number 14 is
377, which is over our range of 255. So the highest Fibonacci term we can correctly display is Fibonacci term 13. We can correctly display 13 Fibonacci terms starting from Fibonacci term 1. We can correctly display 14 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use unsigned short ints (16 bits)?
 Unsigned short ints (16 bits) gives us a maximum value of 1111 1111 1111 1111 in binary or 65,535 in decimal. We have a range of 0 to 65,535 that can be held in a short int. Fibonacci term 24 is 46,368, and Fibonacci term 25 is 75,025. Fibonacci term 25 is the first term greater than the maximum value we can hold in our short int. The highest Fibonacci term we can hold is therefore 24. We can correctly display 24 Fibonacci terms starting from Fibonacci term 1. We can correctly display 25 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use unsigned ints (32 bits)?
 Unsigned ints (32 bits) gives us a maximum value of 1111 1111 1111 1111 1111 1111 1111 1111 in binary or 4,294,967,295 in decimal. Fibonacci term 47 is 2,971,215,073. Fibonacci term 48 is 4,807,526,976. Fibonacci term 48 is the first term larger than our maximum storable
value in an unsigned 32 bit int, so Fibonacci term 47 is the greatest we can store. We can correctly display 47 Fibonacci terms starting from Fibonacci term 1. We can correctly display 48 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use long unsigned ints of 64 bits?
 Unsigned ints (64 bits) gives us a maximum value of 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 in binary or 18,446,744,073,709,551,615 in decimal. Fibonacci term 93 is 12,200,160,415,121,876,738. Fibonacci term 94 is 19,740,274,219,868,223,167. Fibonacci term 94 is the first term larger than our maximum
storable value in an unsigned 64 bit int, so Fibonacci term 93 is the greatest we can store. We can correctly display 93 Fibonacci terms starting from Fibonacci term 1. We can correctly display 94 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use signed ints of 8-bit length?
 Signed ints (8 bits) gives us a maximum value of 0111 1111 in binary or 127 in decimal. Fibonacci term 11 is 89. Fibonacci term 12 is 144. Fibonacci term 12 is the first term larger than our maximum storable value in a signed int of 8-bit length, so Fibonacci term 11 is the greatest we can correctly store. We can correctly display 11 Fibonacci terms starting from Fibonacci term 1. We can correctly display 12 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use signed ints of 16-bit length?
 Signed ints (16 bits) gives us a maximum value of 0111 1111 1111 1111 in binary or 32,767 in decimal. Fibonacci number 23 is 28,657. Fibonacci term 24 is 46,368. Fibonacci term 24 is the first term larger than our maximum storable value in a signed int of 16-bit length, so Fibonacci term 23 is the greatest we can correctly store. We can correctly display 23 Fibonacci terms starting from Fibonacci term 1. We can correctly display 24 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use signed ints of 32-bit length?
 Signed ints (32 bits) gives us a maximum value of 0111 1111 1111 1111 1111 1111 1111 1111
in binary or 2,147,483,647 in decimal. Fibonacci term 46 is 1,836,311,903. Fibonacci term 47 is 2,971,215,073. Fibonacci term 47 is the first term larger than our maximum storable value in a signed int of 32-bit length, so Fibonacci term 46 is the greatest we can correctly store. We can correctly display 46 Fibonacci terms starting from Fibonacci term 1. We can correctly display 47 Fibonacci terms starting from Fibonacci term 0.
How many terms if we use signed ints of 64-bit length?
 Signed ints (64 bits) gives us a maximum value of 0111 1111 1111 1111 1111 1111 1111 1111
1111 1111 1111 1111 1111 1111 1111 1111 in binary or 9,223,372,036,854,775,807 in decimal. Fibonacci term 92 is 7,540,113,804,746,346,429. Fibonacci term 93 is 12,200,160,415,121,876,738. Fibonacci term 93 is the first term larger than our maximum storable value in a signed int of 64-bit length, so Fibonacci term 92 is the greatest we can correctly store. We can correctly display 92 Fibonacci terms starting from Fibonacci term 1. We can correctly display 43 Fibonacci terms starting from Fibonacci term 0.


==Problem 3

Sabrina Sayasith
HW 6 PB 3
class PowersOf2 {
public static void main( String args[] ) {
int x = 1;
while ( x != 0 ) { System.out.println ( x ); x = x * 2;
} }
}
 Why is the loop not an infinite loop?
An int in java is a 32 bit signed integer. The range of values that it can hold is -2,147,483,648 to 2,147,483,647 based on 2’s complement. Starting off at 0000 0000....0001, each time we multiply by 2 the one gets shifted one spot to the left: 0000 0000... 0000 0010, 0000 0000 .... 0000 0100, 0000 0000 ... 0000 1000, and so on until we reach 1000 0000 ... 0000 0000. At this point, the 1 is all the way at the leftmost bit and when it is shifted left there is no spot to hold it. When the value 1000 0000...0000 0000 is multiplied by 2, the value becomes 0000 0000....0000 0000, and the one is no longer a part of our 32 bits. So we effectively get the value 0, and the loop stops when the value equals 0.
 How many times does it go through? Why?
 What is the last number displayed by the loop? Why? Is it a valid power of 2?
It loops 32 times. The value stars at 0000....0001, and the one shifts over 31 spots through looping until we get the value 1000...0000. Then, it loops one last time for the value to become 0000...0000. So it loops 31+1 times.
The last number displayed is -2,147,483,648 represented by 1000...0000 in binary. If we were to not consider 2’s compliment, the number would be 2^(31) or 1000...0000. 2’s complement
represents it as a negative number even though technically it is not.
 Assume now that we are interested in printing powers of 3, so we replace the multiplication line by "x = x * 3;" Is the loop infinite? Why or why not? If not infinite, what is the last number printed by the program?
The loop is infinite. X never equals 0. The rightmost bit of our 32 bits never equals 0 because powers of 3 are always odd numbers, so we’ll always have the 2^(0) bit with a value of 1 filled to +1 to any even number to get it odd.

</showafterdate>