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

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