ASTUCE MATHÉMATIQUE

jordane45 Messages postés 38222 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 23 juillet 2024 - 24 sept. 2010 à 17:06
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 - 22 déc. 2010 à 00:14
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/52323-astuce-mathematique

us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
22 déc. 2010 à 00:14
... et comme disait le plus grand théoricien : "La théorie c'est bien, la pratique c'est mieux"...

Amicalement,
Us.
dheroux Messages postés 52 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 11 juin 2014
19 déc. 2010 à 06:19
Je raisonne sur ce problème de façon théorique et non pratique. En théorie, il ne pourra jamais avoir un autre résultat que celui énoncé. C'est la propriété même d'un logarithme décimal que personne ne pourra remettre en cause.
Bonnes fêtes de fin d'année.
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
18 déc. 2010 à 16:41
Je ferais une autre remarque qui n'aura échappé à personne... La limitation pratique du calcul, qui sera arrondi nécessairement rends faux le calcul au-delà d'un certain nombre...

Exemple en VB :

Debug.Print Log(999999999999#) / Log(10) ' 11 décimale => renvoi 11,9999999999996
Debug.Print Log(9999999999999#) / Log(10) ' 12 décimale => renvoi 13 au lieu de 12,99999999999999999

Il est important de connaître les limitations aussi...

Amicalement,
Us.
dheroux Messages postés 52 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 11 juin 2014
16 déc. 2010 à 19:18
Réponse à US_30:
Quand j'écrivais log(95874) je précisais bien en toutes lettres qu'il s'agissait du logarithme décimal.
Dans certains livres ou calculette on trouve log(pour logarithme décimal) et ln (pour logarithme népérien)
Quand à la rapidité du calcul, effectivement c'est lent, mais l'objet de mon écrit ne ciblait pas ce problème.
Merci et bonne soirée.
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
16 déc. 2010 à 18:00
Ah tient ! j'avais pas fait attention, mais ce que dit dheroux est incomplet !!

La fonction LOG est en base 2 => logarithme népérien...

Il faut donc diviser le nombre par LOG(10) pour le mettre sur la base 10... Soit log(95874)/log(10)=4,981 au lieu de log(95874)=4,981...

CQFD... Encore un mauvais point pour la rapidité...

Amicalement,
Us.
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 74
9 déc. 2010 à 08:26
qui Rame completement non... mais qui pourrais tourner plus vite...

choix technologique ? oui, au final du code mieux pense, mieux ecrit... sans changer de machine, ca s'apparente a de l'optimisation, non ?

idem en SQL, on peut ecrire deux requetes qui font le meme job, avec des differences de temps d'execution dantesques...

bref, quelle que soit la techno, faut bien voir qu'au final c'est l'ASM derriere, avec ses jumps, et autres registres... On ne cherche pas a faire le code le plus facile a relire, mais bien le plus efficace. Le coup du log fonctionne, par exemple, mais a quel prix ? imaginez un soft qui génère des rappports toutes les nuits et qui utiliserait ce genre de pirouette... les quelques dizaines de cycles économisés sur des rapports suffisamment grands pourraient vous faire économiser un sacre temps...
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010
8 déc. 2010 à 19:31
C'est une erreur dans le principe que de se reposer sur le matériel du client, d'autant que souvent dans les entreprises le matériel est pas si actuel que ça, on préfère du vieux dont on sait qu'il marche à un nouveau dont on ignore les failles, et il y a bien des situations actuelles où on refuse pas de minuscules optimisations (genre dans les moteurs 3d)
Mais bon faut savoir raisonnable, quand on apprend à coder c'est beaucoup plus propre de faire des boucles au lieu des goto dans ce cas-ci...
PWM63 Messages postés 127 Date d'inscription lundi 11 octobre 2004 Statut Membre Dernière intervention 18 mai 2016
8 déc. 2010 à 18:36
Tu connais beaucoup de softs qui rament encore sur des pc actuels ?

Même Office rame pas sur mon PC du boulot qui n'est pourtant pas tout jeune.

Par contre, chez moi, j'ai bien 1 PC actuel, et encore, 1 bon rapport qualité prix, pas 1 bête de course, et je trouve que les applis sont très réactives.

Pour moi, le gain de temps, je ne le fais pas dans le choix des lignes de code, mais dans le choix des technologies.
Par exemple, mon 1er programme VB professionnel, 1 table = 1 fichier, en accès séquentiel, ça ramait vraiment du tonnerre, surtout quand j'avais 1 tri bulle à faire sur les données.
1ère optimisation de l'époque, tri dichotomique, j'ai amélioré la vitesse.
Ensuite, je suis passé au XML, gain de temps faramineux. Maintenant, je suis au SQL, c'est encore plus rapide.

La rapidité ne se gagne plus à l'optimisation des lignes de code, mais au choix des technologies utilisées.
Et l'autre gain non négligeable à coder concis, c'est le temps de relecture du code quand on doit revenir dessus 2 ans plus tard.
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 74
8 déc. 2010 à 14:16
"Entièrement d'accord avec Nathansecret et avec Saros, surtout étant donné la puissance des PC actuels."

et voila pourquoi avec nos pc dits actuels tant de softs rament encore... si on se repose sur le matériel pour produire du code lourd sous ce pretexte...
PWM63 Messages postés 127 Date d'inscription lundi 11 octobre 2004 Statut Membre Dernière intervention 18 mai 2016
15 nov. 2010 à 13:32
Entièrement d'accord avec Nathansecret et avec Saros, surtout étant donné la puissance des PC actuels.

En effet, j'estime que maintenant, et en général, il est nettement plus préférable de passer moins de temps à se relire, ou de relire une autre personne, ou (surtout) qu'une autre personne me relise, en choisissant un code le plus clair possible, quitte à multiplier par 1000 le temps d'exécution de l'instruction.

C'est vrai, 1 Next deviendra JMP en assembleur, mais je préfère 100 fois lire 1 boucle For Next que de tester un compteur avant de renvoyer sur la bonne étiquette, même si ça prends plus de temps machine.
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010
15 nov. 2010 à 00:38
"par qui, ceux qui sont passés de l'école à l'école ?"
plutôt par ceux qui aiment pas passer plus de temps que nécessaire à relire le code des autres. Coder en bas niveau ça va sur des codes comme celui-ci mais quand ça prend plus d'envergure c'est vite l'enfer
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
14 nov. 2010 à 23:17
J'oubliais, tu pourras chercher longtemps ce que le CPU peut comprendre d'autre qu'un JMP (le vilain goto).
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
14 nov. 2010 à 23:14
par qui, ceux qui sont passés de l'école à l'école ?

Il est clair que nbr a été NEG au préalable.
bnitoa PROC ; ECX DWORD dwnum, RDX char* szdst
test ecx, ecx
jns short bnultoa
mov byte ptr[rdx], 45
neg ecx
add rdx, 1
bnitoa ENDPbnultoa PROC ; ECX DWORD dwnum, RDX char* szdst
cmp ecx, 10
jae short sup9
add cl, 48
lea rax, [rdx+1]
mov byte ptr[rdx], cl
ret 0
sup9:
lea r9, [rdx + 2] ; R9 pointeur final SANS LE ZERO
cmp ecx, 100
jb short lenOK
etc, etc

bnultao ENDP
nathansecret Messages postés 63 Date d'inscription mardi 11 novembre 2008 Statut Membre Dernière intervention 31 octobre 2011
14 nov. 2010 à 19:14
De plus, utiliser les Goto est très déconseillé...
nathansecret Messages postés 63 Date d'inscription mardi 11 novembre 2008 Statut Membre Dernière intervention 31 octobre 2011
14 nov. 2010 à 18:43
BruNews > Attention :

nbr doit être de type UNSIGNED.

Sinon :

DWORD nbrLen(DWORD nbr)
{
DWORD L = 1;

//////////////
// RAJOUTE ://

if nbr < 0
nbr = 0 - nbr;

// ET VOILA !//
///////////////

if(nbr < 10) goto lenEXIT;
L = 2;
if(nbr < 100) goto lenEXIT;
// etc...
L = 9;
if(nbr < 1000000000) goto lenEXIT;
L = 10;
lenEXIT: return L;
}
betamu Messages postés 6 Date d'inscription mardi 1 mai 2007 Statut Membre Dernière intervention 29 mai 2009
13 oct. 2010 à 01:46
Lorsqu'un nombre est proche d'une puissance de 10 sa représentation interne en nombre flottant (en base 2 pour la mantisse) peut être sujette à caution sur le nombre de chiffres avant la vorgule.
Toutes les puissances de 10 sont des multiples de 2 puisque 10 est un multiple de 5 et 2.
Au bout d'un moment la mantisse ne fournit plus assez de chiffres et arrondi
par défaut de telle manière qu'on obtient un nombre inférieur de chiffres d'une unité.

Je tenais à signaler que suite à une chaine de calculs le résultat obtenu pouvait être proche du résultat attendu, bien sûr, mais sans précaution
d'arrondi on peut trouver un nombre erronné de chiffres.

Exemple (sur ma calculatrice Casio ):
racinecarrée(10 000) = 100
racinecarrée( 9 999,999999) = 100 !!!
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
10 oct. 2010 à 12:37
Bonjour,

Perso, je suis d'accord avec BruNews... Ouais, je sais je ramène ma fraise...

Peut-être qu'une petite boucle en faisant une division par multiple de 10 et test du résultat compris entre >=1 et <10 serait plus agréable, même si un schtouille moins rapide...

Ceci dit, le LOG10 est tout même plus rapide (et plus logique à utiliser sur un nombre) que les horreurs de conversion en string pour en tester la longueur associée à une série d'instruction pour retirer les décimales...

Amicalement,
Us.
radinor Messages postés 12 Date d'inscription mercredi 11 mars 2009 Statut Membre Dernière intervention 24 octobre 2011
27 sept. 2010 à 22:01
c'est par définition que log x = a*10^y (|a| < 10) vaut log a + y ce qui est équivalent à : nombre de chiffres de x = y + 1.
Ce sont les mathématiques.
En programmation tout langage à une fonction de longueur de chaîne. En VBA Excel j'utilise Len("" & nombre)
Quant à Betamu il avance des hypothèses qu'il ne maitrise pas.
Le résultat ne peut pas être faux, et sa solution n'en est pas une.
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
27 sept. 2010 à 12:52
En utilisant amath (librairie Intel), fonction log():
2 RCPSS
9 MULSS
1 CVTSI2SS
pour citer les + lourdes,
sur un total de 38 instructions SSE sur FLOAT32. En tenant compte du fait qu'il faut au préalable passer par un CVTSI2SS pour le param d'entrée.
Tout ceci nous amène au moins à 20 FOIS PLUS LENT que ce que j'ai montré au début. On est très loin du facteur 2.
Si on utilise les calculs en FPU standard, au plaisir...
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010
27 sept. 2010 à 11:28
Ça en prend au moins 2 fois plus, après mort ou pas ça dépend de ce qu'on en fait :)
Le français qui a battu le record du calcul des decimales de Pi récemment a utilisé un algorithme asymtotiquement plus faible que celui qui avait précedemment été utilisé, mais il l'a fait fonctionner 8x plus vite en optimisant les algos de multiplication au max etc.
Pour lui un facteur 2 ça se permettait pas :x
PWM63 Messages postés 127 Date d'inscription lundi 11 octobre 2004 Statut Membre Dernière intervention 18 mai 2016
27 sept. 2010 à 10:39
Log, je sais pas, d'ailleurs, Betamu nous l'a à priori prouvé (je n'ai pas vérifié et je n'en ai pas envie)...
Et si jamais je devais compter le nombre de caractères d'un nombre, j'aimerai vraiment être certain !

Bref, pour compter le nombre de caractères d'un nombre, je ferai ainsi :

Dim entier As Integer = 10000
Dim nb_car_entier As Integer = entier.ToString.Length

ou encore sous forme de fonction si elle est utilisée au moins 2 fois dans le code :

Function nb_car_entier(ByVal entier As Integer) As Integer
Return entier.ToString.Length
End Function

Alors là, bien sûr, c'est du VB.Net, mais bon, c'est juste une question de syntaxe, la logique reste la même.

1) Le code est concis et compréhensible : quand on lit, on sait ce que ça fait, on sait que ça marche toujours, et même pas besoin de commenter
2) En tour de cycle CPU, je suppose que c'est pas la mort (clin d'oeil à BruNews)
betamu Messages postés 6 Date d'inscription mardi 1 mai 2007 Statut Membre Dernière intervention 29 mai 2009
27 sept. 2010 à 09:39
Suivant la représentation interne du nombre le résultat peut être faux.

