Nel mio tempo libero mi sto preparando per domande di intervista come: implementare la moltiplicazione dei numeri rappresentati come matrici di cifre. Ovviamente sono costretto a scriverlo da zero in una lingua come Python o Java, quindi una risposta come "usa GMP" non è accettabile (come menzionato qui: Comprensione dell'algoritmo di Schönhage-Strassen (enorme moltiplicazione di numeri interi)).
Per quale esattamente range delle dimensioni di quei 2 numeri (cioè il numero di cifre), dovrei scegliere
- Algoritmo scolastico
- Algoritmo di Karatsuba
- Toom-Cook
- Algoritmo di Schönhage – Strassen?
È Schönhage – Strassen O(n log n log log n) sempre una buona soluzione? Wikipedia afferma che Schönhage – Strassen è consigliabile per numeri oltre 2^2^15 a 2^2^17. Cosa fare quando un numero è ridicolmente enorme (ad es. 10,000 a 40,000 cifre decimali), ma la seconda è costituita solo da un paio di cifre?
Tutti questi 4 algoritmi si parallelizzano facilmente?
risposte:
1 per risposta № 1Puoi sfogliare la sorgente della GNU Multiple Precision Arithmetic Library e vedere le loro soglie per il passaggio da un algoritmo all'altro.
Più pragmaticamente, dovresti profila semplicemente la tua implementazione degli algoritmi. GMP mette a lotto di sforzo per l'ottimizzazione, quindi i loro algoritmiavrà diversi fattori costanti rispetto ai tuoi. La differenza potrebbe facilmente spostare le soglie di un ordine di grandezza. Scopri dove si incrociano i tempi all'aumentare delle dimensioni di input il tuo codice e impostare le soglie di conseguenza.
Penso che tutti gli algoritmi siano suscettibili diparallelizzazione, dal momento che sono per lo più costituiti da passaggi di divisione e conquista. Ma tieni presente che la parallelizzazione è un'altra cosa che farà muovere le soglie abbastanza.