Transcript ppt

Number Theory Algorithms
Zeph Grunschlag
Copyright © Zeph Grunschlag,
2001-2002.
Agenda
Euclidean Algorithm for GCD
Number Systems


Decimal numbers (base-10)
Binary numbers (base-2)
 One’s complement
 Two’s complement

General base-b number systems
Arithmetic Algorithms



L11
Addition
Multiplication
Subtraction 1’s and 2’s complement
2
Euclidean Algorithm
m,n
Euclidean
Algorithm
gcd(m,n)
integer euclid(pos. integer m, pos. integer n)
x = m, y = n
while(y > 0)
r = x mod y
x=y
y=r
return x
L11
3
Euclidean Algorithm.
Example
gcd(33,77):
L11
Step
r = x mod y
x
y
0
-
33
77
4
Euclidean Algorithm.
Example
gcd(33,77):
L11
Step
r = x mod y
x
y
0
-
33
77
1
33 mod 77
= 33
77
33
5
Euclidean Algorithm.
Example
gcd(33,77):
Step
r = x mod y
x
y
0
-
33
77
77
33
33
11
1
2
L11
33 mod 77
= 33
77 mod 33
= 11
6
Euclidean Algorithm.
Example
gcd(33,77):
Step
r = x mod y
x
y
0
-
33
77
77
33
33
11
11
0
1
2
3
L11
33 mod 77
= 33
77 mod 33
= 11
33 mod 11
=0
7
Euclidean Algorithm.
Example
gcd(244,117):
L11
Step
r = x mod y
x
y
0
-
244
117
8
Euclidean Algorithm.
Example
gcd(244,117):
L11
Step
r = x mod y
x
y
0
-
244
117
1
244 mod 117 = 10
117
10
9
Euclidean Algorithm.
Example
gcd(244,117):
L11
Step
r = x mod y
x
y
0
-
244
117
1
244 mod 117 = 10
117
10
2
117 mod 10 = 7
10
7
10
Euclidean Algorithm.
Example
gcd(244,117):
L11
Step
r = x mod y
x
y
0
-
244
117
1
244 mod 117 = 10
117
10
2
3
117 mod 10 = 7
10 mod 7 = 3
10
7
7
3
11
Euclidean Algorithm.
Example
gcd(244,117):
L11
Step
r = x mod y
x
y
0
-
244
117
1
244 mod 117 = 10
117
10
2
3
4
117 mod 10 = 7
10 mod 7 = 3
7 mod 3 = 1
10
7
3
7
3
1
12
Euclidean Algorithm.
Example
gcd(244,117):
Step
r = x mod y
x
y
0
-
244
117
1
244 mod 117 = 10
117
10
2
3
4
117 mod 10 = 7
10 mod 7 = 3
7 mod 3 = 1
10
7
3
7
3
1
5
3 mod 1=0
1
0
By definition  244 and 117 are rel. prime.
L11
13
Euclidean Algorithm
Correctness
The reason that Euclidean algorithm
works is gcd(x,y ) is not changed from
line to line. If x’, y’ denote the next
values of x , y then:
gcd(x’,y’) = gcd(y, x mod y)
= gcd(y, x + qy)
(the useful fact)
= gcd(y, x )
(subtract y -multiple)
= gcd(x,y)
L11
14
Euclidean Algorithm
Running Time
EX: Compute the asymptotic running
time of the Euclidean algorithm in terms
of the number of mod operations:
L11
15
Euclidean Algorithm
Running Time
Assuming mod operation is O (1):
integer euclid(m, n)
x = m, y = n
while( y > 0)
r = x mod y
x=y
y=r
return x
O (1) +
?  ( O (1) +
O (1)
+ O (1)
+ O (1) )
+ O (1)
= ?  O(1)
Where “?” is the number of while-loop iterations.
L11
16
Euclidean Algorithm
Running Time
Facts: (x’ = next value of x, etc. )
1.
x can only be less than y at very
beginning of algorithm
–once x > y, x’ = y > y’ = x mod y
2. When x > y, two iterations of while loop
guarantee that new x is < ½ original x
–because x’’ = y’ = x mod y. Two cases:
I.
II.
L11
y > ½ x  x mod y = x – y < ½ x
y ≤ ½ x  x mod y < y ≤ ½ x
17
Euclidean Algorithm
Running Time
(1&2) After first iteration, size of x
decreases by factor > 2 every two
iterations.
I.e. after 2m+1 iterations,
x < original_x / 2m
Q: When –in terms of m– does this
process terminate?
L11
18
Euclidean Algorithm
Running Time
After 2m+1 steps, x < original_x / 2m
A: While-loop exits when y is 0, which is
right before “would have” gotten x =
0. Exiting while-loop happens when
2m > original_x, so definitely by:
m = log2 ( original_x )
Therefore running time of algorithm is:
O(2m+1) = O(m) = O (log2 (max(a,b)) )
L11
19
Euclidean Algorithm
Running Time
Measuring input size in terms of n = number of
digits of max(a,b):
n = (log10 (max(a,b)) ) = (log2 (max(a,b)) )
Therefore running time of algorithm is:
O(log2 (max(a,b)) ) = O(n)
(we assumed naively that mod is an O(1)
operation, so this estimate only holds for
fixed-size integers such as int’s and
long’s)
L11
20
Number Systems
Q: What does the string of symbols
2134
really mean as a number and why?
L11
21
Number Systems
A: 2 thousands 1 hundreds 3 tens and 4
= 2  103 + 1  102 + 3  101 + 4  100
But on the planet Ogg, the intelligent life
forms have only one arm with 5 fingers.
L11
22
Number Systems
So on Ogg, numbers are counted base 5.
I.e. on Ogg 2134 means:
2  53 + 1  52 + 3  51 + 4  50
To distinguish between these systems,
subscripts are used:
(2134)10 for Earth
(2134)5 for Ogg
L11
23
Number Systems
DEF: A base b number is a string of symbols
u = ak ak-1 ak-2 … a2 a1 a0
With the ai taken from {0,1,2,3,…,b-2,b-1}.
The string of symbols u represents the number
(u )b = ak bk + ak-1 bk-1 + . . . + a1 b + a0
NOTE: When b > 10, run out of decimal
number symbols so after 7, 8, 9 use capital
letters, starting from A, B, C, …
EG: base-2 (binary) 101, 00010
base-8 (octal ) 74, 0472
base-16 (hexadecimal ) 12F, ABCD
L11
24
Q:
Compute the base 10 version of these.
Number Systems
A: base-2 (binary) 101, 00010
(101)2 = 1  22 + 0  21 + 1  20 = 5
(00010)2 = 0(24+23+22+20) + 121 = 2
base-8 (octal ) 74, 0472
(74)8 = 7  81 + 4  80 = 60
(0472)8 = 4  82 + 7  81 + 2  80 = 314
base-16 (hexadecimal ) 12F, ABCD
(12F)16 = 1162+2161+15160 = 303
(ABCD)16=10163+11162+12161+13160
L11
25
= 43981
Number Systems
The binary and hexadecimal systems are
especially important in computer science
since binary is the most natural system for
bit-strings and hexadecimal for bytestrings (1 byte = 2 hexadecimals)
EG in HTML:
<font color="ff00ff"> Nice Color </font>
Q: What color will this become?
L11
26
Number Systems
A: "ff00ff" represents the rgb –value:
The first byte is for redness, the second
byte is for green-ness, and the last for
blue-ness. The HTML command above
specifies that there should be
1516 + 15 = 255 redness and blueness
values, but no green-ness at all. 255 is
the biggest possible byte value so this is
bright purple.
L11
27
Number Systems
Reverse Conversion
Would also like to convert arbitrary decimal
numbers into various bases, (without using
calculator-function [see Windows Calculator]).
EG: Back at Ogg. Convert 646 to base-5. Try to
do all operations base-5:
(646)10 = (11)5(20)52 + (4)5(20)5+ (11)5
= (11)5(400)5 + (130)5+ (11)5
= (4400)5 + (141)5
= (10041)5
Thinking like an Oggian hurts brain too much…
L11
28
Number Systems
Reverse Conversion
Systematic approach to converting bases.
Given an integer n and a base b find the string u
such that (u )b = n.
Pseudocode:
string represent(pos. integer n, pos. integer b)
q = n, i = 0
while( q > 0 )
ui = q mod b
q = q/b 
i = i +1
L11return ui ui-1 ui-2 … u2 u1 u0
29
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
L11
i
ui = q mod b
q = q/b 
-
-
646
30
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
L11
i
ui = q mod b
q = q/b 
0
-
646
646/5=129
646 mod 5 = 1
31
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
L11
i
ui = q mod b
q = q/b 
0
1
-
646
646/5=129
129/5=25
646 mod 5 = 1
129 mod 5 = 4
32
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
L11
i
ui = q mod b
q = q/b 
0
1
2
-
646
646/5=129
129/5=25
25/5=5
646 mod 5 = 1
129 mod 5 = 4
25 mod 5 = 0
33
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
L11
i
ui = q mod b
q = q/b 
0
1
2
3
-
646
646/5=129
129/5=25
25/5=5
5/5= 1
646 mod 5 = 1
129 mod 5 = 4
25 mod 5 = 0
5 mod 5 = 0
34
Number Systems
Reverse Conversion
EG: Convert 646 to Oggian (base-5):
i
ui = q mod b
q = q/b 
0
1
2
3
4
-
646
646/5=129
129/5=25
25/5=5
5/5= 1
1/5=0
646 mod 5 = 1
129 mod 5 = 4
25 mod 5 = 0
5 mod 5 = 0
1 mod 5 = 1
Reading last column in reverse: 10041
L11
35
Number Systems
Blackboard Exercise
Some number-theory facts are base-dependent.
For example First-Grade Teacher’s Rule:
A base-10 number is divisible by 3 iff the sum of
its digits are. Formally, let
n = (uk uk-1 uk-2 … u2 u1 u0)10. Then:
 k 
