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