The editor for blog posts doesn't have a symbol that looks like the arrow for implication, so these are the symbols I will use here for the logical operators.
^ is AND
v is OR
~ is NOT
=> is IMPLIES
p = 1101
q = 1000
r = 0110
Find the bitstrings that correspond to these logical operations.
a) p v q
b) p ^ ~r
c) r => q
d) ~r => q
e) ~(r => q)
f) p v q ^ r
Answers in the comments.
More practice problems here .
Friday, February 25, 2011
Thursday, February 17, 2011
Algorithms to convert between binary, decimal and hexadecimal representation.
As we discussed in class, the word "algorithm" just means "method", but like most mathematical terms, there are special stipulations. The method always has to work, it must always take a finite amount of steps, and each step must take a finite amount of time to complete.
Decimal, or base 10, is the number system we are used to. Binary, or base 2, is the number system a computer uses, storing all its information as a string of 1s and 0s. Hexadecimal, or base 16, is kind like a compromise, a way to easily represent binary numbers in a way that takes less writing and is easier for the human programming the machines to read.
The algorithm from decimal to binary.
Start with a number written in decimal representation. We are going to build its equivalent binary representation bit by bit from the ones place to the twos place to the fours place, etc., which means building from right to left.
Step 0. Start with a decimal number and an empty representation for the binary equivalent.
Step 1. Is the ones digit of the decimal representation even or odd? If even, put a 0 in the first place to left of the current binary representation. If odd, put a 1 in the first place to the left of the current binary representation.
Step 2. Divide the current decimal representation by 2. If the result is more than 1, go to Step 1. If it is less than 1, STOP. We now have the correct binary representation of the original decimal number.
Example. Let's change 75dec to its binary equivalent.
Step 1a. 75 is odd so our current binary representation will be 1bin.
Step 2a. 75/2 = 37.5, bigger than 1, so we continue.
Step 1b. the ones place of 37.5 is odd so our current binary representation will be 11bin.
Step 2b. 37.5/2 = 18.75, bigger than 1, so we continue.
Step 1c. the ones place of 18.75 is even so our current binary representation will be 011bin.
Step 2c. 18.75/2 = 9.375, bigger than 1, so we continue.
Step 1d. the ones place of 9.375 is odd so our current binary representation will be 1011bin.
Step 2d. 9.375/2 = 4.6375, bigger than 1, so we continue.
Step 1e. the ones place of 4.6375 is even so our current binary representation will be 0 1011bin.
Step 2e. 4.6375/2 = 2.34375, bigger than 1, so we continue.
Step 1f. the ones place of 2.34375 is even so our current binary representation will be 00 1011bin.
Step 2f. 2.34375/2 = 1.171875, bigger than 1, so we continue.
Step 1g. the ones place of 1.17... is even so our current binary representation will be 100 1011bin.
Step 2f. 1.17.../2 = 0.58..., less than 1, so we STOP.
75dec = 100 1011bin
The algorithm from binary to decimal.
How can we check that 100 1011bin is equal to 75dec? The easiest way is to match up the bits that are 1s with the powers of 2 they correspond to in the binary representation. The powers of two, starting with 2^0 = 1, are as follows:
1, 2, 4, 8, 16, 32, 64,...
Match the powers from lowest to highest with the bits from right to left.
1 -> 1
2 -> 1
4 -> 0
8 -> 1
16 -> 0
32 -> 0
64 -> 1
That's all the bits in our string, so we add up the powers of two that correspond to the bits that are 1, which are marked in bold in the list above.
64 + 8 + 2 + 1 = 75 in base 10.
The algorithm from hexadecimal to binary and back.
If we take a bit string of length 4, we can represent all the numbers from 0 to 15 in decimal. The idea of hexadecimal is to have a single numeral represent each of these bit patterns, so this means we need a total of 16 symbols instead of ten. Hexadecimal uses a, b, c, d, e and f as the extra symbols and the pattern is as follows
binary hexadecimal
0000______0
0001______1
0010______2
0011______30100______4
0101______5
0110______6
0111______71000______8
1001______9
1010______a (corresponds to 10 in decimal)
1011______b (corresponds to 11 in decimal)
1100______c (corresponds to 12 in decimal)
1101______d (corresponds to 13 in decimal)
1110______e (corresponds to 14 in decimal)
1111______f (corresponds to 15 in decimal)
This is why we put the courtesy gaps between binary numbers every four places starting from the right. Read each four bit pattern and make the translation. If a bitstring has less than four bits, fill in leading zeros to make it a four bit long string. For example, 11bin would become 0011bin, which translates to 3hex. Or 101bin would become 0101bin, or 5hex.
The translation can work in either direction, so f1dhex = 1111 0001 1101bin.
The algorithm from hexadecimal to decimal.
Step 1: Take the first digit on the left of the hexadecimal number and change it to decimal. This means a becomes 10, b becomes 11, ... up to f becomes 15. If the digit is already 9 or less, you don't have to change it. This number is the first pass at your running total.
Step 2: If there are still more digits, multiply your running total by 16, change the next digit to decimal and add that to the running total. Continue with step 2 until all digits are exhausted.
Example: f1dhex. The first digit on the left is f, which corresponds to 15 in decimal, so the running total starts at 15.
There are more digits still, so we multiply the total by 16 and add the next digit.
15x16 + 1 = 241, our new running total.
We still have digits, so we multiply the running total by 16 and add the next digit d, which corresponds to 13.
241x16 + 13 = 3,856 + 13 = 3,869
That's the last digit, so we should be done. f1dhex = 3869dec.
The algorithm from decimal to hexadecimal.
One way to do this is to go from decimal to binary, then binary to decimal. Let's take 3869dec and change it to binary. If we did everything right in the steps above, we should get the binary number 1111 0001 1101, which translates into f1dhex.
dividing 3869 by two, looking at the ones digit for even or odd, then dividing the new number by two, again and again until the division produces a number less than 1
3869___ 9 is odd, so the first bit on the right is 1bin.
1934.5___ 4 is even, so the bits are now 01bin.
967.25___ 7 is odd, so the bits are now 101bin.
483.625___ 3 is odd, so the bits are now 1101bin.
241.8125___ 1 is odd, bits are 1 1101bin.
120.9...____ 0 is even, bits are 01 1101bin.
60.45...____ 0 is even, bits are 001 1101bin.
30.226...___ 0 is even, bits are 0001 1101bin.
15.113...____ 5 is odd, bits are 1 0001 1101bin.
7.5566...____ 7 is odd, bits are 11 0001 1101bin.
3.778..._____ 3 is odd, bits are 111 0001 1101bin.
1.889..._____ 1 is odd bits are 1111 0001 1101bin.
0.944... less than 1 so done. The final bit string is 1111 0001 1101bin.
That bitstring does correspond to the hexadecimal number we hoped we would get, f1dhex.
Here are some practice problems with solutions.
Decimal, or base 10, is the number system we are used to. Binary, or base 2, is the number system a computer uses, storing all its information as a string of 1s and 0s. Hexadecimal, or base 16, is kind like a compromise, a way to easily represent binary numbers in a way that takes less writing and is easier for the human programming the machines to read.
The algorithm from decimal to binary.
Start with a number written in decimal representation. We are going to build its equivalent binary representation bit by bit from the ones place to the twos place to the fours place, etc., which means building from right to left.
Step 0. Start with a decimal number and an empty representation for the binary equivalent.
Step 1. Is the ones digit of the decimal representation even or odd? If even, put a 0 in the first place to left of the current binary representation. If odd, put a 1 in the first place to the left of the current binary representation.
Step 2. Divide the current decimal representation by 2. If the result is more than 1, go to Step 1. If it is less than 1, STOP. We now have the correct binary representation of the original decimal number.
Example. Let's change 75dec to its binary equivalent.
Step 1a. 75 is odd so our current binary representation will be 1bin.
Step 2a. 75/2 = 37.5, bigger than 1, so we continue.
Step 1b. the ones place of 37.5 is odd so our current binary representation will be 11bin.
Step 2b. 37.5/2 = 18.75, bigger than 1, so we continue.
Step 1c. the ones place of 18.75 is even so our current binary representation will be 011bin.
Step 2c. 18.75/2 = 9.375, bigger than 1, so we continue.
Step 1d. the ones place of 9.375 is odd so our current binary representation will be 1011bin.
Step 2d. 9.375/2 = 4.6375, bigger than 1, so we continue.
Step 1e. the ones place of 4.6375 is even so our current binary representation will be 0 1011bin.
Step 2e. 4.6375/2 = 2.34375, bigger than 1, so we continue.
Step 1f. the ones place of 2.34375 is even so our current binary representation will be 00 1011bin.
Step 2f. 2.34375/2 = 1.171875, bigger than 1, so we continue.
Step 1g. the ones place of 1.17... is even so our current binary representation will be 100 1011bin.
Step 2f. 1.17.../2 = 0.58..., less than 1, so we STOP.
75dec = 100 1011bin
The algorithm from binary to decimal.
How can we check that 100 1011bin is equal to 75dec? The easiest way is to match up the bits that are 1s with the powers of 2 they correspond to in the binary representation. The powers of two, starting with 2^0 = 1, are as follows:
1, 2, 4, 8, 16, 32, 64,...
Match the powers from lowest to highest with the bits from right to left.
1 -> 1
2 -> 1
4 -> 0
8 -> 1
16 -> 0
32 -> 0
64 -> 1
That's all the bits in our string, so we add up the powers of two that correspond to the bits that are 1, which are marked in bold in the list above.
64 + 8 + 2 + 1 = 75 in base 10.
The algorithm from hexadecimal to binary and back.
If we take a bit string of length 4, we can represent all the numbers from 0 to 15 in decimal. The idea of hexadecimal is to have a single numeral represent each of these bit patterns, so this means we need a total of 16 symbols instead of ten. Hexadecimal uses a, b, c, d, e and f as the extra symbols and the pattern is as follows
binary hexadecimal
0000______0
0001______1
0010______2
0011______30100______4
0101______5
0110______6
0111______71000______8
1001______9
1010______a (corresponds to 10 in decimal)
1011______b (corresponds to 11 in decimal)
1100______c (corresponds to 12 in decimal)
1101______d (corresponds to 13 in decimal)
1110______e (corresponds to 14 in decimal)
1111______f (corresponds to 15 in decimal)
This is why we put the courtesy gaps between binary numbers every four places starting from the right. Read each four bit pattern and make the translation. If a bitstring has less than four bits, fill in leading zeros to make it a four bit long string. For example, 11bin would become 0011bin, which translates to 3hex. Or 101bin would become 0101bin, or 5hex.
The translation can work in either direction, so f1dhex = 1111 0001 1101bin.
The algorithm from hexadecimal to decimal.
Step 1: Take the first digit on the left of the hexadecimal number and change it to decimal. This means a becomes 10, b becomes 11, ... up to f becomes 15. If the digit is already 9 or less, you don't have to change it. This number is the first pass at your running total.
Step 2: If there are still more digits, multiply your running total by 16, change the next digit to decimal and add that to the running total. Continue with step 2 until all digits are exhausted.
Example: f1dhex. The first digit on the left is f, which corresponds to 15 in decimal, so the running total starts at 15.
There are more digits still, so we multiply the total by 16 and add the next digit.
15x16 + 1 = 241, our new running total.
We still have digits, so we multiply the running total by 16 and add the next digit d, which corresponds to 13.
241x16 + 13 = 3,856 + 13 = 3,869
That's the last digit, so we should be done. f1dhex = 3869dec.
The algorithm from decimal to hexadecimal.
One way to do this is to go from decimal to binary, then binary to decimal. Let's take 3869dec and change it to binary. If we did everything right in the steps above, we should get the binary number 1111 0001 1101, which translates into f1dhex.
dividing 3869 by two, looking at the ones digit for even or odd, then dividing the new number by two, again and again until the division produces a number less than 1
3869___ 9 is odd, so the first bit on the right is 1bin.
1934.5___ 4 is even, so the bits are now 01bin.
967.25___ 7 is odd, so the bits are now 101bin.
483.625___ 3 is odd, so the bits are now 1101bin.
241.8125___ 1 is odd, bits are 1 1101bin.
120.9...____ 0 is even, bits are 01 1101bin.
60.45...____ 0 is even, bits are 001 1101bin.
30.226...___ 0 is even, bits are 0001 1101bin.
15.113...____ 5 is odd, bits are 1 0001 1101bin.
7.5566...____ 7 is odd, bits are 11 0001 1101bin.
3.778..._____ 3 is odd, bits are 111 0001 1101bin.
1.889..._____ 1 is odd bits are 1111 0001 1101bin.
0.944... less than 1 so done. The final bit string is 1111 0001 1101bin.
That bitstring does correspond to the hexadecimal number we hoped we would get, f1dhex.
Here are some practice problems with solutions.
Thursday, February 10, 2011
Practice problems for prime factorization.
Here's the link to problems with answers. If you need more, let me know.
Tuesday, February 8, 2011
Practical logarithmic problems
There was a 7.6 earthquake in Mindanao in the Philippines and a 5.7 aftershock three days later. Rounded to the nearest multiple of 10, how much stronger was the bigger quake?
One singer is measured at 64 dB. Eight singers at the same level would have eight times more energy. To the nearest decibel, what is the decibel level of the eight singer chorus?
Answers in the comments.
One singer is measured at 64 dB. Eight singers at the same level would have eight times more energy. To the nearest decibel, what is the decibel level of the eight singer chorus?
Answers in the comments.
Saturday, February 5, 2011
Friday, February 4, 2011
Underflow and Overflow on your calculator
Really big numbers and numbers really close to zero are written on your calculator in scientific notation, a x 10^b, where b is an integer and a, known as the significand, is a number more than or equal to 1 but less than 10, which is to say exactly one digit to the left of the decimal place. Some calculators will write this in the form a E b. For example, it's about 96,000,000 miles to the sun. A mile is 5,280 feet and a foot is 12 inches. This means the number of inches to the sun has more than ten digits, so the TI-83 will write the answer as 6.08256E12, which is their way of writing 6.08256 x 10^12, which we could say in words as about six trillion.
With the exception of the high end calculator the TI-89, most calculators have decided they won't display numbers where the exponent is greater than 99 or less than -99. Some numbers in probability are larger than 10^100 or smaller than 10^-100, so the need can arise to express these. We can do this by using our calculators to find two number that multiply to the number we want that the calculator can represent, then multiplying those numbers together by hand. It's not that difficult to multiply numbers in scientific notation. You just add the exponents together to get the new exponent and multiply the significands. Multiplying two number less than 10 can give you a product more than ten. If that happens, you divide the product by ten (move the decimal over to the left) and add 1 to the exponent.
Simple example: 2 x 10^90 x 7 x 10^80 would be 14 x 10^170, but this isn't scientific notation because 14 > 10. To change it to scientific, we change 14 to 1.4 x 10, which raises the exponent by 1, so in scientific notation the answer is 1.4 x 10^171.
Overflow example: 80! is more than 10^100, so we need to split it up into two factors.
Factor #1: 50! = 50 x 49 x 48...x 3 x 2 x 1 = 3.0414 x 10^64
Factor #2: 80 nPr 30 = 80 x 79 x 78... x 53 x 52 x 51 = 2.3532 x 10^54
Multiplying the powers of 10 together is just 10^(64+54) = 10^118.
3.0414 x 2.3532 = 7.15702..., so rounding to four places total, which is called four significant digits, the final answer would be 80! = 7.157 x 10^118.
Underflow example: 1/80! is less than 10^-100, so we need to split it up into two factors.
Factor #1: 1/50! = 1/(50 x 49 x 48...x 3 x 2 x 1) = 3.2879 x 10^-65
Factor #2: 1/(80 nPr 30) = 1/(80 x 79 x 78... x 53 x 52 x 51) = 4.2496 x 10^-55
Multiplying the powers of 10 together is just 10^(-66+-55) = 10^-120.
3.2879 x 4.2496 = 13.96338..., which is more than 10, so we change it to 1.396338 x 10^1, combine 10^1 with 10^-120 to get 10^-119, and the final answer is 1/80! = 1.396 x 10^-119.
Practice problems:
Overflow: 90!
Underflow: 1/90!
Answers in the comments.
With the exception of the high end calculator the TI-89, most calculators have decided they won't display numbers where the exponent is greater than 99 or less than -99. Some numbers in probability are larger than 10^100 or smaller than 10^-100, so the need can arise to express these. We can do this by using our calculators to find two number that multiply to the number we want that the calculator can represent, then multiplying those numbers together by hand. It's not that difficult to multiply numbers in scientific notation. You just add the exponents together to get the new exponent and multiply the significands. Multiplying two number less than 10 can give you a product more than ten. If that happens, you divide the product by ten (move the decimal over to the left) and add 1 to the exponent.
Simple example: 2 x 10^90 x 7 x 10^80 would be 14 x 10^170, but this isn't scientific notation because 14 > 10. To change it to scientific, we change 14 to 1.4 x 10, which raises the exponent by 1, so in scientific notation the answer is 1.4 x 10^171.
Overflow example: 80! is more than 10^100, so we need to split it up into two factors.
Factor #1: 50! = 50 x 49 x 48...x 3 x 2 x 1 = 3.0414 x 10^64
Factor #2: 80 nPr 30 = 80 x 79 x 78... x 53 x 52 x 51 = 2.3532 x 10^54
Multiplying the powers of 10 together is just 10^(64+54) = 10^118.
3.0414 x 2.3532 = 7.15702..., so rounding to four places total, which is called four significant digits, the final answer would be 80! = 7.157 x 10^118.
Underflow example: 1/80! is less than 10^-100, so we need to split it up into two factors.
Factor #1: 1/50! = 1/(50 x 49 x 48...x 3 x 2 x 1) = 3.2879 x 10^-65
Factor #2: 1/(80 nPr 30) = 1/(80 x 79 x 78... x 53 x 52 x 51) = 4.2496 x 10^-55
Multiplying the powers of 10 together is just 10^(-66+-55) = 10^-120.
3.2879 x 4.2496 = 13.96338..., which is more than 10, so we change it to 1.396338 x 10^1, combine 10^1 with 10^-120 to get 10^-119, and the final answer is 1/80! = 1.396 x 10^-119.
Practice problems:
Overflow: 90!
Underflow: 1/90!
Answers in the comments.
Thursday, February 3, 2011
Clarification on homework 2
On the homework, I used a symbol I didn't explain in class. On the third problem in the second section it looks like "60 raised to the power of 40", but the 40 is underlined. This means "60 fall 40", the falling factorial that shows up on most calculators as 60nPr40. The fourth problem in the section section is "60 raised to the power of 40". On many calculators, the button that means "raise to a power" looks like ^, which is pronounced caret.
I will put up some examples of underflow and overflow on Friday.
Subscribe to:
Posts (Atom)
