Algorithme de division entière

votre algorithme est une variation d'un algorithme de base 10 connu sous le nom de"casting out nines". Votre exemple utilise la base 1000 et le" casting out " 999 (un de moins que la base). Cela était enseigné à l'école primaire comme moyen de faire une vérification rapide des calculs à la main. J'avais un prof de maths au lycée qui était horrifié d'apprendre qu'on ne l'enseignait plus et qui nous a mis au courant.

rejetant les 999 en base 1000 ne fonctionnera pas comme un algorithme de division générale. Il générera des valeurs qui sont congruentes modulo 999 au quotient réel et le reste - pas les valeurs réelles. Votre algorithme est un peu différent et je n'ai pas vérifié s'il fonctionne, mais il est basé sur l'utilisation efficace de la base 1000 et le diviseur étant 1 de moins que la base. Si vous voulez l'essayer pour diviser par 47, Vous devriez convertir en un système de base 48 Nombre d'abord.

Google "le rejet de neuf" pour plus d'informations.

Modifier: I a l'origine, lire votre message un peu trop rapidement, et vous savez de cela comme un algorithme de travail. Comme @Ninefingers et @ Karl Bielefeldt l'ont dit plus clairement que moi dans leurs commentaires, ce que vous n'incluez pas dans votre estimation de performance est la conversion en une base appropriée pour le diviseur particulier en question.

je ressens le besoin d'ajouter à cette fonction sur mon commentaire. Ce n'est pas une réponse, mais une explication du contexte.

une bibliothèque bignum utilise ce qu'on appelle limbs - search for mp_limb_t dans la source gmp, qui sont habituellement un champ entier de taille fixe.

quand vous faites quelque chose comme l'ajout, une façon (bien qu'inefficace) de l'aborder est de le faire:

doublelimb r = limb_a + limb_b + carryfrompreviousiteration

débordement de limb_a + limb_b dans le cas où la somme est supérieure à la taille du membre. Donc si le total est plus grand que 2^32 si nous utilisons uint32_t comme taille de membre, le débordement peut être attrapé.

