Início / coding / Perguntas / 78752268
Accepted
Sergio
Asked: 2024-07-16 07:55:52 +0800 CST

Multiplicação de números enormes em python

  • 772

Estou trabalhando em um pequeno programa python para mim e preciso de um algoritmo para multiplicação rápida de uma enorme matriz com números (mais de 660.000 números, cada um com 9 dígitos). O número do resultado tem mais de 4 milhões de dígitos. Atualmente estou usando math.prod, que calcula em aproximadamente 10 minutos, mas é muito lento, especialmente se eu quiser aumentar a quantidade de números.

Verifiquei alguns algoritmos para multiplicações mais rápidas, por exemplo o algoritmo de Schönhage-Strassen e a multiplicação de Toom-Cook, mas não entendi como eles funcionam ou como fazê-los. Tentei algumas versões que encontrei na internet, mas não funcionam muito bem e são ainda mais lentas. Gostaria de saber se alguém sabe como multiplicar essas quantidades de números mais rapidamente ou poderia explicar como usar um pouco de matemática para fazer isso?

python

3 respostas

  1. Best Answer

    math.prodacumulará um produto, um número de cada vez. Você pode fazer melhor dividindo recursivamente a lista, pegando o produto de cada metade, por exemplo, o que reduz o tamanho dos produtos intermediários.

    Isso é executado em alguns segundos para mim:

    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)))
    • 5

  2. Tenho usado um método complicado, sempre multiplicando os dois números mais antigos ainda não multiplicados até que reste apenas um:

    from operator import mul

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

    Quase tão rápido quanto o de @Ry-. A velocidade vem de Karatsuba entrando em ação ao multiplicar dois números grandes em vez de um grande e um minúsculo.

    E usar decimalparece cerca de cinco vezes mais rápido devido aos algoritmos de multiplicação ainda mais rápidos (e tem a vantagem de ser muito mais rápido para imprimir em decimal, se você quiser):

    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]
    • 3

  3. Existem duas chaves para tornar isso rápido. Primeiro, usando a implementação múltipla mais rápida que você pode obter. Para multiplicandos "suficientemente grandes", o Karatsuba mult do Python é O(n^1.585). O decimalmult NTT muito mais sofisticado do módulo é mais parecido com O(n log n). Mas o mais rápido de tudo é instalar o gmpy2pacote de extensão, que envolve a biblioteca GMP do GNU, cujo objetivo principal é a velocidade máxima. Isso tem essencialmente a mesma assintótica que decimalmult, mas com um fator constante menor.

    Em segundo lugar, os algoritmos múltiplos avançados funcionam melhor ao multiplicar dois inteiros grandes com aproximadamente o mesmo tamanho (número de bits). Você pode deixar isso para a sorte ou, como abaixo, pode forçá-lo usando uma fila de prioridade e, a cada passo, multiplicando os “dois menores” produtos parciais restantes.

    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]

    Esse é o código que eu usaria. Observe que o custo da recursão (que não é usado) é trivial comparado ao custo da aritmética enorme. As operações de heap são mais caras que a recursão, mas ainda relativamente baratas, e podem muito mais do que reembolsar seu custo se a entrada estiver em uma ordem tal que os métodos "por sorte" não tenham sorte o suficiente.

    • 3

relate perguntas