Fonction KARATSUBA (N1,N2) : probleme de recursivite [Résolu]

Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention - 21 oct. 2010 à 19:36 - Dernière réponse : Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention
- 24 oct. 2010 à 23:28
Bonjour,
j'essaye de creer une fonction Karatsuba(N1,N2) ou N1 et N2 sont des entiers
mais celle ci ne fonctionne pas.
pouvez vous m'aider a comprendre mes erreurs
Voici mon algo:
'variables
Dim L1, L2, Lbig As Long
Dim MaxLon As Integer
Dim M As Long
Dim A, B, C, D, E, F, Z As Object
Dim X1, X2, Y1, Y2 As Object
Dim G As Integer
'taille de N1 et N2
MaxLon = 5
L1 = Len(N1)
L2 = Len(N2)
G = StrComp(L1, L2)
If G = -1 Then
Lbig = L2
Else : Lbig = L1
End If
'si N1 et N2 ne sont pas trop grands : multiplication naive
If Lbig < MaxLon Then
Karatsuba = N1 * N2
Exit Function
' sinon methode de Karatsuba
Else : M = Lbig / 2
X1 = Mid(N1, 1, M) ' on divise N1 en 2 blocs
X2 = Mid(N1, M + 1, M)
Y1 = Mid(N2, 1, M) ' on divise N2 en 2 blocs
Y2 = Mid(N2, M + 1, M)
A = Karatsuba(X2, Y2) 'calcul de X2,Y2 soit A
B = Karatsuba(X1, Y1) 'calcul de X1,Y1 soit B
C = Karatsuba(X1 + X2, Y1 + Y2) 'calcul de ...soit C
D = (C - A - B) * 10 ^ M
E = B * 10 ^ (2 * M)
Z = A + D + E
Karatsuba = Z

End If

End Function
Afficher la suite 

Votre réponse

9 réponses

Meilleure réponse
us_30 2117 Messages postés lundi 11 avril 2005Date d'inscription 14 mars 2016 Dernière intervention - 24 oct. 2010 à 12:24
3
Merci
Bonjour à tous,

Pour un algorithme de Karatsuba :
http://www.software.maninweb.de/news/132/279/Karatsuba-algorithm-with-Excel-VBA/d,news_details.html

Amicalement,
Us.

Merci us_30 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 92 internautes ce mois-ci

Commenter la réponse de us_30
cs_Jack 14010 Messages postés samedi 29 décembre 2001Date d'inscription 28 août 2015 Dernière intervention - 22 oct. 2010 à 08:40
0
Merci
Salut

Comment veux-tu qu'on t'aide ?
On ne connait pas la déclaration de ta fonction
On ne sait pas ce que tu en attends et à quoi elle sert
On ne sait pas ce que veut dire "elle ne fonctionne pas"

Es-tu vraiment en VB.Net ?

Quand tu colles du code, merci d'utiliser la coloration syntaxique (3ème icone à droite) = plus facile à lire et conserve les espaces de début de ligne.

Vala
Jack, MVP VB
NB : Je ne répondrai pas aux messages privés

Le savoir est la seule matière qui s'accroit quand on la partage (Socrate)
Commenter la réponse de cs_Jack
cs_Jack 14010 Messages postés samedi 29 décembre 2001Date d'inscription 28 août 2015 Dernière intervention - 22 oct. 2010 à 08:45
0
Merci
Si N1 et N2 sont des entiers, Len(N1) n'a aucun sens.
Pas plus de sens à StrComp(L1, L2) où L1/L2 sont des Long
X1 = Mid(N1, 1, M) ?? alors que X1 est un objet ?

Et tout le reste est pareil ...
C'est du grand n'importe quoi
Commenter la réponse de cs_Jack
Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention - 22 oct. 2010 à 13:11
0
Merci
Salut jack
On ne connait pas la déclaration de ta fonction

en effet c'est
Public Function Karatsuba(ByVal N1 As String, ByVal N2 As String)

On ne sait pas ce que tu en attends et à quoi elle sert

KARATSUBA est le createur d'une methode rapide de multiplication de grands nombres
donc ma fonction sert à multiplier 2 grands nombres(que j'entre en string pour
eviter depassement de capacité)

et ce que j'attends c'est de comprendre pourquoi par ex quand N1=456789 et N2=123456
Karatsuba(456789,123456) renvoie :
"Une exception non gérée du type 'System.StackOverflowException' s'est produite dans Microsoft.VisualBasic.dll"
sur la ligne de code: G = StrComp(L1, L2)

Si N1 et N2 sont des entiers, Len(N1) n'a aucun sens.
Pas plus de sens à StrComp(L1, L2) où L1/L2 sont des Long
X1 = Mid(N1, 1, M) ?? alors que X1 est un objet ?

Tout le probleme est la .J'entre N1 et N2 en string (donc ma fonction renvoie un string) je vais essayer de mettre de l'ordre dans les conversions

cordialement
Commenter la réponse de Taur33
cs_Jack 14010 Messages postés samedi 29 décembre 2001Date d'inscription 28 août 2015 Dernière intervention - 22 oct. 2010 à 15:45
0
Merci
Ok, pourquoi pas des String, mais ne va pas dire que ce sont des entiers.

