Feb 11 2007

Greatest Common Divisor & Least Common Multiple

Euclid’s GCD Algorithm:

  • Fundamentals:

    • gcd(N, M) = gcd(M, N mod M)
    • gcd(N, 0) = N
  • Implementation in C:
    • int Euclid_gcd_recursive(int a, int b)
{
  if (b == 0)
    return a;
  return Euclid_gcd_recursive(b, a % b);
}

int Euclid_gcd_iterative(int a, int b)
{
  int t;
  while (b) {
    a = b;
    b = t % b;
  }
  return a;
}
  • Complexity: O(lg(min{a, b})) arithmetic operations.

Stein’s GCD Algorithm:

  • Fundamentals:

    • gcd(N, M) = 2*gcd(N/2, M/2), both N and M are even
    • gcd(N, M) = gcd(N/2, M), N is even but M is odd
    • gcd(N, M) = gcd(N, N-M), both N and M are odd
    • gcd(N, 0) = N
  • Advantages: only uses additions, subtractions and bit-shift operations.
  • Implementation in C:
    • int Stein_gcd(int a, int b)
{
  int t, c = 1;
  if (a < b) {
    t = a;
    a = b;
    b = t;
  }
  while (b) {
    if (a % 2) {
      if (b % 2) {
        a -= b;
      }
      else {
        b >>= 1;
      }
    }
    else if (b % 2) {
      a >>= 1;
    }
    else {
      c <<= 1;
      a >>= 1;
      b >>= 1;
    }

    if (a < b) {
      t = a;
      a = b;
      b = t;
    }
  }
  return a * c;
}
  • Complexity:

Extensions:

  1. Given integers a and b, a slight extension of Euclid's gcd algorithm enables us to find integers x and y

    ax + by = gcd(a, b)
  2. One step further, we can find intergers u and v
    au + bv = 0

    or

    |au| = |bv| = lcm(a, b)

    3. Example 1: a = 51, b = 21

    51 = 2 * 21 + 9 9 = 51 - 2 * 21
    21 = 2 * 9 + 3 3 = 21 - 2 * 9
    = 21 - 2 * (51 - 2 * 21)
    = -2 * 51 + 5 * 21
    9 = 3 * 3 + 0 0 = 9 - 3 * 3
    = 51 - 2 * 21 - 3 * (-2 * 51 + 5 * 21)
    = 7 * 51 - 17 * 21

    Thus x = -2, y = 5 works, and gcd(51, 21) = 3;
    u = 7, v = -17 works, and lcm(51, 21) = 51 * 7 = 21 * 17 = 357.
    Example 2: a = 101, b = 12

    101 = 8 * 12 + 5 5 = 101 - 8 * 12
    12 = 2 * 5 + 2 2 = 12 - 2 * 5
    = 12 - 2 * (101 - 8 * 12)
    = -2 * 101 + 17 * 12
    5 = 2 * 2 + 1 1 = 5 - 2 * 2
    = 101 - 8 * 12 - 2 * (-2 * 101 + 17 * 12)
    = 5 * 101 - 42 * 12
    2 = 2 * 1 + 0 0 = 2 - 2 * 1
    = -2 * 101 + 17 * 12 - 2 * (5 * 101 - 42 * 12)
    = -12 * 101 + 101 * 12

    Thus x = 5, y = -42 works, and gcd(101, 12) = 1;
    u = -12, v = 101, and lcm(101, 12) = 12 * 101 = 1212.

  3. From the second extension, it can be deduced by replacing all minus by plus in the second column that
    |au| + |bv| = 2*lcm(a, b)

    Thus, we've got an lcm algorithm derived from Euclid's gcd algorithm.

Euclid-based LCM Algorithm:

  • Fundamentals: the process of Euclid's GCD algorithm.

  • Implementation in C:
    • int lcm(int a, int b)
{
  int t;
  int u, v;
  if (a < b) {
    t = a;
    a = b;
    b = t;
  }

  u = a;
  v = b;

  while (b) {
    u += a / b * v;
    t = u;
    u = v;
    v = t;
    t = a;
    a = b;
    b = t % b;
  }
  return v / 2;
}
  • Complexity: O(lg(min{a, b})) arithmetic operations.

