Python 大整数矩阵乘积的精度和性能
Python precision and performance on large integer matrix products
我想计算两个量A和B的乘积，然后计算乘积对F的模。一般来说，A和B是大数矩阵，所以操作是常规的矩阵乘法。为简单起见，让我们将 A 和 B 视为标量。我测试过的所有方法的 Python 代码如下：
from __future__ import division
import numpy as np
from sympy import Matrix
from sympy import *
A = 2251875000001
B = 28839630
F = 33232924804801
#Method 1: pure Python
C1 = (A*B) % F
A_mat = np.matrix(A).astype(np.int64)
B_mat = np.matrix(B).astype(np.int64)
#Method 2: numpy matrices and pure Python
C2 = (A_mat*B_mat) % F
#Method 3: numpy
C3 = np.dot(A, B) % F
#Method 4: numpy
C4 = np.dot(A_mat, B_mat) % F
#Method 5: Python objects and numpy
A_mat2 = np.matrix(A, dtype=object)
B_mat2 = np.matrix(B, dtype=object)
C5 = np.dot(A_mat2, B_mat2) % F
C5 = np.concatenate(C5).astype(np.int64)
#Method 6: sympy
A_sp = Matrix(1,1,[A])
B_sp = Matrix(1,1,[B])
C6 = A_sp*B_sp
f = lambda x: x%F
C6 = C6.applyfunc(f)
print(C6)
C6 = matrix2numpy(C6, dtype='int64')
现在结果应该是
(2251875000001 * 28839630) mod 33232924804801 = 25112458407047
当我运行上面的代码时，我得到的C1 == 25112458407047对于这个例子是正确的，但是当我测试大矩阵的乘法时，我用这个方法得到的大部分条目都是错误的.但是，C2、C3、C4 的值都等于 12062945446480，这是错误的。 C5 和 C6 也计算正确。
您可以假设 int64 的 64 位精度对于我正在使用的数字来说绰绰有余，但默认的 32 位精度不够。
我尝试了 Sympy（参见方法 6），因为根据 here.
它应该具有任意精度
我正在使用 Python 2.7.14、Numpy 1.14.2 和 Sympy 1.1.1。
我的第一个问题是为什么我在上面的代码中得到了一些错误的结果？
最后，方法 5 和 6 尽管它们总是正确的，但它们似乎比其他方法慢。你能解释一下吗？上述方法在矩阵乘法的复杂性方面有何不同，您有何建议？
编辑
我认为从我在代码中使用的函数来看应该很清楚，但无论如何，我感兴趣的操作是常规矩阵乘法。另外，对于我的示例实际上是溢出的事实，我深表歉意，但是性能问题仍然有效。
如评论中所述，A*B 不适合 64 位，因此被截断，导致基于 int64 的计算 return 错误结果。由于 int64 不足以容纳 A*B，下一个最好的办法是使用数据类型为 "object" 的数组（本质上是您的方法 5，尽管是时候将 np.matrix 留在后面了）：
A_obj = np.array(A).astype(object)
B_obj = np.array(B).astype(object)
np.dot(A_obj, B_obj) % F
returns 25112458407047.
它比 int64 乘法慢，但仍然比 SymPy 快（在我的测试中大约快 15 倍）。
np.matrix 的存在是模仿 Matlab 语法的黑暗时代的残余；不建议在新代码中使用。在我的测试中，使用 np.matrix 大约慢了 3 倍。
methods 5 and 6 seem to be slower than the other methods.
处理更复杂的对象需要更长的时间。使用能够乘以整数的低级例程处理 int64 数字数组是一回事；处理对象数组是另一回事，这些对象上实现了任何类型的乘法运算符。前者可以（并且已经）在 C 或 Fortran 级别完成，return 将结果转换为 Python；但是要处理 Python 个对象，必须一直停留在 Python 中。
我想计算两个量A和B的乘积，然后计算乘积对F的模。一般来说，A和B是大数矩阵，所以操作是常规的矩阵乘法。为简单起见，让我们将 A 和 B 视为标量。我测试过的所有方法的 Python 代码如下：
from __future__ import division
import numpy as np
from sympy import Matrix
from sympy import *
A = 2251875000001
B = 28839630
F = 33232924804801
#Method 1: pure Python
C1 = (A*B) % F
A_mat = np.matrix(A).astype(np.int64)
B_mat = np.matrix(B).astype(np.int64)
#Method 2: numpy matrices and pure Python
C2 = (A_mat*B_mat) % F
#Method 3: numpy
C3 = np.dot(A, B) % F
#Method 4: numpy
C4 = np.dot(A_mat, B_mat) % F
#Method 5: Python objects and numpy
A_mat2 = np.matrix(A, dtype=object)
B_mat2 = np.matrix(B, dtype=object)
C5 = np.dot(A_mat2, B_mat2) % F
C5 = np.concatenate(C5).astype(np.int64)
#Method 6: sympy
A_sp = Matrix(1,1,[A])
B_sp = Matrix(1,1,[B])
C6 = A_sp*B_sp
f = lambda x: x%F
C6 = C6.applyfunc(f)
print(C6)
C6 = matrix2numpy(C6, dtype='int64')
现在结果应该是
(2251875000001 * 28839630) mod 33232924804801 = 25112458407047
当我运行上面的代码时，我得到的C1 == 25112458407047对于这个例子是正确的，但是当我测试大矩阵的乘法时，我用这个方法得到的大部分条目都是错误的.但是，C2、C3、C4 的值都等于 12062945446480，这是错误的。 C5 和 C6 也计算正确。
您可以假设 int64 的 64 位精度对于我正在使用的数字来说绰绰有余，但默认的 32 位精度不够。
我尝试了 Sympy（参见方法 6），因为根据 here.
它应该具有任意精度我正在使用 Python 2.7.14、Numpy 1.14.2 和 Sympy 1.1.1。
我的第一个问题是为什么我在上面的代码中得到了一些错误的结果？
最后，方法 5 和 6 尽管它们总是正确的，但它们似乎比其他方法慢。你能解释一下吗？上述方法在矩阵乘法的复杂性方面有何不同，您有何建议？
编辑
我认为从我在代码中使用的函数来看应该很清楚，但无论如何，我感兴趣的操作是常规矩阵乘法。另外，对于我的示例实际上是溢出的事实，我深表歉意，但是性能问题仍然有效。
如评论中所述，A*B 不适合 64 位，因此被截断，导致基于 int64 的计算 return 错误结果。由于 int64 不足以容纳 A*B，下一个最好的办法是使用数据类型为 "object" 的数组（本质上是您的方法 5，尽管是时候将 np.matrix 留在后面了）：
A_obj = np.array(A).astype(object)
B_obj = np.array(B).astype(object)
np.dot(A_obj, B_obj) % F
returns 25112458407047.
它比 int64 乘法慢，但仍然比 SymPy 快（在我的测试中大约快 15 倍）。
np.matrix 的存在是模仿 Matlab 语法的黑暗时代的残余；不建议在新代码中使用。在我的测试中，使用 np.matrix 大约慢了 3 倍。
methods 5 and 6 seem to be slower than the other methods.
处理更复杂的对象需要更长的时间。使用能够乘以整数的低级例程处理 int64 数字数组是一回事；处理对象数组是另一回事，这些对象上实现了任何类型的乘法运算符。前者可以（并且已经）在 C 或 Fortran 级别完成，return 将结果转换为 Python；但是要处理 Python 个对象，必须一直停留在 Python 中。