ENSEMBLE DE FONCTION MATHÉMATIQUE (POUR TRES GRAND NOMBRES)
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 2021
-
4 juin 2003 à 21:33
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 2021
-
1 mars 2005 à 09:20
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 1 mars 2005 à 09:20
je suis interessé.... si cela s'appuie sur les methodes de comptages utilisé pour les bouliers, j'imagine le gain !! c'est tellement puissant un boulier (multiplication, fraction, logaritmes.... on peut tout faire avec, avec une simplicité !)
rambc
Messages postés224Date d'inscriptionmercredi 21 avril 2004StatutMembreDernière intervention29 mars 2009 28 févr. 2005 à 18:23
Si cela intéresse quelqu'un, je peux envoyer un document "brouillon" PDF expliquant très rapidement la méthode de KARATSUBA qui permet d'accélerer le calcul d'un produit de deux entiers.
Je l'ai programmé en VBA et j'obtiens les résultats suivants (en comparant avec les fonctions proposées ici) :
TEST 1
Le nombre N°1 a 100 chiffres et le nombre N°1 en a 100 .
cs_Pingouin
Messages postés262Date d'inscriptionlundi 26 août 2002StatutMembreDernière intervention24 août 2005 1 déc. 2004 à 20:22
Ok ben ya pas de koi lol. Bon courage et jspr voir tres bientot le resultat...
MadM@tt
Messages postés2167Date d'inscriptionmardi 11 novembre 2003StatutMembreDernière intervention16 juillet 20091 30 nov. 2004 à 21:17
C'est vrai que je ne saurais meme pas le faire du tout alors..héhé
je l'ai trouvé sur une autre source,
mais pas avec les chaines de caractères...
Je vais m'adapter.
Merci quand même @ +
cs_Pingouin
Messages postés262Date d'inscriptionlundi 26 août 2002StatutMembreDernière intervention24 août 2005 30 nov. 2004 à 20:37
Whaou t exigeant la !! C pas evident un algo pour la racine carrée a la main. Yen a un ki repose sur le fait que la somme des n premiers entiers impairs donne le n² mais pour les décimales c plus coton koike faisable, mais si c pour ton algo sur les nombres premiers un approximation grossiere ca doit suffire non ?
MadM@tt
Messages postés2167Date d'inscriptionmardi 11 novembre 2003StatutMembreDernière intervention16 juillet 20091 30 nov. 2004 à 19:50
Attendez vous n'auriez pas la racine carré ???
MadM@tt
Messages postés2167Date d'inscriptionmardi 11 novembre 2003StatutMembreDernière intervention16 juillet 20091 26 nov. 2004 à 23:57
Merci pour ces fonctions elle vont m'etre très utiles je pense, par contre je suis déçu que ça commence à ramer à environ 1000 chiffres.... Moi qui voulait traiter des nombres possedant des milliers voir des millions, mais bon on peut pas tout avoir :p
DHKold
Messages postés153Date d'inscriptionvendredi 6 décembre 2002StatutMembreDernière intervention29 mai 20052 19 sept. 2004 à 18:41
ok, je vais voir ca
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 23 juil. 2004 à 17:26
il faudrais tester une fois compilé, mais le résultat de ce simple test parle de lui même :
Private Sub Form_Load()
Dim Start As Long
Start = Timer
Call multi2("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
Debug.Print "New : " & Timer - Start
Start = Timer
Call multi("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
Debug.Print "Old : " & Timer - Start
End Sub
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 23 juil. 2004 à 17:24
on pourrais même aller un peu plus loin : éviter la réallocation systématique de la chaine total dans les fonctions :
Private Function multi2(term1 As String, term2 As String)
Dim total2 As String
Dim i As Integer, a As Integer
Dim total As String
Dim nbr As Integer
Dim nbr2 As Integer
Dim nb1 As Integer
total2 = "0"
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
Dim Ind As Long
For i = 0 To L2 - 1
nbd = 0
total = vbNullString
nbr2 = Mid$(term2, L2 - i, 1)
total = Space$(L1)
For a = 0 To L1 - 1
Ind = L1 - a
nb1 = Mid$(term1, Ind, 1)
nbt = nb1 * nbr2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
Mid$(total, Ind, 1) = nbu
Next a
total2 = addition2(nbd & total & String$(i, "0"), total2)
Next i
multi2 = zero2(total2)
End Function
Private Function addition2(term1 As String, term2 As String)
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
Dim i As Integer
Dim nb1 As Integer, nb2 As Integer
Dim total As String
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim Ind As Integer
total = Space$(L1)
For i = 0 To L1 - 1
Ind = L1 - i
nb1 = Mid$(term1, Ind, 1)
nb2 = Mid$(term2, Ind, 1)
nbt = nb1 + nb2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
Mid$(total, Ind, 1) = nbu
Next i
addition2 = zero(nbd & total)
End Function
Private Function soustraction(term1 As String, term2 As String)
Dim mPgdd As Integer: mPgdd = pgdd(term1, term2)
If mPgdd = 0 Then
soustraction = "0"
Exit Function
End If
If mPgdd = 2 Then
soustraction = "-" & soustraction(term2, term1)
Exit Function
End If
Dim nbd As Integer, nbt As Integer, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
Dim i As Integer
Dim total As String
total = Space$(L1)
Dim Ind As Integer
For i = 0 To L1 - 1
Ind = L1 - i
nb1 = Mid$(term1, Ind, 1)
nb2 = Mid$(term2, Ind, 1)
If nb1 - nb2 - nbd2 < 0 Then
nbd = Abs(nb1 - nb2) \ 10 + 1
nb1 = nb1 + nbd * 10
End If
nbu = nb1 - nb2 - nbd2
nbd2 nbd: nbd 0
Mid$(total, Ind, 1) = nbu '& total
Next i
soustraction = zero(total)
End Function
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 23 juil. 2004 à 16:45
J'ai pas touché a tes algos....
mais voici une version qui devrait être sensiblement plus rapide ;)
En quelques mots :
- TYPER toutes les variables (des Variants, c'est lent)
- Ne pas recalculer ce qui ne change pas (pgdd & len, par exemple)
Private Function multi(term1 As String, term2 As String)
Dim total2 As String
Dim i As Integer, a As Integer
Dim total As String
Dim nbr As Integer
Dim nbr2 As Integer
Dim nb1 As Integer
total2 = "0"
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
For i = 0 To L2 - 1
nbd = 0
total = vbNullString
nbr2 = Mid$(term2, L2 - i, 1)
For a = 0 To L1 - 1
nb1 = Mid$(term1, L1 - a, 1)
nbt = nb1 * nbr2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
total = nbu & total
Next a
total2 = addition(nbd & total & String$(i, "0"), total2)
Next i
multi = zero(total2)
End Function
Function zero(term1 As String) As String
Dim i As Integer
For i = 1 To Len(term1) - 1
If Mid$(term1, i, 1) <> "0" Then Exit For
Next i
zero = Mid$(term1, i)
End Function
Private Function addition(term1 As String, term2 As String)
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
Dim i As Integer
Dim nb1 As Integer, nb2 As Integer
Dim total As String
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
For i = 0 To L1 - 1
nb1 = Mid$(term1, L1 - i, 1)
nb2 = Mid$(term2, L1 - i, 1)
nbt = nb1 + nb2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
total = nbu & total
Next i
addition = zero(nbd & total)
End Function
Private Function soustraction(term1 As String, term2 As String)
Dim mPgdd As Integer: mPgdd = pgdd(term1, term2)
If mPgdd = 0 Then
soustraction = "0"
Exit Function
End If
If mPgdd = 2 Then
soustraction = "-" & soustraction(term2, term1)
Exit Function
End If
Dim nbd As Integer, nbt As Integer, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
Dim i As Integer
Dim total As String
For i = 0 To L1 - 1
nb1 = Mid$(term1, L1 - i, 1)
nb2 = Mid$(term2, L1 - i, 1)
If nb1 - nb2 - nbd2 < 0 Then
nbd = Abs(nb1 - nb2) \ 10 + 1
nb1 = nb1 + nbd * 10
End If
nbu = nb1 - nb2 - nbd2
nbd2 nbd: nbd 0
total = nbu & total
Next i
soustraction = zero(total)
End Function
Private Function divis(term1 As String, term2 As String, Optional ByRef rest As Boolean)
Dim total As String: total = "0"
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
Dim i As Integer
Dim reste As String
For i = 1 To 20
Select Case pgdd(term1, term2)
Case 0
total = addition(total, "1")
reste = "0"
Exit For
Case 1
term1 = soustraction(term1, term2)
total = addition(total, "1")
Case 2
reste = term1
Exit For
End Select
Next i
rest = (0 <> LenB(reste))
If rest Then total = total & "r" & reste
divis = zero(total)
End Function
Private Function pgdd(term1 As String, term2 As String) As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 > L2 Then
pgdd = 1
Exit Function
ElseIf L1 < L2 Then
pgdd = 2
Exit Function
End If
Dim i As Integer
For i = 1 To Len(term1)
L1 = Mid$(term1, i, 1)
L2 = Mid$(term2, i, 1)
If L1 > L2 Then
pgdd = 1
Exit Function
ElseIf L1 < L2 Then
pgdd = 2
Exit Function
End If
Next i
pgdd = 0
End Function
DHKold
Messages postés153Date d'inscriptionvendredi 6 décembre 2002StatutMembreDernière intervention29 mai 20052 23 juil. 2004 à 14:16
Je ferai sans doute une amélioration pour supporter les nombre à virgule, mais pour l'instant, j'ai plusieurs client qui attendent leurs scirpts PHP :p
cs_Pingouin
Messages postés262Date d'inscriptionlundi 26 août 2002StatutMembreDernière intervention24 août 2005 1 mai 2004 à 12:29
Je suis un peu decu ca ne gère pas les nompbres a virgule
Mais sinon tres tres bon boulot Si jamais tu fais quelquechose pour les nombres decimaux averti moi, la j'ai ps le temps de bosser dessus.
Mais bon 9/10 kanm^m parce que la chapeau y a du boulot,
Pingouin
DHKold
Messages postés153Date d'inscriptionvendredi 6 décembre 2002StatutMembreDernière intervention29 mai 20052 3 févr. 2004 à 20:41
étrange, moi ca marche correctement
bizmoute
Messages postés29Date d'inscriptionvendredi 21 mars 2003StatutMembreDernière intervention21 novembre 2008 23 janv. 2004 à 01:22
Super comme concept...
cependant... t'as essayé ca : multi("16","16") ?
Je ne sais pas si l'erreur est au niveau du processeur, mais ca m'affiche 156 comme résultat... ;oÞ
Si tu as la solution empresse toi de venir la partager stp...
cs_furybond
Messages postés10Date d'inscriptionvendredi 13 juin 2003StatutMembreDernière intervention29 décembre 2003 25 août 2003 à 13:52
l'antislash n'est pas passé : faut lire
n mod x = n - x * (n
x)
cs_furybond
Messages postés10Date d'inscriptionvendredi 13 juin 2003StatutMembreDernière intervention29 décembre 2003 25 août 2003 à 12:26
n mod x = n - x * (n x)
Pour travailler sur des grands nombres, il vaudrait mieux conserver ceux-ci en binaires dans des tableux d'integer, et d'ecrire une fonction ToString() pour pouvoir les afficher correctment. Ou alors, conserver 1 digit par indice, ce qui eviterait tous ces appels à left, right, ou mid qui prennent enormement de temps cpu.
cs_Arknoth
Messages postés96Date d'inscriptionjeudi 2 janvier 2003StatutMembreDernière intervention22 août 2004 6 juin 2003 à 03:51
erf G oublié d'enlever le "Format" dans la ligne "Len(Format(sDenom))"
cs_Arknoth
Messages postés96Date d'inscriptionjeudi 2 janvier 2003StatutMembreDernière intervention22 août 2004 6 juin 2003 à 03:49
oué en effet, G trouvé pkoi : connard de VB ki transforme les nombres très grands placés en variable "Double". Damn.
--> modif, ca travaille maintenant sur les Strings, avec je pense encore moins de temps de calcul (G essayé^^)
Function Modulo(ByVal sNumerateur As String, ByVal sDenom As String) As Double
On Error GoTo Erreur
Dim sNb As String
Dim iLenDen As Integer
Dim sTemp As String
iLenDen = Len(Format(sDenom))
sNb = sNumerateur
While CDbl(sNb) >= CDbl(sDenom)
If CDbl(Left(sNb, iLenDen)) >= CDbl(sDenom) Then
sTemp = Format(CDbl(Left(sNb, iLenDen)) - CDbl(sDenom))
sNb IIf(CDbl(sTemp) 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen)
Else
sTemp = Format(CDbl(Left(sNb, iLenDen + 1)) - CDbl(sDenom))
sNb IIf(CDbl(sTemp) 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen - 1)
End If
Wend
Modulo = CDbl(sNb)
Exit Function
Erreur:
Modulo = 0
End Function
DHKold
Messages postés153Date d'inscriptionvendredi 6 décembre 2002StatutMembreDernière intervention29 mai 20052 5 juin 2003 à 19:43
j'ai fait des tests pour comparer ta fonction et la mienne, bien que la tienne soit plus rapide le résultat qu'elle renvoie est faut:
64315721649834214273271 mod 2 = 1 et pas 2
8885447741233655996663214 mod 555555 = 279234 et pas 430813
donc je préfère garder ma fonction ;b
cs_Arknoth
Messages postés96Date d'inscriptionjeudi 2 janvier 2003StatutMembreDernière intervention22 août 2004 5 juin 2003 à 18:44
essaye de comparer les temps de calcul de ta fonction modulo et de la mienne (surtout avec un grand chiffrement) - dsl G pas la motivation de le faire, c juste par curiosité ^^
Si tu cherches un générateur de Nombres premiers, le mien est ultra-rapide (par rapport au temps de calcul avec une itération toute simple). et dsl pour les 2 posts identiques, AOL a chié à ce moment-là (pour changer) :p
DHKold
Messages postés153Date d'inscriptionvendredi 6 décembre 2002StatutMembreDernière intervention29 mai 20052 5 juin 2003 à 16:49
C'est en effet pour le cryptage RSA que je calcul de si grands nombre, surtout la fonction mgmod.
cs_Arknoth
Messages postés96Date d'inscriptionjeudi 2 janvier 2003StatutMembreDernière intervention22 août 2004 5 juin 2003 à 14:46
Pour le calcul du modulo j'ai fait ca dans un prog RSA :
(elle est bien plus rapide que la fonction de vébé ^^)
Function Modulo(ByVal nNumerateur As Double, ByVal nDenom As Long) As Double
Dim nNb As Double
Dim iLenDen As Integer
If nNb > nDenom Then
While nNb > nDenom
nNb = nNb - nDenom
Wend
End If
Modulo = nNb
End Function
cs_Arknoth
Messages postés96Date d'inscriptionjeudi 2 janvier 2003StatutMembreDernière intervention22 août 2004 5 juin 2003 à 14:38
Ben our le cryptage Sylric, ca sert à fond, surtout, par exemple, en cryptage RSA. La fonction modulo de VB par défaut ne marche pas au delà de la limite des entiers longs --> crash lors des calculs. En plus, cette fonction modulo est assez lente par rapport à son équivalent "fait à la main".
Juste un truc dans ta source : pense à déclarer et typer ;)
Sinon, super boulot, bravo !
sylric
Messages postés91Date d'inscriptionmardi 21 janvier 2003StatutMembreDernière intervention22 août 2003 5 juin 2003 à 11:39
Je ne remets pas en cause le côté programmation qui marche apparemment très bien, et relativement vite !
Cependant, je ne vois pas très bien l’intérêt de calculer des nombres aussi grands, ou du moins avec une aussi grande précision.
Enfin, du bon boulo quand même !
cs_Patrice99
Messages postés1221Date d'inscriptionjeudi 23 août 2001StatutMembreDernière intervention 9 septembre 2018 5 juin 2003 à 08:49
J'ai vu une fois quelqu'un qui avait fait une classe en C++ pour la manipulation de nombres en précision à la demande : allocation dynamique : une super classe, mais je ne sais plus ou la trouver.
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 4 juin 2003 à 23:00
un portage en c accelererais encore les choses.........
Jujufouq
Messages postés254Date d'inscriptionjeudi 27 décembre 2001StatutMembreDernière intervention 5 mars 2006 4 juin 2003 à 22:56
C'est très bien. Moi aussi j'ai fait un truc comme ça à l'intérieur d'un de mes progs. J'aurais mieux fait de faire une dll... enfin, il est rapide ou pas (j'ai as encore testé)? C'est bien.
Renfield
Messages postés17287Date d'inscriptionmercredi 2 janvier 2002StatutModérateurDernière intervention27 septembre 202174 4 juin 2003 à 21:33
bravo, c'est que c'est du boulot(et des neurones) tout ca !!!
1 mars 2005 à 09:20
28 févr. 2005 à 18:23
Je l'ai programmé en VBA et j'obtiens les résultats suivants (en comparant avec les fonctions proposées ici) :
TEST 1
Le nombre N°1 a 100 chiffres et le nombre N°1 en a 100 .
6484248312346612074105273760496739610942355566742758968174151648322635582372470331999558423228628481
*
1555663255817789031175479074284241314593219940713073894960142813748389321087844775216920735501994733
Méthode KARATSUBA :
10087306841116134372680082506415637898883854900237796828632595647838609649093338128643978796027761503021598342153354294739841108195251474445576484928399010914458114657131027176771624927009887275790573
Méthode Scolaire :
10087306841116134372680082506415637898883854900237796828632595647838609649093338128643978796027761503021598342153354294739841108195251474445576484928399010914458114657131027176771624927009887275790573
Temps KARATSUBA : 0,6601563 s
Temps Scolaire : 4,890625 s
Egalité entre les deux méthodes : Vrai
TEST 2
Le nombre N°1 a 1000 chiffres et le nombre N°1 en a 1000 .
7530808389504628596216512239214761097264590965322031259514500306814190443594822072202595699349055869464842483123466120741052737604967396109423555667427589681741516483226355823724703319995584232286284814625902810395107355255559949106133838746279620952704449561045006595707377296600505473476477728192678833516619350817445296873453368696762523543610747007848425670963242501328326385683234289861635320603232759276495174401364042552654311208856242167372943510797256015282098264823994503311282829558879745383543887020952150623383600340271225693842043724187053131084097961981097081041630748732739439733289838750961416040981728412337129627352650987958805416486836605827375553812536602937841932140064132119972673761800706365667179811741307287760234469564978358992421004009075655317825125834690324993073229835585109833861133524932254304392372418729165386199637563945504238285330992151102647471247368280204645923972003577259352923942772368388562004475046506809676534367075531103895623087003862782713678618730799
*
5277747903752628929590170394164325423960685454409344616377821155063757420102760324348730416121394873415556632558177890311754790742842413145932199407130738949601428137483893210878447752169207355019947331061447811187287482334029882631252344695542832765850649502157435374129604690992803540558761092227737252608447466343771023310401795135775549501136432847284385022333266602585019216608688729546800496579335259844116670541924491330385017165903638451092139587243647109348189690165577404649077949847168771489970589829232682489765581488006826130495851237452666984725600961612328826692209444320846815693716751408093982960242838590667011927118422002044857967912701365918833472211922396342712073397677906844471952269646458236199329997994530029423468460014528824082696841395631289678640981203373592748027346483041698984846056243392695184054881146057695499834546084512755663132823016626114739116818168810252005494418227869397103807627114863887317377473536637669524328064458817246594685144225064843841059929020616
Méthode KARATSUBA :
39745708191270765039617074821012702211274572320801541337412950186793191420738885588409350771865302407072843673572095931411356793703160920922613185652753216248966186948217074446872921027715118749794090734120313131619361559193295032822663289768454698421263845234558902589485803259193500283815783257467382997630380737302002685174738084207889428593362490885095394871675965364590649943753124750144030447000170065403737893663530940822231986623801745609605929616844224799492139998662022593652313493011562838611653039720797745983334765520111143277909182810903953545431996951248984785954951943508946566925797469990973278643669204115629232154809149324552705918604474465292806076253021778565143054422943464679877826350845418140093739500173294006897298471178466477440586516009340207530058922198550078200222628591455818805334681705315147103628812300509276907412866552017130026063654209544793870163798890139728826886562756048528389462496306368369218622896040486283188194812675881364530876522278859218973590293908354971084564312714345374034308414724960069616482391175491285422296220038272829305133359646459487395995830667042383183751129687962569763850827101132083384979675870250451815973328303780895741869051194204195847349718093984172467442830196749434676882543510125033233773627785881876882067138354272742138314003049582016567970000024509287826983100280162503833046534339444528826443122654165043710093361991778772247264503722749968816869467866022935539664154133613546469410416915332436256303920140110052686549074178849608702407782676882434946876128957866439893062724506708234634579141286362494285096333266038284494733560198666737997922442156677849704123910181391796623791221390686755811470049081165575486582433994221128698647782936328246522784880265261584329796795237100352611896792128019027359185412619436182198664851418424807373450678443677196201001693774465238185873076099774643360336410785100179295329616591891671117756810790553368215275547766685536849302830733567683136498339313143740737726526075457025152184
Méthode Scolaire :
39745708191270765039617074821012702211274572320801541337412950186793191420738885588409350771865302407072843673572095931411356793703160920922613185652753216248966186948217074446872921027715118749794090734120313131619361559193295032822663289768454698421263845234558902589485803259193500283815783257467382997630380737302002685174738084207889428593362490885095394871675965364590649943753124750144030447000170065403737893663530940822231986623801745609605929616844224799492139998662022593652313493011562838611653039720797745983334765520111143277909182810903953545431996951248984785954951943508946566925797469990973278643669204115629232154809149324552705918604474465292806076253021778565143054422943464679877826350845418140093739500173294006897298471178466477440586516009340207530058922198550078200222628591455818805334681705315147103628812300509276907412866552017130026063654209544793870163798890139728826886562756048528389462496306368369218622896040486283188194812675881364530876522278859218973590293908354971084564312714345374034308414724960069616482391175491285422296220038272829305133359646459487395995830667042383183751129687962569763850827101132083384979675870250451815973328303780895741869051194204195847349718093984172467442830196749434676882543510125033233773627785881876882067138354272742138314003049582016567970000024509287826983100280162503833046534339444528826443122654165043710093361991778772247264503722749968816869467866022935539664154133613546469410416915332436256303920140110052686549074178849608702407782676882434946876128957866439893062724506708234634579141286362494285096333266038284494733560198666737997922442156677849704123910181391796623791221390686755811470049081165575486582433994221128698647782936328246522784880265261584329796795237100352611896792128019027359185412619436182198664851418424807373450678443677196201001693774465238185873076099774643360336410785100179295329616591891671117756810790553368215275547766685536849302830733567683136498339313143740737726526075457025152184
Temps KARATSUBA : 3,898438 s
Temps Scolaire : 26,25 s
Egalité entre les deux méthodes : Vrai
1 déc. 2004 à 20:22
30 nov. 2004 à 21:17
je l'ai trouvé sur une autre source,
mais pas avec les chaines de caractères...
Je vais m'adapter.
Merci quand même @ +
30 nov. 2004 à 20:37
30 nov. 2004 à 19:50
26 nov. 2004 à 23:57
19 sept. 2004 à 18:41
23 juil. 2004 à 17:26
Private Sub Form_Load()
Dim Start As Long
Start = Timer
Call multi2("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
Debug.Print "New : " & Timer - Start
Start = Timer
Call multi("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
Debug.Print "Old : " & Timer - Start
End Sub
23 juil. 2004 à 17:24
Private Function multi2(term1 As String, term2 As String)
Dim total2 As String
Dim i As Integer, a As Integer
Dim total As String
Dim nbr As Integer
Dim nbr2 As Integer
Dim nb1 As Integer
total2 = "0"
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
Dim Ind As Long
For i = 0 To L2 - 1
nbd = 0
total = vbNullString
nbr2 = Mid$(term2, L2 - i, 1)
total = Space$(L1)
For a = 0 To L1 - 1
Ind = L1 - a
nb1 = Mid$(term1, Ind, 1)
nbt = nb1 * nbr2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
Mid$(total, Ind, 1) = nbu
Next a
total2 = addition2(nbd & total & String$(i, "0"), total2)
Next i
multi2 = zero2(total2)
End Function
Private Function addition2(term1 As String, term2 As String)
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
Dim i As Integer
Dim nb1 As Integer, nb2 As Integer
Dim total As String
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim Ind As Integer
total = Space$(L1)
For i = 0 To L1 - 1
Ind = L1 - i
nb1 = Mid$(term1, Ind, 1)
nb2 = Mid$(term2, Ind, 1)
nbt = nb1 + nb2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
Mid$(total, Ind, 1) = nbu
Next i
addition2 = zero(nbd & total)
End Function
Private Function soustraction(term1 As String, term2 As String)
Dim mPgdd As Integer: mPgdd = pgdd(term1, term2)
If mPgdd = 0 Then
soustraction = "0"
Exit Function
End If
If mPgdd = 2 Then
soustraction = "-" & soustraction(term2, term1)
Exit Function
End If
Dim nbd As Integer, nbt As Integer, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
Dim i As Integer
Dim total As String
total = Space$(L1)
Dim Ind As Integer
For i = 0 To L1 - 1
Ind = L1 - i
nb1 = Mid$(term1, Ind, 1)
nb2 = Mid$(term2, Ind, 1)
If nb1 - nb2 - nbd2 < 0 Then
nbd = Abs(nb1 - nb2) \ 10 + 1
nb1 = nb1 + nbd * 10
End If
nbu = nb1 - nb2 - nbd2
nbd2 nbd: nbd 0
Mid$(total, Ind, 1) = nbu '& total
Next i
soustraction = zero(total)
End Function
23 juil. 2004 à 16:45
mais voici une version qui devrait être sensiblement plus rapide ;)
En quelques mots :
- TYPER toutes les variables (des Variants, c'est lent)
- Ne pas recalculer ce qui ne change pas (pgdd & len, par exemple)
Private Function multi(term1 As String, term2 As String)
Dim total2 As String
Dim i As Integer, a As Integer
Dim total As String
Dim nbr As Integer
Dim nbr2 As Integer
Dim nb1 As Integer
total2 = "0"
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
For i = 0 To L2 - 1
nbd = 0
total = vbNullString
nbr2 = Mid$(term2, L2 - i, 1)
For a = 0 To L1 - 1
nb1 = Mid$(term1, L1 - a, 1)
nbt = nb1 * nbr2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
total = nbu & total
Next a
total2 = addition(nbd & total & String$(i, "0"), total2)
Next i
multi = zero(total2)
End Function
Function zero(term1 As String) As String
Dim i As Integer
For i = 1 To Len(term1) - 1
If Mid$(term1, i, 1) <> "0" Then Exit For
Next i
zero = Mid$(term1, i)
End Function
Private Function addition(term1 As String, term2 As String)
Dim nbd, nbt, nbu As Integer
Dim L1 As Integer, L2 As Integer
Dim i As Integer
Dim nb1 As Integer, nb2 As Integer
Dim total As String
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
For i = 0 To L1 - 1
nb1 = Mid$(term1, L1 - i, 1)
nb2 = Mid$(term2, L1 - i, 1)
nbt = nb1 + nb2 + nbd
nbd nbt \ 10: nbu nbt Mod 10
total = nbu & total
Next i
addition = zero(nbd & total)
End Function
Private Function soustraction(term1 As String, term2 As String)
Dim mPgdd As Integer: mPgdd = pgdd(term1, term2)
If mPgdd = 0 Then
soustraction = "0"
Exit Function
End If
If mPgdd = 2 Then
soustraction = "-" & soustraction(term2, term1)
Exit Function
End If
Dim nbd As Integer, nbt As Integer, nbu As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 < L2 Then
term1 = String$(L2 - L1, "0") & term1
L1 = L2
ElseIf L1 > L2 Then
term2 = String$(L1 - L2, "0") & term2
End If
Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
Dim i As Integer
Dim total As String
For i = 0 To L1 - 1
nb1 = Mid$(term1, L1 - i, 1)
nb2 = Mid$(term2, L1 - i, 1)
If nb1 - nb2 - nbd2 < 0 Then
nbd = Abs(nb1 - nb2) \ 10 + 1
nb1 = nb1 + nbd * 10
End If
nbu = nb1 - nb2 - nbd2
nbd2 nbd: nbd 0
total = nbu & total
Next i
soustraction = zero(total)
End Function
Private Function divis(term1 As String, term2 As String, Optional ByRef rest As Boolean)
Dim total As String: total = "0"
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
Dim nbz As Integer, nbr1 As String
Do While L1 > L2
nbz = L1 - L2 - 1
nbr1 = term2 & String$(nbz, "0")
term1 = soustraction(term1, nbr1)
L1 = Len(term1)
total = addition(total, "1" & String$(nbz, "0"))
Loop
Dim i As Integer
Dim reste As String
For i = 1 To 20
Select Case pgdd(term1, term2)
Case 0
total = addition(total, "1")
reste = "0"
Exit For
Case 1
term1 = soustraction(term1, term2)
total = addition(total, "1")
Case 2
reste = term1
Exit For
End Select
Next i
rest = (0 <> LenB(reste))
If rest Then total = total & "r" & reste
divis = zero(total)
End Function
Private Function pgdd(term1 As String, term2 As String) As Integer
Dim L1 As Integer, L2 As Integer
L1 Len(term1): L2 Len(term2)
If L1 > L2 Then
pgdd = 1
Exit Function
ElseIf L1 < L2 Then
pgdd = 2
Exit Function
End If
Dim i As Integer
For i = 1 To Len(term1)
L1 = Mid$(term1, i, 1)
L2 = Mid$(term2, i, 1)
If L1 > L2 Then
pgdd = 1
Exit Function
ElseIf L1 < L2 Then
pgdd = 2
Exit Function
End If
Next i
pgdd = 0
End Function
23 juil. 2004 à 14:16
1 mai 2004 à 12:29
Mais sinon tres tres bon boulot Si jamais tu fais quelquechose pour les nombres decimaux averti moi, la j'ai ps le temps de bosser dessus.
Mais bon 9/10 kanm^m parce que la chapeau y a du boulot,
Pingouin
3 févr. 2004 à 20:41
23 janv. 2004 à 01:22
cependant... t'as essayé ca : multi("16","16") ?
Je ne sais pas si l'erreur est au niveau du processeur, mais ca m'affiche 156 comme résultat... ;oÞ
Si tu as la solution empresse toi de venir la partager stp...
25 août 2003 à 13:52
n mod x = n - x * (n
x)
25 août 2003 à 12:26
Pour travailler sur des grands nombres, il vaudrait mieux conserver ceux-ci en binaires dans des tableux d'integer, et d'ecrire une fonction ToString() pour pouvoir les afficher correctment. Ou alors, conserver 1 digit par indice, ce qui eviterait tous ces appels à left, right, ou mid qui prennent enormement de temps cpu.
6 juin 2003 à 03:51
6 juin 2003 à 03:49
--> modif, ca travaille maintenant sur les Strings, avec je pense encore moins de temps de calcul (G essayé^^)
Function Modulo(ByVal sNumerateur As String, ByVal sDenom As String) As Double
On Error GoTo Erreur
Dim sNb As String
Dim iLenDen As Integer
Dim sTemp As String
iLenDen = Len(Format(sDenom))
sNb = sNumerateur
While CDbl(sNb) >= CDbl(sDenom)
If CDbl(Left(sNb, iLenDen)) >= CDbl(sDenom) Then
sTemp = Format(CDbl(Left(sNb, iLenDen)) - CDbl(sDenom))
sNb IIf(CDbl(sTemp) 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen)
Else
sTemp = Format(CDbl(Left(sNb, iLenDen + 1)) - CDbl(sDenom))
sNb IIf(CDbl(sTemp) 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen - 1)
End If
Wend
Modulo = CDbl(sNb)
Exit Function
Erreur:
Modulo = 0
End Function
5 juin 2003 à 19:43
64315721649834214273271 mod 2 = 1 et pas 2
8885447741233655996663214 mod 555555 = 279234 et pas 430813
donc je préfère garder ma fonction ;b
5 juin 2003 à 18:44
Si tu cherches un générateur de Nombres premiers, le mien est ultra-rapide (par rapport au temps de calcul avec une itération toute simple). et dsl pour les 2 posts identiques, AOL a chié à ce moment-là (pour changer) :p
5 juin 2003 à 16:49
5 juin 2003 à 14:46
(elle est bien plus rapide que la fonction de vébé ^^)
Function Modulo(ByVal nNumerateur As Double, ByVal nDenom As Long) As Double
Dim nNb As Double
Dim iLenDen As Integer
iLenDen = Len(Format(nDenom))
nNb = nNumerateur
While nNb > nDenom * 10
nNb = nNb - nDenom * 10 ^ (Len(Format(nNb, "0")) - (iLenDen + IIf(Val(Left(Format(nNb, "0"), iLenDen)) > nDenom, 0, 1)))
Wend
If nNb > nDenom Then
While nNb > nDenom
nNb = nNb - nDenom
Wend
End If
Modulo = nNb
End Function
5 juin 2003 à 14:38
Juste un truc dans ta source : pense à déclarer et typer ;)
Sinon, super boulot, bravo !
5 juin 2003 à 11:39
Cependant, je ne vois pas très bien l’intérêt de calculer des nombres aussi grands, ou du moins avec une aussi grande précision.
Enfin, du bon boulo quand même !
5 juin 2003 à 08:49
4 juin 2003 à 23:00
4 juin 2003 à 22:56
4 juin 2003 à 21:33