Умножение огромных чисел в Python

Я работаю над небольшой программой на Python для себя, и мне нужен алгоритм быстрого умножения огромного массива чисел (более 660 000 чисел, каждое из которых состоит из 9 цифр). Число результата превышает 4 миллиона цифр. В настоящее время я использую math.prod, который вычисляет его примерно за 10 минут, но это слишком медленно, особенно если я хочу увеличить количество чисел.

Я проверил некоторые алгоритмы для более быстрого умножения, например алгоритм Шенхаге-Штрассена и умножение Тума-Кука, но я не понимал, как они работают и как их делать. Я попробовал несколько версий, которые нашел в Интернете, но они работают не очень хорошо и даже медленнее. Интересно, знает ли кто-нибудь, как быстрее умножать эти числа, или может объяснить, как для этого использовать некоторые математические методы?

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

user555045 16.07.2024 02:00

Вы можете потратить дни на написание чего-нибудь сносного или просто воспользоваться одной из многих эффективных математических и научных библиотек, над которыми годами работала команда инженеров, ученых и программистов.

Grismar 16.07.2024 02:04

Я не думаю, что есть, все числа в массиве являются степенями простых чисел. Эта программа вычисляет LCM для диапазона от 1 до N, числа выше указаны для N = 10 000 000. Таким образом, это 4-миллионное число является наименьшим числом, которое делится на любое число в диапазоне от 1 до 10 миллионов.

Sergio 16.07.2024 02:05

@Серджио, а как насчет контекста, в котором используется это число, можешь ли ты избежать его вычисления, возможно, работая с ним неявно? (вы знаете его факторы, это хорошее начало неявной работы с ним)

user555045 16.07.2024 02:08

Другими словами, что вы собираетесь делать с этим числом? Наверняка вы не собираетесь это распечатывать и читать. И, возможно, вашей реальной цели можно достичь, не вычисляя это число.

no comment 16.07.2024 03:22

Кроме того, НОК от 1 до 10 000 000 является произведением высших степеней простых чисел в этом диапазоне для каждого простого числа в этом диапазоне — вы имели в виду 664579 семизначных чисел?

Ry- 16.07.2024 05:52

@Ry- да, я виноват, числа здесь семизначные.

Sergio 16.07.2024 10:55

Не комментируйте комментарии, требующие разъяснений или дополнительной информации: отредактируйте свое сообщение.

greybeard 16.07.2024 13:30
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
5
8
230
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

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

У меня это происходит за несколько секунд:

import math


def recursive_prod(ns, r):
    if len(r) <= 10:  # arbitrary small base case
        return math.prod(ns[i] for i in r)

    split_at = len(r) // 2
    return recursive_prod(ns, r[:split_at]) * recursive_prod(ns, r[split_at:])


import random
ns = [random.randrange(1_000_000_000) for _ in range(660_000)]
p = recursive_prod(ns, range(len(ns)))

Я бы избегал рекурсии, если скорость является приоритетом

juanpa.arrivillaga 16.07.2024 02:10

Спасибо, у меня все умножается за 15 секунд!

Sergio 16.07.2024 02:27

Было бы лучше объяснить, «почему» это быстрее.

no comment 16.07.2024 03:00

@juanpa.arrivillaga Как вы думаете, насколько быстрее будет нерекурсивное решение?

no comment 16.07.2024 03:02

Я бы сказал, что «уменьшает размер промежуточных продуктов» - это скорее противоположность тому, почему это быстрее. Вам нужны большие операнды, чтобы можно было использовать лучший алгоритм умножения. А конкатенация строк кажется совершенно вводящей в заблуждение, поскольку конкатенация не использует разные алгоритмы и является линейной. Если вы думаете об основной теореме, ваше рекурсивное умножение подпадает под случай 3, а ваша рекурсивная конкатенация подпадает под случай 1. Случай 1 является причиной того, что оно быстрее, а не потому, что используется другой алгоритм. Это другая причина.

no comment 16.07.2024 04:02

@nocomment: их довольно сложно отделить друг от друга, поскольку нет смысла использовать более быстрый алгоритм умножения на небольших входных данных, но я бы сказал, что меньший размер промежуточных элементов является ключевым, если что-то и есть. И да, конкатенация строк должна быть нижней границей улучшения, поскольку умножение хуже линейного.

Ry- 16.07.2024 04:06

