This code generates all the subsets of {1, 2, ..., n} and prints them.

This also contains a very fast binary counter implementation.

See this for further explanations.

   1  
   2  #include <stdio.h>
   3  
   4  /* Applies the mask to a set like {1, 2, ..., n} and prints it */
   5  void printv(int mask[], int n) {
   6  	int i;
   7  	printf("{ ");
   8  	for (i = 0; i < n; ++i)
   9  		if (mask[i])
  10  			printf("%d ", i + 1); /*i+1 is part of the subset*/
  11  	printf("\b }\n");
  12  }
  13  
  14  /* Generates the next mask*/
  15  int next(int mask[], int n) {
  16  	int i;
  17  	for (i = 0; (i < n) && mask[i]; ++i)
  18  		mask[i] = 0;
  19  
  20  	if (i < n) {
  21  		mask[i] = 1;
  22  		return 1;
  23  	}
  24  	return 0;
  25  }
  26  
  27  int main(int argc, char *argv[]) {
  28  	int n = 3;
  29  
  30  	int mask[16]; /* Guess what this is */
  31  	int i;
  32  	for (i = 0; i < n; ++i)
  33  		mask[i] = 0;
  34  
  35  	/* Print the first set */
  36  	printv(mask, n);
  37  
  38  	/* Print all the others */
  39  	while (next(mask, n))
  40  		printv(mask, n);
  41  
  42  	return 0;
  43  }

Selectv returns the position of the nth smallest number in the list.

Selectv modifies the list.

   1  
   2  #include <stdio.h>
   3  
   4  typedef struct {
   5  	int len;
   6  	int e[102];
   7  } List;
   8  
   9  void printv(char *msg, List l) {
  10  	printf("%s", msg);
  11  	int i;
  12  	for (i = 0; i < l.len; ++i)
  13  		printf("%d ", l.e[i]);
  14  	printf("\n");
  15  }
  16  
  17  int pivot(List *l, int p, int r) {
  18  	int x = l->e[r];
  19  	int i = p - 1;
  20  	int j = r + 1;
  21  	
  22  	while (1) {
  23  		do {
  24  			++i;
  25  		} while (l->e[i] < x);
  26  		do {
  27  			--j;
  28  		} while (l->e[j] > x);
  29  	
  30  		//printf("%d %d\n", i, j);
  31  		
  32  		if (i < j) {
  33  			int aux = l->e[i];
  34  			l->e[i] = l->e[j];
  35  			l->e[j] = aux;
  36  		} else
  37  			return i - 1;
  38  	}
  39  }
  40  
  41  
  42  int selectv(List *l, int nrp, int p, int r) {
  43  	//printf("p, r: %d, %d\n", p, r);
  44  	//printf("nrp: %d\n", nrp);
  45  	//printv("l: ", *l);
  46  	
  47  	if (p == r)
  48  		return l->e[p];
  49  	
  50  	if (p < r) {
  51  		int q = pivot(l, p, r);
  52  		
  53  		//getchar();
  54  		
  55  		if (q - p + 1< nrp)
  56  			return selectv(l, nrp - (q - p) - 1, q + 1, r);
  57  		return selectv(l, nrp, p, q);
  58  	}
  59  	return -1;
  60  }
  61  
  62  int main(int argc, char *argv[]) {
  63  	List l;
  64  	l.len = 100;
  65  	int i;
  66  	for (i = 0; i < l.len; ++i)
  67  		l.e[i] = l.len - i;
  68  	
  69  	int nth = 56;
  70  	printf("%d: %d\n", nth, selectv(&l, nth, 0, l.len - 1));
  71  	
  72  	//printv("L: ", l);
  73  	
  74  	return 0;
  75  }
  76  