n mod 3    ui  mod 3
 i 0 
EG: 3|12135 because 3|(1+2+1+3+5 = 12)
L11
36
Arithmetical Algorithms
Let’s write down some familiar
arithmetical algorithms. Conveniently,
they run the same in any number base.
In some cases, such as addition, there
are asymptotically faster approaches,
but these are the simplest procedures
and tend to be fastest for relatively
small (e.g. < 1000 bits) number sizes.
L11
37
Arithmetical Algorithms
Addition
Numbers are added from least significant
digit to most, while carrying any
overflow resulting from adding a
column:
base-10
Carry:
1
L11
1
1
7
4
6
3
+
2
9
0
9
1
0
3
7
2
x
+y
1
base-16
A
4
F
0
+
C
B
0
9
1
6
F
F
9
38
Arithmetical Algorithms
Addition of Positive Numbers
string add(strings xk xk-1…x1x0, yk yk-1…y1y0 , int base)
carry = 0, xk+1 = yk+1 = 0
for(i = 0 to k+1)
digitSum = carry + xi + yi
zi = digitSum mod base
carry = digitSum /base 
return zk+1zk zk-1…z1z0
L11
39
1’s Complement
2’s Complement
The binary number system makes some
operations especially simple and efficient
under certain representations.
Two such representations are


