Numpy 256-битные вычисления

avatar
Kevin
1 июля 2021 в 18:25
571
1
4

У меня есть несколько больших чисел, которые я использую для криптографии на основе эллиптических кривых. До сих пор я выполнял все вычисления на простом питоне, который изначально поддерживает числа произвольного размера с использованием целочисленного типа «bignum». Однако я хотел бы векторизовать некоторые из этих операций (по соображениям производительности) и хотел бы использовать массив, содержащий 256-битные целые числа без знака. Но, насколько мне известно, максимальный размер целого числа в numpy составляет 64 бита при использовании np.longlong (или np.ulonglong для версии без знака). Идея из следующего сообщения состояла в том, чтобы представить каждое 256-битное число в виде массива с четырьмя 64-битными целыми числами:

large = 105951305240504794066266398962584786593081186897777398483830058739006966285013
arr = np.array([large.to_bytes(32,'little')]).view('P')
arr

Вывод:

array([18196013122530525909, 15462736877728584896, 12869567647602165677,
       16879016735257358861], dtype=uint64)

И я могу преобразовать его обратно в родной Python "bignum", выполнив:

int.from_bytes(arr.tobytes(), 'little')

Вывод:

105951305240504794066266398962584786593081186897777398483830058739006966285013

Однако я хотел бы выполнить некоторые операции, прежде чем преобразовать его обратно в "bignum":

arr2 = arr + 1
int.from_bytes(arr2.tobytes(), 'little')

Вывод:

105951305240504794072543500697971467357257258687906003363414235534976478560982

Что, конечно, не равно large + 1


Можно ли обрабатывать 256-битные числа в numpy? Если нет, существуют ли подходящие обходные пути?

Источник
Mad Physicist
1 июля 2021 в 18:39
0

Python поддерживает целые числа произвольной точности, используя целочисленный тип int. Что такое bignum? Также не забывайте про языковые теги

Mad Physicist
1 июля 2021 в 18:41
0

Вам придется эффективно реализовать все операции самостоятельно. В этот момент, вероятно, быстрее/проще писать непосредственно на C, поскольку вы можете обойти циклы Python, которые вам понадобятся, например. переносить цифры.

hpaulj
1 июля 2021 в 18:44
0

"векторизация" в смысле fast(er) numpy означает использование скомпилированных методов numpy. Если эти методы скомпилированы только для int64, вы не получите никакой скорости, пытаясь обойти их.

Mad Physicist
1 июля 2021 в 19:12
0

Кроме того, вместо arr + 1 выполните arr + [0, 0, 0, 1].

Mad Physicist
1 июля 2021 в 19:12
0

@hpaulj. Хотя зависит от того, как ты это сделаешь

Kevin
1 июля 2021 в 19:15
0

@MadPhysicist Я имею в виду целые числа произвольной точности, я думаю, что python представляет большие целые числа (> 32 бит?) с помощью какого-то фрагментированного массива: levelup.gitconnected.com/… Эта последовательность называется bignum . Я мог бы реализовать это прямо на C, но я хотел бы знать, какие еще существуют варианты.

Kevin
1 июля 2021 в 19:17
0

@MadPhysicist правильно arr + [0, 0, 0, 1]? Мне кажется, что dtype превращается в dtype('float64').

Mad Physicist
1 июля 2021 в 19:21
0

@Кевин. Затем arr + np.array([0, 0, 0, 1], dtype=np.uint64)

Mad Physicist
1 июля 2021 в 20:34
0

@hpaulj. Я опубликовал ответ, который разумно векторизован для добавления. Есть цикл для переноса цифр, но он вряд ли перегрузит вычисления.

Ответы (1)

avatar
Mad Physicist
1 июля 2021 в 20:11
1

Допустим, у вас есть пара массивов по четыре байта:

a = np.array([0b0000_1000, 0b1000_1100, 0b0111_1111, 0b1111_0000], dtype=np.uint8)  # [  8, 140, 127, 240]
b = np.array([0b1111_0000, 0b1111_0000, 0b1111_0000, 0b1111_0000], dtype=np.uint8)  # [240, 240, 240, 240]

Теперь вы хотите сложить их и получить что-то вроде

c = np.array([0b1111_1001, 0b0111_1101, 0b0111_0000, 0b1110_0000], dtype=np.uint8)  # [249, 125, 112, 224]

Я намеренно избегал того, что требует переноса в самом верхнем байте. В этом случае результат был рассчитан с помощью

ai = int.from_bytes(a.tobytes(), byteorder='big')
bi = int.from_bytes(b.tobytes(), byteorder='big')
c = np.frombuffer((ai + bi).to_bytes(4, 'big'), dtype=np.uint8)

Итак, как это сделать без преобразования в и из int? Вы не можете сделать наивный c = a + b:

[1111_1000, 0111_1100, 0110_1111, 1110_0000]
          +1         +1         +1

Обратите внимание, что все керри в отмеченных местах были выброшены. Вы можете проверить наличие переносов, не вызывая переполнения, используя

0xFF - a < b

Хорошая новость заключается в том, что вы можете перенести только один бит на байт: 0xFF + 0xFF + 1 == 0x1FF. Вы также не можете перенести добавление 1, если сумма только что перенесена: (0xFF + 0xFF) & 0xFF == 0xFE. Вот простая реализация правильного сложения:

c = a.copy()
while b.sum():
    carry = np.r_[0xFF - c[1:] < b[1:], False].view(np.uint8)
    c += b
    b = carry

Этот цикл обычно выполняется в течение 1-2 итераций. В самом худшем случае он может выполняться до N-1 итераций, где N=256 в вашем случае или N=4 в этом примере. Использование большего типа данных будет означать, что вы можете уменьшить количество итераций в худшем случае (и, возможно, ускорить в лучшем случае). Единственное предостережение, что вы не сможете использовать трюк ...view(np.uint8) для преобразования вашей логической маски. Но на самом деле это скрытое благословение, потому что вы можете написать

c = a.copy()
carry = np.zeros_like(a)
cbuf = carry.view(bool)[::a.itemsize]
# On big-endian use this instead:
#cbuf = carry.view(bool)[a.itemsize - 1::a.itemsize]
cbuf = cbuf[:-1]
m = np.iinfo(a.dtype).max
while b.sum():
    c += b
    np.less(m - c[1:], b[1:], out=cbuf)
    b = carry

Обратите внимание, что эта версия не только избегает перераспределения буфера переноса, но и полностью не зависит от itemsize из a и b.

Упражнения для чтеца:

  • Правильная обработка прямого порядка (в моих примерах слова расположены в прямом порядке, в отличие от вопроса)
  • Добавление поддержки знака (по умолчанию, если у вас есть дополнение до двух с фиксированной шириной)
  • Фактически векторизация этой операции по N измерениям
  • Реализация таких операций, как умножение