Discussion :

[CetTer]

Bonjour,


J'aimerais vérifier algorithmiquement qu'un nombre commence par "1", quel que soit son rang ("14", "13471", etc...) sans le convertir en chaîne de caractère (pour limiter la complexité en temps et espace).

La seule formule que je trouve (en pseudo code, mais le langage serait sans doute Java) pour récupérer le chiffre situé au début d'un nombre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

=FLOOR(LE_NOMBRE/(10^FLOOR(LOG10(LE_NOMBRE))))

Mais je me demande s'il n'y a pas plus simple (et plus rapide pour le processeur)?

Bien à vous,

[picodev]

Bonjour,

Il y a des problème si LE_NOMBRE vaut 0 ou est négatif. Si on part du principe que LE_NOMBRE≥0 alors il y a une version sans avoir à recourir aux flottants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
while (LE_NOMBRE>9) LE_NOMBRE=LE_NOMBRE/10;
if (LE_NOMBRE==1) commence_par_un=true;
else commence_par_un=false;

ou encore «sans calculs»

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
if (LE_NOMRE==1) || 
   (LE_NOMBRE≥10 && LE_NOMBRE≤19) ||
   (LE_NOMBRE≥100 && LE_NOMBRE≤199) ||
   (LE_NOMBRE≥1000 && LE_NOMBRE≤1999) ||
  ....
  commence_par_un=true;
else
  commence_par_un=false;
endif

ou la version négative de la version précédente …

Le plus simple est de tester plusieurs versions si tu as vraiment besoin de performances. Mais bon la source de tous les maux est dans une optimisation prématurée du code … Il faut toujours partir d'une version fonctionnelle, la profiler pour savoir où les optimisations auront le plus d'impact.

[wiwaxia]

Bonjour,

Je vois deux procédés symétriques limités aux nombres entiers, et basés sur l'itération conditionnelle d'une opération simple: (1) multiplication ou (2) division euclidienne par 10, l'étape essentielle consistant à déterminer le nombre de chiffres (c) de l'entier testé.
C'est d'ailleurs ce que tu fais dans la séquence que tu proposes:

... J'aimerais vérifier algorithmiquement qu'un nombre commence par "1", quel que soit son rang ("14", "13471", etc...) ... La seule formule que je trouve pour récupérer le chiffre situé au début d'un nombre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

=FLOOR(LE_NOMBRE/(10^FLOOR(LOG10(LE_NOMBRE))))

Mais je me demande s'il n'y a pas plus simple (et plus rapide pour le processeur) ...,

la notion d'entier-plancher (FLOOR) renvoyant à la partie entière d'un nombre décimal.
La seule réserve qu'on peut faire (mais d'autres ne seront peut-être pas du même avis) est l'imbrication forcenée des fonctions (4 niveaux !), dans le but probable de faire court à tout prix; pourquoi ne pas écrire (en reprenant la même notation):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
p=LOG10(LE_NOMBRE) ; i=FLOOR(p) ; j=10^(i) ;
q=LE_NOMBRE / j ; k=FLOOR(q)

séquence utilisant deux réels (p, q) et trois entiers, mais tout de même plus lisible ?

1°) Première solution: chercher à encadrer l'entier étudié par les bornes appropriées ( a = 10^(c-1) ; b = 10^(c)-1 ), directement reliées au nombre de chiffres par le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 b:= 1; c:= 0;
REPEAT 
    a:= b; b:= 10 * a; c:= c + 1 
UNTIL b>LE_NOMBRE;
Premier_Chiffre:= LE_NOMBRE DIV a ;

C'est du Pascal (on ne se refait pas), mais cela se traduit sans peine.

2°) La seconde solution (pour autant que je l'ai bien saisie) a été donnée par picodev:

... Si on part du principe que LE_NOMBRE≥0 alors il y a une version sans avoir à recourir aux flottants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
while (LE_NOMBRE>9) LE_NOMBRE=LE_NOMBRE/10;
if (LE_NOMBRE==1) commence_par_un=true;
else commence_par_un=false;

Elle paraît l'emporter en concision.

Cependant la variante proposée ensuite m'intrigue un peu:

... ou encore «sans calculs»

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
if (LE_NOMRE==1) || 
   (LE_NOMBRE≥10 && LE_NOMBRE≤19) ||
   (LE_NOMBRE≥100 && LE_NOMBRE≤199) ||
   (LE_NOMBRE≥1000 && LE_NOMBRE≤1999) ||
  ....
  commence_par_un=true;
else
  commence_par_un=false;
endif

Elle part d'une idée intéressante, mais s'exprime d'une manière lourdement répétitive et devient inapplicable au-delà des limites habituelles (2³² ou 2⁶⁴ selon les langages). Comment faire pour LE_NOMBRE = 1000! (2567 chiffres, à vue d'oeil) ?
Un algorithme apparenté au premier proposé (1), avec une boucle REPEAT ou WHILE, serait peut-être plus adaptée.

