====================================================== Assignment #07 - Floating Point, Endian, Shifts, Characters, Booleans ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Available online: Monday February 28, 2011 Upload due date: Upload answer file before 23:59 (midnight) on Wednesday March 16, 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 "assignment07.txt" Upload the file via the Assignment07 "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. Some of the questions may 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, the same method you will have to use on tests and exams. ============================================================================== 0. What is the date, time, and room number of your Final Exam? CST8281: Saturday Apr 23 11h30 (11:30am to 2pm) - T102 - Final exam *** Floating-Point Section *** 1. The IEEE 754 floating-point number 81234567h is negative. Without converting, give the hexadecimal for the same number, only positive. Turn off the sign bit: 81234567h --> 01234567h 2. IEEE 754 single-precision floating-point can store numbers in the approximate range of -2**127 to +2**127. Look up or use a calculator to express this range (approximately) as powers of ten (decimal). "Approximately plus/minus 10**38" 3. How close to zero can you get with IEEE 754 32-bit floating point? (What is the non-zero value that is closest to zero?) Express the answer in both approximate power-of-two notation and in approximate power-of-ten notation. Approximately 2**(-126) (normalized IEEE) which is approximately 10**(-38). Denormalized IEEE 754 numbers can get closer to zero at the expense of some precision. Remember 10**(-38) and you won't be far wrong. 4. What is floating-point underflow? (Reference: 02.ppt slide 81) Any number that is "too close to zero" to be represented. In IEEE-754 single-precision, numbers less than about 10**(-38) fall into this "zero hole". (You can actually get numbers smaller than this, using de-normalized floating point - see the notes for details.) 5. Give an example of a number that would cause floating-point underflow if you tried to calculate it or represent it using IEEE-754 single-precision floating-point. Anything closer to zero than about 10**(-38), e.g. 1.0e-100 6. Which has more *Precision* available - a 32-bit integer or a 32-bit floating-point number? (Reference: 02.ppt slides 82-83) Integers have 32 bits of precision. Single-precision floats only have about 24 bits of mantissa. Integers have more precision. 7. Which has more *Range* available, - a 32-bit integer or a 32-bit IEEE 754 floating-point number? (Reference: 02.ppt slides 82-83) 32-bit integers only range plus or minus 2**31 (approximately). 32-bit floating point can range plus or minus 2**127 (approximately) or about 10**38. Floating point has more range. 8. True/False: Decimal 1234.0 x 10**37 fits in IEEE 754 single precision floating point. 1234.0 x 10**37 = 1.234 x 10**40 which exceeds 10**38 - FALSE. 9. True/False: Decimal 0.00001 x 10**40 fits in IEEE 754 single precision floating point. 0.00001 x 10**40 = 1.0 x 10**35 which fits in 10**38 - TRUE. 10. Without converting, mark with an "X" the sums that do not fit in IEEE 754 single-precision floating point with no loss of range or precision. Leave unmarked the values that do fit completely accurately: 2**30-3 2**30-1 2**30 2**30+1 2**30+3 2**30+2**29 All the numbers fit within the 2**127 exponent range of IEEE 754. Mark anything that does not fit within 23 bits of precision: X2**30-3 X2**30-1 2**30 X2**30+1 X2**30+3 2**30+2**29 For example, 2**30-1 is 111111111111111111111111111111(2) which is 1.11111111111111111111111111111 x 2**29 and needs 28 bits of precision. Doesn't fit in a 23-bit IEEE mantissa. For example, 2**30+2**29 is 1100000000000000000000000000000(2) = 1.1 x 2**30 which only needs two bits of precision (1.1 x 2**30). Fits. 11. Without converting, mark with an "X" the sums that do not fit in IEEE 754 single-precision floating point with no loss of range or precision. Leave unmarked the values that do fit completely accurately: 2**29+2**10+2**9+2**0 2**26+2**0 2**29+2**28+2**27+2**26 2**27+2**23+2**1 2**29+2**28+2**2+2**1 All the numbers fit within the 2**127 exponent range of IEEE 754. Mark anything that does not fit within 23 bits of precision: X2**29+2**10+2**9+2**0 X2**26+2**0 2**29+2**28+2**27+2**26 X2**27+2**23+2**1 X2**29+2**28+2**2+2**1 For example, 2**26+2**0 needs 27 bits of precision: = 100000000000000000000000001(2) = 1.00000000000000000000000001 x 2**26 For example, 2**29+2**28+2**27+2**26 only needs four bits of precision: = 1.111 x 2**29 12. Why do the decimal numbers 2147483775 (0x8000007F) and 2147483648 (0x80000000) both convert to the same IEEE 754 single-precision floating-point number 0x4F000000 that has decimal value 2147483648.0? The number 2147483775 (0x8000007F) requires 32 bits of precision. The last (rightmost) 9 bits of precision are thrown away when converting to IEEE 754 single-precision, so the "7F" part of 0x8000007F disappears and it looks just like 0x800000, which converts back to 2147483648.0 decimal, not to 2147483775. You lose precision when converting a 32-bit integer into a 23-bit mantissa. In other words: 2147483775 in binary is 10000000000000000000000001111111 2147483648 in binary is 10000000000000000000000000000000 When you convert both of these numbers to IEEE 754 single precision floating point number, the mantissa only holds 23 of those bits. What is stored in the mantissa for 2147483775 is (1.)00000000000000000000000 and the extra 01111111 gets discarded. What is stored in the mantissa for 2147483648 is (1.)00000000000000000000000 which is exactly the same as 2147483775. Even though the numbers are different, since IEEE 754 single-precision floating-point number only has a precision of 23 bits, both of these numbers end up being the same when they are converted, because anything beyond 23bits is discarded. 13. Explain why, in a computer, floating point mathematics may not be associative or distributive, i.e. (A+B)+C may not equal A+(B+C). Floating point arithmetic can lose precision when small numbers are added to or subtracted from big numbers. If you arrange your mathematics so that the small numbers are added to each other first, they stand a better chance of affecting the bigger number. Order matters. 14. Why must you never test floating-point numbers for equality, i.e. why is "if ( a == b )" a bad idea for floating point a and b? Due to errors in precision, floating-point numbers may not achieve exact equality. They may be extremely close together, but not equal. Since you already accept some error when using floating-point numbers, comparison for exact equality makes no sense. The comparisons must be done to with some tolerance, or "epsilon", that you choose depending on your application. 15. What is the correct way to test for floating-point "equality"? (Reference: 02.ppt slides 72 and 84) Decide how close the numbers should be to be considered equal. Call this small difference value "epsilon". Then use: IF ( abs(a - b) < epsilon ) THEN consider a and b are "equal" where a and b are being compared and epsilon is a small number, e.g. 1.0e-9 16. Write a tiny program fragment that uses a floating point loop that starts at 1.5, adds 0.1 each time through the loop, and stops when the loop counter is within 1.0e-5 ("epsilon") of the floating-point value 10.1. Give the code for the FOR loop here: (Reference: 02.ppt slides 72 and 84) for( counter=1.5; abs(counter-10.1) >= 1.0e-5; counter += 0.1 ){ } 17. What is the likely final value of variable "z" in this IEEE 754 single-precision pseudo-code fragment: float x = 2**40 float y = x + 9 float z = x - y Because x is so large, adding 9 to it doesn't change its value. Thus x and y have the same value, and z is zero. *** Endian Section *** 18. What byte-order is used on the Internet to transmit data? The Internet is Big Endian. Most Significant Byte goes First. 19. What is the byte-order of AMD/Intel-based computers? AMD/Intel x86 and x86_64 computers are all Little-Endian. *** Miscellaneous Section *** 20. If a memory has an access time of 50ns, how many accesses can you make in one second (give the answer in MHz)? 50 ns = 50 * 10**(-9) 1 / 50 ns = 1/50 * 10**9 = 0.02 * 10**3 * 10**6 = 20 MHz 21. If a CPU has a clock frequency of 3.2 MHz, how long (in ns) does one access cycle take? 3.2 MHz = 3.2 * 10**6 1 / 3.2 MHz = 1/3.2 * 10**(-6) = 0.3125 * 10**3 * 10**(-9) = 312.5 ns 22. Why isn't a disk that rotates at 10,000 RPM exactly twice as fast as a disk that rotates at 5,000 RPM? What else is involved? You also have to move the disk arm containing the heads. 23. What are the smallest and largest decimal integers an 8-bit word can hold using an excess-127 (bias-127) representation? Bias means we add 127 when putting the number in, and the end result has to fit in 8 bits. The largest number we can store in 8 bits unsigned is 255, so the largest bias-127 number is 255-127=128. Bias means we add 127 when putting the number in, and the end result has to fit in 8 bits. The smallest number we can store in 8 bits unsigned is 0, so the smallest bias-127 number is 0-127=-127. 24. In 13-bit two's complement representation, what decimal number do you get when you add one to decimal 4,095? 13 bits can hold 2**13 (8192) numbers. Half are positive in two's complement; the largest is +4,095. Adding one turns on the sign bit, resulting in the largest negative number -4,096. 25. Convert the two's complement representation 12-bit hexadecimal number "EF6h" to decimal. In 12 bits, EF6h is negative (sign bit is on). Panic. Flip bits, add one. EF6h -> BIT FLIP -> 109h -> ADD ONE -> 10A = 256+10 = 266 so the answer is MINUS 266 = -266 26. Why doesn't the number 1.5 * 10**50 fit accurately in an IEEE 754 single precision floating-point number? The value of the exponent (10**50) is larger than the maximum allowed for IEEE 754 single-precision (10**38 max, approximately). 27. Express -10 decimal in hexadecimal using 20-bit sign-magnitude notation. In 20 bits: 8000Ah (sign bit on; rest of number has value "10") *** Bit Shifting Section *** 28. What happens mathematically to the value of a binary number if you "shift" the bits to the right one place by deleting the rightmost binary digit, e.g. 1100 --> 0110 The value is halved. Any fractional remainder is thrown away. 29. What happens to the value of a binary number if you "shift" the bits to the left two places by adding two zeros after the rightmost binary digit, e.g. 11001 --> 1100100 The value doubles twice, i.e. quadruples (multiply by four). 30. What happens to the value of an octal number if you "shift" the number to the left one place by adding one zero after the rightmost octal digit, e.g. 0377 --> 03770 The value is multiplied by 8 (the base). 31. What happens to the value of a hexadecimal number if you "shift" the number to the left one place by adding one zero after the rightmost hex digit, e.g. 0xABC --> 0xABC0 The value is multiplied by 16 (the base). 32. Is it still true that shifting a binary number left one bit multiplies it by two, if the number is a negative two's complement number? Yes, iff the doubled value can be represented in the number of bits. Consider 4-bit two's complement: 1111(2) = -1(10) shifted left becomes 1110 = -2(10) 1110(2) = -2(10) shifted left becomes 1100 = -4(10) 1101(2) = -3(10) shifted left becomes 1010 = -6(10) 1100(2) = -4(10) shifted left becomes 1000 = -8(10) 1011(2) = -5(10) shifted left becomes 0110 = +6(10) [too big] The left shift doubles the number only if the doubled number is small enough to be represented in the available number of bits. 33. What is the difference between an Arithmetic and Logical Right Shift? An Arithmetic Shift Right replicates the sign bit: 1010 -> 1101 - It is used on signed numbers to preserve the sign. A Logical Shift Right uses zeroes: 1010 -> 0101 - It corresponds to the Left Shift that also uses zeroes. *** Character Section *** 34. True/False - In ASCII, you can add one to any letter to get the next letter in the alphabet (up to "Z"). True - ASCII has no gaps. All the letters are sequential. Upper-case letters start at 41h; lower-case start at 41h+20h=61h. 35. True/False - In UTF-8, you can add one to any English letter to get the next letter in the alphabet (up to "Z"). True - UTF-8 is the same as ASCII for the English alphabets. 36. Name and give the hex values of the seven "Famous ASCII Characters". CR LF SP '0' 'A' 'a' DEL 0D 0A 20 30 41 61 7F 37. In ASCII, which comes first (i.e. has lower hex values): upper-case letters or lower-case letters? Upper case letters precede lower-case letters in ASCII. They sort first. 38. If you sort a file containing lines of mixed-case ASCII text, what is the resulting relationship of lines that begin with upper-case letters and lines that begin with lower-case letters? (Which lines sort first in the file?) ASCII upper-case sorts before ASCII lower-case. 39. If you sort a file containing lines of mixed-case ASCII text and numbers, what is the resulting relationship of lines starting with digits and lines starting with letters? (Which lines sort first in the file?) All ASCII digits sort before (are smaller than) letters. 40. If you want to give a Unix file an ASCII name that sorts before all other file names in a sorted directory listing, what non-blank character(s) might you use to begin the file name? Any of: ! " # $ % & ' ( ) * + , - . (cannot use / in a file name) would sort before letters and digits. Many people start file names with '!', e.g. !README.TXT 41. There is only one bit of difference between an upper-case ASCII character and its lower-case equivalent. What is the hexadecimal and decimal value of this difference? What ASCII character does this difference represent? 'A' = 41h = 0100 0001(2) 'a' = 61h = 0110 0001(2) It is the 2**5 bit, with value 32 decimal or 20h or SP. 'a' - 'A' = ' ' = 0x20 = SP (ASCII) 42. What hex values and (if printable) ASCII characters result from the following ASCII arithmetic (characters in single quotes are ASCII characters): EXAMPLE: 'A' + 1 = 41h + 1 = 42h = 'B' a) 'Z' - 2 = ? b) 'A' + ' ' = ? c) 'b' - 'B' = ? d) '9' - '1' = ? a) 'Z' - 2 = 5Ah - 2 = 58h = 'X' b) 'A' + ' ' = 41h + 20h = 61h = 'a' c) 'b' - 'B' = 62h - 42h = 20h = ' ' d) '9' - '1' = 39h - 31h = 8h = 8 decimal - not printable 43. How do the ASCII character set and the UTF-8 character set relate to each other? The first 128 characters of UTF-8 are identical to ASCII. 'A' = 41h in both ASCII and UTF-8. 44. How do the ASCII character set and the Unicode character set relate to each other? The first 128 characters of Unicode are ASCII, but in 16-bit form. 'A' = 41h in ASCII (7-bit characters) 'A' = 0041h in Unicode (16-bit characters) 45. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as UTF-8. True. That's why UTF-8 is so popular in North America. 46. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as Latin-1. True. The first 128 characters of almost all the 8-bit character encodings are just plain ASCII. Only the last 128 bytes (the bytes with the top bit set) are used for the other languages. 47. True/False: Plain English text, encoded as ASCII, is identical to the same Plain English text encoded as Unicode. False. ASCII is one byte per character; Unicode is two bytes per character. For example, ASCII 'A' = 0x41, Unicode 'A' = 0x0041. ASCII and Unicode have the same *values* for the first 128 characters, but ASCII stores the value in one byte and Unicode needs two. If you encode an ASCII file as Unicode, the file size doubles and every second byte in the file is zero. 48. What advantage does UTF-8 have over Unicode for English text? UTF-8 encodes English exactly the same was that ASCII does - one byte per character. Unicode takes two bytes for every character. 49. Why can't a single text file contain both French, encoded as 8-bit Latin-1, and Polish, encoded as 8-bit Latin-2? If all 258 8-bit codes are used for French, there are no codes left over for Polish. A file can only be interpreted as either Latin-1 or Latin-2, not both at the same time. Use UTF-8 or Unicode if you need multiple languages in the same file. 50. What is the default character set used in the Java language? http://www.exampledepot.com/egs/java.nio.charset/ConvertChar.html "Java's native character encoding is Unicode." http://publib.boulder.ibm.com/infocenter/iseries/v5r3/index.jsp?topic=/rzaha/charenc.htm "Internally, the Java(TM) virtual machine (JVM) always operates with data in Unicode." 51. Without decoding using any ASCII table, explain why the following sequence of hexadecimal bytes is or is not likely to be from an ASCII text file: 84 03 fd ff ff c7 44 24 08 05 00 00 00 31 f6 c7 Many bytes above are either 8-bit characters (e.g. 84, ff) or are unprintable characters (values less than 0x20 such as 03 and 00). ASCII text contains 7-bit printable characters in the range 20h to 7Eh. 52. You look into memory and see the hexadecimal value 40h. Based on what you know in this course so far, what different things might this 40h represent? - an EBCDIC space - an ASCII '@' symbol - the decimal value 64 in 8-bit two's complement, or sign-magnitude, or one's complement (sign bit is off) - the excess-127 number -63 (e.g. an IEEE-754 exponent) 53. Under what operating system was the following text file created? How do you know? 4C 69 6E 75 78 0D 0A 52 6F 63 6B 73 5C 21 0D 0A 0D 0A line ends = CR/LF = Microsoft DOS or Windows 54. Under what operating system was the following text file created? How do you know? 4C 69 6E 75 78 0D 52 6F 63 6B 73 5C 21 0D 0D line ends = CR = Apple Macintosh 55. Under what operating system was the following text file created? How do you know? 4C 69 6E 75 78 0A 52 6F 63 6B 73 5C 21 0A 0A line ends = LF (or NL) = Unix/Linux/BSD/Solaris/AIX/etc. 56. Encode the following seven Famous ASCII characters in hexadecimal using 8-bit Even Parity: 1) A 2) a 3) '0' 4) CR 5) LF 6) SP 7) DEL 8 bit even parity ensures that the sum of the number of "one" bits in a seven bit sequence is an even number by either turning on or leaving off the most significant bit (eighth bit) A = 41h = 0100 0001, MSB off for even parity = 0100 0001 = 41h a = 61h = 0110 0001, MSB on for even parity = 1110 0001 = E1h 0 = 30h = 0011 0000, MSB off for even parity = 0011 0000 = 30h CR = 0Dh = 0000 1101, MSB on for even parity = 1000 1101 = 8Dh LF = 0Ah = 0000 1010, MSB off for even parity = 0000 1010 = 0Ah SP = 20h = 0010 0000, MSB on for even parity = 1010 0000 = A0h DEL = 7F = 0111 1111, MSB on for even parity = 1111 1111 = FFh 57. Encode the following seven Famous ASCII characters in hexadecimal using 8-bit Odd Parity: 1) A 2) a 3) '0' 4) CR 5) LF 6) SP 7) DEL 8 bit odd parity ensures that the sum of the number of "one" bits in a seven bit sequence is an odd number by either turning on or leaving off the most significant bit (eighth bit). The parity bit is the exact opposite of the previous answer: A = 41h = 0100 0001, MSB on for odd parity = 1100 0001 = C1h a = 61h = 0110 0001, MSB off for odd parity = 0110 0001 = 61h 0 = 30h = 0011 0000, MSB on for odd parity = 1011 0000 = B0h CR = 0Dh = 0000 1101, MSB off for odd parity = 0000 1101 = 0Dh LF = 0Ah = 0000 1010, MSB on for odd parity = 1000 1010 = 8Ah SP = 20h = 0010 0000, MSB off for odd parity = 0010 0000 = 20h DEL = 7F = 0111 1111, MSB off for odd parity = 0111 1111 = 7Fh 58. The following ASCII byte is received from a system that generates 8-bit Even Parity: 0xA7 Is there an error in the byte? How do you know? Error, because 0xA7 = 1010 0111 -> which is odd parity, not even. Since even parity expects the sum of the 1 bits to be an even number this byte must be an error because the sum of 1 bits is an odd number (5 bits are "1"). 59. The following ASCII byte is received from a system that generates 8-bit Odd Parity: 0xA5 Is there an error in the byte? How do you know? Error, because 0xA5 = 1010 0101 -> which is even parity, not odd. Since odd parity expects the sum of the 1 bits to be an odd number this byte must be an error because the sum of 1 bits is an even number (4 bits are "1"). *** Boolean Section - see 03.ppt *** Recall that "NOT x" can be written in text using the "prime" mark: x' 60. True/False: (xy)' == x'y' In English: "NOT(red AND jello) == NOT red AND NOT jello" ? FALSE: (xy)' == x' + y' 61. True/False: (x + y)' == x' + y' In English: "NOT(red OR jello) == NOT red OR NOT jello" ? FALSE: (x + y)' == x'y' 62. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(a,b,c) = a(b' + c) "Complement" means apply Boolean "NOT". F'(a,b,c) = (a(b' + c))' : complement the function = a' + (b' + c)' : deMorgan = a' + (b')'c' : deMorgan = a' + bc' : identity 63. Using deMorgan, write a simplified expression for the Boolean complement of the logic function F(a,b,c) = a + (b'c) "Complement" means apply Boolean "NOT". F'(a,b,c) = (a + (b'c))' : complement the function = a'(b'c)' : deMorgan = a'(((b)')'+ c') : deMorgan = a'(b + c') : identity = a'b + a'c' : distribute (optional) 64. Show that x = xy + xy' using a Boolean truth table. x y xy xy' xy + xy' ---------------------------------------------------- 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 65. Prove that x = xy + xy' using a chain of simple Boolean Identities. xy + xy' = x(y + y') : factor out 'x' = x(1) : identity = x : identity 66. Construct a Boolean function F(a,b) that implements the XOR operator using only AND, OR, and NOT logic. (The truth table for the simple function should be the same as the XOR truth table.) F(a,b) = a ^ b : this is the XOR bitwise operator = ab' + ba' : Solution 1: using only AND, OR, and NOT = (a + b)(ab)' : Solution 2: using only AND, OR, and NOT = (a + b)(a' + b') : Solution 2 with deMorgan applied = aa' + ab' + ba' + bb' : expanded = 0 + ab' + ba' + 0 : identities = ab' + ba' : same as Solution 1 67. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "Call the delete routine unless: the product_id is zero or the product_class is 'important'." Write unsimplified: if ( ! (id == 0 || class == 'important' ) ) delete(); Use deMorgan to get: if ( id != 0 && class != 'important' ) delete(); 68. Write the simplest IF statement (simplify the Boolean logic) for the following programming problem specification: "A record is one where the modify_date date is less than a year old and the account_balance is bigger than zero. If the record is NOT current, call the delete routine." Write unsimplified: if( ! ( md < YEAR && bal > 0 ) ) delete(); Use deMorgan to get: if ( md >= YEAR || bal <= 0 ) delete(); Full marks are awarded only if you show your method, the same method you will have to use on 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/