FIT1047 Lab 1
Topics
• Moore’s law
• Conversion of numbers between different bases
Instructions
• The tasks are supposed to be done in groups and might involve considerable discus- sions. Some have a specific solutions, others are supposed to stipulate understanding and thinking about the concepts.
• Form groups of 3 students to work through the exercises together.
• The tutorial is based on the first lecture, but might require to search for additional
information.
• We are aware that students in FIT1047 come from diverse backgrounds and also aim at different degrees. Therefore, the first questions should be the basis to discuss some of the basic concepts and terminology. Discuss them briefly in your group and if you are familiar with the concepts, please explain them to your fellow students who dont have the same background.
• If you are unsure what to do or stuck at any point, dont hesitate to ask your tutor. Tutorials and labs are a chance to get a better understanding of the topics.
Task 1: Moore’s law
Moore’s law is the observation that, over the history of computing hardware, the number of transistors in a dense integrated circuit has doubled approximately every two years (initially it was once per year). This observation was published in a paper in 1965 by Gordon E. Moore, one of the co-founders of Intel. In a simplified version of Moore’s law let us assume that microprocessor power doubles every 18 months.
2.a Assume you have a great idea to speed up microprocessors by a factor of 6. But, you need 4 and a half years to raise money and develop the prototype. If Moore’s law (in the simplified form) holds, it is worth investing in the new technology?
• 4.5 years means we look at 54 months, this is 3 times 18 months.
• Microprocessor power x doubles after 18 months: new power is 2x, then after 36 months we have 2(2x) and after 54 months it is 2(2(2x)) = 23x = 8x. Thus, after 4.5 years, improving by factor 6 is slower than other developments that achieve the improvement matching Moore’s law.
1
2.b If a problem today takes 100,000 hours to compute, which approach would give us the solution first:
(i) Replace the algorithm with one that is twice as fast and let it run on current technology.
(ii) Wait 3 years and then use the slower algorithm on the new technology.
• The faster algorithm would need 50,000 hours. This is around 2083.3 days, which is around 5.7 years.
• After three years, we have a speed-up by factor 4. Thus, we only need 25.000 hours, half the time of the other faster algorithm. Thus, we need around 2.85 years for the computation. Plus the 3 years wait, we get 5.85 years. Thus, waiting is slower.
• Of course, waiting and then use the faster algorithm is better . . .
Task 2: Conversion of numbers between different bases
There are different methods to convert between different bases. In this task you will look at two methods, one slow method and another more efficient method. The advantage of the slow method is, that it nicely shows how number systems with different bases work.
Slow method of converting numbers between bases
This methods needs one preparation step. First, one needs to convert the values for the different places and then add them up to get the converted number. In order to do this, we first need to look at the values for the different places of the number. The following table shows the base 10 values for base 3 and base 10 places 0 to 5.
Base 3
Base 10
35 34 33 32 31 30
24310
8110 2710 910 310 110
105 104 103 102 101 100
100000
10000
1000
100
10
1
In order to convert a number in base 3, we now compute the base 10 value for each single place of the base 3 number and then add these up. As example, the following table shows the conversion of number 1202113 to base 10.
2
Number
Step
Step value
Calculation base 10
Value in base 10
1 2 0 2 1 1
35 34 33 32 31 30
24310
8110 2710 910 310 110
243×1 81×2 27×0
9×2 3×1 1×1
243 162 0 18 3 1
Converted number base 10 427
To convert back from base 10 to base 3, we use a similar approach, but instead of multi- plying with the step value we divide by the step value and continue with the remainder as shown in the following table.
Remainder
Step
Step value
Calculation base 10
Value in base 3 for this step
427 184 22 22 4
1
35 34 33 32 31 30
24310
8110 2710 910 310 110
427/243 184/81 22/27 22/9 4/3 1/1
1 2 0 2 1 1
Concatenate top down to get number base 3 120211
This method works for all bases, but always requires to calculate with rather large inter- mediate results using the values for each place.
More efficient way of converting numbers between bases
For the faster method, take the leftmost place (i.e. in 120211 base 3 take the leftmost 1) multibly by the base, add the next digit, multiply by the base and continue until all numbers are used. By doing this, each place is multiplied by the correct base value for this step. The following table shows the conversion for 120211 base 3.
Action
place base 3
result (base 10 value)
Multiply by 3 Add next place Multiply by 3 Add next place Multiply by 3 Add next place Multiply by 3 Add next place Multiply by 3 Add final place
1 2
0 2 1 1
3
5
15
15
45
47
141
142
426
427
Base 10 result
427
Converted number base 10
427
3
Finally, converting from base 10 to base 3 requires division by three and looking at the remainders.
Division
Result
Remainder
Build base 3 number
427/3 142/3 47/3 15/3 5/3 1/3
= = = = = =
142 47 15 5
1 0
1 1 2 0 2 1
Base 3 number is XXXXX1 Base 3 number is XXXX11 Base 3 number is XXX211 Base 3 number is XX0211 Base 3 number is X20211 Base 3 number is 120211
Converted number base 3 120211
Tasks
Concentrate on the algorithm to calculate the conversion (dont just google the result). 3.a Convert the base 16 number 123C9F to base 10 using both methods
Slow method:
Number
Step
Step value
Calculation base 10
Value in base 10
1 2 3 C 9 F
165 164 163 162 161 160
104857610 6553610 409610 25610
1610 110
1048576 × 1 65536 × 2 4096×3 256×12 16×9 1×15
1048576
131072
12288
3072
144
15
Converted number base 10 1195167
Faster method: 123C9F
Action
place base 3
result (base 10 value)
Multiply by 16 Add next place Multiply by 16 Add next place Multiply by 16 Add next place Multiply by 16 Add next place Multiply by 16 Add final place
1 2
3 12 9 15
16
18
288
291
4656
4668
74688
74697
1195152
1195167
Base 10 result
1195167
Converted number base 10
1195167
4
3.b Convert the base 2 number 1100011101 to base 10 using the slow method.
Number
Step
Step value
Calculation base 10
Value in base 10
1 1 0 0 0 1 1 1 0 1
29 28 27 26 25 24 23 22 21 20
51210 25610 12810
6410 3210 1610
810 410 210 110
512×1 256×1 128×0
64×0 32×0 16×1
8×1 4×1 2×0 1×1
512
256
0
0
0
16
8
4
0
1
Converted number base 10 797
3.c Convert the hexadecimal (base 16) number AFC934B2D to binary without the use of addition, substraction, multiplication, or division.
For each number just replace with the matching 4 digits of the binary representation:
A
F
C
9
3
4
B
2
D
1010
1111
1100
1001
0011
0100
1011
0010
1101
5
TASK 3: Data Representation
How many bytes in a:
SOLUTION:
e) Gigabyte? 230 f) Kilobyte? 210 g) Terabyte? 240 h) Megabyte? 220
How many seconds in a:
SOLUTION:
d) Micro-second 10-6 e) Nano-second 10-9 f) Milli-second 10-3
Data representation – Integers
This exercise needs to be done together with the tutor. Please convert the following Decimal number with fraction to Binary following the method shown by the tutor.
Convert the following decimal fractions to binary number representation:
a) 237.25
SOLUTION:
• Integer part as usual: 11101101
• Fraction: 0.01
0.25 x 2 =
0.5 x 2 = • Result =11101101.01
b) 32.32
SOLUTION:
0.5 → remove the 0 1.0 → remove the 1
• Integer part as usual: 100000
• Fraction: 0.010100011…
0.32 x2 0.64 x2 0.28 x2 0.56 x2 0.12 x2 0.24 x2 0.48 x2 0.96 x2 0.92 x2
= 0.64 → remove the 0 = 1.28 → remove the 1 = 0.56 → remove the 0 = 1.12 → remove the 1 = 0.24 → remove the 0 = 0.48 → remove the 0 = 0.96 → remove the 0 = 1.92 → remove the 1 = 1.84 → remove the 1 …(continues indefinitely)
• Result =100000.010100011………..
6