Division d'un réel par un autreRésolu

Question

Bonjour,

Je suis en train de programmer une classe contenant les opérations élémentaires sur les réels. J'ai trouvé cela sur les entiers (BigInt)... mais jamais sur les réels.

L'avantage de ces techniques c'est qu'en stockant les chiffres dans une chaine et la virgule dans une variable numérique (faisant office de mantisse/significande) on peut créer une classe de calcul théoriquement infini, dont la seule limite repose sur le temps de calcul.

Je possède une structure que j'ai appelé Reel, dans celle ci il y a une variable string Valeur contenant la suite de chiffres qu'est un nombre (sans séparateur décimal), une variable integer Significande (l'équivalent la mantisse dans le langage courant) qui contient la position de la virgule (adaptée sur la notation scientifique, à savoir que lorsque Significande = 0, la virgule est le second caractère de la chaine) et une variable String Signe contenant "+" ou "-". Cette structure représente donc théoriquement est réel de longueur (quasi) infinie.

J'ai déjà programmé les fonctions d'addition et de soustraction sur ce type Reel en m'appuyant sur les programmes de CE2 (quand on posait nos opérations ^^). Mais je bloque sur la conception de la fonction de division car les programmes scolaire n'expliquent comment diviser un réel par un autre réel (le diviseur est toujours entier).

Je cherche donc à trouver l'algorithme permettant de diviser un réel par un autre (et si c'est possible également celui de la division euclidienne). Est-ce que quelqu'un pourrait m'indiquer cela ?

Merci beaucoup de votre attention !
Léo Nicoletti.

us_30 · Accepted Answer

Bonsoir Skanenruf, et BruNews... 

Skanenruf, je ne te suis pas vraiment, surtout quand tu dis : "on peut créer une classe de calcul théoriquement infini, dont la seule limite repose sur le temps de calcul." ... Il ne faudrait pas devienne aussi infini, hein ?!
Mais, ce n'est pas là l'objet de ce petit post... Je rebondis juste sur "en optimisant mes fonctions je dois pouvoir calculer la factorielle de 350 en moins de 2 secondes - c'est mon objectif)" ... Quand tu auras bien étudié l'affaire, on pourra comparer mon algorithme... bon, aller, je joue un peu au mystérieux... Tu peux prendre un moment pour jeter un coup d'oeil sur mon modeste site, où il y a le calcul de la factorielle... euh... en 2 secondes je pense que j'obtiendrais une factorielle énorme... environ 5 ou 6 mille...

Amicalement,
Us.

BruNews · Answer

Pure perte de temps que tout cela, les calculs ne se font jamais à base de chaines de caractères sinon ça prendrait un temps fou.

ciao...
BruNews, MVP VC++

Skanenruf · Answer

Bonjour BruNews,