Dans ton exemple, Karatsuba(456789,123456), tes chiffres sont loin d'être des grands nombres !
En VB6/VBA, un Long (32 bits) peut accueillir des chiffres sans virgule entre -2 147 483 648 à 2 147 483 647
En VB.Net, ce même type s'appelle un Integer.
Un Long .Net, c'est 64 bits et des valeurs entre SuperPasBeaucoup et SuperPleinBeaucoup.

Bien sûr, le résultat de ta fonction fera un grand chiffre, mais ça m'étonnerait franchement qu'il ne puisse tenir dans un Long de 64 bits

Pourquoi utilises-tu des fonctions à la mode VB6 dans un programme .Net ?
Commenter la réponse de cs_Jack
Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention - 22 oct. 2010 à 16:36
0
Merci
Voila l'algo avec les bonnes conversions(je pense)
 Public Function Karatsuba(ByVal N1 As String, ByVal N2 As String)
        'variables
        Dim N1_long, N2_long
        Dim Res As Long
        Dim Lbig, M As Long
        Dim X1_str, X2_str, Y1_str, Y2_str, X3_str, Y3_str As String
        Dim X1_long, X2_long, Y1_long, Y2_long, X3_long, Y3_long As Long
        Dim A_str, B_str, C_str As String
        Dim A_long, B_long, C_long As Long
        Dim D_long, E_long As Long
        Dim MaxLon As Integer

        ' Etape 1: determiner la longeur de N1 et N2 afin de savoir si _
        ' on utilise la methode normale de multiplication(petits nombres) _
        ' ou celle de KARATSUBA(grands nombres)
        MaxLon = 5 ' limite de la methode normale

        If Len(N1) < Len(N2) Then
            Lbig = Len(N2)
        Else : Lbig = Len(N1)
        End If

        If Lbig < MaxLon Then ' si on doit utliser la methode normale
            N1_long = CLng(N1)
            N2_long = CLng(N2)
            Res = N1_long * N2_long
            Karatsuba = CStr(Res) ' resultat de la multiplication
            Exit Function
        Else            ' sinon methode de Karatsuba
            M = Lbig / 2 ' diviser pou regner

            X1_str = Mid(N1, 1, M) ' on divise N1 en 2 blocs
            X2_str = Mid(N1, M + 1, M)
            Y1_str = Mid(N2, 1, M) ' on divise N2 en 2 blocs
            Y2_str = Mid(N2, M + 1, M)

            X1_long = CLng(X1_str)
            X2_long = CLng(X2_str)
            Y1_long = CLng(Y1_str)
            Y2_long = CLng(Y2_str)

            X3_long = X1_long + X2_long
            X3_str = CStr(X3_long)
            Y3_long = Y1_long + Y2_long
            Y3_str = CStr(Y3_long)

            A_str = Karatsuba(X2_str, Y2_str) 'calcul de X2,Y2 
            A_long = CLng(A_str)

            B_str = Karatsuba(X1_str, Y1_str) 'calcul de X1,Y1 
            B_long = CLng(B_str)

            C_str = Karatsuba(X3_str, Y3_str) 'calcul de ...soit C
            C_long = CLng(C_str)

            D_long = (C_long - A_long - B_long) * 10 ^ M
            E_long = B_long * 10 ^ (2 * M)
            Res = A_long + D_long + E_long

            Karatsuba = CStr(Res) ' resultat de la multiplication

        End If
       
    End Function


Le probleme maintenant c'est qu'il ne donne pas les bons resultats
pour 456789*123456 ok il me renvoie 56393342784(c juste)
mais pour 456789123*123456789 i m renvoie 563098575102336(qui est faux) au lieu de
56393718375706047

une erreur sur les calculs à faire ?sur le decoupage en bloc de N1 et N2?ou sur
la recursivité de la fonction'ou autre chose?

Cordialement
Commenter la réponse de Taur33
cs_Jack 14010 Messages postés samedi 29 décembre 2001Date d'inscription 28 août 2015 Dernière intervention - 23 oct. 2010 à 02:27
0
Merci
Mais pourquoi toute cette usine à gaz ?

        Dim N1 As Integer = 456789123
        Dim N2 As Integer = 123456789
        Dim maVar As Long = CLng(N1) * CLng(N2)
        MsgBox(maVar)

te renverra gentiment 56393718375706047
Commenter la réponse de cs_Jack
Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention - 23 oct. 2010 à 20:23
0
Merci
D'accord avec ça
mais multiplier un nombre de + de 100 chiffres par un autre de x chiffres
depasse le cadre d'un décimal
donc il faut trouver une methode : celle de Karatsuba
http://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba
j'ai tenté de la programmer en vb ,c raté
si tu sais faire explique moi

Cordialement
Commenter la réponse de Taur33
Taur33 85 Messages postés vendredi 24 septembre 2010Date d'inscription 20 mai 2011 Dernière intervention - 24 oct. 2010 à 23:28
0
Merci
Merci Us
j'avais pourtant fait des recherches sur Google mais j'étais jamais tombé sur ton lien
faut que je creer maintenant 2 fonctions Add et Sou avant de pouvoir tester le code
de ton lien
Ca devrait pas poser de probleme
Encore merci.
Commenter la réponse de Taur33

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.