4.2 Integer Representations and Algorithms Flashcards
Theorem 1
of allowed bases..:
base b expansion of n ?
Let b be an integer greater than 1. Then if n is a positive integer, it can be expressed uniquely
in the form
n = akb^(k) + ak−1b^(k−1) + ⋯ + a1b + a0,
where k is a nonnegative integer, a0, a1, … , ak are nonnegative integers less than b, and
ak ≠ 0.
Its also denoted by :
(akak−1 … a1a0)b
Common bases in comp sci:
Base 2 : Binary Expansion
Base 8 : Octal
Base 16 : Hexadecimal
Hexadecimal and Binary interconversion :
fact
Each hexadecimal digit can be represented using four bits. For instance, we see that
(1110 0101)2 = (E5)16 because (1110)2 = (E)16 and (0101)2 = (5)16.
Bytes, which are bit
strings of length eight, can be represented by two hexadecimal digits.
Base conversion:
We will now describe an algorithm for constructing the base b expansion of an integer n. First, divide n by b to obtain a quotient and remainder, that is,
n = bq0 + a0, 0 ≤ a0 < b.
The remainder, a0, is the rightmost digit in the base b expansion of n. Next, divide q0 by b to
obtain
q0 = bq1 + a1, 0 ≤ a1 < b.
We see that a1 is the second digit from the right in the base b expansion of n. Continue this
process, successively dividing the quotients by b, obtaining additional base b digits as the remainders. This process terminates when we obtain a quotient equal to zero. It produces the base
b digits of n from the right to the left.
ALGORITHM 1 Constructing Base b Expansions:
What kinda algo is this u think?
procedure base b expansion(n, b: positive integers with b > 1)
q := n
k := 0
while q ≠ 0
ak := q mod b
q := q div b
k := k + 1
return (ak−1,… , a1, a0) {(ak−1 … a1a0)b is the base b expansion of n}
Algorithm 1 can be thought of as a greedy algorithm, because the base b
digits are taken as large as possible in each step.
CONVERSION BETWEEN BINARY, OCTAL, AND HEXADECIMAL EXPANSIONS
each octal digit corresponds to a block of three binary digits and each hexadecimal digit corresponds to a block of four binary digits.
just know binary expansions of numbers 0-15.
ALGORITHM 2 Addition of Integers.
How many additions of bits are required to use Algorithm 2 to add two integers with n bits (or
less) in their binary representations?
To add a and b, first add their rightmost bits. This gives
a0 + b0 = c0 ⋅ 2 + s0,
where s0 is the rightmost bit in the binary expansion of a + b and c0 is the carry, it’s either 0 or 1. Then add the next pair of bits and the carry,
a1 + b1 + c0 = c1 ⋅ 2 + s1,
where s1 is the next bit (from the right) in the binary expansion of a + b, and c1 is the carry.
procedure add(a, b: positive integers)
{the binary expansions of a and b are (an−1an−2 … a1a0)2
and (bn−1bn−2 … b1b0)2, respectively}
c := 0
for j := 0 to n − 1
d := ⌊(aj + bj + c)∕2⌋
sj := aj + bj + c − 2d
c := d
sn := c
return (s0, s1,… , sn) {the binary expansion of the sum is (snsn−1 … s0)2}
number of additions of bits used by Algorithm 2 to add two n-bit integers is O(n)
Multiplication Algorithm concept:
Using the distributive law, we see that
ab = a(b020 + b121 + ⋯ + bn−12n−1)
= a(b020) + a(b121) + ⋯ + a(bn−12n−1).
We first note that abj = a if bj = 1 and abj = 0 if bj = 0.
Each time we multiply a term by 2, we shift its binary expansion one place to the left and add a
zero at the tail end of the expansion. Consequently, we can obtain (abj)2^j by shifting the binary
expansion of abj j places to the left, adding j zero bits at the tail end of this binary expansion.
Finally, we obtain ab by adding the n integers abj
2^j
, j = 0, 1, 2, … , n − 1.
ALGORITHM 3 Multiplication of Integers.
procedure multiply(a, b: positive integers)
{the binary expansions of a and b are (an−1an−2 … a1a0)2
and (bn−1bn−2 … b1b0)2, respectively}
for j := 0 to n − 1
if bj = 1 then cj := a shifted j places
else cj := 0
{c0, c1,… , cn−1 are the partial products}
p := 0
for j := 0 to n − 1
p := add(p, cj)
return p {p is the value of ab}efficient algorithms time complexity?
Surprisingly, there are more efficient algorithms than the conventional algorithm for multiplying integers. One such algorithm, which uses O(n^1.585) bit operations to multiply n-bit numbers, will be described in Section 8.3.
ALGORITHM FOR div AND mod concept:
Given integers a and d, d > 0, we can find q =
a div d and r = a mod d.
when a is positive
we subtract d from a as many times as necessary until what is left is less than d.
The number of
times we perform this subtraction is the quotient and what is left over after all these subtractions
is the remainder.
ALGORITHM 4 Computing div and mod.
Bit operations:
Bit operations of more efficient algo:
procedure division algorithm(a: integer, d: positive integer)
q := 0
r := |a|
while r ≥ d
r := r − d
q := q + 1
if a < 0 and r > 0 then
r := d − r
q := −(q + 1)
return (q, r) {q = a div d is the quotient, r = a mod d is the remainder}
uses O(q log a) bit operations More effiecient : O(log a ⋅ log d) bit operations
Modular Exponentiation:
how to make it fast:
we can avoid using large amount of memory if we
compute b^n mod m by successively computing b^k mod m for k = 1, 2, … , n using the fact that
b^(k+1) mod m = b(b^k mod m) mod m(1 ≤ b < m.)
Use binary expansion of n, say n = (ak−1 … a1a0)2, to compute b^n.
b^n = b^(ak−1⋅2^(k−1) +⋯+a1⋅2+a0 )= b^(ak−1⋅2^(k−1) )
⋯ b^(a1⋅2) ⋅ b^(a0) .
This shows that to compute bn, we need only compute the values of b, b2, (b2)^2 = b^4, (b^4)^2 = b^8, … , b^2^k
. Once we have these values, we multiply the terms b^2^j
in this list, where aj = 1. (For
efficiency and to reduce space requirements, after multiplying by each term, we reduce the result
modulo m.)
ALGORITHM 5 Fast Modular Exponentiation.
Bit operations?
procedure modular exponentiation(b: integer, n = (ak−1ak−2 … a1a0)2,
m: positive integers)
x := 1
power := b mod m
for i := 0 to k − 1
if ai = 1 then x := (x ⋅ power) mod m
power := (power ⋅ power) mod m
return x{x equals bn mod m}
uses O((log m)^2 log n) bit operations to find b^n mod m