Qucksort written in C. Uses the Hoare partition algorithm.

   1  
   2  typedef struct {
   3  	int len;
   4  	int elem[50240];
   5  } vector;
   6  
   7  void printv(char *str, vector v) {
   8  	printf("%s", str);
   9  	int i = 0;
  10  	for (; i < v.len; ++i)
  11  		printf("%d ", v.elem[i]);
  12  	printf("\n");
  13  }
  14  
  15  #define MAX(a, b) ((a > b) ? (a) : (b))
  16  #define MIN(a, b) ((a < b) ? (a) : (b))
  17  
  18  int partition(vector *v, int p, int r) {
  19  	int x;
  20  	if (p + 3 < r)
  21  		x = MIN(v->elem[p], MAX(v->elem[p+1], v->elem[p+2]));
  22  	else
  23  		x = v->elem[p];
  24  	
  25  	int i = p - 1;
  26  	int j = r + 1;
  27  	while (1) {
  28  		do {
  29  			--j;
  30  		} while (v->elem[j] > x);
  31  		do {
  32  			++i;
  33  		} while (v->elem[i] < x);
  34  
  35  		if (i < j) {
  36  			int aux = v->elem[j];
  37  			v->elem[j] = v->elem[i];
  38  			v->elem[i] = aux;
  39  		} else
  40  			return j;			
  41  	}
  42  }
  43  
  44  void quicksort_real(vector *v, int p, int r) {
  45  	if (p < r) {
  46  		int q = partition(v, p, r);
  47  		quicksort_real(v, p, q);
  48  		quicksort_real(v, q + 1, r);
  49  	}
  50  }
  51  
  52  void quicksort(vector *v) {
  53  	printf("Quicksort...\n");
  54  	quicksort_real(v, 0, v->len - 1);
  55  }

Implements the classic Merge-sort algorithm.

Time: theta(lg(n))
Space: theta(n)

   1  
   2  #include <stdio.h>
   3  #include <stdlib.h>
   4  #include <string.h>
   5  
   6  void printv(char* in, int *v, int n) {
   7  	printf("%s", in);
   8  	int i = 0;
   9  	for (; i < n; ++i)
  10  		printf("%d ", v[i]);
  11  	printf("\n");
  12  }
  13  
  14  void merge(int *v, int p, int q, int r) {
  15  	int i = p;
  16  	int j = q + 1;
  17  	
  18  	int *tmp = (int*)malloc((r - p + 1) * sizeof(int));
  19  	int k = 0;
  20  	
  21  	while ((i <= q) && (j <= r)) {
  22  		if (v[i] < v[j])
  23  			tmp[k++] = v[i++];
  24  		else
  25  			tmp[k++] = v[j++];
  26  	}
  27  	
  28  	while (i <= q)
  29  		tmp[k++] = v[i++];
  30  	
  31  	while (j <= r)
  32  		tmp[k++] = v[j++];
  33  	
  34  	memcpy(v + p, tmp, (r - p + 1) * sizeof(int));
  35  	free(tmp);
  36  }
  37  
  38  void mergeS(int *v, int p, int r) {
  39  	if (p < r) {
  40  		int q = (p + r) / 2;
  41  		mergeS(v, p, q);
  42  		mergeS(v, q + 1, r);
  43  		merge(v, p, q, r);
  44  	}
  45  }
  46  
  47  int main(int argc, char *argv[]) {
  48  	int n = 10;
  49  	int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};
  50  	
  51  	printv("V: ", v, n);
  52  	mergeS(v, 0, n - 1);
  53  	printv("V: ", v, n);
  54  	
  55  	return 0;
  56  }

Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach.