@nocomment: Если подумать, то на самом деле это просто другой способ сказать одно и то же, подчеркивая максимальный и минимальный размер на каждом уровне в задаче, где меньший максимум подразумевает больший минимум, и наоборот.

Ry- 16.07.2024 04:16

Разве вы не имеете в виду верхнюю границу улучшения? Потому что он действительно выигрывает от самого принципа «разделяй и властвуй», улучшаясь с O(n^2) до O(n log n). Принимая во внимание, что продукт улучшается только с O(n^2) до O(n^1,58), что является гораздо меньшим улучшением и происходит не из-за принципа «разделяй и властвуй», а из-за вмешательства Карацубы.

no comment 16.07.2024 04:18

@nocomment: я имею в виду нижнюю границу, если вы считаете, что произведение имеет одинаковую асимптотическую сложность O (n ^ 1,58) в обоих случаях. Стоимость одного продукта не увеличивается с O(n^2) до O(n^1,58) при переходе на рекурсивный подход – она ухудшается с O(n) (поскольку один операнд имеет постоянную верхнюю границу)… что может быть, это означает, что моя аналогия неверна (но по противоположной причине?). Вернусь, когда у меня будет возможность.

Ry- 16.07.2024 04:27

Стоимость одного продукта увеличивается до O(n^1,58) при переключении на рекурсивный подход. Потому что рекурсивный подход делает операнды сбалансированными и запускает Карацубу, когда они становятся достаточно большими. Хотя я говорил не об одном продукте, а о целом. Позвольте мне сказать иначе: если бы Python не переключился на Карацубу, а продолжал использовать наивный алгоритм, то ваше рекурсивное решение имело бы ту же сложность, что и math.prod, и, вероятно, было бы таким же медленным.

no comment 16.07.2024 04:48

Я использовал хитрый метод, всегда умножая два самых старых, еще не умноженных числа, пока не останется только одно:

from operator import mul

def prod(ns):
    ns = list(ns)
    it = iter(ns)
    ns += map(mul, it, it)
    return ns[-1]

Примерно так же быстро, как @Ry-. Скорость достигается благодаря тому, что Карацуба умножает два больших числа вместо одного большого и одного крошечного.

А использование decimal кажется примерно в пять раз быстрее из-за еще более быстрых алгоритмов умножения (и имеет то преимущество, что печать в десятичном формате гораздо быстрее, если вы этого хотите):

from operator import mul
from decimal import *

setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX))

def prod(ns):
    ns = list(map(Decimal, ns))
    it = iter(ns)
    ns += map(mul, it, it)
    return ns[-1]
Ответ принят как подходящий

Есть два ключа к тому, чтобы сделать это быстро. Во-первых, используя самую быструю реализацию multi, какую только можно получить. Для «достаточно больших» множимых множитель Карацубы в Python равен O(n^1.585). Гораздо более интересный NTT-мульт модуля decimal больше похож на O(n log n). Но быстрее всего установить пакет расширения gmpy2, который включает в себя библиотеку GMP GNU, главная цель которой — максимальная скорость. По сути, это имеет ту же асимптотику, что и decimal mult, но с меньшим постоянным коэффициентом.

Во-вторых, усовершенствованные алгоритмы multi работают лучше всего при умножении двух больших целых чисел примерно одинакового размера (количества битов). Вы можете оставить это на волю случая или, как показано ниже, заставить это сделать, используя очередь с приоритетами и на каждом шаге умножая оставшиеся «два наименьших» частичных продукта.

from gmpy2 import mpz
from heapq import heapreplace, heappop, heapify

# Assuming your input ints are in `xs`.
mpzs = list(map(mpz, xs))
heapify(mpzs)
for _ in range(len(mpzs) - 1):
    heapreplace(mpzs, heappop(mpzs) * mpzs[0])
assert len(mpzs) == 1
# the result is mpzs[0]

Это код, который я бы использовал. Обратите внимание, что стоимость рекурсии (которая здесь не используется) тривиальна по сравнению со стоимостью арифметики с огромными целыми числами. Операции с кучей более дороги, чем рекурсия, но все же относительно дешевы и могут более чем окупить свои затраты, если входные данные расположены в таком порядке, что методам «по счастливой случайности» не хватает удачи.

Можете ли вы дать представление о том, насколько это быстро, особенно по сравнению с текущим принятым ответом?

nneonneo 16.07.2024 05:02