Je vous remercie de votre aide mais en attendant d'apprendre l'assembleur je préfère sacrifier un peu le temps de calcul (en optimisant mes fonctions je dois pouvoir calculer la factorielle de 350 en moins de 2 secondes - c'est mon objectif) au profit de la disparition totale du message "overflow"...

Pour en revenir à la question initiale, j'avais bien pensé à multiplier par l'inverse de la valeur pour diviser mais le seul problème c'est que calculer l'inverse d'un réel revient à effectuer une division dont le diviseur est un réel.

Quelqu'un pourrait t'il m'aider ?
Merci.

us_30 · Answer

lire :
... pas que le temps devienne ...

au lieu de :
... pas devienne ...

Us.

Skanenruf · Answer

Bonjour US_30,

Pour répondre à votre question sur le temps de calcul : les types de VB.NET sont définis sur un certain ensemble de définition (plus ou moins grand selon si le type est signé, selon s'il possède une virgule flottante, selon l'espace binaire alloué). Par conséquent si je vous donne à effectuer une addition de deux nombres d'environ 20 chiffres chacun, il vous sera plus rapide de la faire à la main grâce aux bonnes vieilles techniques apprises à CE2 pour poser les additions que d'utiliser les types de VB.NET qui bloqueront sur la taille du nombre.

Tout cela pour dire que s'il vous est plus rapide de faire le calcul à la main qu'avec l'ordinateur c'est qu'il y a un malaise... Par conséquent je me suis dit qu'en reproduisant à l'identique les opérations que l'on effectuait en primaire sur les réels je pourrai programmer un module de calcul qui pourrait théoriquement calcul des nombres infinis (avec bien évidemment un temps de calcul infini, à savoir proportionnel de façon linéaire à la longueur (en chiffres) des nombres de l'opération). Pour stocker les nombres j'utilise une chaîne (environ 2 000 000 000 de caractères de longueur maximale) et comme les boucles qui balaient la longueur des nombres (chiffre par chiffre) sont définies par des UInteger (valeur maximale : environ 2 000 000 000) j'en conclue donc que mon module de calcul pourrait effectuer des opérations sur des nombres de deux milliards de chiffres sans planter. Bien évidement, le tout repose sur le temps de calcul (qui augmente de façon linéaire sur les additions, soustractions et de façon exponentielles sur les multiplications et divisions).

Tout cela pour dire, que mon module permettrait de faire entièrement disparaître du vocabulaire du mathématicien informatisé le mot "overflow" (puisque la carte mère de son PC aura déjà grillée avant d'atteindre la limite des 2 milliards de chiffres ^^).

Quant à vos fonctions sur les Grands Nombres. Je suis sincèrement impressionné ! Chapeau bas. Très efficace. Je suis actuellement sur la programmation d'un logiciel "Environnement d'étude et e recherche en ingénierie" (derrière ce nom ambitieux se cache juste un logiciel qui essaye de coupler un maximum de fonctions scientifiques (de la chimie à l'astronomie en passant par (et surtout) les mathématiques)).

Est-ce que, s'il vous plaît pouvez vous me dire (si cela ne vous dérange pas) si vos algorithmes de calculs utilisent les chaines pour stocker les nombres (à ma manière) ?

Merci beaucoup pour votre réponse !
Léo Nicoletti.

jmf0 · Answer

350!    .... !!!! (je les mets plus loin pour ne pas les confondre, des ! là, avec le 1er) !!!
Oh mon dieu ! 
Bye !

jmf0 · Answer

Ah pardon (j'ai oublié une question)
Quand tu "sais" calculer la "chose" manuellement : 
- quel format de papier utilises-tu ?
- quel crayon (ou autre) utilises-tu ?

Tout cela m'intéresse énormément....

us_30 · Answer

Bonsoir à tous,

jmf0, je sens un certain ton sarcastique sur ce coup là ?! ... Je pense que le sujet est intéressant pourtant... (T'pardonné d'avance si tu as lu un peu trop vite de travers )... 

Skanenruf, "un logiciel "Environnement d'étude et de recherche en ingénierie" chapeau bas à mon tour... à 16 ans, sur ta fiche... non, je plaisante un peu à mon tour ... 

"pouvez vous me dire (si cela ne vous dérange pas) si vos algorithmes de calculs utilisent les chaines pour stocker les nombres (à ma manière) ?"
Oui, mes algorithmes utilises les chaines (STRING), on n'a pas vraiment le choix me semble-t-il ?! mais bien sur les calculs ne sont pas fait directement dessus... toute l'idée de mes algos est de décomposer le Grand Nombre en partie (comme un saucisson) de X chiffres et de faire les calculs avec... On ressemble le tout au final, dans une string... pour revenir en fait à un point de départ (en qlq sorte). Cette dernière étape est obligatoire pour les utiliser sous Excel comme tout autre fonction... Maintenant, il est évident qu'on gagnerait encore beaucoup de temps dans un logiciel dédié aux calculs de grands nombres, sans faire cette dernière conversion Nombre>Chaine... (Ces conversions sont très long comparativement aux calculs numériques effectifs). Je ne sais pas si je suis bien clair, mais bon... Enfin, surement le fin du fin serait de faire qlq chose avec l'Assembleur, mais là j'en n'ai pas la maitrise, mais je ne sais pas non plus si cela a déjà été fait... BruNews le sait peut-être ?... Enfin, j'ai déjà lu sur le sujet, que certaines classes de calcul de ce type existe déjà, mais je ne sais pas où... Pour avoir cherché un temps sur le sujet, j'ai fini par faire mes propres algo, que j'ai systématiquement comparés à tous ceux que j'ai pu trouver sur internet... les améliorant aux possibles... Reste que le sujet est vaste, et rempli d'erreur de toute sorte, notamment beaucoup voient la complexité algorithme comme une mesure du temps d'exécution... Si il y a bien un lien, en fait, c'est un peu plus subtile que ça... mais, bon, je dérive...

Pour répondre "(à ma manière)", l'ennui c'est que je ne vois pas ou est ton code ?... Pas de site dans ta fiche, pas de source déposé dessus... donc...

Amicalement,
Us.

Skanenruf · Answer

Bonsoir,

Jmf0, je te pardonne car mon sujet est affreusement long à lire je te l'accorde ! Je parlais d'effectuer une addition de deux nombres (entiers ou non, ça ne change quasi rien) dont la longueur (en nombre de chiffres/digits) est trop importante pour tenir dans les types de VB.NET. Ceci est très simple avec une papier et un crayon car il suffit d'additionner les chiffres un par un, on ne gèrera jamais plus d'une retenue. Une unique question de patience et de rigueur (ce que l'ordinateur effectue très bien).

Us_30, ta technique est très intéressante et elle ne m'était pas du tout venu à l'idée. Je suppose que tu gères une retenue sur le dernier chiffre (ou le premier selon le point de vue ^^) de tes subdivisions de la chaine initiale pour effectuer l'opération correctement... Ou je me trompe.

Mon algorithme utilise fréquemment (à chaque chiffre) une formule comme celle ci : Val(Mid(Chaine, i, 1)) pour récupérer un chiffre (dans une boucle de variable i (UInteger)) et le convertir sous forme de variable numérique (byte). Je suppose que ces fonctions (sur les chaines et sur les conversions) sont longues et contribuent grandement à la lenteur de l'algorithme. Il serait intéressant de connaître le temps que prennent les différents types de fonctions (opérations sur les types numériques, subdivisions de chaines, conversions...) pour pouvoir optimiser son algorithme... Si tu en as une idée, où penses-tu que je pourrai trouver ce genre d'infos ?

Je n'ai pas de site web, je renseignerai l'adresse de celui ci quand j'aurais une première version fonctionnelle de mon logiciel ainsi qu'un site potable ! Mais voici les codes (VB.NET 2008) de mes algorithmes d'additio net de soustraction sur les chaines :


    Function Addition(ByVal pNombre1 As tReel, ByVal pNombre2 As tReel) As tReel
        ' Déclarations
        Dim cResultat As tReel
        With cResultat
            .tSigne = "+"
            .tSignificande = 0
            .tValeur = ""
        End With
        pNombre1 = VirguleFlottante(pNombre1, pNombre2)
        pNombre2 = VirguleFlottante(pNombre2, pNombre1)
        ' Addition
        If (pNombre1.tSigne "+" And pNombre2.tSigne "+") Or (pNombre1.tSigne = "-" And pNombre2.tSigne = "-") Then
            cResultat.tValeur = AdditionMonodigitale(pNombre1.tValeur, pNombre2.tValeur)
            cResultat.tSignificande = cResultat.tValeur.Length - (pNombre1.tValeur.Length - (pNombre1.tSignificande + 1)) - 1
            If (pNombre1.tSigne "-" And pNombre2.tSigne "-") Then cResultat.tSigne = "-"
        End If
        ' Soustraction
        If pNombre1.tSigne "+" And pNombre2.tSigne "-" Then
            If Comparaison(pNombre1, pNombre2) = False Then
                Dim cTransfert As tReel = pNombre1
                pNombre1 pNombre2 : pNombre2 cTransfert
                cResultat.tSigne = "-"
            End If
            cResultat.tValeur = SoustractionMonodigitale(pNombre1.tValeur, pNombre2.tValeur)
            cResultat.tSignificande = cResultat.tValeur.Length - (pNombre1.tValeur.Length - (pNombre1.tSignificande + 1)) - 1
        End If
        Return cResultat ' Renvoie du résultat
    End Function ' Fonction d'addition et soustraction

    Function AdditionMonodigitale(ByVal pNombre1 As String, ByVal pNombre2 As String) As String
        Dim cTemp As Byte, cTemp1 As Byte, cTemp2 As Byte
        Dim cResultat As String "", cRetenue As Byte 0
        For i As Integer = pNombre1.Length To 1 Step -1
            ' Addition monodigitale
            cTemp1 = Val(Mid(pNombre1, i, 1))
            cTemp2 = Val(Mid(pNombre2, i, 1))
            cTemp = cTemp1 + cTemp2 + cRetenue
            cRetenue = 0
            ' Retenue
            If Len(cTemp.ToString) = 2 Then
                cRetenue = Val(Mid(cTemp.ToString, 1, 1))
                cTemp = Val(Mid(cTemp.ToString, 2, 1))
            End If
            cResultat = cTemp.ToString & cResultat ' Concaténation
        Next i
        Return cResultat
    End Function ' Renvoie l'addition de deux chaines

    Function SoustractionMonodigitale(ByVal pNombre1 As String, ByVal pNombre2 As String) As String
        Dim cTemp As Byte, cTemp1 As Byte, cTemp2 As Byte
        Dim cResultat As String "", cRetenue As Byte 0
        For i As Integer = pNombre1.Length To 1 Step -1
            ' Soustraction monodigitale
            cTemp1 = Val(Mid(pNombre1, i, 1))
            cTemp2 = Val(Mid(pNombre2, i, 1))
            If i < pNombre1.Length Then
                cTemp = (Val("1" & cTemp1) + cRetenue) - (cTemp2 + 1)
            Else
                cTemp = (Val("1" & cTemp1) + cRetenue) - cTemp2
            End If
            cRetenue = 0
            ' Retenue
            If Len(cTemp.ToString) = 2 Then
                cRetenue = Val(Mid(cTemp.ToString, 1, 1))
                cTemp = Val(Mid(cTemp.ToString, 2, 1))
            End If
            cResultat = cTemp.ToString & cResultat ' Concaténation
        Next i
        Return cResultat
    End Function ' Renvoie la soustraction de deux chaines


Note : Je travaille sur une structure nommée tReel (je possède mes propres conventions, c'est utile sur les gros projets ^^) qui contient une chaine (tValeur) qui stocke les chiffres à la suite, une integer (tSignificande) qui stocke la virgule flottante et une chaine (tSigne) qui stocke le signe (j'ai entendu dire que le type Boolean de Microsoft n'était pas du tout optimisé sur un bit comme on pourrait le croire donc j'ai opté pour une string (peut-être à tord). Par convention (pour être adéquation avec la notation scientifique, j'ai défini que pour tSignificande=0, la virgule (non mentionnée dans la chaine) se trouvait en seconde position).

Exemple : 
Le réel : -123,45 s'écrirait :
tSigne = "-"
tSignificande = 2
tValeur = "12345"

Merci beaucoup une fois de plus de tes réponses !
Léo Nicoletti. En première S au lycée !

us_30 · Answer

Bonjour,

Cette fois pour te répondre à "(à ma manière)", la réponse est clairement oui. Il suffit de regarder mon code sous VBA et le tient pour s'aperçoire que la structure est identique... à ceci près, comme déjà dit, que j'utilise directement un groupe de chiffre, plutôt qu'un seul chiffre... Gain de temps évident... et on raisonne strictement de la même façon en prenant 1 chiffre ou plusieurs à la fois... seul les grandeurs changent... 

Exemple de mon algo du coeur de l'addition :

    'Addition
    For t = lgmul - Multiple + 1 To 1 Step -Multiple
        V1 = Mid$(Nb1, t, Multiple)
        V2 = Mid$(Nb2, t, Multiple)
        R = V1 + V2 + Ret
        lr = Fix(Log(R + 0.11) / ln10) + 1
        If lr Multiple + 1 Then Ret 1 Else Ret = 0
        Mid$(Total, t - lr + Multiple, lr) = CStr(R)
    Next t


A comparer avec le tient :


        For i As Integer = pNombre1.Length To 1 Step -1
            ' Addition monodigitale
            cTemp1 = Val(Mid(pNombre1, i, 1))
            cTemp2 = Val(Mid(pNombre2, i, 1))
            cTemp = cTemp1 + cTemp2 + cRetenue
            cRetenue = 0
            ' Retenue
            If Len(cTemp.ToString) = 2 Then
                cRetenue = Val(Mid(cTemp.ToString, 1, 1))
                cTemp = Val(Mid(cTemp.ToString, 2, 1))
            End If
            cResultat = cTemp.ToString & cResultat ' Concaténation
        Next i


On voit bien que la structure est identique...

Maintenant, sous VB.NET, si tu fais du vrai .NET (c'est à dire que la compilation sera avec un FrameWork sans fonction compatible VB6), je pense (même certain) qu'il optimisera beaucoup l'exécution de ton code... (reste que prendre 1 chiffre par 1, sera tj plus long qu'avec plusieurs). Les optimisations du code en lui-même devrait venir qu'en dernier après que l'algorithme soit lui-même bien optimisé... Ensuite seulement utiliser un Boolean plutôt qu'un String pour tes besoins, sera à faire dans une seconde étape... Je ne connais pas encore de site qui ont fait ce genre de comparatif sous VB.NET... tu devras surement le faire toi-même. Mais il me semble étrange qu'un Boolean (jusqu'ici très optimale sous VBA/VB6) soit devenu soudainement mauvais sous VB.NET ?!... 

Bon, je ne peux que de conseiller de regarder mes algos sur le sujet, si tu veux une bonne base à adapter sous VB.NET...

Amicalement,
Us.

BruNews · Answer

Je n'avais pas eu le temps de suivre la conversation.

Pour calculs ultra rapide de nombres de longueurs indefinies, voir la bibli GMP. C'est bien entendu full C et ASM.

ciao...
BruNews, MVP VC++

us_30 · Answer

Salut BruNews,

Pendant que je te tiens (enfin, c'est qu'une façon de dire les choses ...) puis-je te demander comment on pourrait utiliser cette bibliotheque sous VB... du moins si cela est possible ? ... 

L'adresse exact : http://gmplib.org/

Amicalement, 
Us.

us_30 · Answer

Merci BruNews pour ta réponse. En fait, il doit surement avoir qlq difficultés pour l'utiliser avec VB, car tout simplement il me semble ne l'avoir vu nul part... pourtant, le sujet, lui, est assez bien traité... Ensuite, je crains fort me casser les dents dessus... cela dépasse un peu trop l'étendu de mes modestes connaissances... même si c'est une bonne incitation à essayer ... Si cela pourrait être fait sous VB/VBA cela ouvrirait d'un coup des possibilités de calcul très intéressantes... 

Skanenruf, si je dois tout re-décortiquer, je crains y passer des heures... Pour de répondre, tout de même un peu... plus ou moins dans le désordre ...

Le "$" est spécifique à VBA/VB6 sur plusieurs fonctions de chaînes : MID ou MID$ sont deux façons d'écrire sous VBA/VB6... mais possède une légère différence qui tient au type de variable renvoyé... MID$ renverra un STRING, MID un VARIANT... Ouais, et là, la correspondance sous VB.NET ? Aucune ! Le type VARIANT a été abandonné sous .NET ... Et l'intérêt, ben, juste l'optimisation d'exécution : MID$ est plus rapide que MID ! J'aurai encore des choses à dire, mais tu vois, c'est déjà très long, et cela n'a peu d'importance sous VB.NET... Ici, c'est pas une optimisation algorithmique mais de codage...

Ensuite, les 3 dernières lignes dans la boucle...

lr = Fix(Log(R + 0.11) / ln10) + 1 
permet de connaître le nombre de chiffre qui compose R. Cette formule bizarroïde, est encore une forme de codage optimisé sous VBA. Regardes mon petit tutoriel sur les optimisations pour avoir une idée plus précise de ce que je parle : http://fordom.free.fr/tuto/OPTIMISATION.htm

If lr Multiple + 1 Then Ret 1 Else Ret = 0
Comme je t'ai dit plus haut, une optimisation algorithmique (cette fois) c'est de découper le nombre en plusieurs morceaux de longueur X... Ici, cette information est dans Multiple. Et une remarque simple sous forme de question ? Si tu additionnes 2 nombres de longueur 14 (ou autre) quelle sera au maximum la valeur de la dernière retenue ? Simple 1 ou 0.
Par exemple : 99999999999999 + 99999999999999 = 199999999999998
Ici, on voit l'intérêt de cette remarque, car il suffit d'un IF et on a une attribution de la retenue... De plus, avec la ligne précédente "lr", je travaille sur un nombre (aucune conversion)... plus rapide que sur des chaînes !
Ainsi, non, même si ce que tu fais est identique, c'est moins optimisé : If Len(cTemp.ToString) = 2 Then
cRetenue = Val(Mid(cTemp.ToString, 1, 1))
...  
Si on décortique ton codage, tu fais trop d'opérations sur les chaines. LEN, ensuite l'autre ligne, tu fais une extraction MID, puis une conversion numérique, et enfin un stockage... et tu continus avec la ligne suivante... au final c'est très lourd en temps d'exécution !

Mid$(Total, t - lr + Multiple, lr) = CStr(R)
permet la concaténation. On voit au passage, que toutes ces lignes sont parfaitement identiques à ton algorithmes, dans son principe...
Ici, encore une fois, j'utilise une forme de codage optimisé. En fait, avant de faire le calcul, je fixe la longueur maximum totale du résultat (variable Total), donc par excès (excès d'1 au pire !) grâce à :
'Déclare le résultat à la longueur maxi
Total = String$(lgmul, z)
puis on peut écrire aux emplacements de cette variable Total grâce à cette égalité ci-dessus. Cela évite au programme de redimensionner la longueur de la variable à chaque nouvelle concaténation... tel que cela se produit dans une ligne du type cResultat = cTemp.ToString & cResultat. En gros, j'évite ici des manipulations en interne lors de l'exécution du code... Gros gain de temps !... Maintenant, je ne sais pas sous VB.NET comment faire cette forme d'optimisation, ni même si cela optimisera VB.NET ?... Les pistes d'optimisation du codage du VB.NET son encore (me semble-t-il) à étudier...

Ensuite... "je suppose qu'il faut signaler au compilateur de n'utiliser que le framework ?" Oui, bien sur. Sous VB2008.NET, il suffit de décocher Microsoft.VisualBasic dans le menu Propriétés/ Références... ce qui interdit toute référence à la compatibilité avec les fonctions VB6, pratiques pour ceux qui connaissent, mais très très mauvais en termes de performances... Pour avoir testé un algo de nombre premier, je suis passé de plusieurs secondes sous VB6 à 8 millisecondes sous pur VB.NET ! Sans comparaison !!

Pour le Boolean, le mieux c'est de tester. Considérer la place qu'il prend en mémoire n'est pas complètement justifié pour savoir si cela prend plus de temps ou pas. Pour une raison simple si un Boolean doit être manipuler, l'algorithme sous-jacent qui sera codé, s'occupera surement que du dernier bit... De plus, un Boolean est codé que sur 1 octet sous VB.NET... enfin, là, je parle sous la vigilance de BruNews (il maîtrise bien mieux que moi ces p'tits bits ...)

Amicalement,
Us.

us_30 · Answer

Bonjour,

Euh, petite précision sur la désactivation de la compatibilité à VB6 de VB.NET... Le gain de rapidité se fait surtout pas le fait que tu codera que avec du vrai "VB.NET", en gros, lors de la compilation il n'y aura pas de retranscription de fonctions VB6... qui visiblement prend souvent du temps d'exécution... J'espère que tu vois la subtilité. 

D'ailleurs avec cette référence en moins, tu peux aussi choisir d'autres d'options, qui oblige à un codage des plus propres et rigoureux... gage d'un temps d'exécution amélioré... 

Reste que l'optimisation ne se borne pas qu'à ça, mais aussi aux algorithmes utilisés... Une bonne idée pour raccourcir les calculs se traduira par un gain de temps bien plus sur... 

Qu'en aux facilités, comme le type Variant et autres déclaration de variables absents, ça du mauvais, mais aussi du bon... Le mauvais, c'est la rapidité ! Le bon côté, c'est la souplesse... donc une aide aux débutants en programmation, mais pas seulement... parfois c'est pratique! ... Mais tout ça, c'est un grand débat qui n'est pas près de se tarir. 

Ensuite, l'appel à une bibliothèque ou pas, c'est pas LA question... Car DLL ou pas, c'est un code cohérent, et rapide qu'il faut recherché... Ensuite la DLL est plus un côté pratique... En principe, avant de faire un DLL, il faut mieux savoir bien programmer, car le but de la DLL, est de pouvoir ré-utiliser les fonctions incluses dans une autre programme... d'où une recherche d'une certaine généralité, rapidité, etc. En principe... mais bon... rien n'empêche quiconque d'en faire une, même mal fichu... mais quel intérêt ?! c'est que mon point de vue... D'autres plus chevronné, peuvent penser autrement... Personne n'a la vérité, je crois... libre à toi, donc.

Amicalement,
Us.

us_30 · Answer

Ouille... surement le fils de la discussion a été un peu oublié, ce qui est un peu normal...

Pour la précision de l'idée du "principe inverse de la multiplication des grands nombres (mais dans ce cas on ne peut pas dépasser un groupe de 8 chiffres)" je vais avoir du mal à mieux d'exprimer les choses sans rentrer dans un grand débat... En gros, si tu te rappelles de la façon dont on fait l'addition, je disais qu'on pouvait "saucissonner" un grand nombre en partie de X nombres à traiter. Par exemple, 123456789123456789 + 987654321987654321 sera décomposé en 4 nombres de 9 chiffres et non en 18 nombres de 1 chiffres... soit 123456789 123456789 + 987654321 987654321 ... C'est la même chose pour la soustraction, pour la multiplication... et aussi pour la division... mais pour ce dernier, pour des problèmes de précision de report des restes, on ne peut pas dépasser 8 chiffres... bref, il faut faire l'algo pour mieux comprendre cette remarque... mais bon, finalement, tu peux facilement regarder sur CS le principe de l'algo de la division à 1 chiffre et l'étendre à 8 chiffres... c'est tout le sens de ma prémière idée... ensuite seulement d'autres considérations plus subtiles sont intervenus, notamment pour la multiplication.

Pour l'algo de Newton, je pense que le plus simple est que tu lises ceci :
public.enst-bretagne.fr/~saouter/Multifr.ppt
Diapo 18 et 19 sur l'inverse... dont la justification (en définitive) repose sur la recherche du zéro d'une fonction qui ici est 1/(x-a) par l'algo de Newton... Donc en ré-utilisant la multiplication (en multiprécision) et la soustraction (en multiprécision), on obtient la division en multiprécision... On obtient donc une division, sans faire intervenir LE calcul de LA division... c'est assez simple d'ailleurs de l'implémenter...

Amicalement,
Us.

us_30 · Answer

Dans les liens intéressants, je citerais encore :
http://pagesperso-orange.fr/robert.mellet/mult_prec/mult_pr_02.htm

et si tu fouilles un peu dans ChronoMath qui fut ma première inspiration :
http://serge.mehl.free.fr/anx/facto_javas.html
http://serge.mehl.free.fr/anx/e300_deci.html
etc...

Amicalement,
Us.

us_30 · Answer

Bonjour,

Les résultats invraisemblables sont (presque surement) dus justement au manque de précision de chiffre significatif... Donc, oui l'algorithme marchera pour les grands nombres... mais, il est bien de remarquer se manque de précision avec des petits nombres, puisque ce "problème" se rencontra aussi pour les grands nombres... mais avec plus de chiffres bien sur. Donc il faut garder 2 estimations successives pour savoir si la précision souhaitée est atteinte en utilisant la différence des 2 estimations... Donc, tu vois apparaître ici que l'optimisation va consister à faire preuve de subtilités... En réalité, il faut utiliser la caractéristique de la convergence quadratique. Si au départ tu parts avec X chiffres juste, la prochaine estimation aura X*X chiffres (à plus ou moins quelque chiffre près) justes... Donc on peut donc dire d'avance combien de "tours" l'algo doit faire pour une précision donnée en connaissant au départ le nb de chiffre juste. Et cela sans faire de soustraction... Il conviendra de prendre une petite marge de sécurité astucieusement cogitée. Je te laisse voir. DONC, la valeur de X0 est le point de départ. Il est facile d'en avoir une valeur approximative avec environ 14 ou 15 chiffres dès le départ, avec un calcul usuel. Si on veut A/B on calculera donc A * (1/B), l'algo lui donnera 1/B. Or même si B est un grand nombre, il suffit d'en extraire les premiers chiffres, pour en calculer 1/B... Sur un exemple réduit, si B=1234567890123456789, on peut avoir la première estimation en considérant l'approximation de B par B = 123456789 * 10^10, donc 1/B vaut environ 1/(123456789*10^10) = (1/123456789)*(1/10^10) ... Le premier terme est facile à calculer par une division normale... ici environ 0.0000000081. Le second terme est encore plus simple et ne demande pas de calcul quel que soit l'exposant... 0.0000000001 (=10^-10) (donc on regarde la longueur du nb B réalité). Ensuite tu obtiens déjà une première estimation pour l'algo de Newton, avec déjà 20 chiffres significatifs sur cet exemple. En conclusion, il faut coder un peu de reconnaissance au départ du nombre à traiter mais le gain de temps est extrêmement important. Bon voilà, en espérant d'être pas trop obscure cette fois... 

Amicalement,
Us.

us_30 · Answer

Bonjour,

Ben, si tu regardes le PPT tu as déjà la réponse à ta question. 
Si tu parts avec X chiffres justes, le tour suivant avec l'algo, donnera 2*X, puis 2*(2*X), 2*(2*(2*X)), etc. Soit "T" le nb de tour, alors le nb de chiffres vaut : X * 2 ^ T chiffres justes.
Pour une précision donné Z (compté en nb de chiffres justes), on obtient le nb de tour d'algo par : X * 2 ^ T Z... soit T LN(Z/X)/LN(2) à arrondir par excès... Voir prendre +1 pour être certain d'avoir suffisamment de chiffres justes, comme dit au-dessus. 

Amicalement,
Us.

us_30 · Answer

Bonsoir,

Il me semble évident qu'il y a quelques subtilités qui t'échappes...

Pour me faciliter cette réponse je vais te "sur-commenté" :

Le problème étant que si je souhaite une précision n'étant pas dans le suite quadratique (2 4 8 16 32...) les résultats peuvent être erronés ainsi il faudrait que je fasse une condition qui augmente Z à la valeur quadratique supérieur pour le calcul puis je découpe la chaine avec la première valeur de Z (avec mon Mid() ou une fonction plus optimisée) mais je vois pas trop comment faire...
Par définition, déjà la 2 4 8 16... n'est pas nécessairement celle-ci. Peut-être que tu écris cela pour simplifier la compréhension. 
Si je reprend mon exemple précédent : Calculer "1/1234567890123456789"
Il faudra déjà se fixer le nb de décimale exacte à renvoyer. Disons 50. 
Donc, comme déjà dit, on a X0 qui vaut 0.00000000000000000081 (en espérant que je ne trompe pas dans le nb de zéro )... Soit alors 20 chiffres justes. Dans l'algo de Newton il faut donc faire T ln(50/20)/ln(2) 1.32 tours... bien sur prendre le nb entier supérieur... Soit 2 tours... Deux tours, veut donc dire qu'on aura à l'issu du 1er tour, 2*20 = 40 chiffres justes, au l'issu du deuxième, 2*40 = 80 chiffres justes... On a dit qu'on en veut 50, il suffit de couper donc à 50 chiffres le résultat... (et à l'arrondir à l'occasion)...
Bon, ensuite je ne comprend pas ce que tu veux dire par "je vois pas trop comment faire" ? Faire quoi ? le découpage ?

Sinon, j'arrive à faire marcher l'algorithme pour des nombres comme 14 et tapant 1/14 sur ma calculatrice et en donnant à x une valeur approchée, cette technique (qui simule le précalcul de x qui sera effectué par les types de VB avant la structure itérative) marche (encore) pour obtenir l'inverse d'un nombre comme 123456789 (avec x=0.000000008) mais j'ai peur que pour des très grands nombres l'écart entre le x0 obtenu (par division VB) et a soit trop important pour que l'algorithme puisse démarrer sa division. 
J'entrevois un peu près le sens de ta remarque. Une première chose, quand on prend qu'une partie du nombre (dans l'exemple 123456789) on restreint ce nombre à une taille calculable. Donc on pourra le faire... Mais il existe un cas à voir avant dans le cas où on calcul l'inverse d'un nombre très petit, disons : 1/0.00000000000000000000123 forcément là, il faudra aussi étudier avant le nombre pour le calcul de X0 avec des nombres significatifs. En réalité, cela à le même aire de famille que précédemment. Ici, il faudra avant compté le nb de zéro et débuter le calcul par 1/123 * 10^20... Par symétrie de raisonnement comme avant, on peut calculer 1/123 = 0.00813... et juste en comptant le nb en exposant (ici 20), on peut par simple déplacement de la virgule obtenir X0... Il n'existe donc pas de cas où X0 n'est pas évaluable....  

Bien sur ces remarques s'entendent pour des nombres en multiprécision. Ton code de base en nb Double (16 chiffres) ne peut pas être d'un grand secours, mais si il reste utile comme démarrage avant de passer au grand nombre...

Amicalement,
Us.

us_30 · Answer

Bonsoir,

Ensuite, pour le calcul de puissance, il est clair qu'il faut utiliser l'algorithme qu'on nomme "Exponentiation rapide"... Voir mon code, ou snippet... nécessairement plus rapide qu'une multiplication successive... Si tu essayes de comprendre le fonctionnent de l'exponentiation, tu comprendras pourquoi...

Bon courage à toi. A priori, il est préférable de reprendre sur un nouveau sujet, car tes futures questions se localiseront surement sur un problème précis dans un algo, et non plus sur ce thème général de calcul en multiprécision... qui est déjà dense pour un futur lecteur intéressé à ce sujet...  De plus, permettra à d'autres intervenants d'apporter des nouvelles suggestions. 

Amicalement, 
Us.

Division d'un réel par un autre

31 réponses

Votre réponse

Discussions similaires