# Le cas des entiers non-positifs n'est pas un problème: il suffit en préambule, de passer à la valeur absolue et d'exclure le zéro.

[picodev]

[...]
ou encore «sans calculs»

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
if (LE_NOMRE==1) || 
   (LE_NOMBRE≥10 && LE_NOMBRE≤19) ||
   (LE_NOMBRE≥100 && LE_NOMBRE≤199) ||
   (LE_NOMBRE≥1000 && LE_NOMBRE≤1999) ||
  ....
  commence_par_un=true;
else
  commence_par_un=false;
endif

[...]

[...]Cependant la variante proposée ensuite m'intrigue un peu:

Elle part d'une idée intéressante, mais s'exprime d'une manière lourdement répétitive et devient inapplicable au-delà des limites habituelles (2³² ou 2⁶⁴ selon les langages). Comment faire pour LE_NOMBRE = 1000! (2567 chiffres, à vue d'oeil) ?
Un algorithme apparenté au premier proposé (1), avec une boucle REPEAT ou WHILE, serait peut-être plus adaptée.

# Le cas des entiers non-positifs n'est pas un problème: il suffit en préambule, de passer à la valeur absolue et d'exclure le zéro.

Évidemment je limite cette version aux entiers «natifs» et oui cela devient trop(?) lourd au-delà de 64bits. Mais si on utilise des entiers arbitrairement long il peut être plus efficace de commencer une conversion vers un string à partir de la gauche … à tester.
Comme je le précise une optimisation prématurée d'un code est souvent une mauvaise chose.
De plus je rajouterai que la concision d'écriture dans un langage donné n'est pas synonyme de performance. Un code plus long mais plus simple peu être plus performant. À nouveau il faut tester et garder à l'esprit que les meilleures optimisations seront celles qui seront pointées par un profiler …

[CetTer]

Merci pour vos réponses, cela donne des pistes pour comparer des implémentations. Il s'agît bien de valeurs positives, résultant elles-même de la divisions d'entiers d'une longueur limitée (8 à 10 rangs).

[phryte]

Bonjour,

Un léger mieux ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

round(N/10^(log10(N)))

[wiwaxia]

Bonsoir,

La divination n'est pas mon fort, mais je crois discerner dans l'énoncé sibyllin de la question posée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

round(N/10^(log10(N)))

une version améliorée des fonctions ou algorithmes précédents ...

Il me semble que 10^(log₁₀(N)) = N , d'où: round(N/10^(log10(N))) = round(N/N) = round(1) = 1
quel que soit l'entier positif de départ.
Il y a comme un défaut dans la fonction proposée.

[Flodelarab]

Bonjour

Il suffit d'écrire le nombre en binaire et il commencera forcément par un 1.

[wiwaxia]

Bonjour,

Pour en revenir à la formule proposée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

round(N/10^(log10(N)))

la fonction d'arrondi < round(x) > est ici à proscrire en raison de la discontinuité présente au voisinage de tout argument semi-entier:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
round(k + u) = k si (u < 1/2) sinon round(k + u) = k + 1 
{ pour tout entier k >= 0 et tout réel du semi-ouvert [0 ; 1[}

C'est la fonction partie entière < int(x) > qu'il faut utiliser - deux fois d'ailleurs si l'on veut parvenir à la réponse définitive:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int(N/10^int(log10(N)))

On vient ainsi au décalque (en je ne sais quel code, mais peu importe) de la formule initialement proposée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

=FLOOR(LE_NOMBRE/(10^FLOOR(LOG10(LE_NOMBRE))))

et déjà commentée plus haut.

[PierroVsf]

Bonjour

Le processeur effectue en 1 tour machine la conversion d'entier en flottant, une fois cette opération effectuée, le nombre est sous forme mantisse, exposant:
N = m * 2^e avec "m" entre 1 et 2 et "e" entier
En cherchant un peut on trouve:
N = m * 10^(e/ln2(10))
N = m * 10^( e/ln2(10) - E( e/ln2(10) ) * 10^( E(e/ln2(10)) )

Soit
N = a*10^b
Avec "a" dans [1, 20[ et "b" entier.

Voilà donc la liste des opérations effectuées:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
N2 = (float)N;
m=mantisse(N);
e=exposant(N);
e*= INV_LN2_10;
e-=floor(e);
m*=10^e;
if m>=10 return 1;
else return floor(e);

Voilà donc un moyen d'éviter un logarithme et une division. Deux opérations en général lourde pour le processeur. Il reste tout de même le calcul de la puissance de 10 qui est lourde, mais étant donné que la puissance calculée est faible, le calcul peut être rapide.
La récupération de la mantisse et de l'exposant ce font par décalage de bit. Le calcul des fonctions mathématiques tire souvent partie de l’écriture mantisse exposant: