乘法总比除法好

这是基于欧几里得辗转相除法的扩展，是一个生成互质的随机数对的快速方法。

在这之前我从没想过，互质的整数还能用乘法算出来。

在这里碎碎念一下，如果我们将一系列小矩阵看作是卷积网络的很多层，把最大公约数看作是迭代开始的种子点，那么这就是一个

生成拥有指定最大公约数的整数对的 GAN 网络

欧几里得算法

考虑两个整数

$$\{a>b | a, b \in \mathcal{Z}^+\} $$

总有下式成立

$$\begin{cases} a = q_1 \cdot b + r_1\\ r_1 由于我们对两个正整数并没有特殊约束，因此这个方程可以迭代下去

$$\begin{cases} a=q_1 \cdot b + r_1 \\ b = q_2 \cdot r_1 + r_2 \\ r_1 = q_3 \cdot r_2 + r_3 \\ \dots \\ r_{n-3} = q_{n-1} \cdot r_{n-2} + r_{n-1} \\ r_{n-2} = q_{n} \cdot r_{n-1} + r_n \end{cases} $$

由于迭代关系可得，这些整数服从严格的递减关系

$$b>r_1>r_2>\dots >r_n $$

代数方程终止的条件是

$$\forall a, b, \exists n, r_n = 0 $$

也就是说，无论两个整数如何取值，迭代总能终止。并且不难发现

$$\begin{cases} r_{n-1} \mod r_{n-2} = 0 \\ r_{n-1} \mod r_i = 0, i=1, 2, \dots n-2 \\ r_{n-1} \mod b = 0 \\ r_{n-1} \mod a = 0 \end{cases} $$

易知，该数是递减序列中第一个拥有这个性质的数，因此可以说它是两个正整数的最大公约数。易见，该方法能够在有限时间内解决最大公约数问题，由于数列严格递减，因此时间复杂度为

$$\mathcal{O}(n) $$

另外，由于每次迭代几乎都能将余数的大小减半（事实上，衰减速度比 2 大得多），因此可以更加激进地说，时间复杂度为

$$\mathcal{O}(\log{n}) $$

唯一性

我们将代数方程组写成矩阵的形式

$$\begin{bmatrix} a \\ b \\ r_1 \\ \dots \\ r_{n-2} \end{bmatrix} = \begin{bmatrix} q_1 & 1 & \space & \space \\ \space &q_2 & 1 \\ \space &\space &\cdots \\ \space &\space &\space &q_{n-1} & 1 \\ \space &\space &\space &\space &q_n \\ \end{bmatrix} \cdot \begin{bmatrix} b \\ r_1 \\ \dots \\ r_{n-2} \\ r_{n-1} \end{bmatrix} $$

不难发现，当余数的递减序列确定后，除数序列也就确定了，反之亦然。因此，当两个整数给定后，除数和余数两个序列也确定了，反之亦然。

这样，就有一个初步的思路，就是从最大公约数出发，经过随机指定的除数序列，可以生成两个整数。这两个整数的最大公约数是指定的，除掉它之后，二者互质。这样做的好处是生成互质整数的时间复杂度是可以指定的，完全由除数序列的长度决定。但如果直接用大矩阵来做就需要引入动态规划，导致空间复杂度大增。因此考虑用矩阵乘法的方式进行代替。

矩阵连乘

如果把每次迭代都写成矩阵乘法的形式，我们有

$$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} b \\ r_1 \end{bmatrix} $$

在迭代过程中，这个等式变为

$$\begin{bmatrix} r_i \\ r_{i+1} \end{bmatrix} = \begin{bmatrix} q_{i+2} & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} r_{i+1} \\ r_{i+2} \end{bmatrix} $$

因此，迭代过程可以表示成矩阵的连乘

$$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} q_2 & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} r_{n-1} \\ 0 \end{bmatrix} $$

算法的输入只需要最大公约数和除数矩阵，即可得到满足要求的整数对

$$a, b = func(r_{n-1}, q_1, q_2, \dots q_n), n \in \mathcal{Z}^+ $$

在这里碎碎念一下，如果我们将一系列小矩阵看作是卷积网络的很多层，把最大公约数看作是迭代开始的种子点，那么这就是一个

生成拥有指定最大公约数的整数对的 GAN 网络

代码实现

代码的样例输出如下

import numpy as np

# Build and test iter decomp method
print('\n ---- Test decomp func ----')
a, b = sorted(np.random.randint(1, 1000, (2, )), reverse=True)
print(f'a={a}, b={b}')

def decomp(x, y):
    '''
    Solve q and r as x = q * y + r
    All numbers are positive int
    '''
    r = x % y
    q = x // y
    print(f'{x} = {q} x {y} + {r}')
    return q, r

decomp(a, b)

# Build and test compute common number func
print('\n ---- Test common number func ----')
a, b = sorted(np.random.randint(1, 100000, (2, )), reverse=True)

print(f'a={a}, b={b}')

def compute(a, b):
    '''
    Compute common number from a > b
    '''
    print(f'Compute: a={a}, b={b}')
    Q = []

    x = a
    y = b
    common = None

    for _ in range(100):
        q, r = decomp(x, y)

        if r == 0:
            common = y
            break

        x = y
        y = r

    print(f'common = {common}')
    return common

common = compute(a, b)

# Generate big numbers
print('\n ---- Generate big numbers ----')
n = 10
com = 133
Q = np.random.randint(5, 10, (n,))

print(f'n={n}, com={com}, Q={Q}')

m = np.eye(2)
for q in Q:
    m = np.matmul(m, [[q, 1], [1, 0]])
    
v = np.matmul(m, [com, 0]).astype(np.int64)

a, b = v
compute(a, b)
print(f'Generated: a={a}, b={b}, com={com}')

分类：

后端

标签：

后端

作者介绍