Discussion :

[fearyourself]

Bonjour, Je vous propose un nouvel élément à utiliser : Comment calculer le nombre de chiffres d'un entier ?



Il peut être parfois utile de connaître le nombre de chiffres que contient un nombre par exemple si l'on souhaite le convertir en chaîne de caractères à l'aide de la fonction sprintf.



Qu'en pensez-vous ?

[shessuky]

int MyInt = 2012;
int NumberOfDigits = String.valueOf(MyInt).length();
//that should return 4

[Obsidian]

int MyInt = 2012;
int NumberOfDigits = String.valueOf(MyInt).length();
//that should return 4

Formidable.

• Ce que tu nous proposes n'est pas du C ;
• Comment fonctionne « valueOf » ;
• Comment t'y prendrais-tu si c'était à toi de l'écrire (pour que les autres puissent l'utiliser) ?

[Bktero]

C'est du Java ça


EDIT : en regardant la source proposé, je me dis qu'il y a des propriétés de la fonction LOG que ne connait pas encore... Pourtant, j'en ai bouffé des maths pendant mes études

EDIT 2: http://forums.futura-sciences.com/ma...ssion-2-n.html Je me passerai un week-end en étant plus intelligent.

[valefor]

Comment fonctionne « valueOf »

Lis le man...

C'est pas sur un ton agressif que je dis cela, c'est juste que l'exemple proposé utilise aussi une fonction externe log10 (même si dans ce cas c'est du c standard).

Autres pistes : http://graphics.stanford.edu/~seande...erLog10Obvious

[Obsidian]

c'est juste que l'exemple proposé utilise aussi une fonction externe log10 (même si dans ce cas c'est du c standard).

Relis bien mon commentaire également, sans agressivité non plus. J'ai bien dit « comment fonctionne » valueOf(). Pas « comment utilise-t-on ».

C'est pas tant le fait que l'exemple utilise une fonction externe qui me gène. Ce qui m'ennuie, c'est qu'outre le fait que le code Java soit hors-sujet dans cette section, il génère directement la chaîne qui représente le nombre pour la mesurer ensuite. Or, l'un des principaux (et rares) cas où une telle fonction serait utile, c'est justement pour connaître à l'avance la place qu'il prend pour pouvoir allouer un tableau de caractères en conséquence, qui puisse le recevoir.

C'est aussi révélateur du fait que beaucoup de programmeurs aujourd'hui apprennent à calculer avec des objets sans avoir la notion de coût en ressources ni de la marche à suivre pour les implémenter.

[Djakisback]

Bonjour,
par curiosité j'ai testé la fonction fournie qui semble ne fonctionner que pour les nombres positifs, à cause des propriétés du logarithme ?

Du coup, un peu hors-sujet et toujours par curiosité, je me demandais ce que vous pensiez de cette fonction que j'ai pondue pour répondre au problème sans la lib math. D'après vous, est-ce qu'elle couvre tous les cas d'utilisation d'entiers (dans l'intervalle du type défini) et est-ce qu'elle serait optimisable ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int nombre_chiffre2(int i)	{
	int c = 0;
 
	if(i < 0)	{
		 i = -i;
	}
 
	do	{
		c++;
	}
	while((i /= 10) > 0);
	return c;
}

Merci d'avance.

[Kirilenko]

Bonjour,
par curiosité j'ai testé la fonction fournie qui semble ne fonctionner que pour les nombres positifs, à cause des propriétés du logarithme ?

Du coup, un peu hors-sujet et toujours par curiosité, je me demandais ce que vous pensiez de cette fonction que j'ai pondue pour répondre au problème sans la lib math. D'après vous, est-ce qu'elle couvre tous les cas d'utilisation d'entiers (dans l'intervalle du type défini) et est-ce qu'elle serait optimisable ?

Après avoir testé sur de nombreuses valeurs, force est de constater que cette fonction marche sur l'intervalle [-INT_MAX ; INT_MAX].
Bon, c'est pas la première fois qu'on voit cette fonction sur le Web, mais elle remplit son boulot.

