Transcript Integers and Algorithms

Section 2.5
Integers and Algorithms
1
Euclidean algorithm for finding
gcd
• Where L is a larger number, and S is a
smaller number, to find gcd(L,S):
– divide L by S to obtain: L = S * c + r where c is
some constant and r is the remainder
– next, find gcd(S,r) using the same method
– continue as long as r > 0; the last r > 0 is the
gcd
2
Example
Find gcd(45, 12)
gcd(45, 12) = gcd (12, 9) because 45 = 12 * 3 + 9
gcd(12, 9) = gcd (9, 3) because 12 = 9 * 1 + 3
gcd(9, 3) = 3 because 9 = 3 * 3 + 0
Therefore gcd(45, 12) = 3
3
Example
Find gcd(271, 83)
gcd(271, 83) = gcd(83, 22) because 271 = 83 * 3 + 22
gcd(83, 22) = gcd(22, 17) because 83 = 22 * 3 + 17
gcd(22, 17) = gcd(17, 5) because 22 = 17 * 1 + 5
gcd(17, 5) = gcd(5, 2) because 17 = 5 * 3 + 2
gcd(5, 2) = 1 because 5 = 2 * 2 + 1
Since 1 is the last non-zero remainder, gcd(271, 83) = 1
and 271 and 83 are relatively prime
4
More on Euclidean Algorithm
• Euclidean algorithm is based on this lemma:
– Let a = bq + r where a, b, q and r are integers
– Then gcd(a,b) = gcd(b,r)
• C++ code for Euclidean Algorithm:
int gcd(int a, int b)
{
int remainder;
while (b != 0)
{
remainder = a % b;
a = b;
b = remainder;
}
return a;
}
5
Representation of Integers
• We are used to expressing integers as base
10, or decimal numbers:
– Each digit represents a number multiplied by
power of 10, with the rightmost digit being
multiplied by 100
– The sum of the digits represents the value
– For example, 472 = 4(102)+7(101)+2(100)
6
Representation of Integers
• Any base can be used, with the same
method employed
• Computers typically use base 2 (binary),
base 8 (octal) and base 16 (hexadecimal) to
represent integers
7
Binary Representation
• Digits are 0s and 1s
• The value of a binary expansion of a
number is the sum of all digits multiplied by
the power of 2 represented by their position,
with the rightmost digit being position 0 and
the leftmost nth position being position n-1
8
Binary Example
1011111 =
1*20 + 1*21 + 1*22 + 1*23 + 1*24 + 0*25 + 1*26
= 1 + 2 + 4 + 8 + 16 + 0 + 64
= 95
9
Hexadecimal Representation
• Digits range 0 .. 9 and A .. F
– A = 10, B = 11, … F = 15
• Hex to decimal conversion example:
14A0E =
14*160 + 0*161 + 10*162 + 4*163 + 1*164
= 14 + 0
+ 2560 + 16384 + 65536
= 84,494
10
Conversion from hex to binary,
and vice-versa
• Each hex digit represents 4 binary digits, or
bits, since 16 = 24
• Table below shows conversion:
Hex
1
2
3
4
Bin
0001
0010
0011
0100
Hex
5
6
7
8
Bin
0101
0110
0111
1000
Hex
9
A
B
C
Bin
1001
1010
1011
1100
Hex
D
E
F
Bin
1101
1110
1111
11
Algorithm for base b expansion
of integer n
• Divide n by b, obtaining quotient & remainder:
n = bq0 + a0 where 0 <= a0 < b
remainder (a0) is rightmost digit in base b expansion
• Divide q0 by b, obtaining:
q0 = bq1 + a1 (0 <= a1 < b)
a1 is second digit from right in base b expansion
• Continue successive divisions until we obtain a
q=0
12
Example
Find octal (base 8) expansion of 474510
4745 =
593 =
74 =
9=
1=
8 * 593 + 1 (rightmost digit)
8 * 74 + 1
8*9+2
8*1+1
8*0+1
(leftmost digit)
Result is 112118
13
C++ for base expansion
algorithm (for base <= 10)
int baseExpand(int n, int b)
{
int k = 0, digit, expansion = 0;
while (n != 0)
{
digit = n % b;
n = n / b;
expansion = expansion + digit * pow(10,k);
k++;
}
return expansion;
}
14
Binary Addition
• Suppose a & b are binary numbers; they can
be represented as:
a = (an-1an-2 … a1a0)
b = (bn-1bn-2 … b1b0)
where n is the number of digits - note that this is
string notation, not indicative of multiplication
15
Binary Addition
• To add a and b, start with rightmost bits:
a0 + b0 = s0 + c0 * 2
where s is the sum and c is the carry (which may
be 0)
• Proceed to next bit, adding previous carry:
a1 + b1 + c0 = s1 + c1 * 2
16
Binary Addition
• Continue process until you reach the last bit
of either number:
an-1 + bn-1 + cn-2 = sn-1 + cn-1 * 2
• If the carry is not 0, it will be the leading bit
of the result
• If the numbers are not the same length, the
carry would be added to the next bit of the
longer number, and the carry from this
would be added to the next bit, etc.
17
Binary Addition Example
Let a = 1110, b = 1001; find a + b
1110 a0 = 0, b0 = 1
+ 1001 a0 + b0 = 1 + 2*0
--------10111 a2 = 1, b2 = 0, c1 = 0
a2 + b2 + c1 = 1 + 2*0
a1 = 1, b1 = 0, c0 = 0
a1 + b1 + c0 = 1 + 2*0
a3 = 1, b3 = 1, c2 = 0
a3 + b3 + c2 = 1 + 1 + 2*0
a4 = 0, b4 = 0, c3 = 1
a 4 + b4 + c 3 = 0 + 1
18
Pseudocode for Addition
Algorithm
Procedure add (input: positive integers a & b)
carry = 0
for (counter = 0; counter < n; counter++)
temp = acounter + bcounter + carry/2
sumcounter = acounter + bcounter + carry – 2 * temp
carry = temp
sumn = carry
19
Multiplication of Binary Integers
• Suppose we have 2 n-bit integers a and b;
by distributive law, we have:
n-1
n-1
ab = a *  bj2j
=  a(bj2j)
j=0
j=0
• Note: abj = a if bj =1, abj = 0 if bj = 0
• Multiply by 2 means shift left and add 0 at
end of expansion
20
Multiplication Example
1110
* 1001
--------1110
0000
0000
1110
-----------1111110
shift
shift
shift
add
21
Pseudocode for multiplication
algorithm
Procedure multiply(inputs: a and b, binary expansions of integers with n digits)
for (counter = 0; counter < n; counter++)
if bcounter == 1
ppcounter = a shifted counter spaces
(partial product counter)
else
ppcounter = 0
product = 0
for (counter = 0; counter < n; counter++)
product = product + ppcounter
22
Section 2.5
Integers and Algorithms
-ends-
23