Ainsi suite à une série de calculs on peut avoir pour 10 :
résultats_suite_de_calculs = 9,999 999 995
n'aurait :
qu'un chiffre avant la virgule
et
9 chiffres après la virgule

La procédure est à améliorer si le nombre est proche d'un nombre entier
par un arrondi de 5 unités de la plus petite unité significative.

arrondi_à_l_unité( 0,000 000 005 + résultats_suite_de_calculs ) ) = 10
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
27 sept. 2010 à 09:18
Un compilo moderne comme VC++ ou Intel produit un code optimal à 98% des cas.
Pour ce qui est de la parallélisation, là c'est à tout coup. Jamais il ne rate l'entrelacement des instructions ni leur alignement.
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010
27 sept. 2010 à 00:44
En effet, utiliser le log pour tester la longueur c'est hautement sous-optimal :x
mais c'est toujours amusant à remarquer
BruNews-> le traitement des cmp & mov en parallèle c'est detecté automatiquement à la compilation ?
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
26 sept. 2010 à 12:39
Salut,
si "en mode programmation" s'entend VB ou tout autre interprété, inutile de lire ce qui suit puisque les perfs ne sont pas à l'ordre du jour.
En vraie prog (C et/ou ASM) il en va tout autrment.

ORIGINAL:
Une astuce intéressante mais totalement inutile en mode programmation !
Comment déterminer le nombre de chiffres d'un nombre par une méthode purement mathématique.

