CSC231 Homework 5 Solutions

--D. Thiebaut 12:50, 14 October 2012 (EDT)

---

Problem #1

• Solution provided this week by Trevor and Sam:

Trevor Haba  and  Sam Goodspeed
231a-ao		  231a-am

Problem 1

53: 20057446674355970889
54: 48422959787805316581
55: 116903366249966604050
56: 282229692287738524680
57: 681362750825443653409
58: 1644955193938625831497
59: 3971273138702695316402
60: 9587501471344016464300

Our java code:

package hw5;

//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
//

import java.math.BigInteger;

class Hw5a {
    public static void main(String[] args ) {
	BigInteger Fn, Fn_1, Fn_2;
	int count;
	
	BigInteger b2 = new BigInteger("2");
	
	Fn_1 = BigInteger.ONE;
	Fn_2 = Fn_1;
	System.out.println( "F[1] = 1" );
	System.out.println( "F[2] = 1" );
 
	count = 2;
	while ( true ) {
	    Fn = Fn_1.multiply(b2).add(Fn_2).subtract(BigInteger.ONE);
	    Fn_2 = Fn_1;
	    Fn_1 = Fn;
	    count++;
	    if ( count >= 53 )
	    	System.out.println(count + ": " + Fn);
	    if (count > 60 )
	    	break;
	}
    }
 
}

• Indeed one of the tricks was to use the BigInteger class of the Java Math library, if you were a java programmer. Using doubles was not adequate, as it only gives approximations of the numbers, not their exact values. Excel suffers from the same problem as it will use doubles which do not contain a sufficient number of bits to represent the numbers exactly.

Problem 2

• Solution provided by Julia.

a.) 0xFFFE

This starts with an F, so it represents a negative value. Therefore, we flip all the nibbles:

     0 = F flipped
     1 = E flipped

     = 0001

     and add 1...

     = 0002

     and convert (don't forget the sign...)

     = -2

b.) 0x1000

    This begins with a 1, so we know it's positive. Therefore...

    (1 * 16^3) + (0 * 16^2) + (0 * 16) + (0) = 4096

c.) 0x00FF

    This begins with a 0, so we know it's positive. Therefore...

    (0 * 16^3) + (0 * 16^2)  + (15 * 16) + (15) = 255

d.) 0x7FFF

    This begins	with a 7, so we	know it's positive. Therefore...

    (7 *  16^3) + (15 * 16^2)  + (15 * 16) + (15) = 32767

e.) 0x000F

    This begins	with a 0, so we	know it's positive. Therefore...

    (0 *  16^3) + (0 * 16^2)  + (0 * 16) + (15) = 15

f.) 0x1111

    This begins	with a 1, so we	know it's positive. Therefore...

    (1 *  16^3) + (1 * 16^2)  + (1 * 16) + (1) = 4369

Problem #3

• Solution provided by Julia

A.) In 2's complement, -1 will be all 1's (or all F's in hex) regardless of the number of bits because the highest order bit 
is the only bit with a negative value. For all positive numbers, the value of this bit is always 0, and for all negative 
numbers, it's 1. Furthermore, this bit always represents -2^(n-1), where n is the number of bits in the format.

All of the other bits have positive values, which, when added to the negative value, make the negative number larger 
(or bring it closer to zero). This is an important thing we need to recognize about 2's complement: the more 1's there 
are in a negative number (especially in higher-order places), the closer the number will be to 0.

This shows us why -1 is always all 1's. The highest-order bit equals -2^n-1, but all of the smaller bits together equal 
+((2^n-1) - 1) since (2^n-2)+(2^n-3)+(2^n-4)+...+(2^0) = (2^n-1)- 1. Therefore, no matter how many bits there 
are, a number that is all 1's in binary = -(2^n-1) + (2^n-1) - 1, or -1. We also could have inferred this from paragraph 
2, because -1 is the closest negative integer to 0.

• DT's addition

Another way to look at it. Let's first describe -1 as coded in 8 bits:

 -1 = 0xFF = 1111 1111 = -2^7 + 2^6 + 2^5 + 2^4 +2^3 +2^2 +2^1 +2^0                 (Eq. 1)

Let's now look at -1 as coded in 16 bits

 -1 = 0xFF = 1111 1111 1111 1111 = -2^15 + 2^14 + ... + 2^8 + 2^7 + 2^6 + 2^5 + 2^4 +2^3 +2^2 +2^1 +2^0  (Eq. 2)

If we subtract the first expression from the second, and if we assume we are right in assuming that their values are both -1, we get:

 -1 - (-1) = -2^15 + 2^14 + 2^13 + ... + 2^8 + 2^7 - ( -2^7 )     (Eq. 3)

and all the other terms cancel out (the 2^6 and lower terms).

The last three terms of Eq. 8 are 2^8 + 2 * ( 2^7 ) = 2^8 + 2^8 = 2^9

So Eq 8 simplifies to

  -1 - (-1) = -2^15 + 2^14 + 2^13 + 2^12 + 2^11 + 2^10 + 2^9 + 2^9           (Eq. 4)

Similarly, the last 3 terms of Eq. 4 simplify to 2^10 + 2^10 = 2^11. Continuing this way backward toward the front of the equation, we get

  -1 - (-1) = 0 =  -2^15 + 2^15           (Eq.5)

which is always true. This is why -1 can be written as a series of 1's in any length 2's complement word.