Question 197

Comment calculer le modulo de grands nombres ?

L'opération modulo est bien connue en informatique, pour son utilisation dans le cadre de comptage cycliques, tels que des calculs de hash, de remplissage de buffers circulaires ou encore pour le calcul de clefs de contrôle (Check Digit). L'opérateur Mod de Visual Basic permet de réaliser sans mal cette opération pour les types de données natifs. Néanmoins, celui-ci ne suffit pas dans le cadre de calculs sur de (très) grands nombres. Cet article présente une méthode pour réaliser une telle opération.

Les propriétés mathématiques du modulo nous assurent que

(a + b) mod c = ((a mod c) + (b mod c)) mod c
(a * b) mod c = ((a mod c) * (b mod c)) mod c

Nous utiliserons ce résultat dans le code suivant, pour évaluer l'opération modulo, dans le cadre d'un grand dividende, représenté sous forme de chaîne de caractères, et d'un diviseur typé Long. Ceci permet une manipulation plus aisée du résultat, puisque le même type peut lui être appliqué.

'---------------------------------------------------------------------------------------
' Procedure : Modulo
' Author    : FAQ VB
' Date      : 26/08/2008
' Purpose   : Compute Value Mod Divisor, where Value can be an arbitrary large number
'             Value is represented as a base 10 number
'---------------------------------------------------------------------------------------
Public Function Modulo(ByVal Value As String, ByVal Divisor As Long) As Long

    Dim Number As String, Negative As Boolean
    Dim TenModDiv As Long
    Dim i As Long

    'Split S as sign and actual value
    Number = Value
    If Left$(Value, 1) = "-" Then
        Negative = True
        Number = Mid$(Value, 2)
    End If

    'sanity check : Number is only composed of digits
    If Number Like "*[!0-9]*" Then
        Exit Function
    End If

    'Compute the modulo digit by digit
    TenModDiv = 10 Mod Divisor
    Modulo = 0
    For i = 1 To Len(Number)
        Modulo = (TenModDiv * Modulo + (CLng(Mid$(Number, i, 1)) Mod Divisor)) Mod Divisor
    Next i

    If Negative Then Modulo = -Modulo
End Function

L'exemple suivant montre l'utilisation de cette fonction au travers d'un exemple concret :

' Exemple : Calcul de la validité d'une clé INSEE
'           (Numéro de Sécurité Social français)
Private Function IsValidInsee(ByVal s As String) As Boolean

    Dim cle1 As Long, cle2 As Long

    If Len(s) = 15 Then
        cle1 = CLng(Mid$(s, 14))
        cle2 = Modulo(Mid$(s, 1, 13), 97)
        IsValidInsee = (cle1 = (97 - cle2))
    End If

End Function

Private Sub Test()

    Dim ret As Boolean

    ret = IsValidInsee("165047687412356")
    If ret Then
        MsgBox "numéro valide"
    Else
        MsgBox "numéro invalide"
    End If

End Sub

Remarques générales

L'opérateur Mod ne travaille que sur des types Byte, Integer ou Long, limitant effectivement à 2147483647 le plus grand nombre utilisable dans une telle opération.

Il est aussi à remarquer que l'utilisation du type double est à proscrire pour des grands nombres : ceci est du au mode de représentation utilisé, qui ne permet pas une précision arbitraire. Les grands nombres en particulier seront "arrondis" à la plus proche valeur représentable, souvent différente du nombre de départ.

Voir aussi :

Date de publication : 11 septembre 2008
Dernière modification : 11 septembre 2008
Rubriques : Math
Mots-clés : modulo, grand nombre, nombre, reste, division, dividende, diviseur, validation, check, digit, mod, insee