===========================================
Assignment #03 - Data Representations
===========================================
- Ian! D. Allen - idallen@idallen.ca - www.idallen.com
Available online: Thursday January 20, 2011
Upload due date:
Upload answer file before 23:59 (midnight) on Thursday January 27, 2011
Answers will be posted shortly after the due date/time and discussed
in class, if there are any questions about the answers.
Late assignments may or may not be marked.
Submission method:
Create a plain text file using the exact name "assignment03.txt"
Upload the file via the Assignment03 "Upload File" facility in Blackboard.
Use "Attach File" and "Submit" to upload your plain text file.
No wordprocessor documents. Do not send email. Use only "Attach File".
Use the file name given above. Upload only one single file of plain text,
not HTML, not MSWord. No fonts, no word-processing. Plain text only.
Did I mention that the format is plain text (VIM/Nano/Pico/Gedit or Notepad)?
NO WORD PROCESSOR DOCUMENTS ACCEPTED.
No marks are awarded for submitting under the wrong assignment number.
Not all assignments will be marked. See the Week 1 Notes for details.
Answers will be posted after the due date/time so that you can check
your answers before coming to class and ask questions about the answers
in class. Please check your answers (and my answers!). I go over
each assignment in class if there are questions about the answers.
No questions means no review - I'll presume you know the material.
Questions similar to ones on these assignments will appear on your tests
and exams.
DO THIS:
Edit this file and answer the following questions underneath each
question, showing the method or formula you used to get the answer.
Many of the questions already give you the answer - you must show
the full method you use to generate that answer. Upload the file
containing the question, methods, formulas, and answers before the
due date. Some of the answers below will require reading the links
published in the weekly course notes.
Full marks are awarded only if you show your method.
==============================================================================
1. Write down all the powers of two from zero ("1") to 16 ("65,536")
showing their decimal values. Memorizing these powers of two will
serve you well in Computer Science:
1 = 2**0
2 = 2**1
4 = 2**2
8 = 2**3
16 = 2**4
32 = 2**5
64 = 2**6
128 = 2**7
256 = 2**8
512 = 2**9
1024 = 2**10
2048 = 2**11 = 2**1 * 2**10
4096 = 2**12 = 2**2 * 2**10
8192 = 2**13 = 2**3 * 2**10
16384 = 2**14 = 2**4 * 2**10
32768 = 2**15 = 2**5 * 2**10
65536 = 2**16 = 2**6 * 2**10
2. Write down all the negative powers of two from -1 ("0.5") to -4 ("0.0625")
showing their decimal and fractional (reciprocal) values:
0.5 = 2**-1 = 1 / 2**1 = 1/2
0.25 = 2**-2 = 1 / 2**2 = 1/4
0.125 = 2**-3 = 1 / 2**3 = 1/8
0.0625 = 2**-4 = 1 / 2**4 = 1/16
3. Write down all the powers of 16 from zero ("1") to 4 ("65,536")
and relate each power of 16 to the corresponding power of two.
1 = 16**0 = (2**4)**0 = 2**0
16 = 16**1 = (2**4)**1 = 2**4
256 = 16**2 = (2**4)**2 = 2**8
4096 = 16**3 = (2**4)**3 = 2**12
65536 = 16**4 = (2**4)**4 = 2**16
4. Using a word size of four bits, list in order vertically all of the
possible bit patterns from 0000(2) to 1111(2). Beside each of the 16
patterns, give:
a) the hexadecimal equivalent of the bit pattern
b) the unsigned decimal value of the bit pattern
c) the four-bit signed-magnitude decimal value of the bit pattern
d) the four-bit one's complement decimal value of the bit pattern
e) the four-bit two's complement decimal value of the bit pattern
You will create a small text table with 16 rows and five columns.
Class Notes Reference: 060_different_binary_integers.html
BINARY |HEX |DEC |S/M |1's |2's
0000 0 0 0 0 0
0001 1 1 1 1 1
0010 2 2 2 2 2
0011 3 3 3 3 3
0100 4 4 4 4 4
0101 5 5 5 5 5
0110 6 6 6 6 6
0111 7 7 7 7 7
1000 8 8 -0 -7 -8
1001 9 9 -1 -6 -7
1010 A 10 -2 -5 -6
1011 B 11 -3 -4 -5
1100 C 12 -4 -3 -4
1101 D 13 -5 -2 -3
1110 E 14 -6 -1 -2
1111 F 15 -7 -0 -1
5. Why do computer programmers always start counting with zero (0), and
not with one (1)?
Arrays start at zero. The first element of an array is element zero.
6. The prefix used for a thousand Kilobytes is Megabytes.
What is the prefix used for a thousand Gigabytes?
Tera: GB * 1000 = TB (terabyte) = 10**12 (e.g. disk)
If "thousand" is KiB, then GiB * KiB = TiB (tebibyte) = 2**40 (e.g. memory)
7. The prefix used for a thousand Kilobytes is Megabytes.
What is the prefix used for a thousand Terabytes?
Peta: TB * 1000 = PB (petabyte) = 10**15 (e.g. disk)
If "thousand" is KiB, then TiB * KiB = PiB (pebibyte) = 2**50 (e.g. memory)
8. What is the difference between writing KB (kilobyte) and KiB (kibibyte)
and MB (megabyte) and MiB (mebibyte)?
a. KB (Kilobyte) = 1000 bytes = 10**3 bytes
b. KiB (Kibibyte) = 1024 bytes = 2**10 bytes
c. MB (megabyte) = 1000*1000 bytes = 1,000,000 bytes = 10**6 bytes
d. MiB(mebibyte) = 1024*1024 bytes = 1,048,576 bytes = 2**20 bytes
9. What is the closest power of two to 1000 (i.e. closest to 10**3)?
1 K = 1000 (power of ten) = 10**3
1 Ki = 1024 (power of two) = 2**10
10. How many ns (nanoseconds) are in a ms (millisecond)?
1 ns = 1 * 10**(-9)
1 ms = 1 * 10**(-3)
1 ms / 1 ns = 10**(-3) / 10**(-9) = 10**6 = 1,000,000 = a million
11. How many KiB are in a GiB?
1 Ki = 2**10
1 Gi = 2**30
1 Gi / 1 Ki = 2**30 / 2**10 = 2**20 = 1,048,576 = Mi (power of two)
12. How many MiB are in a GiB? Give the answer as a power of two.
1 Mi = 2**20
1 Gi = 2**30
1 Gi / 1 Mi = 2**30 / 2**20 = 2**10 = 1024 = Ki (power of two)
13. Which of these measurements are powers of two, and which are powers of ten?
a) Distances in kilometres?
b) amount of hard disk capacity?
c) amount of CDROM capacity?
d) computer memory size?
e) processor speed (clock frequency)?
f) processor bus speed (e.g. PCI bus or front side bus or memory bus)?
g) network card speed?
h) dial-up modem speed?
i) ADSL modem speed?
j) Size of a file on your hard disk?
Computer memory is always powers-of-two.
File size may be either, depending on the program that displays size.
All the rest are powers-of-ten.
14. Give two reasons why you can't store 8GB of system memory in a file
on a hard drive with an advertised capacity of 8GB.
1. 8 GB of system memory is measured in powers-of-two GiB that is
larger than powers-of-ten 8 GB of hard drive storage, i.e.
8 GiB = 8,589,934,592 bytes and 8 GB = 8,000,000,000 bytes.
2. The operating system needs to store name and directory information on
the disk, as well as the data. That extra overhead takes space, so
not all 8GB of the disk space are available for data.
15. What is 2**16 in decimal?
65,536, a famous number in computer science
16. A computer has a 32-bit word size. Using this word size, what is the
largest size memory it can address, in GiBi? (Microsoft Windows XP
computers are limited to using this much memory.)
How many items can 32 bits count? 2**32
2**32 = 2**2 * 2**30 = 4 GiB
17. By what order of magnitude (power of 10) is something that runs in
nanoseconds (e.g. a CPU memory access) faster than something that
runs in milliseconds (e.g. a hard disk access)?
millisec / nanosec = 10**(-3) / 10**(-9) = 10**6 = six orders of magnitude
(An "order of magnitude" is a power of ten; the answer is "six orders".)
18. Refer to the above answer. You have a program that takes 8 minutes
to finish, running entirely in the computer's memory. With a bigger
data set, you need to change the program to access the hard disk
instead of memory. You change the program so that *all* accesses
are via the slower hard disk. Roughly how long (in years) will it
now take your "8-minute" program to finish?
Computer memory is approximately a million (10**6) times faster than disk.
The new program will be a million times SLOWER; it will run a million
times LONGER. How long is eight minutes times a million?
(8 minutes)*(million)/(minutes in a year) =
= (8)*(10**6)/(60*24*365) = about 15.2 years to finish!
19. Exactly how many bytes (in decimal) are in 4GiB of memory?
4 GiB = 4 * 2**30 [a GiB is a power of two, not a power of ten]
= 2**2 * 2**30
= 2**32 [add exponents]
= 4,294,967,296 bytes
20. Exactly how many bytes (in decimal) are on an advertised 4GB hard disk?
4 GB = 4 * 10**9 = 4 * 1000 * 1000 * 1000 = 4,000,000,000 bytes
21. How many power-of-two TiB are on an advertised 1.5TB hard disk?
TiB = 2**40 [power of two]
1.5 TB = 1.5 * 10**12 [power of ten]
1.5*(10**12)/(2**40) = 1.364 TiB (not 1.5 TiB!)
22. By what percentage is a power-of-two GiB larger than a power-of-ten GB?
GiB = 2**30 = 1,073,741,824
GB = 10**9 = 1,000,000,000
GiB/GB = 1.073741824, so about 7.4% bigger
23. By what percentage is a power-of-two TiB larger than a power-of-ten TB?
TiB = 2**40 = 1,099,511,627,776
TB = 10**12 = 1,000,000,000,000
TiB/TB = 1.099511627776, so about 9.95% bigger
24. Which has more space, a 2 TB disk or a 1.8 TiB disk?
2TB = 2 * 10**12 = 2000000000000
1.8TiB = 1.8 * 2**40 = 1979120929996.8 <- a little bit smaller
25. How many power-of-two MiB are on an advertised 2TB hard disk?
How many power-of-two GiB are on an advertised 2TB hard disk?
How many power-of-two TiB are on an advertised 2TB hard disk?
2TB disk = 2,000,000,000,000 = 2*(10**12) bytes
1 MiB = KiB * Kib = 2**10 * 2**10 = 2**20 bytes
2*(10**12)/(2**20) = 1,907,348.633 MiB
2TB disk = 2,000,000,000,000 = 2*(10**12) bytes
1 GiB = KiB * KiB * KiB = 2**30 bytes
2*(10**12)/(2**30) = 1,862.645 GiB
2TB disk = 2,000,000,000,000 = 2*(10**12) bytes
1 TiB = 2**40 bytes
2*(10**12)/(2**40) = 1.8189894 TiB
= 1.82 TiB (your computer may show this size number)
26. What are the largest and smallest integers (in decimal) an 8-bit word
can hold using a sign-magnitude representation?
Half the of the 2**8 bit patterns are negative; half are positive.
2**8 divided by two is 2**7. We start from zero, therefore:
+ (2**7 - 1) = +127 (128 numbers from +0 -> +127)
- (2**7 - 1) = -127 (128 numbers from -0 -> -127)
The top bit is the sign bit, leaving 7 bits for the magnitude.
27. What are the largest and smallest integers (in decimal) an 8-bit word
can hold using a one's complement representation?
Half the of the 2**8 bit patterns are negative; half are positive.
2**8 divided by two is 2**7. We start from zero, therefore:
+ (2**7 - 1) = +127 (128 numbers from +0 -> +127)
- (2**7 - 1) = -127 (128 numbers from -0 -> -127)
28. What are the largest and smallest integers (in decimal) an 8-bit word
can hold using a two's complement representation?
Due to the "flip bits and add one", there is no "minus zero".
+ (2**7 - 1) = +127 (128 numbers from +0 -> +127)
- (2**7) = -128 (128 numbers from -1 -> -128 -- we start at -1 not -0)
29. What are the largest and smallest integers a 16-bit word can hold
using a sign-magnitude representation?
Half the of the 2**16 bit patterns are negative; half are positive.
2**16 divided by two is 2**15. We start from zero, therefore:
+ (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767)
- (2**15 - 1) = -32,767 (32,768 numbers from -0 -> -32,767)
The top bit is the sign bit, leaving 15 bits for the magnitude.
30. What are the largest and smallest integers a 16-bit word can hold
using a one's complement representation?
Half the of the 2**16 bit patterns are negative; half are positive.
2**16 divided by two is 2**15. We start from zero, therefore:
+ (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767)
- (2**15 - 1) = -32,767 (32,768 numbers from -0 -> -32,767)
31. What are the largest and smallest integers a 16-bit word can hold
using a two's complement representation?
Due to the "flip bits and add one", there is no "minus zero".
+ (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767)
- (2**15) = -32,768 (32,768 numbers from -1 -> -32,768 -- start at -1)
32. Generalize: For an N-bit word size, express as a formula using N as a
power of two (i.e. using 2**N) what are the largest (most positive)
and smallest (least positive) integers possible for:
a) N-bit unsigned
b) N-bit one's complement
c) N-bit signed-magnitude
d) N-bit two's complement
Your formulas should produce the answers you gave in the above
questions, e.g. your formula should output "+1023" for N=10 unsigned.
a) N-bit unsigned
Largest = (2**N) - 1
Smallest = 0
b) N-bit one's complement
Largest = + ( (2**(N-1)) - 1 )
Smallest = - ( (2**(N-1)) - 1 )
c) N-bit signed-magnitude
Largest = + ( (2**(N-1)) - 1 )
Smallest = - ( (2**(N-1)) - 1 )
d) N-bit two's complement
Largest = + ( (2**(N-1)) - 1 )
Smallest = - ( (2**(N-1)) )
33. What is the minimum number of binary bits needed to represent 187 items?
Knowing your powers-of-two table makes this a quick answer.
2**7 = 128 items - TOO SMALL
2**8 = 256 items - BIG ENOUGH
Therefore we need 8 bits which can hold 0 to 255 (unsigned)
34. What is the minimum number of binary bits needed to represent 31,386 items?
Knowing your powers-of-two table makes this a quick answer.
2**14 = 16,384 items (a number to remember) - TOO SMALL
2**15 = 32,768 items (a number to remember) - BIG ENOUGH
Therefore we need 15 bits which can hold 0 to 32,767 (unsigned)
35. What is the minimum number of binary bits needed to represent the number
of days in a week?
Need to represent seven items: 1 through 7 or 0 through 6.
Seven items can be counted with a minimum of three bits.
(Three bits can count 2**3 things.)
36. What is the minimum number of binary bits needed to represent the
number of each day in the year, if the number of days in the year can
be used positive or negative (e.g. "minus 300 days" or "today - 300")?
Knowing your powers-of-two table makes this a quick answer.
Need to represent -366 through +366. Using two's complement (and the
formula above), we choose 10 bits with range:
-(2**9) to +((2**9)-1) or -512 to +511
37. Develop a binary encoding scheme which could be used to encode a field to
represent one of the weeks of the year. Use the minimum number of bits.
Knowing your powers-of-two table makes this a quick answer.
52 weeks in a year.
2**5 = 32 - TOO SMALL
2**6 = 64 - BIG ENOUGH
Therefore we need 6 bits which can hold 0 to 63 (unsigned)
38. How many different numbers can be represented in 15 bits?
2**15 = 32,768 different numbers
39. What is the largest unsigned positive number that can be represented
in 15 bits?
2**15 - 1 = 32,767 (because zero is one of the numbers)
40. What is the largest unsigned positive number that can be represented
in one nybble?
One nybble = half a byte = 4 bits
4 bits can count 2**4 = 16 things.
For unsigned numbers, the range is 0 to 15
Answer: 2**4 - 1 = 15(10)
41. Unix/Linux has traditionally used a 32-bit signed integer to
store the number of seconds since midnight on January 1, 1970, UTC.
Calculate roughly in what year/month/day this value overflows and
time starts going negative. (Modern Unix systems use 64 bit time.)
32 bits signed means the max positive seconds is +((2**31)-1) or
2,147,483,647 seconds.
A year is about 365.25 days or 31,557,600 seconds.
2,147,483,647 / 31,557,600 = 68.049650385 years.
year 1970 + 68 = year 2038
The remainder 0.049650385 years is about 18.134803121 days.
January 1 + 18 = January 19 (2038)
A Wikipedia search confirms the actual date as 03:14:07 UTC on Tuesday,
19 January 2038: http://en.wikipedia.org/wiki/Year_2038_problem
42. Convert the following binary to hexadecimal. Hint:
Your answer will have eight hex digits, all different:
1011000010010110010111101110110(2)
= 0101 1000 0100 1011 0010 1111 0111 0110 (group binary from right)
5 8 4 B 2 F 7 6 (hex)
= 584B2F76(16)
43. Express floating-point 123.654 as a normalized decimal number using
scientific notation with four significant digits of precision.
Normalized: 1.23654 x 10**2
Four digits: 1.236 x 10**2 (or 1.237 with rounding)
In program code (Java) write this as 1.236e2 (1.236 times 10**2)
44. Add floating-point decimal 1243000.0 to 1.6 and express the result as
a normalized decimal number using scientific notation with four
significant digits of precision.
Decimal addition: 1243000.0 + 1.6 = 1243001.6 decimal
Normalized: 1.2430016 x 10**6
Four digits: 1.243 x 10**6
Note that adding 1.6 had no effect, given the precision available.
The smallest change you could make to the four-digit mantissa,
e.g. change 1.243 to 1.244, changes the value of the number by 0.001
x 10**6 or 10**3. A one-digit change affects the value by a thousand!
45. Add *binary* floating-point 1101000.0 to 1.11 and express the result
as a normalized binary number using (binary) scientific notation
with four (binary) significant digits of precision.
Binary addition: 1101000.0 + 1.11 = 1101001.11 binary
Normalized: 1.10100111 x 2**6
Four digits: 1.101 x 2**6
Note that adding 1.11 had no effect, given the precision available.
The smallest change you could make to the four-bit mantissa,
e.g. change 1.101 to 1.100, changes the value of the number by 0.001
x 2**6 or 2**3. A one-bit change affects the value by eight.
46. Looking at the two previous questions, is it possible in a computer
to add a small floating-point number to a larger floating-point
number without having any effect, i.e. is it true that A+B=A for
certain floating-point values where B is much smaller than A?
Class Notes Reference: 090_FloatingPoint.htm
Yes. Both previous questions show cases where A+B=A when A is big
and B is small. Because the number of bits of precision is fixed
in ordinary floating-point arithmetic inside a computer, there will
be some arithmetic that will not have enough precision to represent
the true answer. Adding two values of greatly differing magnitudes
(e.g. add 3 to 10**99) usually leaves the larger number unchanged,
because there are not enough bits of precision to represent the
small number being added to it. See the FunnyMath0.java program.
47. Assuming unsigned binary encoding, what decimal value is represented
by the binary pattern: 1 0 1 0 1 0 0 1 ?
128 64 32 16 8 4 2 1 <-- powers of two
--- -- -- -- - - - -
1 0 1 0 1 0 0 1 = 10101001(2) in binary
= 1*128 + 0*64 + 1*32 + 0*16 + 1*8 + 0*4 + 0*2 + 1*1
= 169(10) decimal
48. Conversions from different bases and representations to decimal:
a) Given the digits 101011(16), convert to decimal from base "16" =
b) Given the digits 101011(10), convert to decimal from base "10" =
c) Given the digits 101011(8), convert to decimal from base "8" =
d) Given the digits 101011(2), convert to decimal from base "2" =
e) Given the digits 101011(-2), convert to decimal from base "-2" =
f) Given the digits 101011(2), convert to decimal from bias-127 =
g) Given the digits 101011(2), convert to decimal from bias-63 =
h) Given the digits 101011(2), convert to decimal from bias-31 =
i) Given the digits 101011(2), convert to decimal from bias-16 =
Reference: http://en.wikipedia.org/wiki/Signed_number_representations
Class Notes Reference: 060_different_binary_integers.html
All of these just multiply out and add up using powers of the
given base. I'll do one example in full to show the method (the
strange base -2); generalize the same method to the other bases.
a) 101011(16) = 1048576 + 4096 + 16 + 1 = 1052689 decimal
b) 101011(10) = 100000 + 1000 + 10 + 1 = 101011 decimal (identity!)
c) 101011(8) = 32768 + 512 + 8 + 1 = 33289 decimal
d) 101011(2) = 32 + 8 + 2 + 1 = 43 decimal
e) Given the digits 101011(-2), convert to decimal from base "-2" =
Successive powers of a negative base alternate in sign!
Powers: -2^5 -2^4 -2^3 -2^2 -2^1 -2^0
Powers: -32 16 -8 4 -2 1
Digits: 1 0 1 0 1 1
---------------------------------
Add Up: -32 + 0 + -8 + 0 + -2 + 1
= -41 base 10
For all the bias (or "excess" notation) numbers, we first convert
the binary pattern to unsigned decimal, i.e.: 101011(2) = 43 decimal
then we subtract the given bias to get the actual value:
f) 101011(2), bias-127 = 43-127 = -84 decimal (same as IEEE 754 exponent)
g) 101011(2), bias-63 = 43- 63 = -20
h) 101011(2), bias-31 = 43- 31 = 12
i) 101011(2), bias-16 = 43- 16 = 27
IEEE 754 Single Precision Floating-Point uses an excess-127 representation.
49. In a 16-bit word, unsigned, what is the decimal value of the top bit?
(What is the decimal value of an unsigned binary 16-bit number that
has only the highest bit set?)
The "top" bit is the leftmost, most significant bit.
Bit 0 is 2**0 so bit 15 is 2**15 which is 32,768 (a famous number).
50. True/False: The most negative two's complement number has only
the sign bit turned on and all the other bits are zeroes.
True. -64 = 100000(2) in 6 bits, -1024 = 1000000000(2) in 10 bits, etc.
51. True/False: Two's complement -1 is always "all bits on".
True, no matter how many bits you use. -1 = 11111111(2) in eight
bits. -1 = 1111(2) in four bits. If you add one to it, you get
zero - all bits off. Subtracting one from zero gives "all bits on".
52. What happens mathematically to the range of values possible in a word
if you increase the word length by one bit, e.g. from eight bits to
nine bits or from 100 bits to 101 bits?
The range of possible values doubles. For example, 10 bits holds 2**10
values (1024 values) and 11 bits holds 2**11 values (2048 values).
DO THIS:
Edit this file and answer the above questions underneath each
question, showing the method or formula you used to get the answer.
Many of the questions already give you the answer - you must show
the full method you use to generate that answer. Upload the file
containing the question, methods, formulas, and answers before the
due date. Some of the answers above will require reading the links
published in the weekly course notes.
Full marks are awarded only if you show your method.
Answers will be posted after the due date/time so that you can check
your answers before coming to class and ask questions about the answers
in class. Please check your answers (and my answers!). I go over
each assignment in class if there are questions about the answers.
No questions means no review - I'll presume you know the material.
Questions similar to ones on these assignments will appear on your tests
and exams.
--
| Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada
| Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/
| College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/
| Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/