1’s complement
2’s complement
Each makes subtraction much simpler.
Each has disadvantage that number length is
pre-determined. What’s actually done in
practice.
L11
40
1’s Complement
Fix k bits. (EG, k = 8 for bytes)
Represent numbers with |x | < 2k-1
Most significant bit tells the sign


0 –positive
1 –negative
Positive numbers the same as standard binary
expansion
Negative numbers gotten by taking the
boolean complement, hence nomenclature
L11
41
1’s Complement
Examples
k = 8:
00010010 represents 18
11101101 represents -18
Notice that adding these two representations as
usual results in the number 11111111, which
by definition is negative 00000000 or 0. This
leads to:
Guess: adding numbers with mixed sign is
the same as adding positive numbers
Unfortunate: 0 is not represented uniquely
L11
42
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
43
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
44
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
0
1
1
45
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
46
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
1
1
0
0
1
1
47
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
48
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
49
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
50
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
51
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
52
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
0
53
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
0
54
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
1
0
55
1’s Complement
Addition
Addition is the same as usual binary addition except:
if the final carry is 1, cycle the carry to the least
significant digit:
00010010 represents 18, 11110011 represents -12
Sum 00000110 represents 6:
Carry:
x
+y
pre-sum
overflow
answer
L11
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
0
56
2’s Complement
Fixes the non-uniqueness of zero problem
Adding mixed signs still easy
No cycle overflow
Java’s approach (under the hood)
Same fixed length k , sign convention, and
definition of positive numbers as with 1’s
complement
Represent numbers with -2(k-1)  x < 2(k-1)

L11
EG. Java’s byte ranges from -128 to +127
57
2’s Complement
Negative numbers:
1. Compute 1’s complement
2. Add 1

Not as simple as negating 1’s complement
Summarize: -x = ¬x + 1. EG:
00010010 represents 18, 11101101 + 1 =
11101110 represents -18. Add together:
00000000 (over-flow is lost).
Q: What are the ranges of Java’s 32-bit int and
64-bit long? (All of Java’s integer types use
2’s complement)
L11
58
2’s Complement
A:
1) 32-bit int’s: Largest int =
011111….1 = 231-1 = 2,147,483,647
Smallest int =
100000….0 = -231 = -2,147,483,648
2) 64-bit long’s: Largest long =
011111….1 = 263-1 =
9,223,372,036,854,775,807
Smallest int =
100000….0 = -262 =
-9,223,372,036,854,775,808
L11
59
2’s Complement
Addition
Addition is the same as usual binary addition no
exceptions!!
11101110 represents -18, 11110100 represents -12
Sum 11111010 represents -30:
Carry:
x
+y
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
0
As a final check take the negative to see if get 30:
(¬11100010+1) = (00011101+1) = 00011110. YES!
L11
60
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
1
1
0
0
1
0
1
1
Add rows:
L11
61
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
1
1
1
0
0
0
1
0
1
1
1
1
Add rows:
L11
62
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
0
1
1
1
0
0
0
0
0
1
0
1
0
1
1
1
Add rows:
L11
63
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
1
1
Add rows:
L11
64
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
Add rows:
L11
65
Arithmetical Algorithms
Positive Binary Multiplication
Long multiplication simplifies in binary because
multiplying by 2k amounts to left-shifting k-places
(<<k), and each time multiply either by 0·2k or 1·2k.
EG:
x
y
1·(x<<0)
0·(x<<1)
0·(x<<2)
1·(x<<3)
Add rows:
L11
1
1
0
0
1
0
0
1
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
66
Arithmetical Algorithms
Binary Multiplication
bitstring multiply(bitstrings xk xk-1…x1x0, yk yk-1…y1y0)
x = xk xk-1…x1x0
p = 0 // the partial product
for(i = 0 to k+1)
if(yi == 1)
p = add(p , x << i ) // prev. algorithm
return p
L11
67