Quel est l'algorithme le plus rapide pour la division de grands entiers fous?
je dois diviser les nombres représentés par des chiffres dans des tableaux d'octets avec un nombre non standard d'octets. Peut-être 5 octets ou 1 Go ou plus. La Division devrait être faite avec des nombres représentés comme des tableaux d'octets, sans aucune conversion en nombres.
2 réponses
Divide-and-conquer division finit par être beaucoup plus rapide que la méthode du livre d'école pour de très grands entiers.
GMP est une bibliothèque ultramoderne à grand nombre. Pour à peu près tout, il a plusieurs implémentations d'algorithmes différents qui sont accordés pour des tailles d'opérande spécifiques.
Ici est BPF "division des algorithmes" de la documentation. Les descriptions d'algorithmes sont un peu ternes, mais elles vous donnent au moins quelque chose à google quand vous voulez en savoir plus.
Brent et Zimmermann Moderne de l'Arithmétique des ordinateurs est un bon livre sur la théorie et la mise en œuvre de l'arithmétique grand nombre. Probablement intéressant à lire si vous voulez savoir ce qui est connu.
l'algorithme standard long division, qui est similaire à grade school long division est Algorithme D décrit dans Knuth 4.3.1. Knuth a une longue discussion sur la division dans cette section de son livre. Le résultat de ceci qu'il y a des méthodes plus rapides que L'algorithme D mais elles ne sont pas beaucoup plus rapides et elles sont beaucoup plus compliquées que L'algorithme D.
si vous avez décidé d'obtenir l'algorithme le plus rapide possible, vous pouvez recourir à ce qui est connu sous le nom de la TRR algorithme.
Tout cela et plus est couvert par la voie sur la Wikipédia Algorithme De Division.