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. For example, here's part of the output with doubles:

F[48] =             590436102659356800
F[49] =            1425438846754932220         ( 2 * 20 + 00 - 1 = 39)
F[50] =            3441313796169221100
F[51] =            8308066439093375000

Notice that F[49] ends in 20. The last 2 digits of F[50] should represent 20 * 2 + 00 (the last digits of F[48]) - 1. However, F[50]'s last 2 digits are 00. F[50] is incorrect. Not all digits are accurate starting with F[50]. Using doubles is not the solution.

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 both their values are -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.

Problem #4

• Solution provided by Naomi:

128         0x0080     0000 0000 1000 0000
-128        0xFF80     1111 1111 1000 0000
1024        0x0400     0000 0100 0000 0000
-1024       0xFC00     1111 1100 0000 0000
32767       0x7FFF     0111 1111 1111 1111
-32767      0x8001     1000 0000 0000 0001
-2          0xFFFE     1111 1111 1111 1110