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.