Используя их способ построения тестовых данных (и это нормально — скажем так, чтобы было понятно), этот код выполняется менее чем за треть времени, и независимо от того, включено ли время на преобразование из int в mpz (это дешево ). И, кстати, они вычисляют тот же результат :-)

Tim Peters 16.07.2024 05:18

Означает ли это, что он медленнее моего decimal? Так как это заняло пятую часть времени.

no comment 16.07.2024 05:20

На моем компьютере время в секундах составляет 10,1 (исходное), 3,3 (десятичное) и 2,1 (мое). Если вместо 9 используются 18 цифр, то 32,0 (исходное), 7,1 (десятичное) и 3,4 (мое). Для небольших входных данных мой работает намного медленнее (тогда доминируют операции с кучей). Не на тихой машине.

Tim Peters 16.07.2024 05:35

Спасибо. А раньше у вас было другое время? Я бы не назвал 2.1 «менее трети» от 10,1.

no comment 16.07.2024 05:43

Не позволю мне редактировать последний комментарий: время для моего должно быть 2,9 вместо 2,1 для 9-значного числа.

Tim Peters 16.07.2024 05:44

Поместите их в ответ, а затем сможете редактировать по своему усмотрению :-) (И в любом случае им лучше быть там.)

no comment 16.07.2024 05:45

Нет, я закончил. Скорость всех методов здесь будет зависеть от платформы. Записывать только один мне не так интересно. В любом случае, это не имеет отношения к пунктам высокого уровня, самый важный из которых: если вас очень заботит гигантская скорость int, используйте gmpy2.

Tim Peters 16.07.2024 05:50

Я бы назвал другое более важным. Использование gmpy2 мало поможет с несбалансированными операндами (как в вопросе /math.prod).

no comment 16.07.2024 05:53

Если вас волнует худший случай, конечно. Я делаю. Но я ожидаю, что большая часть входных данных в большинстве случаев не будет располагаться в патологическом порядке. Для конкретных тестовых данных использование кучи в большинстве случаев является ненужным накладным расходом. И нет, я больше не провожу тестов: я закончил :-) Нисколько не спорю, что «по одному слева направо» — это ужасно. Совсем не об этом. Рассказываем о трёх небезумных методах, представленных на столе.

Tim Peters 16.07.2024 05:56

Ваша куча может быть более накладной, чем необходимо, но им нужно что-то сделать, чтобы сбалансировать операнды. Я имею в виду, что если они используют gmpy2 с math.prod, это все равно будет медленным, тогда как рекурсия, или мой путь, или ваша куча с ints Python, будет быстрой. Поэтому я считаю использование gmpy2 (намного) менее важным моментом, а использование лучшего алгоритма высокого уровня — более важным.

no comment 16.07.2024 06:14

«Говорим о трех небезумных методах в таблице» — Ага, это изменение появилось только после того, как я опубликовал свой комментарий выше.

no comment 16.07.2024 06:15

Это нормально: мое «если вас очень волнует скорость гигантских целых чисел, используйте gmpy2» в любом случае на самом деле не относилось к этому посту: независимо от того, что вы делаете с гигантскими целыми числами, «использование gmpy2» будет частью лучший ответ, который вы когда-либо найдете.

Tim Peters 16.07.2024 06:23

Это работает даже лучше, чем то, что я принял сначала. @nocomment для меня примерно такая же скорость, как и твой десятичный способ.

Sergio 16.07.2024 10:56

Спустя несколько тестов decimal вычислил результат для 5,7 млн ​​8-значных цифр за ~63 секунды, gmpy2 за ~59 секунд. Наверное, у них примерно одинаковая скорость.

Sergio 16.07.2024 11:11

Чем крупнее продукты, тем лучше подойдет gmpy2. Под покровом происходят чрезвычайно сложные вещи. gmpy2 на самом деле реализует множество различных алгоритмов мультирования и меняет те из них, которые он использует, в зависимости от точных размеров битов, которые могут даже варьироваться в зависимости от того, на каком оборудовании он работает, decimal реализует только 3 алгоритма мультирования и выбирает размеры обрезки независимо от оборудования. Дон Я также не ожидаю воспроизвести одни и те же различия на разных платформах.

Tim Peters 16.07.2024 11:43

@Sergio Still: Что вы собираетесь делать с этим огромным числом, которое теперь даже превышает 40 миллионов цифр?

no comment 16.07.2024 12:32

Другие вопросы по теме