No meu tempo livre, estou me preparando para perguntas como: implementar números de multiplicação representados como matrizes de dígitos. Obviamente, sou forçado a escrever do zero em uma linguagem como Python ou Java, portanto, uma resposta como "usar GMP" não é aceitável (conforme mencionado aqui: Compreendendo o algoritmo Schönhage-Strassen (multiplicação inteira enorme)).
Para qual exatamente range de tamanhos desses 2 números (ou seja, número de dígitos), devo escolher
- Algoritmo de notas escolares
- Algoritmo Karatsuba
- Toom-Cook
- Algoritmo de Schönhage-Strassen?
Is Schönhage-Strassen O(n log n log log n) sempre uma boa solução? Wikipedia menciona que Schönhage-Strassen é aconselhável para números além 2^2^15 para 2^2^17. O que fazer quando um número é ridiculamente grande (por exemplo, 10,000 para 40,000 dígitos decimais), mas o segundo consiste em apenas alguns dígitos?
Todos esses 4 algoritmos paralelizam facilmente?
Respostas:
1 para resposta № 1Você pode navegar na fonte da GNU Multiple Precision Arithmetic Library e ver seus limites para alternar entre algoritmos.
Mais pragmaticamente, você deveria apenas o perfil de sua implementação dos algoritmos. GMP coloca um muito de esforço para otimizar, então seus algoritmosterá fatores constantes diferentes dos seus. A diferença pode facilmente mover os limites em uma ordem de magnitude. Descubra onde os tempos se cruzam conforme o tamanho da entrada aumenta para seu código e definir os limites correspondentemente.
Acho que todos os algoritmos são receptivos aparalelização, uma vez que eles "são compostos principalmente de passes de divisão e conquista. Mas tenha em mente que paralelizar é outra coisa que mudará bastante os limites.