[souviron34]

et j'ajouteraais qu'elle va beaucoup plus vite que la fonction intitiale :

calculer un log est long (développemeny de Taylor), utilise des doubles, alors qu'on a besoin que d'arithmétique entière, et sans log

Mais on peut l'optimiser sans fair de division :

Code :

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

1
2
3
4
do	{
		c++;
	}
	while((i /= 10) > 0);

peut devenir, à base d'un tableau :

Code :

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

1
2
3
4
5
6
7
int tab[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000...} ;
int *p = tab ;
 
do	{
		c++;
	}
	while(*(p+c) < i);

le plus optimal...

[Djakisback]

Merci pour vos réponses.
Pas mal, le coup du tableau

[diogene]

Une variante qui permet d'avoir un temps de calcul plus rapide sur les grands nombres (limités dans ce code à i <10^16 si le unsigned int le supporte naturellement)

Code :

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

1
2
3
4
5
6
7
8
9
int nombre_chiffre2(unsigned int i)
{
 int c = 1;
 if(i>=100000000) { c += 8; i/= 100000000;}
 if(i>=10000) { c += 4; i/= 10000;}
 if(i>=100){ c += 2; i/= 100;}
 if(i>=10)c +=1;
 return c;
}

il y a de toute façon 5 tests et le nombre d'additions et de divisions pour un nombre à N chiffres (décimaux) dépend du nombre de 1 dans la représentation binaire de N-1
Par exemple, un nombre à 10 chiffres demandera
5 tests + (1 addition +1 division) + 1 addition

[souviron34]

Une variante qui permet d'avoir un temps de calcul plus rapide sur les grands nombres (limités dans ce code à i <10^16 si le unsigned int le supporte naturellement)

Code :

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

1
2
3
4
5
6
7
8
9
int nombre_chiffre2(unsigned int i)
{
 int c = 1;
 if(i>=100000000) { c += 8; i/= 100000000;}
 if(i>=10000) { c += 4; i/= 10000;}
 if(i>=100){ c += 2; i/= 100;}
 if(i>=10)c +=1;
 return c;
}

il y a de toute façon 5 tests et le nombre d'additions et de divisions pour un nombre à N chiffres (décimaux) dépend du nombre de 1 dans la représentation binaire de N-1
Par exemple, un nombre à 10 chiffres demandera
5 tests + (1 addition +1 division) + 1 addition

Avec ton idée, on doit pouvoir utiliser une dichotomie pour optimser les seuils, et utiliser des else, ce qui évite des tests.

Mais vu que sur un 32 bits le max est 10 chiffres, donc un tableau de 10, mais que même si on double, c'est encore très acceptable, on peut utiliser le tableau sans aucune division. (10 (ou 20) (addition+test) max)

[Djakisback]

diogene, finalement quittes à faire pratiquement tous les tests, est-ce que ce ne serait pas plus efficace de retourner directement les valeurs avec quelque chose de ce type ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int nombre_chiffre2(unsigned int i)
{
 if(i >= 100000000) return 9;
 if(i >= 10000000) return 8;
 if(i >= 1000000) return 7;
 if(i >= 100000) return 6;
 if(i >= 10000) return 5;
 if(i >= 1000) return 4;
 if(i >= 100) return 3;
 if(i >= 10) return 2;
 return 1;
}

Sinon, je m'aperçois que la solution avec tableau semble nécessiter pas mal de calculs supplémentaires pour la création du tableau si on veut se baser sur la taille réelle du int, est-ce que je me trompe ?

