0x310 Arithmetic


Following are useful bitwise operations of set representations

  • $\emptyset: 0$
  • $\{ i \}: 1 << i$
  • $\{0, 1, …, n-1\}: (1<<n) -1$
  • $i \in S: (S >>i) \& 1$
  • $S \cup \{ i \} : S | 1 << i$
  • $S \ \{ i \}: S \& ~(1<<i)$
  • $S \cup T: S | T$
  • $S \cap T: S \& T$



Algorithm (Russian Peasant Method) multiply a, b by recursively doubling a and halve b, run in log complexity

(define (multi a b)
  (define (multi-iter a b s)
    (cond ((= b 1) (+ a s))
          ((even b) (multi-iter (double a) (halve b) s))
          (else (multi-iter a (- b 1) (+ s a)))))
  (multi-iter a b 0))

Primality Test

Problem (primality) Check whether a give integer is prime or not

Algorithm (Sieve of Eratosthenes) deterministic $O(\sqrt{n})$

Algorithm (Fermat test) probablistic $O(\log(n))$. To test primality of $n$, randomly select a number $a < n$, check whether $a^n$ is congruent to $a$ under base of $n$. This is based on the Fermat Little Theorem such that if $n$ is prime, then

$$\forall(a < n) a^n \equiv a \mod n$$

Note that Carmichael numbers are exceptions to Fermat test (e.g: 561, 1105, ….)

Algorithm (Miller-Rabin) probablistic, check existence of square root

Algorithm (AKS primality test) deterministic (PRIMES is in P)



Matrix Multiplication

Eigenvalue and Eigenvectors

Algorithm (QR algorithm) To find the eigenvalue of a given matrix. Iteratively compute $A_k = Q_k R_k$, then construct $A_{k+1} = R_k Q_k$ where $A_{k+1} \sim A_k$ and it converges to a triangular matrix (Schur form), in which eigenvalue can be easily identified



Algorithm (Simpson) Approximating definite integral as follows. Usually works very well

$$\int_{a}^{b} f(x) dx = \frac{dx}{3} (f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + 2f(x_4) … + 4f(x_{n-1}) + f(x_n)$$