Variant of Euclid-based LCM Algorithm:

  • Fundamentals: divisions and modulo operations are decayed to subtractions, while multiplications are decayed to additions.
  • Advandages: only uses additions and subtractions.
  • Implementation in C:
    • int lcm(int a, int b)
{
  int u = a, v = b;

  while (a != b) {
    if (a > b) {
      a -= b;
      u += v;
    }
    else {
      b -= a;
      v += u;
    }
  }
  return (u + v) / 2;
}
  • Complexity:

no comments   |  tags: | posted in development

Feb 2 2007

Classic Sorting Algorithms

  • Comparison Sort
    1. Selection Sort
      • advantages: least data movement (N – 1 exchanges).
      • disadvantages: does not make good use of the initial order of the keys, and one pass through the keys does not give any hint to the next pass.
      • stability: stable.
      • operations: N2/2 comparisons, N – 1 exchanges.
      • space: in-space sort, O(N).
      • implementation in C: 
        void selection_sort(Item a[], int l, int r)
{
  int i, j;
  for (i = l; i < r; ++i)
  {
    int min = i;
    for (j = i + 1; j <= r; ++j)
      if (less(a[j], a[min])) min = j;
    exch(a[i], a[min]);
  }
}
    2. Insertion Sort
      • advantages: make good use of the initial order of the keys, so efficient for partially sorted sequences; uses much fewer comparisons than selection sort and bubble sort.
      • disadvantages:
      • stability: stable.
      • operations: the running time is proportional to the total number of inversions in the sequence, and is irrelevant of the distribution of the inversions.
        • best case: N comparisons, no movement.
        • average case: N2 / 4 comparisons, N2 / 4 movements.
        • worse case: N2 / 2 comparisons, N2 / 2 movements.
      • space: in-space sort, O(N).
      • implementation in C: 
        void insertion_sort(Item a[], int l, int r)
{
  int i;
  /* find the minimun first to use as a sentinel */
  for (i = l + 1; i <= r; ++i)
    compexch(a[l], a[i]);
  for (i = l + 2; i <= r; ++i)
  {
    int j = i;
    Item v = a[i];
    while (less(v, a[j - 1]))
    {
      a[j] = a[j - 1];
      --j;
    }
    a[j] = v;
  }
}
    3. Bubble Sort
      • advantages: efficient for one type of partially sorted sequences which has few right inversions corresponding to each element, such as a new sequence built from a sorted sequence by appending a few elements.
      • disadvantages: slowest in most cases.
      • stability: stable.
      • operations: the number of passes through the sequence during sorting is equal to the maximum number of right inversions corresponding to one element.
        • best case: O(N2) comparisons(can be reduced to N by tracing whether the sequence is already in order), no movement.
        • average case: O(N2) comparisons, N2 / 4 exchanges(can be reduced to N2 / 4 movements).
        • worst case: O(N2) comparisons, N2 / 2 exchanges(can be reduced to N2 / 2 movements).
      • space: in-space sort, O(N).
      • implementation in C: 
        void bubble_sort(Item a[], int l, int r)
{
  int i, j;
  for (i = l; i < r; ++i)
    for (j = r; j > i; --j)
      compexch(a[j-1], a[j]);
}
    4. Shell Sort
      • advantages: extension of insert sort with more effective(long distance) movements; insensitive to the input.
      • disadvantages: hard to analyze the running time and to choose a best increment sequence; bad increment sequences exist.
      • stability: stable.
      • operations:
        • less than O(N3/2) comparisons for the increments 1 4 13 40 121 364 1093 3280 9841 ... (s(i+1) = s(i) * 3 + 1)
        • less than O(N4/3) comparisons for the increments 1 8 23 77 281 1073 4193 16577 ... (s(i) = 4i + 3*2i + 1)
        • less than O(Nlog2N) comparisons for the increments 1 2 3 4 6 9 8 12 18 27 16 24 36 54 81 ...
          (that is Pratt increment sequence: each number in the triangle is two times the number above and to the right of it and also three times the number above and to the left of it.

                   1

       2   3

     4   6   9

  8   12   18  27

16  24   36   54  81

          )

      • space: in-space sort, O(N).
      • implementation in C: 
        /* increment sequence: 1 4 13 40 121 364 1093 3280 9841 ... */