Pour la rendre fonctionnelle, je suis parti sur ce code qui me semble pas mal lourd, et qui oblige à faire quand même les divisions par 10 pour connaître le nombre d'éléments dans le tableau à partir de la valeur maximum d'un int :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int nombre_chiffre3(int i)	{
 
	int c = 0;
	int size = sizeof(int);
	int bits = size * 8;
 
	printf("size: %d bytes\n", size);
	printf("bits: %d bits\n", bits);
 
	// Calcul de la valeur max d'un int
	int j;
	int maxValue = 0;
	for(j = bits; j > 0; j--) 	{
		  maxValue += pow(2, j);
	}
 
	printf("max value : %d \n", maxValue);
 
	// Calcul de la taille du tableau
	do	{
		c++;
	}
	while((maxValue /= 10) > 0);
 
	printf("tab size : %d \n", c);
 
	// Remplissage du tableau
	int tab[c];
	int n;
	for(n = 1, j = 0; j < c; n *= 10, j++) 	{
		  tab[j] = n;
		  printf("tab[%d] : %d \n", j, tab[j]);
	}
 
	// Calcul du nombre de chiffres
	c = 0;
	int *p = tab;
 	if(i < 0)	{
		 i = -i;
	}
 
 	do	{
		c++;
	}
	while(*(p+c) < i);
 
	return c;
}

Est-ce que je me plante complètement ?

[Jean-Marc.Bourguet]

INT_MAX est plus fiable que ta méthode pour avoir la valeur maximale dans un int.

pow(2, j), c'est 1<<j sans passer par les flottants.

Sinon, quand tu peux mélanger le calcule de ton tableau et la recherche dans celui-ci. Et après avoir viré le code mort, tu te retrouves avec la simple boucle qui a déjà été donnée. L'intérêt du tableau, c'est de le précalculer; le faire à chaque fois, c'est un peu stupide.

(Je me demande l'effet des sauts non-prédits avec la méthode pleine de if; il faudrait des mesures parce que ça ne m'étonnerait pas que la simple boucle soit plus rapide -- ça dépend peut être de la distribution des données)

[valefor]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int nombre_chiffre2(unsigned int i)
{
 if(i >= 100000000) return 9;
 if(i >= 10000000) return 8;
 if(i >= 1000000) return 7;
 if(i >= 100000) return 6;
 if(i >= 10000) return 5;
 if(i >= 1000) return 4;
 if(i >= 100) return 3;
 if(i >= 10) return 2;
 return 1;
}

Vous aviez lu le lien que j'ai donné ? (http://graphics.stanford.edu/~seande...erLog10Obvious)

[souviron34]

Sinon, je m'aperçois que la solution avec tableau semble nécessiter pas mal de calculs supplémentaires pour la création du tableau si on veut se baser sur la taille réelle du int, est-ce que je me trompe ?

Comme cité plus haut, la taille du int , INT_MAX, est déterminée (sauf sur 64 bits) par la taille de l'architecture...

INT_MAX en 32 bits fait 10 chiffres (exactement)..

Comme je l'ai dit, on peut sans problèmes se faire un tableau du double...

Aucun intérêt à le créer dynamquement, puisqu'on fait des calculs...

Maintenant la solution des if peut être optimisée par dichotomie :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int nombre_chiffre2(unsigned int i)
{
 if(i >= 100000) 
     {
         if(i >= 10000000)
           {
              if(i >= 100000000) return 9;
              return 8 ;
           ]
        if(i >= 1000000) return 7;
        return 6;
    }
 else
  {
        if(i >= 1000) 
          {
              if(i >= 10000) return 5;
              return 4;
         ]
      else
        {
            if(i >= 10) 
              {
                  if ( i >= 100 ) return 3 ;
                   return 2;
               }
            return 1;
         }
    }
}

[diogene]

@souviron34

Avec ton idée, on doit pouvoir utiliser une dichotomie pour optimser les seuils, et utiliser des else, ce qui évite des tests

Je ne pense pas qu'on puisse optimiser les choses au niveau des seuils. On ne peut pas utiliser des else sur ce code.


Si on pose que l'unsigned utilisé a au maximum M chiffres (décimaux), pour un nombre de N chiffres (décimaux), alors, sauf erreur,

1- Pour la méthode avec plein de if, on a M-N tests (il manque un if pour un unsigned de 32 bits) (ou N tests si on codait en ordre et en sens inverse les if).

