ENSEMBLE DES NOMBRES ENTIERS

Signaler
Messages postés
6413
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
17 mai 2018
-
lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
-
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

lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
2
ce que je t'avais proposé avec le calcul des 2 vecteurs c'était pour montrer qu'il était possible de le faire pour l'un ou l'autre (pair ou impair)...

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^^
eishtein
Messages postés
52
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
23 janvier 2014

je crois plutôt que j'ai utilisé le test de modulo pour eviter l'utilisation de deux vecteurs ( ce que tu m'avais proposé dans ton commentaire).... comme çà je verifie sur place si l'element de mon vecteur est pair ou non... en plus ,j'aurais pu créer les deux vecteurs pour effectuer le test si il n'y aurait pas cette contrainte d'optimisation de l'espace mémoire
--> 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...
lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
2
Oui merci BruNews.

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)
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
if (x AND 1) IMPAIR
C'est 1 cycle parallelisable.

Modulo est une division (40 cycles) et teste de EDX en sortie (autre cycle).