Arithmétique des nombres entiers à plusieurs chiffres. Lab3 (arithme long). Formes numériques

Programmation_en_algorithmes_(1).pdf

S. M. Okulov PROGRAMMATION EN ALGORITHMES 6e édition (électronique) Moscow Knowledge Lab 2017

Page 2

UDC 519.85(023) BBC 22.18 O-52 La série a été fondée en 2008 par Okulov S. M. O-52 Programmation en algorithmes [ressource électronique] / S. M. Okulov.- 6e éd. (él.).-Électronique. données textuelles. (1 fichier pdf : 386 pages).-M. : Laboratoire des connaissances, 2017.-(Développement de l'intellect des écoliers).- Système. configuration requise : Adobe Reader XI ; écran 10". ISBN 978-5-00101-449-2 L'art de la programmation est présenté sous la forme d'une formation qui révèle les secrets des algorithmes les plus populaires. Des sujets tels que les algorithmes combinatoires, l'énumération, les algorithmes sur les graphes, le calcul algorithmes de géométrie sont couverts Des problèmes Olympiade sélectionnés sont donnés sur la programmation avec des instructions pour les résoudre Des recommandations pratiques pour les programmes de test sont un complément nécessaire au cours Pour les écoliers, les étudiants et les professionnels qui étudient sérieusement la programmation, ainsi que pour les enseignants des établissements d'enseignement UDC 519.85 (023 ) LBC 22.18 Programmation en algorithmes / S. M. Okulov.-4e éd.-M.: BINOM Knowledge Laboratory, 2013.-383 pp.: Ill.-(Développement de l'intellect des écoliers).- ISBN 978-5-9963-0848 -4 Conformément aux articles 1299 et 1301 du Code civil de la Fédération de Russie, lorsque les restrictions établies par des moyens techniques de protection du droit d'auteur sont supprimées, le titulaire du droit a le droit d'exiger du contrefacteur dommages ou compensation ISBN 978-5-00101-449-2 ○ Knowledge Lab, 2015 c

Page 3

Table des matières Préface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Arithmétique des entiers multi-bits. . . . . . 8 1.1. Opérations arithmétiques de base. . . . . . . . . . . . . . 8 1.2. Tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2. Algorithmes combinatoires. . . . . . . . . . . . . . . . . . . . . . . . 27 2.1. Problèmes classiques de combinatoire. . . . . . . . . . . . . . 27 2.2. Génération d'objets combinatoires. . . . . . . . . . . . . . 34 2.2.1. Permutations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2. Hébergement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.3. Combinaisons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2.4. Décomposer un nombre en parties. . . . . . . . . . . . . . 58 2.2.5. Séquences de zéros et de uns de longueur N sans deux uns d'affilée. . . . . . . . . . . 64 2.2.6. Sous-ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.2.7. Séquences de parenthèses. . . . . . . . . . . . . 71 2.3. Tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3. Recherche et méthodes de sa réduction. . . . . . . . . . . . . . . . 87 3.1. Recherche avec retour (schéma général). . . . . . . . . . . . . . . . 87 3.2. Exemples de tâches pour analyser le schéma général d'énumération 89 3.3. Programmation dynamique. . . . . . . . . . . . . . . . .106 3.4. Exemples de tâches pour analyser l'idée de la méthode de programmation dynamique. . . . . . . . . . . . . . . . . . . . . . . . .108 3.5. La méthode branch and bound. . . . . . . . . . . . . . . . . . . . . . . . . . . .116 3.6. Méthode tamisée. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121 3.7. Tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126 4. Algorithmes sur les graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .158 4.1. Représentation d'un graphique dans la mémoire d'un ordinateur. . . . . . . .158 4.2. Rechercher dans le graphique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.1. Recherche en profondeur. . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.2. Largeur première recherche. . . . . . . . . . . . . . . . . . . . . . . . . . .161

Page 4

