Les opérations sur les grands nombres (100, 200 chiffres)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 671 fois - Téléchargée 19 fois

Contenu du snippet

Qui n'a jamais été curieux de savoir comment faire une addittion, une soustraction, une multiplication avec des drands nombres ayant jusqu'à 200 chiffres ?
J'ai conçu ces fonctions pour le besoins d'un système de cryptage que je mettais sur place. Alors je le partage avec vous. J'attends toutes vos suggestions d'amélioration.
Un exemple d'utilisation avec :
a="1234567891011121314151617181920212223242523272829303132333435363738394041"
b="1234567891011121314151617181920212223242523272829303132333435363738394041424344454647484950515253545556575859"

La multiplication de ces deux nombres donne:
Multiplication(a,b)="1524156877515647915714744540673658430040733651926643869374389760363874548465760339953903581267217630853994489609779067085290100257651497011735453700251937161627394225799459650056219"
Soustraction(a,b)="-1234567891011121314151617181920212222007955381818181818181818181818181818181821181818181818181818181818181818"

J'ai aussi besoin de faire de meme pour la division. Alors un coup de main sera le bienvenu

Source / Exemple :


Function DeleteZeroDebut(Texte As String) As String
    'Fonction utilisée pour éliminer les 0 au début d'un nombre
   i = 0
   DeleteZeroDebut = ""
   ZeroDebut = True
   Do
    i = i + 1
    If (Mid(Texte, i, 1) <> 0 And ZeroDebut = True) Then
        ZeroDebut = False
    End If
    If (ZeroDebut = False) Then DeleteZeroDebut = DeleteZeroDebut & Mid(Texte, i, 1)
   Loop While i < Len(Texte)
   If (DeleteZeroDebut = "") Then DeleteZeroDebut = 0
End Function
Function EstSuperieur(Nombre1 As String, Nombre2 As String) As Boolean
    'Fonction utiliser pour comparer deux grands nombres
    'Equivalent de  "Nombre1 > Nombre2"
    Nombre1 = DeleteZeroDebut(Nombre1)
    Nombre2 = DeleteZeroDebut(Nombre2)
    EstSuperieur = True
    'Rechercher le plus grand
    If Len(Nombre1) < Len(Nombre2) Then 'Cas ou les deux nombres ont le meme nombre de chiffre
        EstSuperieur = False
    ElseIf (Len(Nombre1) = Len(Nombre2)) Then
        i = 0
        Do
            i = i + 1
            If (Mid(Nombre1, i, 1) < Mid(Nombre2, i, 1)) Then EstSuperieur = False
        Loop While (i < Len(Nombre1) And EstSuperieur = True)
    End If
End Function
Function Addition(Nombre1 As String, Nombre2 As String) As String
'Cette fonction sert à additionner des grands nombres
    
    'Supprimer éventuellement les zeros en début
    Nombre1 = DeleteZeroDebut(Nombre1)
    Nombre2 = DeleteZeroDebut(Nombre2)
    
    Dim Retenu
    Dim Signe
    
    Addition = ""
    Signe = ""
    
    'Rechercher le signe des nombres
    If Mid(Nombre1, 1, 1) = "-" Then 'Nombre1 négatif
        If Mid(Nombre2, 1, 1) = "-" Then 'Les deux nombres sont négatifs
            Signe = "-"
            Nombre1 = Mid(Nombre1, 2)
            Nombre2 = Mid(Nombre2, 2)
        Else 'Nombre1 négatif et nombre2 positif
            Addition = Soustraction(Nombre2, Mid(Nombre1, 2))
            Exit Function
        End If
    Else 'Nombre1 positif
        If Mid(Nombre2, 1, 1) = "-" Then 'Nombre1 positif et Nombre2 négatif
            Addition = Soustraction(Nombre1, Mid(Nombre2, 2))
            Exit Function
        End If
    End If
  
    If (Len(Nombre1) < Len(Nombre2)) Then
        a = Nombre1
        Nombre1 = Nombre2
        Nombre2 = a
    End If
    
    n = Len(Nombre1)
    Retenu = 0
    i = 0
    Do
        i = i + 1
        n1 = Mid(Nombre1, Len(Nombre1) - i + 1, 1)
        
        If (i < Len(Nombre2) + 1) Then
            n2 = Mid(Nombre2, Len(Nombre2) - i + 1, 1)
        Else
            n2 = 0
        End If
        
        r = Retenu + CInt(n1) + CInt(n2)
        Addition = Right(r, 1) & Addition
        
        If (r > 9) Then
            Retenu = 1
        Else
            Retenu = 0
        End If
   Loop While i < n
   If (r > 9) Then Addition = "1" & Addition
   Addition = Signe & Addition
