Bigint! une structure pour surcharger les entiers (long) sans limite de taille. surcharge des opérations et comparaisons de

Télécharger le projet
Commenter

Description

Plus de risque de OverFlow avec cette classe, vous pouvez enfin calculer 350! (factorielle 350, le résultat fais 741 chiffres, en moins de 2 secondes)
les opérations + - * / ainsi que les comparaisons = <> > < ... et la puissance sont déjà disponibles.
On peut également multiplier un BigInt par un Long ou autre type de base (simple mais il fallait l'implémenter aussi)

Cerise sur le gateau: j'ai joint au zip la classe complexe modifiée pour utiliser des BigInt en partie réelle et partie imaginaire! les complexes décomplexés, sans limite de taille (mais aussi sans décimale du coup...)

Source / Exemple : 


Public Structure BigInt
    Implements IComparable, IEquatable(Of BigInt), IEquatable(Of Long), IComparable(Of Long), IComparable(Of BigInt)

    Private mNumber As String   ' nombre SANS le signe
    Private mSign As Int16      ' -1 0 ou 1
    Private mLength As Int16    ' longueur avec le signe (si négatif)
    Private Const BASE_NOMBRE As Int16 = 10

#Region "Constructeurs"

    ''' <summary>
    ''' constructeurs de BigInt à partir d'un String, ou bien Long, ou bien Double (3 surcharges)
    ''' </summary>
    ''' <param name="initVal">valeur initiale (nombre et un signe - facultatif)</param>
    Public Sub New(ByVal initVal As String)
        ' signe
        If initVal.Substring(0, 1) = "-" Then mSign = -1 ' négatif
        mNumber = ""
        For i As Int16 = 0 To initVal.Length - 1
            If IsNumeric(initVal(i)) Then
                mNumber = mNumber & initVal(i)
            ElseIf i <> 0 Or initVal(i) <> "-" Then
                Throw New System.Exception("Ceci n'est pas un chiffre correctement identifié! 1 seul séparateur décimal (.) 1 signe (-) au début, le reste n'est que des chiffres")
            End If
        Next
        While mNumber <> "" AndAlso mNumber(0) = "0" ' supprimer les zéro redondants
            mNumber = mNumber.Remove(0, 1)
        End While
        If mNumber = "" Then
            mNumber = 0
            mSign = 0
        Else
            mLength = mNumber.Length
            If mSign <> -1 Then mSign = 1 Else mLength += 1
        End If
    End Sub

    Public Sub New(ByVal initVal As Long)
        mSign = Math.Sign(initVal)
        mNumber = CType(Math.Abs(initVal), String)
        mLength = mNumber.Length
    End Sub

    Public Sub New(ByVal initVal As Double)
        mSign = Math.Sign(initVal)
        mNumber = CType(Math.Abs(Int(initVal)), String)
        mLength = mNumber.Length
    End Sub

    Public Sub New(ByVal initVal As Decimal)
        mSign = Math.Sign(initVal)
        mNumber = CType(Math.Abs(initVal), String)
        mLength = mNumber.Length
    End Sub

    Public Shared ReadOnly Empty As BigInt = New BigInt("0")

#End Region

#Region "Surcharge des opérateurs + - * / "

#Region "Opérateurs Principaux (BigInt, BigInt) + - * / "
    ''' <summary>
    ''' surcharge principale des opérateurs habituels + - * / avec 2 nombres BigInt
    ''' </summary>
    ''' <param name="A">1er opérande BigInt</param>
    ''' <param name="B">2eme opérande BigInt</param>
    ''' <returns>somme / soustraction / multiplication / division entière</returns>
    ''' <remarks>la division est entière</remarks>
    Public Shared Operator +(ByVal A As BigInt, ByVal B As BigInt) As BigInt
        ' cas triviaux: 
        If A.Sign = 0 Then
            Return B
        ElseIf B.Sign = 0 Then
            Return A
        ElseIf A.Sign <> B.Sign Then ' soustraction
            Return A - B
        End If

        ' plus grande longueur+1 pour la retenue
        Dim longChiffre As Long = IIf(A.Length > B.Length, A.Length, B.Length)
        Dim arrAddTable(longChiffre, 2) As Long
        Dim lLength As Long
        Dim lresult As String = ""

        ' remplir les 2 tableaux d'entrée
        lLength = A.Abs.Length
        For i As Integer = 0 To lLength - 1
            arrAddTable(i, 0) = Val(A.Abs(lLength - i - 1))
        Next
        lLength = B.Abs.Length
        For i As Integer = 0 To lLength - 1
            arrAddTable(i, 1) = Val(B.Abs(lLength - i - 1))
        Next

        For i As Integer = 0 To longChiffre
            arrAddTable(i, 2) += arrAddTable(i, 0) + arrAddTable(i, 1)
            If arrAddTable(i, 2) >= BASE_NOMBRE Then ' retenue
                ' j'enlève 10 et je retiens 1
                arrAddTable(i + 1, 2) += 1
                arrAddTable(i, 2) = arrAddTable(i, 2) - BASE_NOMBRE
            End If
            lresult = arrAddTable(i, 2) & lresult
        Next

        If B.Sign = -1 Then ' A<0 aussi: -(A+B)
            Return -New BigInt(lresult)
        Else
            Return New BigInt(lresult)
        End If
    End Operator

    Public Shared Operator -(ByVal A As BigInt, ByVal B As BigInt) As BigInt ' A-B
        ' cas triviaux: écartés, pour se ramener à A-B avec A>0 et B>0
        If A.Sign = 0 Then
            Return -B
        ElseIf B.Sign = 0 Then
            Return A
        ElseIf A.Sign <> B.Sign Then ' addition!
            If A.Sign = 1 Then Return A + (-B) Else Return (-A) + B
        ElseIf B.Sign = -1 Then ' A>0, B<0
            Return A + B
        ElseIf A < B Then
            Return -(B - A) ' = A-B
        End If

        ' longueur du résultat
        Dim longChiffre As Long = IIf(A.Length > B.Length, A.Length, B.Length)
        Dim arrSousTable(longChiffre, 2) As Long
        Dim lLength As Long
        Dim lresult As String = ""

        lLength = A.Length
        For i As Integer = 0 To lLength - 1
            arrSousTable(i, 0) = Val(A.Abs(lLength - i - 1))
        Next
        lLength = B.Length
        For i As Integer = 0 To lLength - 1
            arrSousTable(i, 1) = Val(B.Abs(lLength - i - 1))
        Next

        For i As Integer = 0 To (longChiffre - 1)
            If arrSousTable(i, 0) < arrSousTable(i, 1) Then
                'trop petite quantité! j'ajoute 10 et j'enlèverais 1 unité au prochain tour
                arrSousTable(i, 0) += BASE_NOMBRE
                arrSousTable(i + 1, 1) += 1
            End If
            arrSousTable(i, 2) = arrSousTable(i, 0) - arrSousTable(i, 1)
            lresult = arrSousTable(i, 2) & lresult
        Next

        Return New BigInt(lresult)
    End Operator

    'Multiplication (TODO : algorithme de KARATSUBA? )
    Public Shared Operator *(ByVal A As BigInt, ByVal B As BigInt) As BigInt
        Dim result As String = "", BigIntResultat As New BigInt(0)
        Dim lLength As Int16, strTemp(BASE_NOMBRE) As String, lngNumber As Int16

        If A.Sign = 0 OrElse B.Sign = 0 Then Return New BigInt("0")

        ' boucle sur les chiffres de B pour multiplier A
        lLength = B.Abs.Length
        For i As Integer = lLength - 1 To 0 Step -1
            lngNumber = Val(B.Abs(i))
            If lngNumber <> 0 Then
                ' enregistrer dans un tableau les calculs intermédiaires
                If strTemp(lngNumber) Is Nothing Then strTemp(lngNumber) = (A * lngNumber).Value
                BigIntResultat += New BigInt(strTemp(lngNumber) & "".PadRight(lLength - i - 1, "0"))
            End If
        Next

        If A.Sign = B.Sign Then
            Return BigIntResultat
        Else
            Return -BigIntResultat
        End If
    End Operator

    ' division : A = dividende, B = diviseur
    Public Shared Operator /(ByVal A As BigInt, ByVal B As BigInt) As BigInt

        If A.Sign = 0 Then
            Return New BigInt("0")
        ElseIf B.Sign = 0 Then
            Throw New Exception("Erreur! Division par 0")
        End If

        Dim N As Short = B.Abs.Length
        Dim biMinor As New BigInt(B.Abs), biReste As New BigInt(A.Abs)
        Dim i As Long, lResult As String = ""

        Do Until biMinor > A ' recherche du plus grand multiple de B*10 minorant A
            ' multiplication par 10 = décalage d'une unité, ajouter un 0 à droite
            N = N + 1
            biMinor = New BigInt(B.Abs.PadRight(N, "0")) ' B x BASE ^ N
        Loop

        N = N - 1

        For k As Long = 0 To N - B.Abs.Length
            ' décalage à gauche pour le diviseur
            biMinor = New BigInt(biMinor.Abs.Remove(N - k, 1))
            For i = 0 To BASE_NOMBRE - 1
                If (i + 1) * biMinor > biReste Then Exit For
            Next i
            ' i => ajouté au résultat
            lResult = lResult & i.ToString
            ' calcul du reste
            biReste = biReste - i * biMinor

        Next k

        If A.Sign = B.Sign Then
            Return New BigInt(lResult)
        Else
            Return New BigInt("-" & lResult)
        End If

    End Operator

#End Region

#Region "Surcharge autres opérateurs - négation, Puissance(BigInt ^Long), modulo"

    ''' <summary>
    ''' A puissance B (soyons raisonable, dans A ^ B le B ne sera pas un BigInt!)
    ''' </summary>
    ''' <param name="A">BigInt</param>
    ''' <param name="B">Long</param>
    ''' <returns>A ^ B BigInt</returns>
    Public Shared Operator ^(ByVal A As BigInt, ByVal B As Long) As BigInt
        Dim biTmp As New BigInt(1)

        If B = 0 Then
            Return New BigInt(1)
        ElseIf B = 1 Then
            Return A
        ElseIf B < 0 Then ' le résultat ne sera pas un entier /!\
            Return New BigInt(0)
        Else
            Do ' calcul des puissances par mod 2
                If B And 1 Then biTmp = biTmp * A
                B = B \ 2
                A = A * A
            Loop While B > 1

            Return biTmp * A
        End If
    End Operator

    ''' <summary>
    ''' opérateur négation unaire
    ''' </summary>
    ''' <param name="nbr1">BigInt à inverser</param>
    ''' <returns>- nbr1</returns>
    Public Shared Operator -(ByVal nbr1 As BigInt) As BigInt
        nbr1.Sign = -nbr1.Sign
        Return nbr1
    End Operator

    ''' <summary>
    ''' Modulo : reste de la division entière A / B
    ''' </summary>
    ''' <param name="A">BigInt</param>
    ''' <param name="B">BigInt</param>
    ''' <returns>reste de A/B</returns>
    Public Shared Operator Mod(ByVal A As BigInt, ByVal B As BigInt) As BigInt
        If A.Sign = 0 Then
            Return New BigInt("0")
        ElseIf B.Sign = 0 Then
            Throw New Exception("Erreur! Division par 0")
        End If

        Dim N As Short = B.Abs.Length
        Dim biMinor As New BigInt(B.Abs), biReste As New BigInt(A.Abs)
        Dim i As Long, lResult As String = ""

        Do Until biMinor > A ' recherche du plus grand multiple de B*10 minorant A
            ' multiplication par 10 = décalage d'une unité, ajouter un 0 à droite
            N = N + 1
            biMinor = New BigInt(B.Abs.PadRight(N, "0")) ' B x BASE ^ N
        Loop

        N = N - 1
        For k As Long = 0 To N - B.Abs.Length
            ' décalage à gauche pour le diviseur
            biMinor = New BigInt(biMinor.Abs.Remove(N - k, 1))
            For i = 0 To BASE_NOMBRE - 1
                If (i + 1) * biMinor > biReste Then Exit For
            Next i
            ' i => ajouté au résultat
            lResult = lResult & i.ToString
            ' calcul du reste
            biReste = biReste - i * biMinor

        Next k

        If A.Sign = B.Sign Then
            Return biReste
        Else
            Return -biReste
        End If
    End Operator

    ''' <summary>
    ''' Multiplication (BigInt * Long) 
    ''' </summary>
    ''' <param name="A">BigInt</param>
    ''' <param name="B">Long</param>
    ''' <returns>A * B BigInt</returns>
    ''' <remarks>plus simple que BigInt * BinInt et nécessaire pour l'opérateur *</remarks>
    Public Shared Operator *(ByVal A As BigInt, ByVal B As Long) As BigInt
        ' une petite optimisation est possible ici
        Dim lresult As String = ""
        Dim lLength As Long = A.Abs.Length
        Dim loperation As Long
        Dim lretenue As Long = 0

        For i As Long = lLength - 1 To 0 Step -1
            loperation = Val(A.Abs(i)) * B + lretenue
            ' retenue pour le tour suivant
            lretenue = loperation \ BASE_NOMBRE
            ' ôter le chiffre des dizaines
            loperation = loperation Mod BASE_NOMBRE
            lresult = loperation & lresult
        Next
        If lretenue <> 0 Then lresult = lretenue & lresult
        Return New BigInt(lresult)
    End Operator

#End Region

#End Region

#Region "Surcharge des opérateurs de comparaison = <> < > <= >="

    ''' <summary>
    ''' égalité ( l'opérateur = implique l'opérateur <> (différent) )
    ''' </summary>
    ''' <param name="a">A BigInt</param>
    ''' <param name="b">B bigInt</param>
    ''' <returns>True si A=B, False sinon</returns>
    Public Shared Operator =(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        Return a.Sign = b.Sign AndAlso a.Abs = b.Abs
    End Operator
    Public Shared Operator <>(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        Return Not a = b
    End Operator

    ''' <summary>
    ''' opérateurs de comparaison surchargé sur 2 objets de type BigInt ( > < >= <= )
    ''' </summary>
    ''' <param name="a">BigInt</param>
    ''' <param name="b">BigInt</param>
    ''' <returns>True ou False selon la comparaison de A et B</returns>
    ''' <remarks>Seul l'opérateur > est 'calculé', les autres sont déduit de celui ci.</remarks>
    Public Shared Operator >(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        If a.Sign <> b.Sign Then
            Return a.Sign > b.Sign
        ElseIf a.Length <> b.Length Then    ' a et b de même signe, comparer leur longueur
            Return a.Length > b.Length      ' le + long est le + grand
        Else
            Return a.Abs > b.Abs
        End If
    End Operator
    Public Shared Operator <(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        Return Not (a > b OrElse a = b)
    End Operator
    Public Shared Operator >=(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        Return a > b OrElse a = b
    End Operator
    Public Shared Operator <=(ByVal a As BigInt, ByVal b As BigInt) As Boolean
        Return Not a > b
    End Operator

#End Region

#Region "Propriétés usuelles"
    ''' <summary>
    ''' calcul par itérations de la racine carrée.
    ''' </summary>
    ''' <param name="P">BigInt</param>
    ''' <returns>BigInt</returns>
    ''' <remarks>le résultat est une valeur approchée entière BigInt</remarks>
    Public Function Sqr(Optional ByVal P As Double = 1) As BigInt
        ' racine carrée, algo par itérations
        Dim X, Y As BigInt

        Y = (Me + 1) / 2
        X = Me / Y
        Do While Y - X > P
            Y = (X + Y) / 2
            X = Me / Y
        Loop
        Return (X + Y) / 2
    End Function

    ''' <summary>
    ''' Valeur du BigInt, c.à.d sa représentatino littérale
    ''' </summary>
    ''' <remarks>concaténation du signe (-) si besoin et du chiffre</remarks>
    Public ReadOnly Property Value() As String
        Get
            Select Case Me.mSign
                Case 1
                    Return Me.mNumber
                Case -1
                    Return "-" & mNumber
                Case Else
                    Return "0"
            End Select
        End Get
    End Property

    ''' <summary>
    ''' Longueur du nombre
    ''' </summary>
    ''' <value></value>
    ''' <returns></returns>
    ''' <remarks>nombre de chiffres +1 si négatif</remarks>
    Public ReadOnly Property Length() As Int16
        Get
            Return mLength
        End Get
    End Property

    ''' <summary>
    ''' signe du nombre -1 si <0, +1 si >0, 0 si =0
    ''' </summary>
    ''' <value></value>
    ''' <returns></returns>
    ''' <remarks>propriété lecture/écriture: on peut inverser un nombre par ce moyen</remarks>
    Public Property Sign() As Int16
        Get
            Return mSign
        End Get
        ' on peut changer de signe simplement
        Set(ByVal value As Int16)
            If value = 1 Or value = -1 Then mSign = value
        End Set
    End Property

    ''' <summary>
    ''' Valeur absolue du nombre
    ''' </summary>
    ''' <value></value>
    ''' <returns></returns>
    Public ReadOnly Property Abs() As String
        Get
            Return mNumber
        End Get
    End Property

    ''' <summary>
    ''' exposant de 10 (base) = simple décalage, on ajoute ou supprime des zéros
    ''' </summary>
    ''' <param name="exposant">nombre de puissances de 10 à ajouter/supprimer</param>
    ''' <value></value>
    ''' <returns>Me * 10^exposant</returns>
    Public ReadOnly Property Exp(ByVal exposant As Long) As BigInt
        Get
            If exposant > 0 Then ' ajouter n zéros
                If Me.Sign > 0 Then
                    Return New BigInt(Me.Abs.PadRight(Me.Length + exposant, "0"))
                ElseIf Me.Sign < 0 Then
                    Return -New BigInt(Me.Abs.PadRight(Me.Abs.Length + exposant, "0"))
                Else
                    Return New BigInt(0)
                End If
            ElseIf exposant < 0 Then ' supprimer des zéros (ou pas) = arrondi /!\
                If Me.Abs.Length > -exposant Then
                    If Me.Sign > 0 Then
                        Return New BigInt(Me.Abs.Remove(Me.Length + exposant, -exposant))
                    ElseIf Me.Sign < 0 Then
                        Return -New BigInt(Me.Abs.Remove(Me.Abs.Length + exposant, -exposant))
                    Else
                        Return New BigInt(0)
                    End If
                Else
                    Return New BigInt(0)
                End If
            Else
                Return Me
            End If
        End Get
    End Property

    ''' <summary>
    ''' surcharges pour l'implémentation de l'interface IComparable
    ''' </summary>
    ''' <param name="other"></param>
    ''' <returns></returns>
    ''' <remarks>surcharges sur Object, Long, BigInt</remarks>
    Public Overloads Function CompareTo(ByVal other As Object) As Integer Implements IComparable.CompareTo
        If TypeOf other Is Long Then
            Return Me.CompareTo(New BigInt(CType(other, Long)))
        ElseIf TypeOf other Is Integer Then
            Return Me.CompareTo(New BigInt(CType(other, Integer)))
        ElseIf TypeOf other Is BigInt Then
            Return Me.CompareTo(CType(other, BigInt))
        End If

        Throw New ArgumentException("Impossible de convertir l'objet en BigInt")
    End Function
    Public Overloads Function CompareTo(ByVal other As Long) As Integer Implements IComparable(Of Long).CompareTo
        Return Me.CompareTo(New BigInt(other))
    End Function
    Public Overloads Function CompareTo(ByVal other As BigInt) As Integer Implements IComparable(Of BigInt).CompareTo
        If other = Me Then
            Return 0
        ElseIf other < Me Then
            Return -1
        Else
            Return 1
        End If
    End Function

    ''' <summary>
    ''' Surcharges pour l'implémentation de l'interface IEquatable
    ''' </summary>
    ''' <param name="other"></param>
    ''' <returns></returns>
    ''' <remarks>surcharges sur Long, BigInt</remarks>
    Public Overloads Function EqualsTo(ByVal other As BigInt) As Boolean Implements IEquatable(Of BigInt).Equals
        Return other.Sign = Me.Sign AndAlso other.Abs = Me.Abs
    End Function
    Public Overloads Function EqualsTo(ByVal other As Long) As Boolean Implements IEquatable(Of Long).Equals
        Dim a As New BigInt(other)
        Return a.Sign = Me.Sign AndAlso a.Abs = Me.Abs
    End Function

#End Region

#Region "Conversions explicites et implicites"

    ''' <summary>
    ''' conversion implicite, Long ou Double ou String => BigInt, automatique et sans perte de données
    ''' </summary>
    ''' <param name="a"></param>
    ''' <returns></returns>
    Public Shared Widening Operator CType(ByVal a As Long) As BigInt
        Return New BigInt(a)
    End Operator
    ' conversion implicite, Double => BigInt, automatique et sans perte de données
    Public Shared Widening Operator CType(ByVal a As Double) As BigInt
        Return New BigInt(a)
    End Operator
    ' conversion implicite String => BigInt !
    Public Shared Widening Operator CType(ByVal a As String) As BigInt
        Return New BigInt(a)
    End Operator

    ''' <summary>
    ''' conversion implicite BigInt => String
    ''' </summary>
    ''' <param name="c"></param>
    ''' <returns></returns>
    Public Shared Widening Operator CType(ByVal c As BigInt) As String
        Return c.Value
    End Operator

#End Region

End Structure

Conclusion :


J'ai pas cherché à pousser plus loin les performances pour l'instant. J'ai sous la main un algo pour calculer les puissances plus optimisé, je dois aussi rechercher du coté des génériques pour m'éviter tant de surcharge (c'est lourd la surcharge) mais en attendant d'avoir le temps je poste déjà ce résultat. Il faudra implémenter le modulo également.

Et plus tard j'espère construire une classe "BigNum" qui sera les nombres réels sans limite, en utilisant celle ci: simple, un BigNum c'est un BigInt et son exposant (entier, disons Long) en puissance de 10.

ps: j'ai purgé le ZIP des sous-répertoires bin et obj (à priori inutiles)
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (pifou25)