================================================= Assignment #02 - Fundamental Computer Terminology ================================================= - Ian! D. Allen - idallen@idallen.ca - www.idallen.com 1. What is the minimum number of binary bits needed to represent 43,386 items? Knowing your powers-of-two table makes this a quick answer. 2**15 = 32,768 (a number to remember) - TOO SMALL 2**16 = 65,536 (another number to remember) - BIG ENOUGH Therefore we need 16 bits which can hold 0 to 65,535 (unsigned) 2. Assuming an 8-bit word, show, in binary, how such a word would be encoded to represent the decimal number 87 using unsigned binary encoding. * METHOD 1 - Successive Subtraction of powers of two Write down some powers of two: ... 256 128 64 32 16 8 4 2 1 Biggest power of two that fits 87: 64 87 - 64 = 23 Biggest power of two that fits 23: 16 23 - 16 = 7 Biggest power of two that fits 7: 4 7 - 4 = 3 Biggest power of two that fits 3: 2 3 - 2 = 1 Biggest power of two that fits 1: 1 1 - 1 = 0 --> we're done. 87 = 1*64 + 0*32 + 1*16 + 0*8 + 1*4 + 1*2 + 1*1 Express the powers of two that we used in binary: 64 32 16 8 4 2 1 <-- powers of two -- -- -- - - - - 1 0 1 0 1 1 1 = 1010111(2) in binary * METHOD 2 - Successive division by two 87 divided by 2 is 43 remainder 1 43 divided by 2 is 21 remainder 1 21 divided by 2 is 10 remainder 1 10 divided by 2 is 5 remainder 0 5 divided by 2 is 2 remainder 1 2 divided by 2 is 1 remainder 0 1 divided by 2 is 0 remainder 1 Answer (write the remainders right-to-left): 1010111(2) in binary 3. What is the minimum number of binary bits needed to represent 87 items? Knowing your powers-of-two table makes this a quick answer. 2**6 = 64 - TOO SMALL 2**7 = 128 - BIG ENOUGH Therefore we need 7 bits which can hold 0 to 127 (unsigned) 4. 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) 5. Assuming unsigned binary encoding, what decimal value is represented by the binary pattern: 1 0 1 0 1 0 1 1 ? 128 64 32 16 8 4 2 1 <-- powers of two --- -- -- -- - - - - 1 0 1 0 1 0 1 1 = 10101011(2) in binary = 1*128 + 0*64 + 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 1*1 = 171(10) decimal 6. Convert 16-bit hexadecimal 0x142A to decimal. (Show your method!) Write down some hex digits: A=10, B=11, C=12, D=13, E=14, F=15 Write down some powers of 16: 16**0=1, 16**1=16, 16**2=256, 16**3=4096 Now add up the given powers of 16 in 142A(16): A times 16**0 = 10 * 1 = 10 2 times 16**1 = 2 * 16 = 32 4 times 16**2 = 4 * 256 = 1024 1 times 16**3 = 1 * 4096 = 4096 TOTAL = 5162(10) decimal 7. Convert decimal 2.5625 to binary. (Show your method!) Write down some powers of 2: 2**1=2, 2**0=1, 2**(-1)=0.5, 2**(-2)=0.25, 2**(-3)=0.125, 2**(-4)=0.0625 2.0 in binary is simply 10.0(2) What (negative) powers of two sum to make 0.5625? Biggest power of two that fits 0.5625: 0.5 0.5625 - 0.5 = 0.0625 Biggest power of two that fits 0.0625: 0.0625 0.0625 - 0.0625 = 0 --> we're done. Express the (negative) powers of two that we used in binary: 0.5 0.25 0.125 0.0625 <-- powers of two --- ---- ----- ------ 1 0 0 1 = 0.1001(2) in binary Therefore 2.5625(10) decimal is 10.0(2) + 0.1001(2) = 10.1001(2) in binary. 8. Which has more *Precision* available - a 32-bit integer or a 32-bit IEEE 754 floating-point number? Integers have 32 bits of precision. IEEE single-precision floats only have 24 bits of mantissa (including the assumed leading "1" digit), since one bit is used for sign and eight bits are used for an exponent. Integers have more precision. 9. Which has more *Range* available - a 32-bit integer or a 32-bit floating-point number? 32-bit signed integers only range plus or minus 2**31 (approximately). 32-bit floating point can range plus or minus 2**126 (approximately). (Recall 2**126 is approximately 10**38.) Floating point has more range. 10. What is the approximate range, in powers of ten, of IEEE 754 single-precision floating-point numbers? (i.e. what is the approximate largest and approximate smallest number) From -10**38 to -10**(-38), zero, +10**(-38) to 10**38 (approximately) (Using de-normalized floating-point this range can be expanded slightly.) 11. 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; see the literature for details. Remember 10**(-38) and you won't be far wrong. 12. 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). Due to the fixed number of bits in the mantissa, floating point arithmetic can lose precision when small numbers are added to or subtracted from big numbers. In the worst case, the small number has no effect at all on the larger number. 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. 13. Define the term "word" as it is used in computer architecture. A word is the typical native "integer" type used in the CPU, i.e. the collection of bits used by a particular processor to represent its basic integer numeric form. 32-bit processors have 32-bit words (integers); 64-bit processors have 64-bit words (integers). Processors can still do mathematics on larger and smaller integers, but it may require more (often much more) CPU or extra instructions. 14. Which of these measurements are powers of two, and which are powers of ten? a) amount of hard disk capacity? b) amount of CDROM capacity? c) computer memory size? d) processor speed (clock frequency)? e) processor bus speed (e.g. PCI bus or front side bus or memory bus)? f) network card speed? g) dial-up modem speed? h) ADSL modem speed? i) Distances in kilometres? Computer memory is powers-of-two. All the rest are powers-of-ten. 15. Give two reasons why you can't store 12GB of system memory in a file on a hard drive with an advertised capacity of 12GB. 1. 12 GB of system memory is measured in powers-of-two GiB that is larger than powers-of-ten 12 GB of hard drive storage, i.e. 12 GiB = 12,884,901,888 bytes and 12 GB = 12,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. 16. What is the difference between writing KB (kilobyte) and KiB (kibibyte) and MB (megabyte) and MiB (mebibyte)? a. KB (Kilobyte)=1000 bytes b. KiB (Kibibyte)=1024 bytes c. MB (megabyte)=1000*1000 byte=1,000,000 bytes d. MiB(mebibyte)=1024*1024 byte=1,048,576 bytes 17. Exactly how many bytes (in decimal) are in 4GiB of memory? 4 GiB = 4 * 1024 * 1024 * 1024 = 4,294,967,296 bytes 18. Exactly how many bytes (in decimal) are on an advertised 4GB hard disk? 4 GB = 4 * 1000 * 1000 * 1000 = 4,000,000,000 bytes 19. How many power-of-two MiB are on an advertised 2TB hard disk? 2TB disk = 2,000,000,000,000 = 2*(10**12) bytes 1 MiB = 1024 * 1024 = 2**10 * 2**10 = 2**20 bytes 2*(10**12)/(2**20) = 1,907,348.633 MiB Note: 2TB = 1,862.6 GiB = 1.82 TiB (your computer may show this size number) 2TiB = 2*(2**40) = 2,199,023,255,552 bytes 20. 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 21. What is the prefix used for a thousand Gigabytes? GB * 1000 = TB (terabyte) = 10**12 (disk) or 2**40 (memory) 22. If a memory has an access time of 10ns, how many accesses can you make in one second (give the answer in MHz)? 10 ns = 10 * 10**(-9) seconds Take the reciprocal to find the accesses per second: 1 / (10 ns) = 1/(10 * 10**(-9)) = 0.1 * 10**9 = 0.1 * 10**3 * 10**6 = 100 * 10**6 = 100 MHz 23. If a CPU has a clock frequency of 3.6 GHz, how long (in ns) does one access cycle take? 3.6 GHz = 3.6 * 10**9 cycles per second Take the reciprocal to find out the seconds per cycle: 1 / (3.6 GHz) = 1/(3.6 * 10**9) = 0.2777 * 10**(-9) = 0.2777 ns 24. What is the closest power of two to 1000 (i.e. closest to 10**3)? 1 K = 1000 (power of ten) 1 Ki = 1024 (power of two) = 2**10 25. How many ns (nanoseconds) are in a ms (millisecond)? 1 ns = 1 * 10**(-9) 1 ms = 1 * 10**(-3) 1ms / 1ns = 10**-3 / 10**-9 = 10**6 = a million 26. How may 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) 27. What is 2**16 in decimal? (This is a common number worth remembering.) 2**16 = 2**10 * 2**6 = 1024 * 64 = 65,536 28. 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.) 32 bits can contain 2**32 addresses = 2**2 * 2**30 = 4 GiB 29. 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? The time needed to move the arm holding the disk heads doesn't change when the disk rotation speed changes. 30. What is the standards group responsible for the Internet standards? Give the full name and the 4-letter acronym. Internet Engineering Task Force (IETF) 31. In the world of Internet standards, what do the letters "RFC" stand for? Request For Comment - Internet standards See http://tools.ietf.org/html/ 32. What is the modern version of Moore's Law? "the density of silicon chips doubles every 18 months" 33. Why can't Moore's law continue indefinitely? At some point the wires and components get so small that they become close to the size of individual molecules and stop working. 34. Put these terms in order, from most general (high level) to most specific (low level): Java or C++ Language (HIGH LEVEL) Microprocessor Assembly Language CPU Instruction Set Architecture (ISA) CPU microcode Logic gates (LOW LEVEL) 35. 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. 36. Whose name is attached to the idea of a computer that can store its programs and instructions in memory (a stored-program computer)? The name John von Neumann is usually used, but John Mauchley and/or J Presper Eckert are now being recognized as the originators of the idea. 37. What is the "von Neumann bottleneck"? "The limited throughput (data transfer rate) between the CPU and memory compared to the amount of memory. In most modern computers, throughput is much smaller than the rate at which the CPU can work. This seriously limits the effective processing speed when the CPU is required to perform minimal processing on large amounts of data. The CPU is continuously forced to wait for needed data to be transferred to or from memory. Since CPU speed and memory size have increased much faster than the throughput between them, the bottleneck has become more of a problem, a problem whose severity increases with every newer generation of CPU." 38. What are some ways to work around the "von Neumann bottleneck"? Use on-chip registers and cache memory, separate paths for instructions and data, multiple processors. 39. By what order of magnitude (power of 10) is something that runs in nanoseconds (e.g. a CPU) faster than something that runs in milliseconds (e.g. a hard disk)? millisec / nanosec = 10**(-3) / 10**(-9) = 10**6 = 1,000,000 = six orders of magnitude (a million times) 40. You have a program that takes 5 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 "5-minute" program to finish? It will take about one million times longer. A million times 5 minutes: (5)*(10**6)/(60*24*365.25) = about 9.5 years to finish! -- | 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/