Classe bistromathique

[Skynyrd777]

Bonjour à tous,

Je suis sur un gros projet en VB.NET : la réalisation d'une classe de bistromathique. C'est une classe qui permet d'effectuer des calculs sur un registre d'une taille immense (en général 4 294 967 296). Je m'explique : quand vous calculez avec une calculatrice ou un ordinateur, vous avez un nombre limité de chiffres dans vos nombres (par exemple 9 sur certaines calculatrices) c'est ce qu'on appelle le registre. C'est comme si la machine a calculer n'avait que 9 cases et qu'elle ne peut donc pas dépasser une certaine taille de nombres.

Or si je vous mets au défi d'une simple addition de deux nombres vous allez sortir votre calculatrice, le problème mathématique est simple. Mais si je vous donne deux nombres de 20 chiffres comme cette addition par exemple :

90772432101215467690
+ 12378945607598315418
-------------------------
= ?

Vous ne pouvez pas à la calculatrice et même votre ordinateur aura du mal. Pas à cause de la difficulté du calcul (il vous est simple de le faire à la main si vous vous rappelez de la technique du primaire ) mais à cause de la taille du registre. Même en .Net qui est une plate-forme puissante aucun type de variable ne dépasse un registre de 18.

L'idée est donc de créer des algorithmes qui font le calcul comme on le fait à la main, ou plutôt le faisait en primaire. On n'est plus obligé de faire les additions chiffre par chiffre puisque l'ordinateur sait calculer avec plus gros. J'ai par exemple choisi d'effectuer des additions par paquet de 18 chiffres, une rapide gestion des retenues permet de créer des calculs sur des nombres presque infiniment gros ! Je dis presque car les nombres sont stockés dans des chaînes alphanumériques (type string) qui ont en .Net une taille de 2^32 soit 4 294 967 296. Cela représente des additions sur des nombres qui font 4 294 967 295 chiffres !

Les difficultés de la réalisation d'une classe bistromathique (qui gère des calculs sur des aussi grands nombres) se trouve répartie en plusieurs points :
- Il faut programmer l'addition, la soustraction, la multiplication et la division.
- A partir de là on peut programmer les autres fonctions par dessus (en utilisant ces opérations élémentaires).
- C'est une classe de calcul sur les réels, il faut donc gérer la virgule (technique de la virgule flottante) ainsi que le signe (+ ou -).
- Le temps de calcul doit être optimisé, il faut donc réduire au maximum les opérations sur les chaînes et utiliser des formules d'optimisation.

Je me suis lancé là dedans avec l'opération la plus simple : l'addition. Après quelques dizaines d'heures de travail j'obtiens une procédure qui me permet d'additionner des réels extrêmement grands. Le signe n'est pas encore traité, il sera ajouté quand j'aurais programmé la soustraction pour la règle des signes. Voici le fruit de ce dur labeur :

Code:

    Structure Reel
        Dim Significande As String
        Dim Exposant As Integer
        Dim Signe As Boolean
    End Structure

    Sub Main()

        Dim c As Reel, d As Reel
        c.Significande = "173"
        c.Exposant = 1
        d.Significande = "346720"
        d.Exposant = 3
        Dim e As Reel = Addition(c, d)
        MsgBox(e.Significande & vbCrLf & e.Exposant)

    End Sub

    Function Addition(ByVal a As Reel, ByVal b As Reel) As Reel

        ' Déclarations
        Dim r As String = "" ' chaîne résultat
        Dim m As Byte = 18 ' addition par paquet

        ' Ajustement de la virgule flottante
        If a.Significande.Length - a.Exposant > b.Significande.Length - b.Exposant Then
            b.Significande = b.Significande.PadRight((a.Significande.Length - a.Exposant) - (b.Significande.Length - b.Exposant) + b.Significande.Length, "0")
        Else
            a.Significande = a.Significande.PadRight((b.Significande.Length - b.Exposant) - (a.Significande.Length - a.Exposant) + a.Significande.Length, "0")
        End If

        ' Égalisation des longueurs
        If a.Significande.Length > b.Significande.Length Then
            b.Significande = b.Significande.PadLeft(a.Significande.Length, "0")
        Else
            a.Significande = a.Significande.PadLeft(b.Significande.Length, "0")
        End If

        ' Ajustement des longueurs
        Dim ratio As Decimal = a.Significande.Length / m
        If Not Int(ratio) = ratio Then
            a.Significande = a.Significande.PadLeft(m * (Int(ratio) + 1), "0")
            b.Significande = b.Significande.PadLeft(m * (Int(ratio) + 1), "0")
        End If

        ' Addition polydigitale
        Dim ret As UShort = 0 ' retenue
        Dim v1 As ULong = 0, v2 As ULong = 0, vr As ULong = 0 ' variables d'addition
        For t As Integer = a.Significande.Length - m + 1 To 1 Step -m
            v1 = CLng(Mid(a.Significande, t, m))
            v2 = CLng(Mid(b.Significande, t, m))
            vr = v1 + v2 + ret
            If Fix(Log(vr + 0.11) / Log(10)) + 1 = m + 1 Then
                ret = 1
                vr = CLng(Mid(vr.ToString, 2, m))
            Else
                ret = 0
            End If
            If t - m < 1 Then
                If ret = 1 Then ' cas exceptionnel
                    Dim ad As String = vr.ToString.PadLeft(m, "0")
                    r = "1" & ad & r
                Else
                    r = vr.ToString & r
                End If
            Else
                Dim ad As String = vr.ToString.PadLeft(m, "0")
                r = ad & r ' concaténation
            End If
        Next t

        ' Retour du résultat
        Addition.Significande = r
        If a.Exposant > b.Exposant Then
            Addition.Exposant = a.Exposant
        Else
            Addition.Exposant = b.Exposant
        End If

    End Function

