Texts: Algorithms Comparison
Given two algorithms "function divide(x, y)" in my lecture note Ch 00_02_IntroFoundation_ProgCorrectionLec.pptx, (posted in the Purdue.brightspace.com), the first one is iterative and the second one is recursive. The operators used are: "shift right one bit", "shift left one bit", copy, add (+), compare two contents of given variables (such as ≥), assign (:=), and call statement (such as a recursive call statement).
Algorithm Ia: function divide(x, y)
Input: Two n-bit integers x and y, where y ≥ 1.
Output: The quotient and remainder of x divided by y.
if x = 0, then return (q, r) := (0, 0);
q := 0;
r := x;
while (r ≥ y) do // takes n iterations for the worst case.
{
q := q + 1;
r := r – y
}; // O(n) for each r – y, where y is n bits long.
return (q, r);
Algorithm Ib: function divide(x, y)
Input: Two n-bit integers x and y, where y ≥ 1.
Output: The quotient and remainder of x divided by y.
if (x = 0) then return (q, r):=(0, 0);
(q, r) := divide(└x/2┘, y )
q := 2 * q, r := 2 * r;
if (x is odd) then r := r + 1;
if (r ≥ y) then //requires n-bits right shift
// shift left one bit.
// needs c*n-bits
{
r := r – y;
q := q + 1
};
return (q, r);
(I.ab) Give the input and output specifications for:
(I.a) for the algorithm Ia?
(I.b) for the algorithm Ib?
(I.cd) What is the input size for:
(I.c) for the algorithm Ia?
(I.d) for the algorithm Ib?
(I.ef) What is the basic operation for:
(I.e) for the algorithm Ia?
(I.f) for the algorithm Ib?
(I.g) In algorithm Ib, state the functionality for the following statements?
q := 2 * q, r := 2 * r; // shift left one bit.
if (x is odd) then r := r + 1; // needs c*n-bits
if (r ≥ y) then // additions
{
r := r – y;
q := q + 1
};