CSC231 Homework 5 2012

--D. Thiebaut 09:40, 3 October 2012 (EDT)

---

This assignment is due the evening of 10/10/12, at midnight. Problems 2, 3, and 4 should be done by hand as much as possible. For once I'd like you to break my rule of "let's be lazy and let the computer do the work" and instead try to do as much of the work by hand without writing a program or using an app to do the work. If you work on these puzzles by hand, their solutionwill remain with you and you will retain this important material much longer. :-)

Problem #1

Assume that we want to print the first 60 terms of the series of Homework 4 using a Java program. We are aware of limitations due to the range of integers, so we use the long data type to represent the terms of the series.

Here's our first shot at this program (sorry, undocumented... just a first rough version ;-):

// Hw5a.java
// Prints first terms of recursive series:
// F[1] = 1, F[2] = 1, F[n] = 2 * F[n-1] + F[n-2] - 1
// Stops when negative value comes up...
// To compile and run:
//    javac Hw5a.java
//    java Hw5a
//
class Hw5a {
    public static void main(String[] args ) {
	long Fn, Fn_1, Fn_2;
	int count;
	Fn_1 = 1;
	Fn_2 = 1;
	System.out.println( "F[1] = 1" );
	System.out.println( "F[2] = 1" );

	count = 2;
	while ( true ) {
	    Fn = 2 * Fn_1 + Fn_2 - 1;
	    Fn_2 = Fn_1;
	    Fn_1 = Fn;
	    System.out.println( "F[" + count + "] = " + Fn );
	    count++;
	    if ( Fn <= 0 )
		break;
	}
    }

}

You can create this program and run it. You will observe that its last output is:

   F[53] = -6917272433323338267

Your Assignment

• Find a way to generate the exact (i.e. all the digits), unsigned values in decimal of the last 7 terms of the series of 60 terms. In other words find a way to generate the exact unsigned values of F[53] to F[60].
• Your answer should list these values, and explain how you obtain them.

Grading

• Extra credits if your answer is a program written in a non interpreted language...
• Lower credits (up to B only) for solutions done by hand... (After all, we are programmers, and we don't want to do work a computer can do for us!)

Problem #2

What is the decimal equivalent of the following 16-bit 2's complement integers shown here in hexadecimal? These are sometimes referred to as short ints in some languages.

• 0xFFFE

• 0x1000

• 0x00FF

• 0x7FFF

• 0x000F

• 0x1111

Problem #3

Here's something interesting about all negative numbers that is best illustrated with -1.

In 2's complement, the binary representation of -1 is 11111...111. It does not matter how many bits are used in the integer format you pick, -1 is all 1s. For example, in 8-bit bytes, -1 is 11111111. In 16-bit words, -1 is 1111 1111 1111 1111. In 32-bit words, -1 is 1111 1111 1111 1111 1111 1111 1111 1111. Explain why.

Problem #4

What are the binary and hexadecimal representations of these 2's complement numbers? Assume they are defined as 16-bit words: Please refrain from using a calculator! (The list of powers of 2 shown below might be useful for this problem.)

• 128

• -128

• 1024

• -1024

• 32767

• -32767

• -2

Powers of 2

2^0 =  1
2^1 =  2
2^2 =  4
2^3 =  8
2^4 =  16
2^5 =  32
2^6 =  64
2^7 =  128
2^8 =  256
2^9 =  512
2^10 =  1,024
2^11 =  2,048
2^12 =  4,096
2^13 =  8,192
2^14 =  16,384
2^15 =  32,768
2^16 =  65,536
2^17 =  131,072
2^18 =  262,144
2^19 =  524,288
2^20 =  1,048,576

Submission

• Write your answers for all the problems above in one single text file called hw5.txt and submit it as follows:

  rsubmit hw5 hw5.txt

• If you wrote a program for Problem #1, include the listing of your program in the text file as well.