Pourquoi avons-nous besoin de ça? Eh bien, ce que vous faites généralement est boucle à travers tous les membres - vous avez fait cela vous - même en divisant votre entier et en passant par chacun d'eux-mais nous le faisons LSL d'abord (donc le plus petit membre d'abord) tout comme vous feriez arithmétique à la main.

cela peut sembler inefficace, mais c'est juste la façon de faire les choses. Pour vraiment faire éclater les gros canons, x86 A adc comme instruction - ajouter avec carry. Ce que cela fait est une arithmétique et sur vos champs et définit le carry bit Si l'arithmétique déborde la taille du registre. La prochaine fois que vous faites add ou adc , le processeur prend également en compte le portage. En soustraction, ça s'appelle le drapeau d'emprunt.

cette disposition s'applique également: des opérations de déplacement. En tant que tel, Cette caractéristique du processeur est essentielle à ce qui rend bignums rapide. Donc, le fait est, il ya des circuits électroniques dans la puce pour faire ce genre de choses - le faire dans le logiciel est toujours va être plus lent.

sans entrer trop dans les détails, les opérations se construisent à partir de cette capacité d'ajouter, décaler, soustraire, etc. Ils sont essentiels. Oh et vous utilisez la pleine largeur du registre de votre processeur par membre si vous le faites droit.

Deuxième point, la conversion entre les bases. Vous ne pouvez pas prendre une valeur au milieu d'un nombre et changer sa base, parce que vous ne pouvez pas tenir compte du débordement du chiffre en dessous de lui dans votre base originale, et ce nombre ne peut pas tenir compte du débordement du chiffre en dessous... et ainsi de suite. En bref, chaque fois que vous voulez changer de base, vous devez convertir le bignum entier de la base d'origine à votre nouvelle base de retour. Il faut donc marcher le bignum (tous les membres) au moins trois fois. Ou, alternativement, détecter les débordements de façon coûteuse dans toutes les autres opérations... rappelez-vous, Maintenant vous devez faire des opérations modulo pour travailler si vous avez débordé, alors qu'avant le processeur le faisait pour nous.

je voudrais également ajouter que bien que ce que vous avez est probablement rapide pour cette affaire, gardez à l'esprit que comme une bibliothèque bignum gmp fait un peu de travail pour vous, comme la mémoire gestion. Si vous utilisez mpz_ vous utilisez une abstraction au-dessus de ce que j'ai décrit ici, pour commencer. Enfin, gmp utilise un assemblage optimisé à la main avec boucles déroulantes pour à peu près toutes les plateformes dont vous avez entendu parler, plus encore. Il y a une très bonne raison pour laquelle il est livré avec Mathematica, Maple et al.

maintenant, juste pour référence, du matériel de lecture.

• calculateur moderne est un Knuth-comme le travail de précision arbitraire des bibliothèques.
• Donald Knuth, Seminumerical Algorithms (The Art of Computer Programming Volume II).
• William Hart blog sur la mise en œuvre de l'algorithme pour bsdnt , dans lequel il traite de divers algorithmes de division. Si vous êtes intéressé par les bibliothèques de bignum, c'est une excellente ressource. Je me considérais comme un bon programmeur jusqu'à ce que je commence à suivre ceci genre de choses...

pour résumer pour vous: les instructions d'assemblage de division sont nulles, de sorte que les gens calculent généralement des inverses et se multiplient à la place, comme vous le faites lors de la définition de la division en arithmétique modulaire. Les différentes techniques qui existent(voir MCA) sont principalement O (n).

---

Edit: Ok, pas toutes les techniques sont en O(n). La plupart des techniques appelées div1 (divisant par quelque chose pas plus grand qu'un membre sont O(n). Lorsque vous allez plus vous retrouver avec O(n^2) complexité; c'est difficile à éviter.

maintenant, pourriez-vous implémenter bigints comme un tableau de chiffres? Eh bien oui, bien sûr, vous pourriez. Cependant, considérer l'idée juste sous addition

/* you wouldn't do this just before add, it's just to 
   show you the declaration.
 */
uint32_t* x = malloc(num_limbs*sizeof(uint32_t));
uint32_t* y = malloc(num_limbs*sizeof(uint32_t));
uint32_t* a = malloc(num_limbs*sizeof(uint32_t));
uint32_t m;

for ( i = 0; i < num_limbs; i++ )
{
    m = 0;
    uint64_t t = x[i] + y[i] + m;
    /* now we need to work out if that overflowed at all */
    if ( (t/somebase) >= 1 ) /* expensive division */
    {
        m = t % somebase; /* get the overflow */
    }
}

/* frees somewhere */

c'est une ébauche de ce que vous cherchez à ajouter via votre schéma. Donc vous avez pour exécuter la conversion entre les bases. Donc, vous allez avoir besoin d'une conversion à votre représentation pour la base, puis de retour quand vous avez terminé, parce que cette forme est juste vraiment lent partout ailleurs . Nous ne parlons pas ici de la différence entre O(n) et O(N^2), mais nous parlons d'une instruction de division coûteuse par membre ou une conversion coûteuse chaque fois que vous voulez diviser . voir ce .

suivant, comment élargissez-vous votre division pour la division des cas généraux? Par cela, je veux dire quand vous voulez diviser ces deux nombres x et y du code ci-dessus. Vous ne pouvez pas, est la réponse, sans avoir recours aux installations de bignum, qui sont coûteuses. Voir Knuth. Prendre modulo un nombre supérieur à votre taille ne fonctionne pas.

Laissez-moi vous expliquer. Essayez le 21979182173 mod 1099. Admettons ici par souci de simplicité que le plus grand champ de taille que nous pouvons avoir est à trois chiffres . C'est un exemple artificiel, mais la plus grande taille de champ que je connaisse utilise 128 bits en utilisant des extensions gcc. Quoi qu'il en soit, le point est, vous:

21 979 182 173

divisez votre nombre en membres. Puis vous prenez modulo et sum:

21 1000 1182 1355

ça ne marche pas. C'est là Qu'Avi a raison, parce que c'est une forme de moulage des dents, ou une adaptation de celle-ci, mais ça ne marche pas ici. parce que nos champs ont débordé pour un début - vous utilisez le modulo pour s'assurer que chaque champ reste à l'intérieur de sa taille de membre/champ.

Quelle est la solution? Diviser votre numéro en une série de bignums de taille appropriée? Et commencer à utiliser les fonctions de bignum pour calculer tout ce dont vous avez besoin? Cela va être beaucoup plus lent que tout autre manière de manipuler les champs directement.

maintenant peut-être que vous proposez seulement cette affaire pour diviser par un membre, pas un bignum, dans ce cas, il peut fonctionner, mais la division hensel et les inverses précalculés etc font à sans l'exigence de conversion . Je n'ai aucune idée si cet algorithme serait plus rapide que say Hensel division; ce serait une comparaison intéressante; le problème vient avec une représentation commune à travers la bibliothèque de bignum . La représentation choisie existants bignum bibliothèques est pour les raisons que j'ai développé - il un sens au au niveau de l'assemblage, là où il a été fait pour la première fois.

comme note latérale; vous n'avez pas à utiliser uint32_t pour représenter vos membres. Vous utilisez une taille idéalement la taille des registres du système (par exemple uint64_t) afin de pouvoir profiter de versions optimisées en assemblage. Ainsi, sur un système 64 bits adc rax, rbx ne définit le débordement (CF) que si le résultat dépasse 2^64 bits.

tl;dr version: le problème n'est pas votre algorithme ou idée; c'est le problème de conversion entre bases, puisque la représentation dont vous avez besoin pour votre algorithme n'est pas le moyen le plus efficace de le faire dans add/sub/mul etc. Pour paraphraser knuth: cela vous montre la différence entre l'élégance mathématique et l'efficacité computationnelle.

si vous avez besoin de diviser fréquemment par le même diviseur, en utilisant it (ou une puissance de celui-ci) que votre base rend la division aussi bon marché que bit-shifting est pour la base 2 entiers binaires.

vous pouvez utiliser la base 999 si vous voulez; il n'y a rien de spécial sur l'utilisation d'une puissance-de-10 base sauf qu'il rend la conversion en entier décimal très bon marché. (Vous pouvez travailler un membre à la fois au lieu d'avoir à faire une division complète sur l'entier entier entier. C'est comme la différence entre convertir un entier binaire en décimal vs. transformer tous les 4 bits en un chiffre hexadécimal. Binaire - > hex peut commencer avec les bits les plus significatifs, mais la conversion à des bases non-power-of-2 doit être LSB-première utilisation de la division.)

---

par exemple, pour calculer les premiers 1000 décimales de Fibonacci(10 ⁹ ) pour une question de code-golf avec une exigence de performance, mon 105 octets de machine x86 code answer utilisé le même algorithme que cette réponse Python : l'habituel a+=b; b+=a itération Fibonacci, mais diviser par (une puissance de) 10 chaque fois a devient trop grande.

Fibonacci croît plus vite que carry propage, donc jeter les décimales basses ne change pas les décimales élevées à long terme. (Vous gardez quelques extra au-delà de la précision que vous voulez).

divisé par une puissance de 2 ne fonctionne pas , sauf si vous tenez compte du nombre de puissances de 2 que vous avez écartées, parce que l'éventuelle conversion binaire -> décimale à la fin dépend de cela.

donc pour cet algorithme, vous devez faire l'addition de précision étendue, et la division par 10 (ou n'importe quelle puissance de 10 que vous voulez).

---

j'ai stocké en base 10 ⁹ membres en entier de 32 bits éléments. En divisant par 10 ⁹ est trivialement bon marché: juste un incrément d'aiguille pour sauter le membre bas. Au lieu de réellement faire un memmove , je viens de décaler le pointeur utilisé par la prochaine itération add.

je pense que la division par une puissance de 10 autre que 10^9 serait assez bon marché, mais exigerait une division réelle sur chaque membre, et propageant le reste au membre suivant.

L'ajout de précision coûte un peu plus cher de cette façon qu'avec des branches binaires, parce que je dois générer le carry-out manuellement avec un comparer: sum[i] = a[i] + b[i]; carry = sum < a; (comparaison non signée). Et aussi envelopper manuellement à 10^9 basé sur cette comparaison, avec une instruction de mouvement conditionnel. Mais j'ai pu utiliser ce carry-out comme entrée dans adc (instruction x86 add-with-carry).

vous n'avez pas besoin d'un modulo complet pour manipuler l'emballage sur addition, parce que vous savez que vous avez enveloppé au plus une fois.

cela gaspille un peu plus de 2 bits de chaque branche de 32 bits: 10^9 au lieu de 2^32 = 4.29... * 10^9 . Stocker base-10 chiffres un par octet serait beaucoup moins efficace de l'espace, et très bien pire pour la performance, parce qu'une addition binaire 8 bits coûte la même chose qu'une addition binaire 64 bits sur un CPU moderne 64 bits.

je visais pour la taille de code: pour la performance pure j'aurais utilisé 64-bit membres tenant la base-10^19 "chiffres". ( 2^64 = 1.84... * 10^19 , donc cela gaspille moins de 1 bit pour 64.) Cela vous permet d'obtenir deux fois plus de travail fait avec chaque matériel add instruction. Hmm, en fait cela pourrait être un problème: la somme de deux membres pourrait envelopper le 64-bit entier, donc juste vérifier pour > 10^19 n'est pas suffisant plus. Vous pouvez travailler dans la base 5*10^18 , ou dans la base 10^18 , ou faire une détection de carry-out plus compliquée qui vérifie le carry binaire aussi bien que le carry manuel.

stockage un sac de BCD avec un chiffre pour 4 bits de nibble serait encore pire pour la performance, parce qu'il n'y a pas de support matériel pour bloquer le carry d'un nibble à l'autre dans un octet.

---

dans l'ensemble, ma version fonctionnait environ 10 fois plus vite que la version Python extended-precision sur le même matériel (mais il y avait place pour une optimisation significative de la vitesse, en divisant moins souvent). (70 secondes ou 80 secondes contre 12 minutes)

Néanmoins, je pense que pour cette implémentation particulière de l'algorithme que (où je n'avais besoin que d'addition et de division, et où la division se produisait après quelques additions), le choix des membres de base-10^9 était très bon. Il existe des algorithmes beaucoup plus efficaces pour le nième nombre de Fibonacci qui n'ont pas besoin de faire 1 milliard d'additions de précision.