Time: O(lg(n))
Memory: O(n)

   1  
   2  #include <stdio.h>
   3  
   4  int gcd(int a, int b) {
   5  	int r = a % b;
   6  	while (r) {
   7  		a = b;
   8  		b = r;
   9  		r = a % b;
  10  	}
  11  	return b;
  12  }
  13  
  14  int gcdv(int *v, int p, int r) {
  15  	if (r == p + 1) {
  16  		//printf("%d,%d: %d\n", p, r, gcd(v[p], v[r]));
  17  		return gcd(v[p], v[r]);
  18  	}
  19  	
  20  	if (r == p) {
  21  		//printf("%d: %d\n", r, v[r]);
  22  		return v[p];
  23  	}
  24  	
  25  	int q = (p + r) / 2;
  26  	//printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r)));
  27  	return gcd(gcdv(v, p, q), gcdv(v, q + 1, r));
  28  }
  29  
  30  int main(int argc, char *argv[]) {
  31  	int v[] = {45, 60, 125, 345, 65, 9875, 4555};
  32  	
  33  	printf("GCD: %d\n", gcdv(v, 0, 6));
  34  	
  35  	return 0;
  36  }
  37  

Pollard's rho heuristic is a method used to find a number's factors. This is faster than the classic brute-force, try every number until sqrt(n) method, but it's results are highly unpredictable.

This just prints the factors.

   1  
   2  import sys
   3  import random
   4  
   5  def Euclid(a, b):
   6    while b != 0:
   7      r = a % b
   8      a = b
   9      b = r
  10    return a
  11  
  12  def PollardRho(n):
  13    i = 1
  14    x = random.randint(0, n - 1)
  15    y = x
  16    k = 2
  17    tried = set()
  18    tried.add(x)
  19    while True:
  20      i = i + 1
  21      x = (x ** 2 - 1) % n
  22      if x in tried:
  23        return
  24      tried.add(x)
  25      d = Euclid(y - x, n)
  26      if d != 1 and d != n:
  27        print d # d is a factor. Print it.
  28      if i == k:
  29        y = x
  30        k = 2 * k
  31  
  32  def main(argv):
  33    PollardRho(int(argv[0]))
  34  
  35  if __name__ == "__main__":
  36      main(sys.argv[1:])

The Miller-Rabin primality test.

MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not. This is an extremley fast algorithm designed to test very large numbers.

s is the number of tests to perform. The chance that Rabin-Miller is mistaken about a number (i.e. thinks it's prime, but it's not) is 2^(-s). So, a value of 50 for s is more than enough for any imaginable goal (2^(-50) is 8.8817841970012523e-16).

   1  
   2  import sys
   3  import random
   4  
   5  def toBinary(n):
   6    r = []
   7    while (n > 0):
   8      r.append(n % 2)
   9      n = n / 2
  10    return r
  11  
  12  def test(a, n):
  13    """
  14    test(a, n) -> bool Tests whether n is complex.
  15  
  16    Returns:
  17      - True, if n is complex.
  18      - False, if n is probably prime.
  19    """
  20    b = toBinary(n - 1)
  21    d = 1
  22    for i in xrange(len(b) - 1, -1, -1):
  23      x = d
  24      d = (d * d) % n
  25      if d == 1 and x != 1 and x != n - 1:
  26        return True # Complex
  27      if b[i] == 1:
  28        d = (d * a) % n
  29    if d != 1:
  30      return True # Complex
  31    return False # Prime
  32  
  33  def MillerRabin(n, s = 50):
  34    """
  35      MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not
  36  
  37      Returns:
  38        - True, if n is probably prime.
  39        - False, if n is complex.
  40    """
  41    for j in xrange(1, s + 1):
  42      a = random.randint(1, n - 1)
  43      if (test(a, n)):
  44        return False # n is complex
  45    return True # n is prime
  46  
  47  def main(argv):
  48    print MillerRabin(int(argv[0]), int(argv[1]))
  49  
  50  if __name__ == "__main__":
  51    main(sys.argv[1:])

Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation:
d = ax + by

   1  
   2  def euclidExtended(a, b):
   3    if b == 0:
   4      return a, 1, 0
   5    dd, xx, yy = euclidExtended(b, a % b)
   6    d, x, y = dd, yy, xx - int(a / b) * yy
   7    return d, x, y
   8  

Euclid(a, b) calculates the largest common denominator d, and returns it.

Uses the well-known Euclid's algorithm.

   1  
   2  def euclid(a, b):
   3    while b != 0:
   4      r = a % b
   5      a = b
   6      b = r
   7    return a

