Nombre pair

[zarake]

Bonjour,

j'ai un pb surement très simple mais je ne trouve pas :

soit N un nombre pair. Il peut s'écrire N = 2^p*Q avec Q impair. ex: 36=2²*9

Comment déterminer p (sans faire de divisions successives pas 2) ?
-----

[Schrodies-cat]

Ce n'est pas compliqué les divisions successives par 2 !
En base 2, on voit en fait tout de suite le nombre p dans l'écriture du nombre.
En base 10, par exemple, il y a des critères de divisibilité par 2^n

[pgs.dev]

Bonjour,
Juste pour savoir :
Es-ce que tu cherches comment le résoudre dans le cadre d'une méthode numérique (informatique), ou bien cherches tu une expression générale (analytique ou algébrique) pour caractériser p ?

- La méthode numérique "informatique" passe par l'écriture en bits (en notant que Q=2*K+1, on a N= (2^(p+1))*K+(2^p), ce qui te donne p par le nombre de zéro en bits de poids faibles dans ton nombre écrit en base 2)
- La méthode "analytique" : tu peux écrire p = (ln(N)-ln(Q))/ln(2), ou encore p=log2(N)-log2(P) (avec log2(x)=ln(x)/ln(2), car en général logZ(x)=ln(x)/ln(Z)), ce qui te donne par le calcul directement p (et en utilisant une machine, tu prends l'entier le plus proche de ton résultat pour palier aux erreurs d'arrondi)

Je n'ai pas cherché pour une méthode algébrique ou géométrique, mais je suis sur qu'en réfléchissant aux propriétés des angles des polygones convexes réguliers à N côtés, on doit pouvoir trouver des trucs...

[zarake]

En fait je cherche à calculer p (N étant donné) dans le tableur calc d'OpenOffice, en utilisant les fonctions standard.

[A voir en vidéo sur Futura]

[pelkin]

dans le tableur calc d'OpenOffice, en utilisant les fonctions standard.

On croit rêver

[stefjm]

On croit rêver

Pourquoi donc?

[Resartus]

Bonjour,
La question aurait été plus à sa place en informatique...

Si le but est d'avoir une formule qui donne directement le résultat, on peut utiliser la fonction PGCD qui doit exister dans le tableur
(ou sinon, il faut charger un module qui la contient).
Le pgcd de N et de 2^a avec a assez grand va donner la plus grande puissance de 2 qui divise N.
Pour être sûr d'avoir un a "assez grand", on peut par exemple prendre a=ENT(LOG(N)/LOG(2))

(nom des fonctions PGCD, ENT, LOG à adapter à calc, que je ne connais pas)

[ansset]

oui, je ne sais pas pour la fct PGCD sur tableur.
en revanche, je ne sais pas faire mieux que de tester en gros LOG(N/3) valeurs environ, ce qui est déjà mieux que LOG(N/2)

[mike.p]

Salut,

en effet, c'est de l'informatique à moins de présenter ça comme la construction d'un algo pour log base 2 pour les entiers

La fonction standard est int ffs(int) dans glibc , ffs comme First Bit Set. Faut voir quelle est sa fonction équivalente dans excel.

C'est facile de la réécrire dans des langages comme C et ses similaires, en faisant une boucle de test utilisant , par exemple, shift ( >> ) et And. La méthode implémentée en C utilise pour l'efficacité , entre autres , une table.