void shell_sort(Item a[], int l, int r)
{
  int i, j, h;
  for (h = 1; h <= (r - l) / 9; h = 3 * h + 1) ;
  for ( ; h > 0; h /= 3)
    for (i = l + h; i <= r; ++i)
    {
      int j = i;
      Item v = a[i];
      while (j >= l + h && less(v, a[j - h]))
      {
        a[j] = a[j-h];
        j -= h;
      }
      a[j] = v;
    }
}
    5. Quick Sort
      • advantages: has extremely short inner loop, thus small constant factor; has been thoroughly analyzed, extensively verified, wisely refined, thus can be widely used in a broad variety of practical sorting applications.
      • disadvantages: little mistakes in the implementation easily go unnoticed and badly impair the performance for some sequences; sensitive to input, thus worst case can not be completely avoided.
      • stability: unstable.
      • operations:
        • best case: NlgN comparisons.
        • average case: 2NlnN comparisons.
        • worse case: N2 / 2 comparisons.
      • space: in-space sort, O(N) + O(N)(taken by recursion stack, can be reduced to O(lgN) by first sorting the smaller subsequence and tail-recursion removal).
      • implementation in C: 
        void sort(Item a[], int l, int r)
{
  quick_sort(a, l, r);
  /* refinement 1: insertion sort is efficient for the almost sorted
   * file left by the prudent quick sort */
  insertion_sort(a, l, r);
}

void quick_sort(Item a[], int l, int r)
{
  int i, j;

  stackinit();
  push2(l, r);
  while (!stackempty())
  {
    l = pop();
    r = pop();
    /* refinement 1: use cutoff for small subfiles to limit the number
     * of small problems at deep recursion, thus to save a major part
     * of recursive subroutine call overhead */
    if (r-1 < M) continue;
    partition(a, l, r, &i, &j);
    /* refinement 2: use explicit pushdown stack to do tail-recursion
     * removal, and sort small subfile first to reduce the maximum stack depth */
    if (i-l > r-i) {
      push2(l, i-1);
      push2(i+1, r);
    }
    else {
      push2(i+1, r);
      push2(l, i-1);
    }
  }
}

void partition(Item a[], int l, int r, int *ii, int *jj)
{
  int i,j, k, p, q;
  Item v;

  /* refinement 3: median-of-three(sampling) partitioning */
  exch(a[(l+r)/2], a[r-1]);
  compexch(a[l], a[r-1]);
  compexch(a[l], a[r]);
  /* the median is left at the right end to serve as the pivot */
  compexch(a[r], a[r-1]);

  v = a[r];
  i = l-1;
  j = r;
  p = l-1;
  q = r;

  for (;;)
  {
    while (less(a[++i], v)) ;   /* a[l] serves as sentinel */
    while (less(v, a[--j])) ;   /* a[r] serves as sentinel */
    if (i >= j) break;
    if (eq(a[i], v)) {
      ++p;
      /* throw equals to the ends */
      exch(a[p], a[i]);
      if (eq(a[j], v)) {
        --q;
        /* throw equals to the ends */
        exch(a[q], a[j]);
      }
      else {
        /* a[j] will be processed in next loop */
        ++j;
      }
    }
    else if (eq(v, a[j])) {
      --q;
      /* throw equals to the ends */
      exch(a[q], a[j]);
      /* a[i] will be processed in next loop */
      --i;
    }
    else {
      exch(a[i], a[j]);
    }
  }

  /* crossing at an element equal to v */
  if (i == j) {
    exch(a[i+1], a[r]);
    j = i-1;
    i = i+2;
  }
  else {
    exch(a[i], a[r]);
    j = i-1;
    i = i+1;
  }
  /* refinement 4: three-way partitioning */
  /* move the equals from ends to middle */
  /* move the lesses to the left subfile */
  /* move the largers to the right subfile */
  for (k = l  ; k <= p; ++k, --j) exch(a[k], a[j]);
  for (k = r-1; k >= q; --k, ++i) exch(a[k], a[i]);
  *ii = i;
  *jj = j;
}
    6. Merge Sort
      • advantages: it has a guaranteed O(NlgN) running time; it is normally implemented such that it accesses the data primarily sequentially, thus it is the method of choice for sorting a linked list, where sequential access is the only kind of access available.
      • disadvantages: extra space proportional to N is needed.
      • stability: stable.
      • operations: NlgN comparisons
      • space: O(N) extra space is needed.
      • implementation in C: 
        void mergeAB(Item c[], Item a[], int N, Item b[], int M)
{
  int i, j, k;
  for (i = 0, j = 0, k = 0; ; ++k) {
    if (i == N) break;
    if (j == M) break;
/*     c[k] = less(b[i], a[i]) ? b[i++] : a[j++];     */
    /* keep stability in the assumption that a[] is before b[] in the
     * original sequence */
    c[k] = less(b[i], a[i]) ? b[i++] : a[j++];
  }

  if (i == N) {
    for ( ; k < M + N; ++k) {
      c[k] = b[j++];
    }
  }
  else {                        /* j == M */
    for ( ; k < M + N; ++k) {
      c[k] = a[i++];
    }
  }
}

