Algorithme pour diviser de très grands nombres

Question

Je dois écrire un algorithme (je ne peux utiliser aucune bibliothèque tierce, car c'est une affectation) pour diviser (division entière, les parties flottantes ne sont pas importantes) de très grands nombres comme 100 - 1000 chiffres . J'ai trouvé http://en.wikipedia.org/wiki/Fourier_division algorithme mais je ne sais pas si c'est la bonne façon de procéder. Avez-vous des suggestions?

1) check divisior < dividend, otherwise it's zero (because it will be an int division) 
2) start from the left 
3) get equal portion of digits from the dividend 
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1 
5) multiply divisor by 1-9 through the loop 
6) when it exceeds the dividend portion, previous multiplier is the answer 
7) repeat steps 3 to 5 until reaching to the end 

Answer 1

Knuth, Donald, L'art de la programmation informatique, ISBN 0-201-89684-2, Volume 2: Seminumerical algorithmes, Section 4.3.1: Les algorithmes classiques

Answer 2

À moins une partie de votre mission devait être complètement original, je vais avec l'algorithme I (et je suppose que vous) ont été enseigné à l'école primaire pour faire grande division à la main.

Answer 3

J'imagine que diviser le «long chemin» comme à l'école primaire serait un itinéraire potentiel. Je suppose que vous recevez le numéro d'origine sous forme de chaîne, ce que vous faites est d'analyser chaque chiffre. Exemple:

Étape 0:

/----------------- 
13 | 453453453435.... 

Étape 1: "Combien de fois 13 aller dans 4 0

 0 
    /----------------- 
13 | 453453453435.... 

Étape 2:" Combien de fois 13 aller dans 45? 3

 03 
    /----------------- 
13 | 453453453435.... 
    - 39 
    -- 
     6 

Étape 3: « Combien de fois 13 aller dans 63 4

etc etc Avec cette stratégie, vous pouvez avoir une longueur de nombre et seulement vraiment tenir suffisamment de chiffres en mémoire pour un int (diviseur) et un double (dividende). (En supposant que j'ai obtenu ces termes) Vous stockez le résultat comme le dernier chiffre de votre chaîne de résultats

Lorsque vous frappez un point où aucun chiffre ne reste et le calcul ne aller dans 1 fois ou plus, vous renvoyez votre résultat, qui est déjà formaté en tant que chaîne (car il pourrait être potentiellement plus grand qu'un int)

Answer 4

Vous devriez probablement essayer quelque chose comme la division longue, mais utiliser des mots informatiques au lieu de chiffres. Dans un langage de haut niveau, il est plus pratique de considérer que votre «chiffre» est la moitié de votre plus grand nombre entier de précision fixe. Pour la méthode de division longue, vous devrez gérer le cas où votre résultat intermédiaire partiel peut être désactivé par un, car votre division à précision fixe ne peut gérer que la partie la plus significative de votre diviseur de précision arbitraire.

Il existe des moyens plus rapides et plus compliqués d'effectuer une arithmétique de précision arbitraire. Découvrez le wikipedia page approprié. En particulier, la méthode Newton-Raphson, lorsqu'elle est mise en œuvre avec soin, peut garantir que la performance temporelle de votre division est dans un facteur constant de votre multiplication de précision arbitraire.

Answer 5

L'algorithme de division le plus simple à mettre en œuvre pour les grands nombres est le décalage et la soustraction.

if numerator is less than denominator then finish 
shift denominator as far left as possible while it is still smaller than numerator 
set bit in quotient for amount shifted 
subtract shifted denominator from numerator 
repeat 
the numerator is now the remainder 

Le décalage n'a pas besoin d'être littéral. Par exemple, vous pouvez écrire un algorithme pour soustraire une valeur décalée à gauche d'une autre valeur, au lieu de déplacer la valeur entière avant de la soustraire. La même chose vaut pour la comparaison.

La division longue est difficile à mettre en œuvre car l'une des étapes de la division longue est la division longue. Si le diviseur est un int, alors vous pouvez faire de longues divisions assez facilement.