NEGATION DE TOUT CELA:
La longueur d'un nombre base 10 (représentation humaine ordinaire) est indispensable. Grace à cela on évite un retournement des octets lors d'une converion comme atoi() et on retourne direct le pointeur sur fin d'écriture sans reparcours.
Enorme gain en perfs, exemple en module de reporting:
char buf[1000], *c;
c = bnitoa(nbr1, buf);
*c++ = 9; // TABULATION
c = bnitoa(nbr12, c);
etc...

Une méthode purement mathématique ne doit jamais être transcrite direct en prog sans passage par le cerveau d'un informaticien.
Exemple:
Combien de cycles CPU pour la longueur par le log ??? Enorme.
Nettement plus rapide:
DWORD nbrLen(DWORD nbr)
{
DWORD L = 1;
if(nbr < 10) goto lenEXIT;
L = 2;
if(nbr < 100) goto lenEXIT;
// etc...
L = 9;
if(nbr < 1000000000) goto lenEXIT;
L = 10;
lenEXIT: return L;
}
On sortira en 9 cycles dans le pire des cas (CMP et MOV parallélisables).
Pour un nombre 64 bits, je passe par un tableau indexé prédéfini, tout aussi rapide.
aeder Messages postés 14 Date d'inscription vendredi 26 juin 2009 Statut Membre Dernière intervention 30 mars 2008
25 sept. 2010 à 12:53
Pas si inutile que cela car ça m'a permis, dans une fonction, de tester la bonne longueur d'un numéro de téléphone.
En revanche, log(x) renvoit le logarithme NEPERIEN.
Pour obtenir le logarithme DECIMAL, il faut diviser par le logarithme népérien de 10.
log10(x) = log(x)/log(10)
jordane45 Messages postés 38222 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 23 juillet 2024 344
24 sept. 2010 à 17:06
pas bête.
j'aime bien ^^
Rejoignez-nous