4 Sommaire 4.3. Des arbres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162 4.3.1. Concepts de base. Tirer des arbres. .162 4.3.2. Génération de tous les frameworks du graphe. . . . . . . . . . .163 4.3.3. Wireframe de poids minimum Méthode de J. Kraskal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165 4.3.4. Cadre de poids minimum. La méthode de R. Prim168 4.4. Connectivité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.1. Accessibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.2. Définition de la connectivité. . . . . . . . . . . . . . . . . . . . .172 4.4.3. Biconnectivité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173 4.5. cycles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.1. cycles d'Euler. . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.2. Cycles de Hamilton. . . . . . . . . . . . . . . . . . . . . .177 4.5.3. Ensemble fondamental de cycles. . . . . . .179 4.6. Les chemins les plus courts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .180 4.6.1. Formulation du problème. Sortie de chemin. . . . . . . . . . . .180 4.6.2. Algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . .182 4.6.3. Chemins dans un graphe sans contour. . . . . . . . . . . . . . . . .183 4.6.4. Les chemins les plus courts entre toutes les paires de sommets. Algorithme de Floyd. . . . . . . . . . . . . . . . .186 4.7. Ensembles indépendants et dominants. . . . . . . .188 4.7.1. ensembles indépendants. . . . . . . . . . . . . . . . . . .188 4.7.2. Méthode pour générer tous les ensembles maximaux indépendants d'un graphe. . . . . . . . . . . . . . . . . . .189 4.7.3. ensembles dominants. . . . . . . . . . . . . . . .194 4.7.4. Le problème de la moindre couverture. . . . . . . . . . . .195 4.7.5. Méthode pour résoudre le problème de la plus petite partition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .196 4.8. Pages de coloriages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202 4.8.1. Coloration correcte. . . . . . . . . . . . . . . . . . . . .202 4.8.2. Trouver la coloration minimale des sommets du graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 4.8.3. Utilisation du problème de la moindre couverture lors de la coloration des sommets du graphe. . . . . . .207 4.9. Flux dans les réseaux, appariements. . . . . . . . . . . . . . . . . . . .208 4.9.1. Formulation du problème. . . . . . . . . . . . . . . . . . . . . . . . .208 4.9.2. Méthode de construction du débit maximal dans le réseau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210 4.9.3. La plus grande correspondance dans un graphe biparti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215

Page 5

Table des matières 5 4.10. Méthodes de résolution approchée du problème du voyageur de commerce. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219 4.10.1. Méthode d'optimisation locale. . . . . . . . . . . .219 4.10.2. Algorithme d'Euler. . . . . . . . . . . . . . . . . . . . . . . . .222 4.10.3. Algorithme de Christophide. . . . . . . . . . . . . . . . . .225 4.11. Tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227 5. Algorithmes de géométrie computationnelle. . . . . . . . . .249 5.1. procédures de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .249 5.2. Droite et segment de droite. . . . . . . . . . . . . . . . . .255 5.3. Triangle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262 5.4. Polygone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266 5.5. Coquille convexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272 5.6. Problèmes sur les rectangles. . . . . . . . . . . . . . . . . . . . . . . .284 5.7. Tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293 6. Problèmes de programmation choisis pour l'Olympiade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300 7. Notes sur les tests du programme. . . . . . . . . . . . . . . .358 7.1. À propos de la programmation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .359 7.2. Recommandations pratiques. . . . . . . . . . . . . . . . . . . . . .360 7.3. Tester un programme pour résoudre un problème (par exemple) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370 Index bibliographique. . . . . . . . . . . . . . . . . . . . . . . .382

Dans le cas le plus simple, pour les nombres à un chiffre, les règles d'addition binaire sont :

Lors de l'ajout de (), il y a deux cas :

Les nombres multi-bits sont additionnés selon les mêmes règles, mais la retenue d'entrée dans chaque bit est prise en compte : la retenue de sortie du bit le moins significatif est la retenue d'entrée pour le bit le plus significatif adjacent. Prenons quelques exemples d'addition de nombres à plusieurs chiffres.

soustraction binaire

Ici, nous considérons les règles qui fonctionnent dans le cas de la soustraction d'un plus petit nombre à un plus grand. Tous les autres cas sont discutés ci-dessous dans la section 3.2 sur l'arithmétique binaire signée. Dans le cas le plus simple, pour chaque bit, les règles de soustraction binaire sont :

Lorsqu'une soustraction () est effectuée, un emprunt est effectué à partir d'un ordre supérieur. Le point d'interrogation signifie que la catégorie du diminué change à la suite du prêt selon la règle :

En soustrayant (0 - 1) au chiffre de la différence, on obtient 1, les chiffres du réduit, à partir du suivant, sont inversés (inversés) jusqu'à la première unité de compteur (incluse). Après cela, une soustraction est effectuée à partir des chiffres modifiés de la réduction.