Item aux[maxN];

void merge_sortAB(Item a[], Item b[], int l, int r)
{
  int m = (l + r) / 2;
  if (r - 1 < 10) {             /* improvement 1: cutoff for small subfiles */
    insertion_sort(a, l, r);
    return;
  }

  merge_sortAB(b, a, l, m);
  merge_sortAB(b, a, m + 1, r);
  mergeAB(a + l, b + l, m - l + 1, b + m + 1, r - m);
}

void merge_sort(Item a[], int l, int r)
{
  int i;
  /* improvement 2: merge data in a flip-flop manner between two arrays
   * to eliminate the time taken to copy to the auxiliary array in
   * every merging */
  for (i = l; i <= r; ++i) aux[i] = a[j];
  merge_sortAB(a, aux, l, r);
}
    7. Heap Sort
      • advantages: it has a guaranteed O(NlogN) running time sort; it is in-place sort; it is insensitive to input.
      • disadvantages: no good locality for cache mechanisms to take advantage of.
      • stability: unstable.
      • operations: fewer than 2NlogN(bottom-up heap construction) or 3NlogN(top-down heap construction) comparisons and exchanges.
      • space: in-space sort, O(N).
      • implementation in C: 
        void heap_sort(Item a[], int l, int r)
{
  int k, N = r - l + 1;
  Item *pq = a + l - 1;
  for (k = N/2; k >= 1; k--)
    fixDown(pq, k, N);
  while (N > 1) {
    exch(pq[1], pq[N]);
    fixDown(pq, 1, --N);
  }
}

void fixDown(Item a[], int k, int N)
{
  int i;
  while (2 * k <= N) {
    i = 2 * k;
    if (i < N && less(a[i], a[i+1])) ++i;
    if (!less(a[k], a[i])) break;
    exch(a[k], a[j]);
    k = i;
  }
}
  • Non-comparison Sort
    1. Counting Sort
      • advantages: efficient when the key values are limited in a relatively small range with respect to the size of sequence.
      • disadvantages:
      • stability: stable.
      • operations: the running time is proportional to max{max key value(M), size of sequence(N)}, thus linear when the range of key values is within a constant factor of the sequence size.
      • space: O(N) + O(N) + O(M).
      • implementation in C: 
        void counting_sort(int a[], int l, int r)
{
  int i, j, cnt[M];
  int b[maxN];
  for (j = 0; j < M; ++j) cnt[j] = 0;
  for (i = l; i <= r; ++i) ++cnt[a[i] + 1];
  for (j = 1; j < M; ++j) cnt[j] += cnt[j - 1];
  for (i = l; i <= r; ++i) b[cnt[a[i]]++] = a[i];
  for (i = l; i <= r; ++i) a[i] = b[i];
}
    2. Radix Sort
      • advantages: it is based on key-indexed counting sort.
      • disadvantages: it does not work well on files that contain huge numbers of duplicate keys that are not short, because all the bits of equal keys are examined.
      • stability: stable.
      • Approaches:
        1. MSD (most-significant-digit) Radix Sort
          • advantages: generalizes quick sort; examines the minimum amount of information necessary to get a sorting job done; is insensitive to key order.
          • disadvantages: is sensitive to the distribution of key values, and does not work well for nonrandom data; produces a large number of small or even empty bins in the late stages.
          • operations: can be sublinear in the total number of data bins, because the whole key does not necessarily have to be examined; O(NlogRN) on average; within a small constant factor of the number of bits in the keys in the worst case.
          • space: extra O(N) + O(R) space is required in each pass.
          • Implementation in C: 
            #define bin(A) l+count[A]