2- La méthode de Djakisback donne une addition, un test et une division par boucle soit N tests + N additions + N divisions.

3- La méthode tabulée de souviron34 donne un test, 2 additions (et un déréférencement) par boucle soit N tests et 2N additions

4- La méthode "dichotomique" donne un nombre de tests, et d'opérations en log2(M). Le nombre de tests est P+1 si 2^(P-1)< M <= 2^P. Pour passer d'un M de 10 (unsigned de 32 bits)à M de 20 (unsigned de 64 bits), il suffit de rajouter un if(). le nombre d'additions est le nombre de 1 dans la représentation binaire de N-1 et le nombre de divisions est égal au nombre de 1, le lsb exclus, dans la représentation binaire de N-1. Pour un unsigned de 32 bits (M = 10) le pire cas sera pour N = 8 et pour un 64 bits (M=20) pour N = 16.

Si on tabule les pires cas :

                       unsigned 32 bits    unsigned 64 bits
                            M = 10            M = 20
                         tests  +   /        tests  +   /
méthode 1  (if)           9     0   0         19    0   0
méthode 2  (div/10)      10    10  10         20   20  20
méthode 3  (table)       10    20   0         20   40   0
méthode 4  (dicho)        5     3   2          6    4   3

A chacun de choisir en fonction de sa problématique.

[souviron34]

@souviron34

Je ne pense pas qu'on puisse optimiser les choses au niveau des seuils. On ne peut pas utiliser des else sur ce code.
..
1- Pour la méthode avec plein de if, on a M-N tests (il manque un if pour un unsigned de 32 bits) (ou N tests si on codait en ordre et en sens inverse les if).
..
4- La méthode "dichotomique" donne un nombre de tests, et d'opérations en log2(M). Le nombre de tests est P+1 si 2^(P-1)< M <= 2^P. Pour passer d'un M de 10 (unsigned de 32 bits)à M de 20 (unsigned de 64 bits), il suffit de rajouter un if(). le nombre d'additions est le nombre de 1 dans la représentation binaire de N-1 et le nombre de divisions est égal au nombre de 1, le lsb exclus, dans la représentation binaire de N-1. Pour un unsigned de 32 bits (M = 10) le pire cas sera pour N = 8 et pour un 64 bits (M=20) pour N = 16.

Je ne crois pas qu'il y ait besoin de divisions.. Tel que j'ai mentionné dans le message précédent, appliquer une dichotomie sur les if amène simplement à log2 M tests... ce qui me semblerait le plus optimal... non ?

Ni addition, ni division..

log2 M tests , et 1 assignation..

Pour 10 chiffres 3 tests au max en moyenne, et 4 pour 0.000001% (proportion "à l'oeil", j'ai la flemme de calculer) des cas (chiffres entre 10 et 999)..

Et simplement le double en 64 bits, non ?

[diogene]

Je ne crois pas qu'il y ait besoin de divisions.. Tel que j'ai mentionné dans le message précédent, appliquer une dichotomie sur les if amène simplement à log2 M tests

J'ai rédigé mon message précédent avant de lire ta proposition dichotomique des if, aussi la méthode 4 ne lui correspond pas (mais à la méthode que j'avais proposée).
Je n'avais pas interprété correctement ta phrase :

Avec ton idée, on doit pouvoir utiliser une dichotomie pour optimser les seuils, et utiliser des else, ce qui évite des tests.

... ce qui me semblerait le plus optimal... non ?

En temps d'exécution, certainement.

[valefor]

Pour 10 chiffres 3 tests au max en moyenne, et 4 pour 0.000001% (proportion "à l'oeil", j'ai la flemme de calculer) des cas (chiffres entre 10 et 999)..

Pour des valeurs uniformément réparties sur 32 bits :
- 76% sont > 10^9 donc sortent au premier test
- 21% des restantes sont > 10^8 donc sortent au second
- 2% des restantes sont > 10^7 donc sortent au troisième...
- ...

En moyenne on tombe à moins de 2.6 opérations (méthode avec les ifs sans dichotomie).