Prenons plusieurs exemples de soustraction de nombres à plusieurs chiffres (un nombre plus petit est soustrait d'un nombre plus grand).

De toute évidence, en décimal comme en binaire, l'addition est beaucoup plus facile que la soustraction. Par conséquent, l'arithmétique binaire, prenant en compte les signes des nombres, s'est généralisée, où la soustraction est remplacée par l'addition des nombres, en tenant compte de leur signe. Dans ce cas, le rapport des nombres les uns aux autres n'a plus d'importance, lequel d'entre eux est le plus grand - soustrait ou réduit. Le signe de la différence est obtenu automatiquement.

Arithmétique binaire, tenant compte des signes des nombres

Codes directs, inverses et supplémentaires

En code binaire, le signe d'un nombre est le chiffre attribué à gauche des chiffres significatifs du nombre. Le signe " " est noté par logique , le signe " " - par logique . Pour plus de clarté, tous les exemples seront considérés pour des nombres entiers, en séparant le bit de signe par un point.

Code direct (PC) pour les nombres négatifs et positifs, il est formé de la même manière, en ajoutant simplement un bit de signe.

Ainsi, au format huit bits

Code inversé (OK) pour les nombres positifs, il coïncide avec le direct, c'est-à-dire Les bits significatifs sont affectés aux bits significatifs. Pour les nombres négatifs, les chiffres significatifs sont inversés (les zéros sont remplacés par des uns, les uns par des zéros), après quoi le signe est attribué.

Pour le même numéro, le code inverse est : , .

désavantage Code de retour est qu'un même nombre s'écrit différemment : , , ce qui peut provoquer un décalage indésirable dans le fonctionnement du circuit logique. Par conséquent, un code supplémentaire est préférable.

Code supplémentaire (DC) pour les nombres positifs, il coïncide avec l'inverse et le direct, c'est-à-dire Les bits significatifs sont affectés aux bits significatifs. Pour les nombres négatifs, le code de complément à deux est 1 de plus que l'inverse. Après la formation des chiffres significatifs, un chiffre de signe est attribué.

Pour les chiffres significatifs d'un nombre négatif, la formule est valide :

Écrivons le nombre en code complément à deux sur 7 bits :

Donc en code supplémentaire , donc, l'inconvénient indiqué Code de retour surmonter.

Considérez la formation d'un code supplémentaire pour le nombre 10. Pour un nombre positif et pour un nombre négatif co supplémentaire ré est obtenu comme suit :

Pour remplacer la soustraction par l'addition, appliquez et arrière, Et Additionnel codes, et chacun d'eux a ses propres règles.

Arithmétique binaire en complément à deux

Pour plus de clarté, prenons deux nombres décimaux, par exemple, et , et effectuons toutes les options de calcul possibles :

.

Le nombre est positif, donc D'accord=PC, pour vérifier le nombre il faut traduire ses chiffres significatifs en un code décimal selon (P3-2) : .

• . Tout d'abord, nous obtenons le code supplémentaire d'un nombre négatif :

  

  Il est important de comprendre ici que les zéros les plus à gauche en chiffres significatifs ne peuvent pas être réduits, car ils sont significatifs. En d'autres termes, tous les calculs pour chaque exemple sont effectués dans un format inchangé, dans ce cas dans l'exemple (b) il s'agit de six chiffres significatifs, c'est-à-dire autant qu'il est contenu dans le plus grand nombre.

  Nous avons de nouveau reçu le signe du nombre et ses chiffres significatifs, occupant des positions codées en dur dans le format numérique sélectionné. Comme c'est un nombre négatif, alors CC PC, pour vérifier ses chiffres significatifs, il faut d'abord calculer le code inverse , puis le traduire en code direct par inversion -

  

  puis le traduire en un code décimal selon (P3-2) : .

• - Nous obtenons d'abord CC nombre négatif.

  

  Après cela, nous ferons les calculs.

Arithmétique à plusieurs chiffres

Complété:
étudiant de 3ème année
Faculté de Mathématiques
33 groupes

Présentation……………………………………………………………………………...3

Représentation d'un nombre dans n'importe quel système de numération …………………………4
Opérations sur les numéros longs..…………………………………………..... .5
Addition de nombres à plusieurs chiffres………………………………………………….6
Soustraction de nombres à plusieurs chiffres ………………………………………………...7
Multiplication de nombres à plusieurs chiffres ………………………………………………………8
Multiplication rapide………………………………………………………………...11
Comparaison des multiplications "rapide" et "scolaire"…...………………………………22
Précision des calculs et son amélioration…………………………………………...23

Conclusion…………………………………………………………………………….24

Littérature…………………………………………………………………………….26

Candidature…..…………………………………………………………………….27

introduction
Pour de nombreuses applications, les types de base fournis par le processeur sont suffisants. Cependant, il existe de nombreux problèmes dont les données initiales sont trop volumineuses. Un nombre de 1000 chiffres ne rentre dans aucun registre. Par conséquent, la représentation informatique de ces nombres et les opérations sur ceux-ci doivent être implémentées indépendamment.
Dans le même temps, le temps d'exécution d'un algorithme externe qui utilise de tels nombres dépend beaucoup de l'efficacité de leur implémentation. Par exemple, si l'estimation de temps est déterminée par O(n2) multiplications, alors l'utilisation d'un algorithme deux fois plus rapide pour cette opération donne
accélération de 4 fois. Par conséquent, nous serons peut-être plus sérieusement intéressés par des algorithmes non seulement corrects, mais peut-être plus efficaces qui, si nécessaire, peuvent être implémentés à un niveau décent.

Représentation d'un nombre dans n'importe quel système de numération
Habituellement, un entier non négatif N de longueur n est représenté par N = a0 + a1*BASE + a2*BASE2 + ... + an-1 BASEn-1,
où BASE est la base du système numérique, tous les coefficients sont 0 . ai< BASE.
Par exemple, un nombre dans cette interprétation ressemblerait à
1234510 = 5 + 4*10 + 3*102 + 2*103 + 1*104 (BASE=10).
Le nombre long est stocké dans un tableau, où le i-ème élément correspond au facteur du nombre dans BASE.
A titre d'exemple, considérons un tableau pour : : (5, 4, 3, 2, 1).
Comme vous pouvez le voir, les numéros sont stockés dans l'ordre inverse. C'est une sorte de "préparation pour l'avenir": le fait est que les implémentations des algorithmes dans ce cas ont un aspect plus naturel.
Une telle représentation de N est un cas particulier du polynôme du nième degré P(x) = a0 + a1*x + a2*x2 + ... + an-1 xn-1, qui est également stocké de manière pratique sous forme de tableau de coefficients . Par conséquent, la plupart des opérations de base sur les nombres, avec une simplification correspondante des algorithmes, fonctionnent pour des polynômes arbitraires (addition, multiplication, etc.).
Le signe du nombre, ainsi que la place de la virgule décimale, peuvent être stockés dans une variable distincte et pris en compte lors de l'exécution des opérations. Dans ce qui suit, nous n'opérerons qu'avec des entiers non négatifs.
La base du système de numérotation BASE dépend généralement de la taille maximale du type de données de base sur l'ordinateur et est choisie en fonction des considérations suivantes :
1. La base doit correspondre à l'un des types de données de base
2. BASE doit être aussi grand que possible pour réduire la taille de la représentation d'un nombre long et augmenter la vitesse des opérations avec eux, mais suffisamment petit pour que toutes les opérations avec des coefficients utilisent le type de données de base.
3. Pour plus de commodité, vous pouvez choisir BASE comme puissance de 10 (sortie d'informations, débogage).
Opérations sur les "nombres longs"
Considérons un problème assez populaire en programmation pour travailler avec des nombres "longs". En réalité, on n'a pas si souvent affaire à des nombres "astronomiques" ou "microscopiques". Cependant, les exercices abordés dans cette publication peuvent constituer une bonne formation dans le domaine de la programmation et prendre toute leur place dans les cours d'approfondissement de l'informatique ou dans les cercles de programmation. Les algorithmes présentés ci-dessous sont écrits en Turbo Pascal, version 7.0 et en C++. Si désiré ou nécessaire, ils peuvent facilement être adaptés à tout autre environnement logiciel. La plage de représentation des entiers (Integer, Word, LongInt) est limitée, ce qui a déjà été mentionné plus d'une fois (cependant, cette remarque est également pertinente pour les valeurs réelles). Par conséquent, lors de la résolution de problèmes, vous devez toujours agir avec prudence - comment éviter l'apparition d'une erreur hors plage ou de dépassement. Par exemple, calculer la factorielle ( n! = 1 * 2 * 3 * … * n), dans la plage de représentation des valeurs de type Integer, seules 7 peuvent être correctement obtenues ! = 5040, et dans la plage de la représentation LongInt - 12 ! = 479001600. Pour les grandes valeurs, bien sûr, vous pouvez utiliser des types de données réels, mais cela ne garantit plus un résultat précis. Par conséquent, il est utile de développer d'autres façons de représenter ces nombres, des algorithmes pour effectuer des opérations arithmétiques et autres, des procédures de saisie et de sortie des résultats, etc. pour obtenir des valeurs précises lors de l'utilisation de nombres à plusieurs chiffres.
Les nombres qui n'ont pas assez de bits pour être représentés dans les types de données informatiques standard sont appelés "long". L'implémentation d'opérations arithmétiques sur de tels nombres "longs" est appelée "arithmétique longue". La façon la plus naturelle de représenter un nombre à plusieurs chiffres est d'écrire chacun de ses chiffres comme un élément séparé d'un tableau linéaire (ou d'une liste, où la mémoire pour un chiffre sera allouée selon les besoins, tandis que dans le tableau, vous devez pré -définir le nombre maximum d'éléments qu'il contient). Laissez (pour la commodité des actions ultérieures) les chiffres du nombre "long" lors de l'écriture dans le tableau être numérotés à partir de un, en commençant par le chiffre des uns, c'est-à-dire le chiffre de la place de l'unité est l'élément de tableau avec le numéro un, le chiffre de la place des dizaines est l'élément de tableau avec le numéro deux, et ainsi de suite. Définissons un type de données pour travailler avec des nombres "longs" non négatifs :
Mais si nous implémentons des opérations arithmétiques sur ce nombre, alors la taille du tableau doit être suffisante pour accueillir le résultat, par exemple, de la multiplication. La multiplication est la plus complexe de toutes les opérations arithmétiques et son résultat final est la plus grande place dans la mémoire de l'ordinateur. Les opérations les plus simples sur les nombres à plusieurs chiffres sont l'addition et la soustraction.
Addition de nombres à plusieurs chiffres (longs)
Presque tout le monde sait comment additionner de longs nombres à l'aide d'une feuille de papier et d'un crayon. Ce que nous allons faire maintenant, c'est transférer la compréhension que nous avons dans le langage compris par l'ordinateur.
Le schéma d'addition est très simple : on additionne les nombres de gauche à droite (les nombres sont stockés dans l'ordre inverse). Si un débordement est détecté (c'est-à-dire que lors de l'addition, on obtient un chiffre supérieur au maximum possible dans un système de numération donné), alors un "transfert" vers le bit suivant se produit.
Trouvons la somme des nombres A et B. Nous ajouterons les éléments des tableaux avec les mêmes nombres et stockerons les résultats en tant qu'éléments du tableau C (l'algorithme pour travailler avec de tels tableaux ressemble à l'addition dans une colonne). Si à une certaine étape nous obtenons С[i] , alors à la place de C[i] nous laissons le reste de la division de C[i] par 10 (le nombre d'unités de ce chiffre), et ajoutons 1 à l'élément C (transfert 1 au chiffre suivant).
Si A a N chiffres et B a M chiffres, alors C a soit max(N,M) chiffres soit max(N,M)+1 chiffres. Notons K la valeur max(N,M)+1.
Avant d'effectuer l'addition, vous devez compléter le nombre avec moins de chiffres avec des zéros non significatifs afin que le nombre de chiffres soit égal. Ceci peut être réalisé en mettant à zéro les tableaux A et B avant d'entrer les nombres.
L'algorithme d'addition de deux nombres à plusieurs chiffres est présenté en annexe 1.
Après l'exécution de cet algorithme, la somme des nombres A et B sera stockée dans les K premiers éléments du tableau C, C étant le chiffre du chiffre le moins significatif. La dernière vérification vous permet de supprimer un zéro non significatif de l'ordre supérieur du nombre C.
Soustraction à plusieurs chiffres
La soustraction s'effectue de manière similaire, à la seule différence que le transfert des « emprunts » s'effectue. Nous travaillons avec des nombres positifs, donc si la soustraction est de grande taille, une sortie se produit.
Si les longueurs sont identiques, mais que l'une est supérieure à l'autre, cela se traduira par un emprunt inutilisé à la fin du processus, et le résultat sera le complément de BASEB.Size.
Pour être précis, nous supposerons que A>B. Sinon, vous devez échanger les nombres et rendre le résultat négatif.
Si A a N chiffres, alors B ne peut pas avoir plus de N chiffres. La différence ne contiendra pas plus de N chiffres.
Trouvons la différence entre les nombres A et B. Nous allons soustraire les éléments du tableau B des éléments du tableau A avec les nombres correspondants. Nous stockerons les résultats obtenus dans le tableau C. Si à une étape nous obtenons C[i]<0, то к элементу C[i] прибавляем 10, а от элемента C отнимаем 1(забираем 1 из следующего разряда).
L'algorithme de soustraction de deux nombres à plusieurs chiffres est présenté en annexe 2.
Multiplication de nombres à plusieurs chiffres
La façon la plus naturelle de représenter un nombre à plusieurs chiffres est d'écrire chacun de ses chiffres comme un élément séparé d'un tableau linéaire (ou d'une liste, où la mémoire pour un chiffre sera allouée selon les besoins, tandis que dans le tableau, vous devez pré -définir le nombre maximum d'éléments qu'il contient). Laissez (pour la commodité des actions ultérieures) les chiffres du nombre "long" lors de l'écriture dans le tableau être numérotés à partir de un, en commençant par le chiffre des uns, c'est-à-dire le chiffre de la place de l'unité est l'élément de tableau avec le numéro un, le chiffre de la place des dizaines est l'élément de tableau avec le numéro deux, et ainsi de suite. Définissons un type de données pour travailler avec des nombres "longs" non négatifs :
Const MNax = 2000 ;
Type Chiffre = 0..9 ;
DlChislo = tableau de chiffres ;
Pour résoudre le problème, vous devez être en mesure d'effectuer les actions suivantes :
1) entrée du nombre "long" ;
2) la multiplication réelle de deux nombres "longs" ;
3) sortie d'un nombre "long" ;
4) déterminer le nombre de chiffres dans une entrée numérique.
Nous mettons en œuvre chacune des sous-tâches en tant que sous-programme distinct. Commençons par l'entrée. Il est conseillé d'entrer un grand nombre sous forme de chaîne, puis de le convertir en un tableau de nombres. La procédure prend en compte la manière ci-dessus de placer un nombre "long" dans un tableau, c'est-à-dire du point de vue de l'utilisateur, le nombre est écrit comme s'il était dans l'ordre inverse.
(La procédure de conversion d'un long nombre écrit sous forme de chaîne en un tableau de chiffres ; la variable OK est définie sur True s'il n'y a pas de caractères étrangers autres que des chiffres décimaux dans l'entrée du nombre, sinon elle est fausse)
Procédure Translate(S : String ; Var A : DlChislo ; Var OK : Boolean) ;
Var I : Mot ;
Commencer
Zéro(A); I := Longueur(S) ; OK := Vrai ;
Tant que (I >= 1) Et OK Do
Commencer
Si S[I] Dans ["0".."9"]
Alors A:= Ord(S[I]) - 48
Sinon OK := Faux ; je := je - 1
finir
finir;
Le sous-programme Zéro(A) est appelé dans la procédure dont le but est d'écrire un zéro sur chaque bit d'un nombre long. Voici le texte de cette procédure :
(Procédure de remise à zéro d'un nombre long)
Procédure Zéro (Var A : DlChislo) ;
Vari I : Entier ;
Commencer
Pour I:= 1 Vers NMax Faire A[I] := 0;
finir;
Ainsi, un nombre long est écrit dans un tableau, où les premiers (comme éléments avec de grands nombres) sont des zéros non significatifs. Lors de l'exécution d'actions et de l'affichage d'une réponse, elles ne sont pas prises en compte.
Nous allons maintenant développer une fonction pour déterminer le nombre de chiffres significatifs dans une entrée numérique, car elle sera nécessaire lors de la mise en œuvre du sous-programme de multiplication.
(Fonction de détermination du nombre de chiffres dans une entrée de numéro long)
Longueur de la fonction (C : DlChislo) : nombre entier ;
Vari I : Entier ;
Commencer
I:=NMax ;
Tant que (I > 1) Et (C[I] = 0) Do I:= I - 1;
Longueur := je
finir;
Lors de son développement, la considération suivante a été utilisée : si le nombre n'est pas égal à zéro, alors le nombre de chiffres de son enregistrement est égal au nombre du premier chiffre différent de zéro, si le nombre est vu du plus chiffre significatif au moins significatif. Si le nombre long est égal à zéro, il s'avère que le nombre de chiffres dans son enregistrement est égal à un, ce qui était requis.
Et, enfin, la procédure principale, pour laquelle tout le travail précédent a été effectué. Lors de la compilation de l'algorithme, l'idée de multiplication par une "colonne" est utilisée, bien que dans notre version, l'addition ne soit pas effectuée à la fin de la multiplication, mais le long de son parcours, c'est-à-dire en multipliant les chiffres suivants, ajoutez immédiatement le chiffre résultant au chiffre souhaité et effectuez un transfert vers le chiffre suivant.
(Procédure de multiplication de nombres longs. A, B - facteurs, C - produit)
Procédure de multiplication(A, B : DlChislo ; Var C : DlChislo) ;
Var I, J : Entier ; P : numérique ; VspRez : 0..99 ;
Commencer
Zéro(C);
For I := 1 To Length(A) Do (boucle sur le nombre de chiffres du premier nombre)
Commencer
P : = 0 ; (Initialement, le portage est égal à zéro)
For J := 1 To Length(B) Do (boucle sur le nombre de chiffres du deuxième nombre)
Commencer
VspRez := A[I] * B[J] + P + C ;
C := VspRez Mod 10 ; (La valeur suivante du chiffre dans le chiffre I + J - 1)
P := VspRez Div 10 (Porter au chiffre suivant)
finir;
C := P
finir
finir;
L'ensemble du programme est présenté en annexe 3.

QUICK_MULTIPLY
Nous avons entrepris d'écrire non seulement comment la multiplication fonctionne sur des nombres longs, mais aussi d'établir comment la rendre plus rapide.
Faisons un algorithme de multiplication :
1. Trouvez le plus petit nombre Len - une puissance de deux : Len . A.Taille + B.Taille. Pour les nombres considérés Len=8.
2. Remplir A et B avec des zéros non significatifs devant Len. Et dans notre exemple A=(3,4,0,0,0,0,0,0), B=(5,4,3,2,1,0,0,0).
3. Calculez la FFT des vecteurs réels sur les deux tableaux de chiffres.
4. Multipliez scalairement les vecteurs transformés, en obtenant un vecteur de taille Len.
5. Appliquez la transformée de Fourier inverse, ce qui entraînera une convolution.
6. Convertissez la convolution en un tableau d'entiers, effectuez des transferts.
Les chiffres des grands nombres sont stockés au format entier. Par conséquent, pour la FFT, ils doivent être copiés dans des tableaux temporaires de type virgule flottante. Si vous avez l'intention d'obtenir un résultat de longueur maximale N, vous devez leur allouer de la mémoire au moins la taille
MaxLen=2k, où MaxLen est la puissance minimale de deux supérieure à N. Par exemple, si le résultat maximal est de 1000 chiffres de BASE, alors la taille minimale de la mémoire est MaxLen=1024, puisque c'est la longueur de la FFT qui sera calculée .
réel *NumLong1=NULL, *NumLong2=NULL ;
// L'initialisation ne peut être effectuée qu'une seule fois dans tout le programme.
void FastMulInit(ulong Len) (
long MaxLen ;
si ((Len & -Len) == Len) // Len = puissance de deux
Max Len = Len ;
else ( // sinon calculer MaxLen - la plus petite puissance de 2,
Maxlen = 2 ; // tel que 2MaxLen . Len
faire MaxLen*=2 ; tandis que (MaxLen< Len);
}
LongNum1 = nouveau réel ;
LongNum2 = nouveau réel ;
}
// Désinitialisation
annuler FastMulDeInit() (
supprimer LongNum1 ;
supprimer LongNum2 ;
}
La fonction RealFFT() analysée dans la section correspondante effectue la transformation sur place, renvoyant les vecteurs résultants sous forme compressée.
Par conséquent, la fonction de produit scalaire doit tenir compte de ce format.
// Multiplication scalaire de vecteurs complexes sous forme compressée : LongNum1 = LongNum1*LongNum2
void RealFFTScalar(real *LongNum1, const real *LongNum2, ulong Len) (
Complexe *CF1= (Complexe*)LongNum1 ;
const Complexe *CF2=(Complexe*)LongNum2 ;
// les deux premiers éléments sont regroupés en un nombre réel complexe

NumLong1 = NumLong1 * NumLong2 ;
pour (ulong x = 1; x< Len/2; x++) // остальные – комплексные, как им и
CF1[x] = CF1[x]*CF2[x] ; // devrait être après DFT
}
Examinons de plus près la dernière étape.
Tous les calculs sont au format à virgule flottante, utilisent des nombres irrationnels, de sorte que le résultat ne sera pas un ensemble d'entiers, mais plutôt une approximation de celui-ci. Pour obtenir une réponse, chaque coordonnée de convolution doit être arrondie au nombre entier le plus proche.
une une une une ….. une
b b b b ….. b
Le problème réside dans le fait que si la précision des calculs n'est pas suffisamment élevée, un arrondi peut se produire au mauvais nombre. En conséquence, l'algorithme se terminera avec succès, mais la réponse sera incorrecte.
Une partie des problèmes liés à la précision a été résolue lors de la discussion de la FFT. Cependant, même avec une trigonométrie absolument précise, les erreurs de calcul s'accumuleront, car les opérations arithmétiques ne peuvent pas être effectuées avec une précision absolue. Par conséquent, la taille du type de données utilisé doit être suffisamment grande pour que l'erreur sur n'importe quel signe soit inférieure à 0,5.
Par exemple, lors de l'utilisation d'un type de données de taille 1, la fraction 1/3 est représentée par 0,3. En additionnant trois fractions, on obtient
1/3 + 1/3 + 1/3 = (au format flottant) 0,3 + 0,3 + 0,3 = 0,9
Si la taille est à deux chiffres, alors 1/3 = 0,33,
1/3 + 1/3 + 1/3 = 0,33 + 0,33 + 0,33 = 0,99. La précision des calculs a considérablement augmenté.
D'une manière générale, il existe deux façons d'augmenter la précision. L'une d'elles est liée à l'augmentation de la longueur du type utilisé : De float à double, puis à long double, puis à double double2…
Une autre approche est plus flexible. Il propose, avec un type fixe, de réduire la longueur de la base BASE. Ainsi, le nombre deviendra plus long, il prendra plus de mémoire, mais au détriment de cela, la précision augmente.
Limites de la multiplication FFT
Une évaluation intéressante des erreurs a été donnée par Colin Percival.
Soit nécessaire de multiplier les vecteurs à partir de 2n coordonnées en utilisant la FFT pour les vecteurs à coordonnées réelles. Il découle alors de ses résultats que l'erreur err de la multiplication de x par y est estimée d'en haut par l'expression
se tromper< 2n BASE2 (.*3n + . 5 (3n+4) + .(3n+3)) (2)
où. - précision de l'addition/multiplication, . - précision des calculs trigonométriques,
Donc, pour ., . il n'est pas difficile de trouver la plus petite base possible de BASE.
Par exemple, si le type utilisé est double(53 bits), .=2-53. Les erreurs de trigonométrie sont limitées à .=./ 2 .
Estimons la borne supérieure des erreurs (2) par un nombre. En comptant approximativement les constantes, nous obtenons 2n BASE2 2-53 (11,83 n + 11,07)< .
Pour les nombres de longueur 220, cela conduit à l'inégalité BASE< 4100. Такова оценка худшего случая, обоснованная математически.
En pratique, cependant, BASE=10000 est un bon choix. La multiplication FFT avec une telle base peut fonctionner même pour de nombreux grands nombres. Cependant, il n'y aura aucune garantie mathématique du résultat correct.
Lors de l'arrondi, vous devez regarder la différence entre la valeur arrondie et le résultat de l'arrondi. S'il est inférieur à 0,2, la multiplication donne très probablement le résultat correct, s'il est supérieur, il est recommandé de réduire BASE ou d'utiliser un autre type de base pour stocker les coefficients.
Après l'étape 5, il n'y a pas de produit fini, mais seulement une convolution - le résultat sans transferts. Comme déjà mentionné lors de l'examen de la pyramide de multiplication, les valeurs des coefficients de convolution peuvent être beaucoup plus grandes que la base, atteignant 2N*BASE2. Si l'on rappelle en plus que lors de la transformée de Fourier inverse, les résultats de la fonction RealFFT() sont divisés par N , alors la taille maximale d'un digit devient 2N2*BASE2, il faut donc veiller à ne pas déborder. En particulier, BASE ne doit pas être déclaré avec plus de 4 chiffres décimaux.
Les deux derniers types ne sont pas pris en charge par tous les processeurs.

En résumé de ce qui précède, nous notons qu'il n'y a que trois problèmes :
1. Précision de la trigonométrie
2. Précision lors du calcul de la FFT
3. Débordement de type base.
Le premier problème est résolu lors de l'examen de la FFT. Les deuxième et troisième sont résolus en diminuant BASE ou en augmentant le type de base. Dans ce cas, l'efficacité de l'algorithme diminue, car une base plus petite signifie une augmentation du nombre de chiffres, et un type de base plus grand n'est pas toujours disponible.
La fonction suivante convertit une convolution de longueur Len en un grand nombre C en arrondissant et en effectuant des traductions. A la fin de l'exécution, la variable MaxError contiendra l'erreur d'arrondi maximum.
RealFFT() ne normalise pas le résultat, il faut donc le faire ici.
réel MaxError ;
void CarryNormalize(real *Convolution, ulong Len, BigInt &C) (
inv réel = 1.0 / (Len/2); // facteur de normalisation
// La DFT a été réalisée sur le vecteur "complexe"
// 2 fois plus petite longueur
réel RawPyramid, Pyramid, PyramidError, Carry = 0 ;
court *c = C.Coef ;
x long ;
// Mettre en C uniquement la partie du résultat qui y correspond
// DFT a une longueur de 2k, mais le vecteur de coefficients
// peut être initialisé avec moins d'éléments, pas avec des puissances de 2.
si (Len > C.SizeMax) Len=C.SizeMax ;
MaxErreur = 0 ;
pour (x = 0; x< Len; x++) {
RawPyramid = Convolution[x] * inv + Carry ;
// Ajouter 0,5 pour arrondir à l'entier le plus proche
Pyramide = étage(RawPyramid + 0.5);
PyramidError = fabs(RawPyramid - Pyramid);
si (PyramideErreur> MaxErreur)
ErreurMax = ErreurPyramide ;
Porter = étage(Pyramide / BASE); // calcule les portées
c[x] = (court)(Pyramide - Porte * BASE);
}
// Tout est prêt, il ne reste plus qu'à définir la taille C, selon le premier
// coefficient non nul.
faire ( x--; ) tant que (c[x]==0);
C.Taille = x+1 ;
}
Nous pouvons maintenant implémenter l'algorithme complet.
// Calculer C = A*B, FastMul(A, B, A) fonctionne
void FastMul(const BigInt &A,const BigInt &B, BigInt &C) (
x long ;
const short *a=A.Coef, *b=B.Coef ;
if (!LongNum1 || !LongNum2) error("FastMul not initialized.");
// Étape 1
Long Len = 2 ;
tandis que (Len< A.Size + B.Size) Len *=2;
si (Len< 8) Len = 8; // FFT работает

// Étape 2. Réécrivez le nombre dans un tableau temporaire et complétez avec des zéros non significatifs
// L'ordre des chiffres est inversé, donc les zéros non significatifs seront à la fin
pour (x = 0; x< A.Size; x++) LongNum1[x] = a[x];
etc.................