#define digit(A, B) ...          /* retrive the Bth digit of A */
void radixMSD(Item a[], int l, int r, int w)
{
  int i, j, count[R+1];
  if (w > bytesword) return;
  /* cutoff for small file */
  if (r-l <= M) {
    insertion(a, l, r);
    return;
  }
  for (j = 0; j < R; j++) count[j] = 0;
  for (i = l; i <= r; i++)
    count[digit(a[i], w) + 1]++;
  for (j = 1; j < R; j++)
    count[j] += count[j-1];
  for (i = l; i <= r; i++)
    aux[l+count[digit(a[i], w)]++] = a[i];
  for (i = l; i <= r; i++) a[i] = aux[i];
  radixMSD(a, l, bin(0)-1, w+1);
  for (j = 0; j < R-1; j++)
    radixMSD(a, bin(j), bin(j+1)-1, w+1);
}
        2. Three-Way Radix Quick Sort (comparison sort)
          • advantages: hybrid of quick sort and MSD radix sort.
            • comparison with MSD: avoids large number of empty bins, adapts well to handle duplicate keys, keys that fall into a small range, small files, different types of nonrandomness; no auxiliary array is required; is independent of the radix.
            • comparison with quick sort: avoid redundant comparisons over all the equal leading bytes which are already compared during the previous stages.
          • disadvantages: three-way partition is slow compared with multiway partition that extra exchanges are required to get the equivalent partitioning effect.
          • operations: 2NlnN byte comparisons on average.
          • space: in-place sort, O(N).
          • Implementation in C: 
            #define ch(A) digit(A, D)
void quicksortX(Item a[], int l, int r, int D)
{
  int i, j, k, p, q;
  int v;
  if (r-l <= M) {
    insertion(a, l, r);
    return;
  }
  v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
  while (i < j)
  {
    while (ch(a[++i]) < v) ;
    while (v < ch(a[--j])) if (j == l) break;
    if (i > j) break;
    exch(a[i], a[j]);
    if (ch(a[i])==v) { p++; exch(a[p], a[i]); }
    if (v==ch(a[j])) { q--; exch(a[j], a[q]); }
  }
  /* all are equal at digit D */
  if (p == q)
  {
    if (v != END_OF_KEY) quicksortX(a, l, r, D+1);
    return;
  }
  if (ch(a[i]) < v) i++;
  for (k = l; k <= p; k++, j--) exch(a[k], a[j]);
  for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
  quicksortX(a, l, j, D);
  if1 i++;
  if (v != END_OF_KEY) quicksortX(a, j+1, i-1, D+1);
  quicksortX(a, i, r, D);
}
        3. LSD (least-significant-digit) Radix Sort
          • advantages: it involves extremely simple control structures and its basic operations are suitable for machine-language implementation, which can directly adapt to special-purpose high-performance hardware; it has moderate performance independent of the input.
          • disadvantages: does no work unless the sort method used is stable; is based on fixed-length key; may do unnecessary work on the right parts of the keys; key abstraction operations are not as efficient as general comparison operations in conventional programming environments, so a more costly inner loop than quick sort or merge sort.
          • operations: N(w/lgR) byte comparisons with w-bit keys.
          • space: extra O(N) + O(R) space is required.
          • Implementation in C: 
            void radixLSD(Item a[], int l, int r)
{
  int i, j, w, count[R+1];
  for (w = bytesword-1; w >= 0; w--)
  {
    for (j = 0; j < R; j++) count[j] = 0;
    for (i = l; i <= r; i++)
      count[digit(a[i], w) + 1]++;
    for (j = 1; j < R; j++)
      count[j] += count[j-1];
    for (i = l; i <= r; i++)
      aux[count[digit(a[i], w)]++] = a[i];
    for (i = l; i <= r; i++) a[i] = aux[i];
  }
}

Definitions:

  • Inversion: An inversion is a pair of keys that are out of order in the sequence.
  • Left inversion: The number of larger elements to the left of an element.
  • Right inversion: The number of smaller elements to the right of an element.


Footnotes:
  1. i == r) && (ch(a[i]) == v [↩]

no comments   |  tags: | posted in development