End Function
Function Soustraction(Nombre1 As String, Nombre2 As String) As String
    Nombre1 = DeleteZeroDebut(Nombre1)
    Nombre2 = DeleteZeroDebut(Nombre2)
    Signe = ""
    Soustraction = ""
    Dim Resultat()
    Dim Retenu
    
    'Rechercher le signe des nombres
    If Mid(Nombre1, 1, 1) = "-" Then 'Nombre1 négatif
        If Mid(Nombre2, 1, 1) = "-" Then 'Les deux nombres sont négatifs
            Soustraction = Soustraction(Mid(Nombre2, 2), Mid(Nombre1, 2))
            Exit Function
        Else 'Nombre1 négatif et nombre2 positif
            Soustraction = "-" & Addition(Mid(Nombre1, 2), Nombre2)
            Exit Function
        End If
    Else 'Nombre1 positif
        If Mid(Nombre2, 1, 1) = "-" Then 'Nombre1 positif et Nombre2 négatif
            Soustraction = Addition(Nombre1, Mid(Nombre2, 2))
            Exit Function
        End If
    End If
  
    If (Len(Nombre1) < Len(Nombre2)) Then
        a = Nombre1
        Nombre1 = Nombre2
        Nombre2 = a
    End If

    'Renverser au cas ou le premier argument est inférieur
    If (EstSuperieur(Nombre2, Nombre1)) Then
        Signe = "-"
        a = Nombre1
        Nombre1 = Nombre2
        Nombre2 = a
    End If
    
    ReDim Resultat(1 To Len(Nombre1))
    Retenu = 0
    Jeretiens = False
    i = 0
    Do
        i = i + 1
        n1 = Mid(Nombre1, Len(Nombre1) - i + 1, 1)
        If (i < Len(Nombre2) + 1) Then
            n2 = Mid(Nombre2, Len(Nombre2) - i + 1, 1)
        Else
            n2 = 0
        End If
        If (CInt(Retenu + n2) > CInt(n1)) Then
            n1 = n1 + 10
            Jeretiens = True
        Else
            Jeretiens = False
        End If

        Resultat(i) = n1 - n2 - Retenu
        
        If (Jeretiens = True) Then
            Retenu = 1
        Else
            Retenu = 0
        End If
   Loop While i < Len(Nombre1)
   'Inversion du texte obtenu
   i = 0
   Soustraction = ""
   ZeroDebut = True
   Do
    i = i + 1
    
    If (Resultat(Len(Nombre1) + 1 - i) <> 0 And ZeroDebut = True) Then
        ZeroDebut = False
    End If
    If (ZeroDebut = False) Then Soustraction = Soustraction & Resultat(Len(Nombre1) + 1 - i)
   Loop While i < Len(Nombre1)
   If (Soustraction = "") Then Soustraction = 0
   Soustraction = Signe & Soustraction
   If Soustraction = "-0" Then Soustraction = "0"
End Function
Function Multi_Chiffre(Nombre As String, chiffre As Integer) As String
' Cette fonction multiplie un nombre quelconque par un chiffre entre 0 et 9
'Cette fonction n'est que la mise en oeuvre de la procedure du calcul manuel faite à l'ecole primaire
    If chiffre = 0 Then
        Multi_Chiffre = "0"
        Exit Function
    End If
    Nombre = DeleteZeroDebut(Nombre)
    Dim Retenu As Integer
    Dim n As Integer
    Retenu = 0
    Multi_Chiffre = ""
    i = 0
    Do
        i = i + 1
        n = CInt(Mid(Nombre, Len(Nombre) + 1 - i, 1)) * CInt(chiffre) + CInt(Retenu)
        Multi_Chiffre = Right(n, 1) & Multi_Chiffre
        Retenu = (n - (n Mod 10)) / 10
    Loop While i < Len(Nombre)
    If Retenu <> 0 Then Multi_Chiffre = Retenu & Multi_Chiffre
End Function