Compute Easter date in NASM.

   1  
   2  segment .text
   3    global easter_asm
   4  
   5  ;typedef struct {
   6  ;  unsigned short d;
   7  ;  unsigned short m;
   8  ;} Date;
   9  
  10  ;void easter_asm(unsigned short Y, Date *d)
  11  ;   computes the Easter date for the year Y and stores it in d
  12  ;
  13  ;Parameters
  14  ;   Y - the year
  15  ;   d - the Date struct in which to store the result
  16  
  17  %define d [ebp + 12]
  18  %define Y [ebp + 8]
  19  easter_asm:
  20    enter 0, 0
  21    sub esp, 28
  22    %define G [ebp - 4]
  23    %define C [ebp - 8]
  24    %define X [ebp - 12]
  25    %define Z [ebp - 16]
  26    %define D [ebp - 20]
  27    %define E [ebp - 24]
  28    %define N [ebp - 28]
  29  
  30    ; int G = (Y % 19) + 1;
  31    xor edx, edx
  32    mov eax, Y
  33    mov ebx, 19
  34    div ebx
  35    inc edx
  36    mov G, edx
  37  
  38    ; int C = (int)(Y / 100) + 1;
  39    xor edx, edx
  40    mov eax, Y
  41    mov ebx, 100
  42    div ebx
  43    inc eax
  44    mov C, eax
  45  
  46    ; int X = 3 * C / 4 - 12;
  47    xor edx, edx
  48    mov eax, C
  49    mov ebx, 4
  50    div ebx
  51    mov ebx, 3
  52    mul ebx
  53    sub eax, 12
  54    mov X, eax
  55  
  56    ; int Z = (8 * C + 5) / 25 - 5;
  57    xor edx, edx
  58    mov eax, C
  59    mov ebx, 8
  60    mul ebx
  61    add eax, 5
  62    mov ebx, 25
  63    div ebx
  64    sub eax, 5
  65    mov Z, eax
  66  
  67    ; int D = 5 * Y / 4 - X - 10;
  68    xor edx, edx
  69    mov eax, Y
  70    mov ebx, 5
  71    mul ebx,
  72    mov ebx, 4
  73    div ebx
  74    sub eax, X
  75    sub eax, 10
  76    mov D, eax
  77  
  78    ; int E = (11 * G + 20 + Z - X) % 30;
  79    mov eax, G
  80    mov ebx, 11
  81    mul ebx
  82    add eax, 20
  83    add eax, Z
  84    sub eax, X
  85    xor edx, edx
  86    mov ebx, 30
  87    div ebx
  88    mov E, edx
  89  
  90    cmp dword E, 24
  91    jne after_e1
  92    inc dword E
  93    jmp after_e2
  94  after_e1:
  95    cmp dword E, 25
  96    jne after_e2
  97    cmp dword G, 11
  98    jle after_e2
  99    inc dword E
 100  after_e2:
 101  
 102    ; int N = 44 - E;
 103    mov eax, 44
 104    sub eax, E
 105    mov N, eax
 106  
 107    cmp dword N, 21
 108    jge after_n
 109    add dword N, 30
 110  after_n:
 111    ; N = N + 7 - ((D + N) % 7);
 112    mov eax, N
 113    add eax, D
 114    xor edx, edx
 115    mov ebx, 7
 116    div ebx
 117    add dword N, 7
 118    sub N, edx
 119  
 120    mov eax, d
 121  
 122    ; N is the nuber of day from March 1 to easter. Check if easter is in April.
 123    cmp dword N, 31
 124    jle in_march
 125    mov bl, N
 126    sub bl, 31
 127    mov [eax], bl
 128    mov word [eax + 2], 4
 129    jmp quit
 130  in_march:
 131    mov bl, N
 132    mov [eax], bl
 133    mov word [eax + 2], 3
 134  quit:
 135    leave
 136    ret