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