Je l'ai programmé pour VB.NET 2010 mais il doit marcher dans les versions antérieures de VB.NET. Collez tout ça dans un module de console et importez la librairie Math du framework (en faisant "Imports System.Math" au dessus de la déclaration du module).

Dans le sub Main() j'effectue un test avec deux réel (c et d). Vous mettez dans la chaîne Significande la liste des chiffres des nombres à additionner et vous indiquez dans Exposant la place de la virgule. Par exemple :

Pour coder c=1,73 et d=346,720

Code:

c.Significande = "173"
c.Exposant = 1
d.Significande = "346720"
d.Exposant = 3

Voilà ce n'est que le début mais je compte bien persévérer !
Merci d'avance pour vos commentaires !


Skynyrd777.

[the prisoner]

Impressionnant, il faudra que je test ça, maintenant que j'ai installé VB Express 2010

[Guemtek]

Bistro ?

Un algorithme d'alcolo ?

[Skynyrd777]

Merci.

@ Guemtek : Oui le nom m'a toujours intrigué ! Et comme ce genre de classe est particulièrement peu connue, impossible de trouver des informations sur le mot. J'en ai juste déduis qu'il signifiait ça car je le vois sur tous les projets de la sorte.

Il est nécessaire de programmer l'addition, puis la soustraction pour pouvoir programmer ensuite ce que l'on appelle l'addition algébrique. C'est à dire une procédure qui va renvoyer les nombres sur l'addition classique (dite arithmétique) ou la soustraction classique en fonction de la règle des signes. Par exemple : un nombre positif plus un nombre négatif et l'addition algébrique renverra les deux nombres sans leurs signes vers une soustraction.

La multiplication est aussi nécessaire à programmer et c'est elle qui doit être le plus optimisée (à la base de nombreuses fonctions à DL ou DIL). La technique simple serait tout simplement d'additionner plusieurs fois pour faire une multiplication. Ainsi, a*b reviendrait à additionner a à a, b fois. Cette technique de l'addition itérative est très lente et pas du tout optimisée ; il va donc falloir que je me cogne les algorithmes compliqués de multiplication. Je me demande si je reproduis notre technique de multiplication ou alors si j'utilise une technique alternative (comme la multiplication à la russe - cf. Banque d'algorithmes).

Enfin, la division est un vrai casse-tête, d'une difficulté élevée, l'algorithme n'est pas à mon niveau je pense. J'avais demandé de l'aide en début d'année scolaire sur vbfrance dans la partie math > algorithmes et on m'avait indiqué une technique puissante à base de l'algorithme de Newton. L'idée étant de multiplier par l'inverse pour diviser (au lieu de a/b faire a * (1/b)). Comme ça, la multiplication est déjà programmée mais il faut trouver comment calculer un inverse ! C'est là qu'advient l'algorithme de Newton... C'est compliqué mais je vais m'essayer à ça quand j'aurai fini la multiplication.

Parmi les opérations élémentaires on classe aussi la comparaison algébrique (inférieur, inférieur ou égal, égal, supérieur ou égal, supérieur) mais ça c'est ultra simple !

[Guemtek]

Ultra simple pour toi peut être mais pour moi c'est du chinois, bien joué a toi pour le partage d'un tel savoir !

[Skynyrd777]

Faut que je trouve le temps de continuer la classe... Je suis même pas sûr de réussir à la finir en un an. J'avais quand même trouvé des techniques pour chaque opération mais bon, c'est vachement chaud (c'est un exercice de BAC +2 en programmation).

[Contenu sponsorisé]