Точность и производительность Python для больших целочисленных матричных продуктов - PullRequest
Новая
       37

Точность и производительность Python для больших целочисленных матричных продуктов

0 голосов
/ 18 мая 2018

Я хочу вычислить произведение двух величин 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 также рассчитаны правильно.

Можно предположить, что 64-битная точность int64 более чем достаточна для чисел, с которыми я работаю, но 32-битная по умолчанию - нет.

Я попробовал Sympy (см. Метод 6), так какон должен иметь произвольную точность в соответствии с здесь .

Я использую Python 2.7.14, Numpy 1.14.2 и Sympy 1.1.1.

Мой первый вопроспочему я получаю некоторые результаты неправильно в приведенном выше коде?

Наконец, методы 5 и 6, даже если они всегда правильные, кажутся медленнее, чем другие методы.Вы можете это объяснить?Чем вышеописанные методы отличаются сложностью умножения матриц и что вы предлагаете?

EDIT

Я подумал, что это должно быть понятно из функций, которые я использую вкод, но в любом случае интересующая меня операция - это обычное матричное умножение.Кроме того, я прошу прощения за тот факт, что мой пример на самом деле был переполнением, но вопрос производительности все еще актуален.

1 Ответ

0 голосов
/ 18 мая 2018

Как отмечается в комментариях, A * B не умещается в 64 бита, поэтому он усекается, в результате чего вычисления на основе int64 возвращают неверные результаты.Так как int64 недостаточно для хранения A*B, следующая лучшая вещь - это использовать массивы с типом данных «объект» (по сути, ваш метод 5, хотя пора оставить np.matrix позади): 

A_obj = np.array(A).astype(object)
B_obj = np.array(B).astype(object)
np.dot(A_obj, B_obj) % F

возвращает 25112458407047.

Это медленнее, чем умножение int64, но все же быстрее, чем SymPy (в моем тесте примерно в 15 раз).

Существование np.matrix является остаткомтемных веков, имитирующих синтаксис Matlab;это не рекомендуется в новом коде.В моем тесте использование np.matrix было примерно в 3 раза медленнее.

методы 5 и 6 кажутся медленнее, чем другие методы.

Обработка более сложных объектов занимает больше времени.Одно дело обрабатывать массив чисел типа int64 с помощью низкоуровневой подпрограммы, способной умножать целые числа;Другое дело - обрабатывать массив объектов, в которых реализованы операторы умножения.Первый может быть (и выполняется) на уровне C или Fortran, возвращая результаты в Python;но чтобы обрабатывать объекты Python, нужно постоянно оставаться в Python.

...