Bonjour @depasse : Ton explication est parfaitement claire, mais pour un tableau de $h = 28$ lignes et en numérotant tes lignes comme tu le fais , ligne $0$ , cellule numéroté $1$ ; ligne $1$ cellule numéroté $2$ de valeur $V=2*1$ et cellule $3$ de valeur $V= 1 + 2^{28-1}=134217729$
Tu peux d'ailleurs vérifier avec le deuxième petit programme c++ de @Marco. : la cellule n° 500 ligne 9 colonne 245 = 255 852 548 donne deux cellules ; la n°1000 qui vaut $(255 852 548 +1)$ et la cellule n° 1001 qui vaut $255 852 548 + 2^{h-9} =256376836$
Bonjour @depasse Autant pour moi ! Ton explication est parfaitement claire, c'est moi qui n'ai pas numéroté dans l'ordre toutes les cellules ligne par ligne (j'ai pris qu'une partie du tableau) jusqu'à la 64 ème colonne, d'où la cellule 1001 se trouve ligne 10 et non ligne 21... Ce qui change les antécédents... etc.
@depasse Merci beaucoup ! c'est le genre de chose que je cherchais. Cela va peut-être faire gagner du temps de calcul. Par contre, je sais calculer la somme des 2-valuations (@lourrran m'a expliqué) mais pas la 2-valuation tout court. Si j'ai bien compris la définition, il faut tester les restes de division de n par 2ˆk pour trouver le plus grand k possible donnant un reste nul, ou y a-t-il une formule plus "directe" ? Encore merci pour votre aide à tous.
Pour avoir de bonnes performances (et même d'excellentes performances), un bon informaticien saura t'aider. Ici, tu t'intéresses aux divisions par 2, pas aux divisions par 3 ou par 5. Et en informatique, la division par 2, c'est un truc qui se fait vachement bien. Par exemple, le nombre 48, écrit en binaire, c'est 110000 ; il se finit par 4 fois le chiffre 0, et donc $v_2(48)=4$ Selon le langage de programmation que tu vas utiliser, il y aura (ou pas) des outils pour exploiter cette propriété bien pratique.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Cette fonction est certainement la plus performante ...
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
Si $n$ est un entier , la somme des $v_2(i)$ pour $i$ entre $1$ et $n$ vaut $E(n/2) + E(n/4) +E(n/8) + .... +E(n/2^k)$
Bonsoir, Je reviens après un moment d'absence pour mes problèmes de tableau et d'informatique. J'ai constaté expérimentalement que cette somme des $v_2(i)$ pour $i$ entre $1$ et $n$ valait aussi $n -$ "le nombre de bits mis à 1 dans $n$", c'est à dire $n$ moins le nombre de termes non nuls dans la décomposition de $n$ en somme de puissances de deux. Cela rend la somme très simple à calculer par ordinateur, car il est aisé pour les processeurs de compter le nombre de bits mis à 1 dans un entier non signé.
Ma question est : puis-je tirer parti de cela pour calculer le numéro d'un noeud dans un arbre différent ? Par exemple dans un arbre où chaque noeud aurait 4 enfants comme celui-ci :
Dit autrement, cette "technique" de comptage du nombre de bits mis à 1 dans $n$ peut-elle me servir pour calculer simplement la somme des $v_4(i)$ pour $i$ variant de $1$ à $n$ ? (Je crois savoir que normalement les valuations p-adiques concernent les nombres premiers, mais vous me comprenez). Je cherche depuis un certain temps sans trouver. Merci d'avance à ceux qui pourront m'aider. Bonne soirée à tous.
Sachant que (si cela peut aider), la meilleure façon que j'ai trouvée pour calculer la somme des valuations 2-adiques est la suivante : $\sum_{k=1}^n v_2(k) = n - $ "number_of_set_bits($n$)"*
*est égal au nombre de termes non nuls dans la décomposition de n en somme de puissances de deux.
Je pense que la magie ne va plus marcher. Dans le premier cas, on tombait pile-poil sur : combien de fois tel nombre est il divisible par 2. C'est à dire, sur le seul cas adapté à une optimisation. Essaie déjà d'écrire un programme 'non-optimisé'. Puis, pour d'éventuelles optimisations, soumets-le, ici ou sur un forum spécialisé dans ton langage de programmation. Chercher cet exercice la 1ère fois, c'était un challenge amusant ; chercher cette variante, c'est beaucoup moins motivant.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Merci de ta réponse. Je ne veux forcer personne à chercher bien sûr. Si quelqu'un a un éclair de génie je suis preneur, voilà tout J'ai déjà bien avancé grâce à vous tous. Encore merci.
Réponses
@depasse :
Ton explication est parfaitement claire, mais pour un tableau de $h = 28$ lignes et en numérotant tes lignes comme tu le fais , ligne $0$ , cellule numéroté $1$ ; ligne $1$ cellule numéroté $2$ de valeur $V=2*1$ et cellule $3$ de valeur $V= 1 + 2^{28-1}=134217729$
Tu peux d'ailleurs vérifier avec le deuxième petit programme c++ de @Marco. : la cellule n° 500 ligne 9 colonne 245 = 255 852 548 donne deux cellules ; la n°1000 qui vaut $(255 852 548 +1)$ et la cellule n° 1001 qui vaut $255 852 548 + 2^{h-9} =256376836$
Autant pour moi ! Ton explication est parfaitement claire, c'est moi qui n'ai pas numéroté dans l'ordre toutes les cellules ligne par ligne (j'ai pris qu'une partie du tableau) jusqu'à la 64 ème colonne, d'où la cellule 1001 se trouve ligne 10 et non ligne 21... Ce qui change les antécédents... etc.
Merci beaucoup ! c'est le genre de chose que je cherchais. Cela va peut-être faire gagner du temps de calcul. Par contre, je sais calculer la somme des 2-valuations (@lourrran m'a expliqué) mais pas la 2-valuation tout court.
Si j'ai bien compris la définition, il faut tester les restes de division de n par 2ˆk pour trouver le plus grand k possible donnant un reste nul, ou y a-t-il une formule plus "directe" ?
Encore merci pour votre aide à tous.
Ici, tu t'intéresses aux divisions par 2, pas aux divisions par 3 ou par 5.
Et en informatique, la division par 2, c'est un truc qui se fait vachement bien.
Par exemple, le nombre 48, écrit en binaire, c'est 110000 ; il se finit par 4 fois le chiffre 0, et donc $v_2(48)=4$
Selon le langage de programmation que tu vas utiliser, il y aura (ou pas) des outils pour exploiter cette propriété bien pratique.
Merci, oui effectivement c'est assez simple apparement. Il y a pas mal de fonctions pour faire cela,
ici par exemple : https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set
Cette fonction est certainement la plus performante ...
unsigned GetLowestBitPos(unsigned value) { double d = value ^ (value - !!value); return (((int*)&d)[1]>>20)-1023; }Je reviens après un moment d'absence pour mes problèmes de tableau et d'informatique. J'ai constaté expérimentalement que cette somme des $v_2(i)$ pour $i$ entre $1$ et $n$ valait aussi $n -$ "le nombre de bits mis à 1 dans $n$", c'est à dire $n$ moins le nombre de termes non nuls dans la décomposition de $n$ en somme de puissances de deux.
Cela rend la somme très simple à calculer par ordinateur, car il est aisé pour les processeurs de compter le nombre de bits mis à 1 dans un entier non signé.
Ma question est : puis-je tirer parti de cela pour calculer le numéro d'un noeud dans un arbre différent ? Par exemple dans un arbre où chaque noeud aurait 4 enfants comme celui-ci :
Dit autrement, cette "technique" de comptage du nombre de bits mis à 1 dans $n$ peut-elle me servir pour calculer simplement la somme des $v_4(i)$ pour $i$ variant de $1$ à $n$ ? (Je crois savoir que normalement les valuations p-adiques concernent les nombres premiers, mais vous me comprenez). Je cherche depuis un certain temps sans trouver.
Merci d'avance à ceux qui pourront m'aider.
Bonne soirée à tous.
Je reformule de manière plus concise.
Existe-t-il une façon simple et optimisée pour un ordinateur de calculer la somme suivante :
pour $n \in \mathbb{N}$
$S_n = \sum_{k=1}^n v_4(k)$
avec
$v_4(k) = \max \{ p \in \mathbb{N} \mid 4^p$ divise $k \} $
Sachant que (si cela peut aider), la meilleure façon que j'ai trouvée pour calculer la somme des valuations 2-adiques est la suivante :
$\sum_{k=1}^n v_2(k) = n - $ "number_of_set_bits($n$)"*
*est égal au nombre de termes non nuls dans la décomposition de n en somme de puissances de deux.
Dans le premier cas, on tombait pile-poil sur : combien de fois tel nombre est il divisible par 2.
C'est à dire, sur le seul cas adapté à une optimisation.
Essaie déjà d'écrire un programme 'non-optimisé'. Puis, pour d'éventuelles optimisations, soumets-le, ici ou sur un forum spécialisé dans ton langage de programmation.
Chercher cet exercice la 1ère fois, c'était un challenge amusant ; chercher cette variante, c'est beaucoup moins motivant.
Merci de ta réponse. Je ne veux forcer personne à chercher bien sûr. Si quelqu'un a un éclair de génie je suis preneur, voilà tout
def V4(n): # Valuation 4-adique v = 0 while n % 4 == 0: n //= 4 v += 1 return v def S(n): return sum([V4(k) for k in range(1,n+1)]Cordialement,Rescassol
Merci beaucoup ! Je vais partir de cela.
Bonne soirée à tous.