ENSEMBLE DES NOMBRES ENTIERS
cs_Julien39
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
-
14 mai 2011 à 11:49
lynxtyle Messages postés 79 Date d'inscription samedi 25 septembre 2004 Statut Membre Dernière intervention 31 octobre 2011 - 27 mai 2011 à 11:06
lynxtyle Messages postés 79 Date d'inscription samedi 25 septembre 2004 Statut Membre Dernière intervention 31 octobre 2011 - 27 mai 2011 à 11:06
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/53158-ensemble-des-nombres-entiers
https://codes-sources.commentcamarche.net/source/53158-ensemble-des-nombres-entiers
27 mai 2011 à 11:06
plutot que de tester tout tes nombres entre 2 limites je propose d'utiliser des notions de mathématiques de base :
-les nombres pairs s'écrivent sous la forme 2*x (avec x un naturel compris dans ]0;+infini[ )
{dans notre cas x compris entre 1 et (limite haute)/2}
-les nombres impairs s'écrivent sous la forme 2*x+1 (avec x un naturel compris dans [0;+infini[ )
{dans notre cas x compris entre 0 et ((limite haute)-1)/2}
on peut aussi utiliser :
-les nombres impairs s'écrivent sous la forme 2*x-1 (avec x un naturel compris dans ]0;+infini[ )
{dans notre cas x compris entre 1 et (limite haute)/2}
donc tu choisis le vecteur que tu souhaite calculer (et la méthode si c'est le vecteur impair) et tu lance le calcul de celui-ci.
ensuite pour l'optimisation tu as intérêt d'utiliser le binaire pour faire ton tableau de valeur pour la construction de ton vecteur et utiliser des masques pour remplir tes plages mémoires...
Par exemple si tu veux faire un vecteur pair à l'aide d'int codé sur 4 octés passé en champs de bits, tu utilise un masque int de 2863311530 (soit en binaire 10101010101010101010101010101010). Tu calcul ainsi en 1 passe 32 valeur de ton vecteur...
Mais là encore on retombe sur le chien qui se mord la queue... une fois ce vecteur mis en place c'est son utilisation qui ne sert à rien (tout du moins qui n'offre aucune performance) :
si n la valeur à tester alors
si(vecteur[n] == 1) alors n pair sinon n impair
qui est certe rapide mais le temps utilisé pour créer le vecteur représente une masse de calcul à rajouter à ce teste...
donc la façon la plus rapide et simple de tester la parité d'un nombre est celle proposé par BruNews : c'est de tester avec un opérateur binaire le dernier bit de ton nombre
si ton nombre est pair son dernier bit est égal à 0
si ton nombre est pair son dernier bit est égal à 1
donc si tu rajoute à ton nombre le masque 1 (opérateur logique AND) si celui-ci est toujours égal à nombre alors il est impair sinon il est pair.
cette méthode est donc la plus rapide pour tester la parité d'un nombre (dans la limite des int... en cas de teste d'un nombre entier plus grand il faut jouer avec char[] et tester la parité du dernier octé)
par contre la méthode la plus rapide pour faire le vecteur impair (ou impair) c'est celle que je propose (et oui la méthode de BruNews incrémente le masque puis teste le résultat... alors que ma méthode ne nécessite aucun test et incrémente "un masque" directement...)
et je serai réellement intéressé de savoir si toi tu as une utilisation de ce vecteur car (pour ma part) sachant que les nombres pairs/impairs sont déterminé, donc tous regroupé dans une formule déterministe précise... en quoi calculer un tel vecteur devient-il utile ? (je dirai que sans réponse à cette question je ne vois pas quel utilité a ce code ce qui fait que je ne l'appécis peut être pas à sa juste valeur)
PS : au moins au passage on aura passé en revu toute les possibilités de tester la parité lol^^
27 mai 2011 à 09:46
--> pour le depassement des limites au niveau de l'indexeur je crois que vous avez raison car je dois réfléchir à lancer une exeption au moyen d'un 'try/catch' ....
merci encore une fois pour vos réponses...
26 mai 2011 à 14:28
Par contre eishtein utilise le test Modulo pour créer un vecteur des nombres pairs ou impairs... donc utiliser modulo ou if(x AND 1)IMPAIR ou autre chose est totalement inutile pour faire un tel vecteur...
effectuer l'opération 2x donnera tout les nombres pairs du vecteur ou 2x+1 (ou 2x-1) donneront tout les impairs... (on peut d'ailleur parallèliser cette opération sans mal)
d'où ma réaction un peu vive sur cette source indiqué de niveau Initié...!
si on veut partir sur de la performance sur la création de se vecteur je remplirai chaque octé avec la valeur décimal 170 (soit en binaire 10101010) pour le vecteur pair ou 85 (soit en binaire 01010101) pour le vecteur impair que j'exploiterai avec un champs de bit {1bit;1bit;1bit;1bit;1bit;1bit;1bit;1bit;} afin de créer mon tableau de données pour mon vecteur...
mais encore une fois : à quoi pourrait bien servir un tel vecteur? (le test pour le parité étant tellement plus rapide à mettre en place qu'un chargement de vecteur + comparaison et ce même si le nombre à tester est supérieur à la limite offerte par les int)
26 mai 2011 à 10:00
C'est 1 cycle parallelisable.
Modulo est une division (40 cycles) et teste de EDX en sortie (autre cycle).
17 mai 2011 à 13:23
ensuite donne moi un intérêt de faire une tel chose...!?!
créer un vecteur pour comparer d'autre nombre pour savoir s'ils sont pair ou nom n'a aucun intérêt pour la complexité de la chose (ça se comprend pour les nombres premiers mais les nombres pairs là je ne vois pas...!)
Pour finir si à la place de faire un vecteur des nombres pairs, faire un testeur de nombre >MAX_int te semble idiot alors je ne peux plus rien faire pour t'aider à progresser...
Bon courage
17 mai 2011 à 00:59
-->encore une chose , et avec toute politesse cette fois, je crois que tu m'as insulté deux fois, que je m'excuse si j'ai inconsciemment fait quelque chose qui ne vas pas et que j'ai remis mon ego en question avant meme de créer mon compte sur ce forum...
merci pour les reponses que tu m'as envoyé :)
17 mai 2011 à 00:27
que ce soit ta méthode pour calculer ton vecteur, faire :
x=ValeurMAX
Tant que x>0{
si x%2==0 alors v[x]=1
x--
}
est vraiment plus lourd que la méthode que je t'ai proposé :
x=0
tant que x<ValeurMAX{
v[x]=1
}
si tu trouve lourd de tester pour le nombre 9548345737943795349726953467423694369324324297437543975439739739 seulement le dernier chiffre alors on ne peux plus rien faire pour toi (ton programme sera incapable de traiter ce nombre car trop grand pour un int... hors seul le dernier chiffre compte pour savoir s'il est pair ou impair... donc tu récupère ce nombre par un []char et tu ne lis que le dernier chiffre... mais bon ça doit être une méthode trop compliqué pour toi) !
Pour finir encore une fois je ne vois pas l'intérêt de faire un vecteur de nombre pair/impair car ceci sont déductibles au cas par cas très rapidement (infiniment plus rapidement que le temps de charger ton vecteur en mémoire puis de faire une comparaison... surtout sur de très grand nombre...) !
[enfin je ne vois pas pourquoi je m'embête à répondre, de toute façon ce post sera bientôt effacé et surtout tu ne cherche pas à apprendre... Bonne chance à toi si les maths ou la programmation est ta voie : tu en auras grandement besoin si tu ne remet pas ton égo en question !]
16 mai 2011 à 20:50
c'est un travail fastidieux que je ne chercherais jamais à faire... au contraire , et sans vous offenser, la méthode que vous proposez m'est trop archi LOUUUUUURDE XD XD
16 mai 2011 à 08:40
Ton programme sert à quoi ? savoir si un nombre est pair ou impair ?
Alors pour ta gouverne if (x % 2 == 0) { //x est pair } else { //x est impair } CQFD pas besoin de partir dans des vecteurs !
Et si tu calcul se vecteur pour éviter les caculs par la suite, sache que ta méthode sera plus lente et aura consommé toute la mémoire !
Et si tu souhaite vraiment faire un vecteur pair/impair :
int i=1;
int[] Vpairs; //<- enfin il serait judissieux de mettre une gestion de la mémoire
int[] Vimpairs; // <- idem
while(i<max){
Vimpairs[i]=1;
i++;
Vpairs[i]=1;
i++;
}
Voilà tu as tes 2 vecteurs ! (un aurait suffit)
Enfin si tu veux savoir si un nombre trop grand pour rentrer dans une variable est pair ou impair :
- tu récup le nombre sous forme de chaine de caractère
- tu vas sur le dernier caractère
- tu le transforme en nombre (char -> int)
- tu vérifis si c'est 0 ou s'il est divisible par 2 : si oui il est pair sinon impair
- CQFD
(variante : dans la table ascii le char 1 vaut en décimal 49, 2 vaut 50 ainsi de suite... donc tu peux traiter directement la valeur char sans chercher à transformer ton 1(char) en 1(int) etc...)
14 mai 2011 à 11:49