Function Multiplication(Nombre1 As String, Nombre2 As String) As String
    Nombre1 = DeleteZeroDebut(Nombre1)
    Nombre2 = DeleteZeroDebut(Nombre2)
    
    'Eliminer les cas zeros
    If (Nombre1 = "0" Or Nombre2 = "0" Or Nombre1 = "-0" Or Nombre2 = "-0") Then
        Multiplication = "0"
        Exit Function
    End If
    
    Signe = ""
    'Regarder le signe
    If Mid(Nombre1, 1, 1) = "-" Then 'Nombre1 négatif
        Nombre1 = Mid(Nombre1, 2)
        If Mid(Nombre2, 1, 1) = "-" Then 'Les deux nombres sont négatif
            Nombre2 = Mid(Nombre2, 2)
        Else
            Signe = "-"
        End If
    Else 'Nombre1 positif
        If Mid(Nombre2, 1, 1) = "-" Then 'Nombre1 positif et Nombre2 négatif
            Signe = "-"
            Nombre2 = Mid(Nombre2, 2)
        End If
    End If

    'Enlever les zero a droites et les ajouter en fin d'opération
    ' cas du premier nombre
    ZeroDroite = ""
    Do
        If Right(Nombre1, 1) = "0" Then
            ZeroDroite = ZeroDroite & "0"
            Nombre1 = Mid(Nombre1, 1, Len(Nombre1) - 1)
        End If

    Loop While Right(Nombre1, 1) = "0"
    'Cas du deuxième nombre
    Do
        If Right(Nombre2, 1) = "0" Then
            ZeroDroite = ZeroDroite & "0"
            Nombre2 = Mid(Nombre2, 1, Len(Nombre2) - 1)
        End If
    Loop While Right(Nombre2, 1) = "0"
    
    If (Len(Nombre1) < Len(Nombre2)) Then
        a = Nombre1
        Nombre1 = Nombre2
        Nombre2 = a
    End If
    
    Multiplication = "0"
    Retenu = ""
    Dim chiffre As Integer
    i = 0
    Do
        i = i + 1
        chiffre = Mid(Nombre2, Len(Nombre2) + 1 - i, 1)
        Multiple_Partiel = Multi_Chiffre(Nombre1, chiffre)
        Multiplication = Addition(Multiplication, Multiple_Partiel & Retenu)
        Retenu = Retenu & "0"
    Loop While i < Len(Nombre2)
    Multiplication = Signe & Multiplication & ZeroDroite
End Function

A voir également

Ajouter un commentaire

Commentaires

Merci !
Tes fonctions sont parfaites, mais il me semble que tu as oublié de déclarer toutes les valeurs utilisées, mais une fois déclarées, tout marche bien !

Ahmonn
Messages postés
4
Date d'inscription
samedi 11 février 2006
Statut
Membre
Dernière intervention
13 mai 2009

Bonjour, je trouve ton programme audacieux et le sujet m'intéresse d'autant
plus que j'en ai fait un dans le même style avec une bonne complexité
temporelle, je me sers de la transformée de fourrier rapide (la version algébrique);
En fait je peux multiplier des nombres de n'importe quel taille, c'est juste une
question de temps et cela dépend surtout de la puissance du compilateur et de la bécanne.
J'en ai fait une application concrète avec un nombre à 2048 chiffres exprimé en base 65536.
Mon programme est sur caml, dis moi si ça t'intéresse.
Messages postés
20
Date d'inscription
mardi 11 janvier 2005
Statut
Membre
Dernière intervention
9 mars 2019

Merci à Amghid2007 pour son commentaire. Je pense que j'ai trouvé l'origine du bug. En fait il se pose chaque fois que la somme du premier chiffre du premier nombre et celui du second nombre est supérieur à 10.
exemple (9+1) vous trouverai 0 au lieu de 10
(98+31) vous trouverai 29 au lieu de 129

Donc a chaque fois, il y a le 1 qui est enlevé. Pour corriger ce problème j'ai juste ajouter après la boocle DO While i<n le code suivant:
If (r > 9) Then Addition = "1" & Addition
Messages postés
14
Date d'inscription
vendredi 23 mars 2007
Statut
Membre
Dernière intervention
6 mars 2010

salut...
chapeau !!!..j'avais l'idé depuis longtemps..mais pour la division c un peu compliqué
j'ai utiliser vos fonctions ça marche mais il y a un bug
99999999999999999999999999999999999999+1= 0 je ne sais pas pourquoi
dans l'ensemble ça marche a mervielle..
amghid l'amateur
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

L'algorithme de Karatsuba est une méthode simple et rapide pour la mutiplication : http://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba.

Pour la division, c'est plus compliqué car la méthode scolaire peut être assez lente sur de grands nombres. Regardes ici par exemple : http://tima-cmp.imag.fr/~guyot/Cours/Arithmetique/pdffile/divis.pdf.
Afficher les 7 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.