In today's lectures we'll see talk about examples of abstraction in every day thinking and in computing and we'll learn how work with abstractions by learning to convert numbers from one type of number system to another.
Abstraction is an important cognitive process that refers to our ability to derive general concepts from particular objects or instances. It has various manisfestations in our thinking and in how we represent knowledge. Our ability to think abstractly underlies our ability to communicate.
In these an other cases, the abstraction removes details about the thing or things it describes or denotes or stands for and is thereby a generalization:
Example Numbers In App Inventor we represent numbers in decimal (base 10) notation. But at the hardware level numbers are often represented in binary (base 2) notation. And in HTML when we talk about RGB colors, we often represent them in hexadecimal (base 16) notation.
Our decimal number system (and binary and hexadecimal) is a particular instance of a more general abstraction, the positional number system.
In In a positional number system the same symbol can represent different values depending on its place in the numeral. For example, in 91, the 9 represents 90 (the 10s place) but in 19 it represents 9 (the ones place). Contrast this with Roman numerals where X always represents 10.
The base of a number system represents the number of digits:
Positional number systems use exponentiation to determine the value of a digit in a number based on its place. In all cases, the value of the digit is the digit multiplied by the value of its place. For example,
The above examples illustrate a simple algorithm for converting a number in any base to base 10.
Let the number of digits in the number be n. For example, 104 has 3 digits, so n=3. Let b be the base of the number. For example, 104 is decimal so b = 10. Let s be a running total, initially 0. For each digit in the number, working left to right do: Subtract 1 from n. Multiply the digit times bn and add it to s. When your done with all the digits in the number, its decimal value will be s
Let's try it on the binary number 1011.
Let n = 4. Let b = 2. Let s = 0. First digit, 1: n = 3, 1 × bn is 1 × 23 = 8. So s = 8. Second digit, 0: n = 2, 0 × bn is 0 × 22 = 0. So s = 8. Third digit, 1, n = 1, 1 × bn is 1 × 21 = 2. So s = 10 Last digit, 1, n = 0, 1 × bn is 1 × 20 = 1. So s = 11
Let's try it on the hex number 7E.
Let n = 2. Let b = 16. Let s = 0. First digit, 7: n = 1, 7 × bn is 7 × 161 = 7 × 16 = 112. So s = 112. Last digit, E n = 0, 14 × bn is 14 × 160 = 14. So s = 112 + 14 = 126.
To convert a decimal number, n, to binary notation, we can use another simple algorithm:
Let's try converting 45 into binary.
Let n = 45. Repeat 45 divided by 2 gives 22 remainder 1. So d=22 and r=1. So m=1 and the new n is 22. 22 divided by 2 gives 11 remainder 0. So d=11 and r=1. So m=01 and the new n is 11. 11 divided by 2 gives 5 remainder 1. So d=5 and r=1. So m=101 and the new n is 5. 5 divided by 2 gives 2 remainder 1. So d=2 and r=1. So m=1101 and the new n is 2. 2 divided by 2 gives 1 remainder 0. So d=1 and r=0. So m=01101 and the new n is 1. 1 divided by 2 gives 0 remainder 1. So d=0 and r=1. So m=101101 and the new n is 0. So we stop and m = 101101
Let's try converting 99 into binary.
Let n = 99. Repeat 99 divided by 2 gives 49 remainder 1. So d=49 and r=1. So m=1 and the new n is 49. 49 divided by 2 gives 24 remainder 1. So d=24 and r=1. So m=11 and the new n is 24. 24 divided by 2 gives 12 remainder 0. So d=12 and r=0. So m=011 and the new n is 12. 12 divided by 2 gives 6 remainder 0. So d=6 and r=0. So m=0011 and the new n is 6. 6 divided by 2 gives 3 remainder 0. So d=3 and r=0. So m=00011 and the new n is 3. 3 divided by 2 gives 1 remainder 1. So d=1 and r=1. So m=100011 and the new n is 1. 1 divided by 2 gives 0 remainder 1. So d=0 and r=1. So m=1100011 and the new n is 0. So we stop and m is 1100011
To convert decimal (base 10) numbers into hexadecimal (base 16) numbers we can use an algorithm that's similar to one we just used to convert decimal to binary.
Thinking Abstractly: In fact, we can generalize that algorithm so that it works for converting to any base. In the original algorithm we are "dividing by 2" because 2 is the base that we are converting to. So, to generalize this we can say "divide by the base":
NOTE: Note how we have generalized the algorithm here by replacing the constant 2 with a variable, b that can stand for any base. This is an example of abstraction.Let n be the decimal number. Let m be the number, initially empty, that we are converting to. We'll be composing it right to left. Let b be the base of the number we are converting to. Repeat until n becomes 0 Divide n by b, letting the result be d and the remainder be r. Write the remainder, r, as the leftmost digit of b. Let d be the new value of n.
Let's try converting 45 into hexadimal.
Let n = 45. Let b = 16. Repeat 45 divided by 16 gives 2 remainder 13. So d=2 and r=13. So m=D and the new n is 2. 2 divided by 16 gives 0 remainder 2. So d=0 and r=2. So m=2D and the new n is 0. So we stop and m is 2D.
Let's try converting 99 into hexadecimal.
Let n = 99. Let b = 16. Repeat 99 divided by 16 gives 6 remainder 3. So d=6 and r=3. So m=3 and the new n is 6. 6 divided by 16 gives 0 remainder 6. So d=0 and r=6. So m=63 and the new n is 0. So we stop and m is 63.