0x310 Arithmetic
1. Bitwise
1.1. Set Representation
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\)
The Go programming language book has a good code sample to show this in Chapter 3.1
var x uint8 = 1<<1 | 1<<5
var y uint8 = 1<<1 | 1 <<2
fmt.Printf("%08b\n", x) // "00100010", the set {1, 5}
fmt.Printf("%08b\n", y) // "00000110", the set {1, 2}
fmt.Printf("%08b\n", x&y) // "00000010", the intersection {1}
fmt.Printf("%08b\n", x|y) // "00100110", the union {1, 2, 5}
fmt.Printf("%08b\n", x^y) // "00100100", the symmetric difference {2, 5}
fmt.Printf("%08b\n", x&^y) // "00100000", the difference {5}
for i := uint(0); i < 8; i++ {
if x&(1<<i) != 0 { // membership test
fmt.Println(i) // "1", "5"
}
}
1.2. XOR
Problem (sum of all xor pairs)
Problem (ABC201 E - Xor distance)
2. Integer
2.1. Multiplication
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))
Algorithm (Karatsuba) efficient algorithm for big integer, reducing the standard complexity from \(O(n^2)\) to \(O(n^{\log_2 3})\) (around \(O(n^{1.5})\))
Basic idea is to apply the following steps recursively: Consider multiplication of \(x=x_1 b + x_0\) and \(y=y_1 b + y_0\), in the long multiplication's algorithm, we do 4 times of multiplications
Instead, compute the \(z_1\) with
Algorithm (Schönhage–Strassen) recursively apply FFT, complexity is \(O(n \log(n) \log\log(n))\), used in Great Internet Mersenne Prime Search
2.2. Division
Algorithm (Euclid) The Euclid's algorithm is used to find the gcd of two integers, it is from the Elements (300 B.C) and one of the oldest algorithm in the world.
int gcd(int a, int b) {
if (b==0) return a;
return gcd(b, a%b);
}
The complexity of Euclid can be estimated with the Fibonacci number \(F_k\) as follows
Theorem (Lame's theorem) For any integer \(k \geq 1\), if \(a > b \geq 1, b < F_{k+1}\), then the recursion call is less than \(k\) recursive.
This gives us the complexity of \(O(log_2(b))\)
Algorithm (extended Euclid) Euclid's algorithm can also be extended to solve the equation
or similarly
Consider we have solved the following equation and know \(x', y'\) \(\(bx' + (a \% b)y' = gcd(a,b)\)\)
We can rearange this into
when \(b=0\), the start point is
int extgcd(int a, int b, int&x, int& y) {
if d = a;
if (b != 0){
d = extgcd(b, a%b, y, x);
y -= (a/b)*x;
}
else{
x = 1; y=0;
}
return d;
}
2.3. Module
Theorem (Chinese remainder theorem) Let \(n=n_1 n_2 ... n_k\) where \(n_i\) are pairwise relatively prime. Consider the correspondence
where \(a \in Z_n, a_i \in Z_{n_i}\) and
Then this mapping is 1-to-1 correspondence between \(Z_n\) and \(Z_{n_1} \times Z_{n_2} \times ... \times Z_{n_k}\)
2.4. Primality Test
Problem (primality) Check whether a give integer is prime or not The most simple algorithm to check \(n\)'s primality is check all numbers up to \(\sqrt{n}\).
Algorithm (Sieve of Eratosthenes) complexity is \(O(n \log\log n)\), so nearly linear
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
Note that Carmichael numbers are exceptions to Fermat test (e.g: 561, 1105, ....)
Algorithm (Miller-Rabin) probablistic, check existence of square root Given \(n\), find \(s\) such that \(n-1 = 2^sq\) for some odd \(q\), then do the following test
- pick a random number \(a \in [1, n-1]\)
- if \(a^q=1\), then passes
- for \(i=[0, s-1]\), check whether \(a^{2^i q} = -1\), if so it passes
- otherwise \(n\) is composite.
The prob to fail to detect composite with \(k\) is around \((1/4)^k\)
Algorithm (AKS primality test) deterministic (PRIMES is in P)
2.4.1. Problems
Problem (abc206 e: divide both)
- problem: count coprime pair within \([L,R]\) range
- solution: inclusion-exclusion
Problem (abc212 g: power pair) - problem: count number of pair \(\{(x,y) | x^n=y (\mod p) \}\) - solution: 原始根を使って,\(an=b (mod p-1)\)に書き換える。そして\(g=gcd(a,g-1)\)のときに\((a,b)\)のカウントが\(p-1/g\)になることを注意して、gcdを\(p-1\)の約 数降順で数え上げる。降順DPで数える方法は206eと似ている
2.5. Factorization
Factorization problem is much more difficult than the primality test, which guarantees the safety of many cryptography schemes.
Algorithm(Pollard's rho) randomly generate \(x,y\) based on cycle-detection algorithm, then check \(gcd(x-y, n)\) until cycle detected.
- x ← 2, y ← 2; d ← 1
- While d = 1:
- x ← f(x)
- y ← f(f(y))
- d ← GCD(|x − y|, n)
- If d = n, return failure.
- Else, return d.
Its expected running time is proportional to the square root of the size of the smallest prime factor of the composite number being factorized
Algorithm(Number Field Sieve) I do not understand..
2.6. Pseudorandom Number Generator (PRNG)
Algorithm (Linear Congruence Generator) One of the oldest and best-known algorithm, many libraries (e.g: glibc) uses this to generate number.
Note recently there is some improved version of this: Permuted congruential generator (PCG), this is used in numpy random.
Algorithm (Mesenne Twister)
3. Float
3.1. Random Variable Generation
Algorithm (direct methods) If \(Y\) is a continuous random variable with cdf\(F_Y\), then random variable \(F^{-1}_Y(U)\) where \(U \sim \text{uniform}(0,1)\) has distribution \(F_Y\)
Generate a random variable \(u\), and solve it with respect to \(y\).
Algorithm (Box-Muller) Given two independent \(U_1, U_2 \sim \text{uniform}(0, 1)\), and set
then
Are independent \(n(0,1)\) random variables
4. Reference
- [1] Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.
- [2] Abelson, Harold, and Gerald Jay Sussman. Structure and interpretation of computer programs. The MIT Press, 1996.
- [3] 秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).
- [4] Donovan, Alan AA, and Brian W. Kernighan. The Go programming language. Addison-Wesley Professional, 2015.
- [5] Miller-Rabin test note