π
<-
Chat plein-écran
[^]

quelques fonctions d'arithmétique

Re: quelques fonctions d'arithmétique

Unread postby parisse » 19 Sep 2021, 21:13

Bien entendu, stocker un booleen dans un bit a un cout d'acces plus eleve en operations arithmetiques que d'acceder a un int (au passage, un int sur les compilateurs usuels pour processeurs ARM ou i386/amd64, c'est 32 bits, pas 16, donc 4 octets, pas 2) : il faut ajouter a l'operation de lecture/ecriture un decalage et un bitmask. Mais le gain en memoire (un facteur 8 ou 32 ou 64) compense largement ce petit overhead en temps de calcul, par exemple sur la Numworks qui a tres peu de RAM. Et meme si on beaucoup de RAM, le temps de calcul devient plus rapide avec des bool stockes sur 1 bit des que la taille des donnees manipulees sort du cache, car alors le temps d'acces a la memoire depasse de tres loin les 1 ou 2 cycles necessaires au decalage/bitmask.

Sinon, les optimisations SIMD n'ont rien a voir avec de la compression de donnees. Il s'agit de vectorisation pour paralleliser certains calculs et les faire plus rapidement.

Voila, je vous suggere de vous documenter un peu plus.
User avatar
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 33%
 
Posts: 2648
Joined: 13 Dec 2013, 16:35
Gender: Not specified

Re: quelques fonctions d'arithmétique

Unread postby rentech7289 » 19 Sep 2021, 23:45

int sur les compilateurs usuels pour processeurs ARM ou i386/amd64, c'est 32 bits, pas 16, donc 4 octets, pas 2

La taille et le nom des types primitifs a été défini par l'IEEE. Elle n'est pas liée à la taille du bus de données, qui elle permettrait justement de charger les deux long ou float d'une opération en une seule fois et d'avoir le résultat avant le passage à l'instruction suivante. Autre exemple: l'unité de calcul flottante des x86 a un bus de 256 bits (jeu d'instructions AVX2). Ce n'est pas pour autant qu'un float demande 32 octets pour être stocké...
il faut ajouter a l'operation de lecture/ecriture un decalage et un bitmask

Faux, il s'agit une comparaison logique entre les deux opérandes, suivi de la fonction assembleur CMP Z (compararaison du bit Z, zéro, du registre d'état). Le résultat de ce test décide de la suite du programme.
le gain en memoire (un facteur 8 ou 32 ou 64) compense largement ce petit overhead en temps de calcul

Faux, un décalage en mode bit à bit veut dire déplacement d'un unique rang à chaque fois que l'instruction est utilisées. Ce qui veut dire que l'opération doit être répétée n fois pour arriver au bit de poids faible et donc l'utilisation d'un registre supplémentaire pour ce décompte. Ce qui alourdit le travail du microprocesseur et donc ralentit l'entrée des informations.
D'autre part le facteur auquel vous faites allusion est uniquement lié aux données de type primitif. Une opération de lecture ou d'écriture d'un char (8 bits) demandera le même temps que pour un double (8 octets). La différence est que l'occupation en mémoire ne sera pas la même: le double utilisera toute la largeur de l'adresse mémoire mais pas un char (1/8 seulement).
le temps de calcul devient plus rapide avec des bool stockes sur 1 bit des que la taille des donnees manipulees sort du cache

Le rôle des caches est d'augmenter le débit par des technologies de plus en plus rapides. Les données ne sont pas traitées, elles ne prennent que de la vitesse...
Sinon, les optimisations SIMD n'ont rien a voir avec de la compression de donnees. Il s'agit de vectorisation pour paralleliser certains calculs et les faire plus rapidement.

Les optimisations SIMD servent à accélérer les calculs c'est vrai. Mais les deux sont liées parce que le compilateur utilisera toujours un algorithme basé sur l'algorithme LZW qui comme tous les algorithmes liés aux compilateurs optimisent le code par compression pour ne pas avoir à écrire x fois le même code.
Voila, je vous suggere de vous documenter un peu plus.

Je vous rappelle que c'est mon métier et je pense être bien mieux expérimenté et documenté sur le sujet que vous ne le pensez
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Re: quelques fonctions d'arithmétique

Unread postby Adriweb » 20 Sep 2021, 00:21

rentech7289 wrote:
parisse wrote:Voila, je vous suggere de vous documenter un peu plus.

Je vous rappelle que c'est mon métier et je pense être bien mieux expérimenté et documenté sur le sujet que vous ne le pensez

Plusieurs d'entre nous ici, aussi informaticiens (ou ingé développeurs) de métier interviennent sur ce forum. Et parmi nous, on a du faire des réponses pour vous reprendre / corriger des informations douteuses voir fausses dans vos posts, souvent remplis de buzzwords qui n'ont rien à voir avec la choucroute.

Donc je suis d'accord avec Bernard Parisse, merci de vous documenter davantage avant de répondre à tire larigot sur plein de sujets (y compris certains vieux de plusieurs années) en ajoutant pas toujours grand chose de correct ou utile à la discussion.

Chacun peut faire des erreurs, mais essayer de se justifier à plusieurs reprises, en disant que vous avez forcément raison car vous êtes X ou Y de métier, ne fait en fin de compte qu'entacher votre réputation de développeur professionnel. A un moment donné, il faut savoir reconnaître d'avoir tort sur tel ou tel sujet, et passer à autre chose.
Image
MyCalcs
: Help the community's calculator documentations by filling out your calculator info!
MyCalcs
: Aidez la communauté à documenter les calculatrices en donnant des infos sur votre calculatrice ![/url]
Inspired-Lua.org
: All about TI-Nspire Lua programming
User avatar
AdriwebAdmin
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Level up: 58.7%
 
Posts: 13611
Images: 1101
Joined: 01 Jun 2007, 00:00
Location: France
Gender: Male
Calculator(s):
Twitter: adriweb
GitHub: adriweb

Re: quelques fonctions d'arithmétique

Unread postby rentech7289 » 20 Sep 2021, 02:10

Donc je suis d'accord avec Bernard Parisse

Sans doute, mais par rapport aux programmes ici présentés en pur python sans import de paquetage, je m'en tiendrait à la définition officielle de python pour les booléens:
https://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not
section "Truth Value Testing", c'est-à-dire un entier qui n'occupe que deux octets. Boolean est un sous-type de int.

Source que j'avais déjà citée et remise en cause par la personne à laquelle vous donnez raison. En bas de la même page:
Boolean Values
Boolean values are the two constant objects False and True. They are used to represent truth values (although other values can also be considered false or true). In numeric contexts (for example when used as the argument to an arithmetic operator), they behave like the integers 0 and 1, respectively. The built-in function bool() can be used to convert any value to a Boolean, if the value can be interpreted as a truth value (see section Truth Value Testing above).

They are written as False and True, respectively.

Et en bon français:
Valeurs booléennes
Les valeurs booléennes sont les deux objets constants False et True. Ils sont utilisés pour représenter des valeurs de vérité (bien que d'autres valeurs puissent également être considérées comme fausses ou vraies). Dans les contextes numériques (par exemple lorsqu'ils sont utilisés comme argument d'un opérateur arithmétique), ils se comportent comme les entiers 0 et 1, respectivement. La fonction intégrée bool()peut être utilisée pour convertir n'importe quelle valeur en booléen, si la valeur peut être interprétée comme une valeur de vérité (voir la section Test de la valeur de vérité ci-dessus).

Ils sont écrits comme Falseet True, respectivement.

en ajoutant pas toujours grand chose de correct ou utile à la discussion

Que je cite mes sources les informations fournies sont fiables et vérifiables. Malheureusement, dans la majorité des cas je ne peux pas dire si la personne concernée dispose déjà de celle-ci....
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Re: quelques fonctions d'arithmétique

Unread postby parisse » 20 Sep 2021, 07:03

Quelques precisions en vrac:
Les flottants sont de taille definie (32 ou 64 bits), mais ca n'est pas le cas des int (seule la taille minimale est fixee, a 16 bits).
Un booleen peut prendre deux valeurs, mais ca ne veut evidemment pas dire qu'il est stocke sur un entier occupant 2 octets. En Python, c'est certainement stocke comme un petit entier (donc sur un nombre important de bits) sauf si on utilise un type specifique, ce que numpy semble precisement proposer.
Les tests avec des booleens stockes sur 1 bit peuvent se faire avec un bitmask sans decalage, mais si on veut ramener la valeur a 0 ou 1, il faut faire un decalage et un bitmask. Et c'est une situation assez frequente, car on preferera toujours eviter de faire un test si on peut, car un test coute du temps en execution parce que le processeur ne peut pas facilement predire quelles seront les prochaines instructions a executer)
Un decalage de bit se fait en une seule instruction de CPU pour les CPU usuels, le temps d'execution ne depend que tres peu du nombre de decalage (en tout cas ca n'a absolument rien de lineaire).
Toujours sur le temps d'execution, on a souvent tendance a se focaliser sur le nombre d'operations arithmetiques d'un algorithme, en oubliant que le temps d'acces en lecture et ecriture a la memoire est plus long, surtout si les donnees ne sont pas dans le cache L1/L2/L3. D'ou l'interet de pouvoir lire/ecrire/stocker dans un registre 64 bits la valeur de 64 booleens simultanement, par exemple dans un crible.
User avatar
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 33%
 
Posts: 2648
Joined: 13 Dec 2013, 16:35
Gender: Not specified

Re: quelques fonctions d'arithmétique

Unread postby rentech7289 » 22 Sep 2021, 06:24

mais ca n'est pas le cas des int (seule la taille minimale est fixee, a 16 bits)

Cette taille est définie pour la grande majorité des langages. Et ne se limite pas à ce seul type: long en C/C++ et classe BigInteger (entier de longueur arbitraire) en Java par exemple.
En Python, c'est certainement stocke comme un petit entier

J'ai déjà répondu sur ce point avec la documentation officielle de Python. Rien à ajouter à ce que j'ai déjà posté.
D'ou l'interet de pouvoir lire/ecrire/stocker dans un registre 64 bits la valeur de 64 booleens simultanement, par exemple dans un crible.

Sans aucun doute mais
Et c'est une situation assez frequente, car on preferera toujours eviter de faire un test si on peut, car un test coute du temps en execution parce que le processeur ne peut pas facilement predire quelles seront les prochaines instructions a executer

Et c'est là que vous faites erreur: les booléens servent généralement aux microprocesseurs à effectuer les tests logiques qui indique au pointeur de pile quelle adresse mémoire il doit utiliser pour la suite de l'exécution du programme. Or un test n'a que deux solutions, la première étant l'instruction suivante qui est déjà en mémoire cache puisqu'elle est contenue dans la partie exécutée du programme. La seconde est envoyée au gestionnaire de mémoire qui doit charger les données concernées pour exécution si tel est le résultat du test. Il y a une dizaine d'années, la prédiction de branchement a été améliorée par Intel et est à l'origine de l'amélioration des performances de leurs microproceseurs face à ceux d'AMD. Pour résumer, en améliorant cette phase Intel a pu diminuer le nombre d'étapes dans le traitement des instructions et donc augmenter la vitesse de calcul.
La memoire allouee pour un tableau est liberee par les fonctions de la librairie C

Vrai mais cela pose de sérieux problèmes: on ne peut pas récupérer le moindre octet tant que ce tableau est utilisé. En C, un tableaux ne peux contenir qu'un type de données primitif. Ce qui veut dire que plus le type primitif utilise d'octets, plus il utilise de mémoire.
Il n'y a pas de compression quand on utilise des booleens, c'est juste une utilisation optimale de l'espace disponible: sur un octet on peut mettre 8 booleens, chacun sur un bit. Donc un tableau de booleen (par exemple cree avec le type std::vector<bool> de la libstdc++) occupe 32 fois moins de place qu'un tableau d'entiers 32 bits (int).


Les tableaux ne sont pas les meilleures structures de données comme nous l'avons vu dans le point précédent. Et comme vous avait l'air d'être à l'aise sur ce sujet je vous demande de ne pas hésiter à me corriger si je me trompe dans ce qui suit. Je n'aborderait que les matrices carrées par simplicité, mais garderait la logique ligne-colonne par souci de compréhension sur certains points. J'utiliserais True pour indiquait la présence d'une valeur non nulle, et False pour la présence d'une valeur nulle dans un élément du tableau correspondant.
Une matrices de taille 2 x 2 est un tableau de 4 éléments. Dans la matrice booléenne indiquant peut avoir 4 valeurs à True. Cette matrice est l'équivalent d'un polynôme du second dégré. Ce qui signifie que si nous avons une matrice diagonale non nulle, nous avons les solutions de ce polynôme et que la matrice en question est résolue. Ce qui veut dire que dans le cas présent nous avons au maximum 2 éléments non nuls soit 2 sur 4, ce qui donne une probabilité de valeurs non nulles dans la matrice de 0,5. Comme il ne peut y avoir que deux valeurs possibles, le pire cas est donc 1 sur 4, soit 0,25.
Ce qui veut dans le meilleur cas que notre matrice a lignes x colonnes éléments non nuls au départ, et au mieux après résolution a lignes divisé par le nombre de valeurs initiales non nulles. D'accord?
Si je passe à une matrice de taille 8 par 8, il y 64 éléments à valeurs non nulles au départ, mais plus que 8 dans le meilleur des cas à l'arrivée sur 8 / 64 = 0,125.
Ce qui veut dire que pour une matrice carrée de taille n, le nombre de valeur de non nulles après résolution est de 1 sur n. Ce qui veut que plus une matrice booléenne est grande plus les tests sur celle-ci deviennent coûteux et plus elles perturbent le fonctionnement de l'ordinateur puisque la majorité partie de la mémoire y est occupée en pure perte.

Dans ces derniers cas je trouve que ça fait beaucoup de performances perdues pour pas grand chose. Je ne parle même des opérations de permutations de lignes ou de colonnes. Si vous votre matrice numérique est modifiée mais pas votre matrice booléenne, vous ne pouvez plus itérer sur votre matrice booléenne directement comme vous le faites avec la matrice numérique. Il vous faut calculer les indices en fonction des modifications apportées à la première matrice pour que les données issues de la seconde soient correctes et vice-versa.
Le dernier point est le suivant: Si les booléens sont stockés en suivant les lignes, permuter des lignes n'est pas un problème. Par contre cela le devient dès qu'il s'agit de déplacer des colonnes: il faut soit changer l'orientation de la matrice, soit opérer avec travailler avec des fonctions bit à bit. Autant dire une perte de temps de calcul inestimable surtout si la matrice a une taille de l'ordre de la centaine ou du millier d'éléments par côté.

La seule alternative aux tableaux de type primitif est l'utilisation de structures de données mutables comme les dictionnaires ou offrant une possibilité similaire à ce que je vais vous expliquer. Un dictionnaire occupe beaucoup de mémoire mais en tant que stockage linéaire, c'est plutôt pratique et facile à gérer surtout quand les seules valeurs stockées ne sont des 1 ou True. Il faut un dictionnaire par ligne, et tous les réunir dans un dictionnaire qui contiendra les dictionnaires-lignes, même vides, qui seront assimilés aux colonnes.
Certes, un dictionnaire-ligne sera volumineux au départ puisqu'il contiendra toutes les clés contenant une valeur. La clé étant l'index de la colonne concernée. Si la valeur devient nulle on supprime la clé, si la valeur devient non nulle on ajoute la clé au dictionnaire. Les permutations? Pour une ligne, l'opération est effectuée avec la méthode
Code: Select all
copy
. Pour une colonne, on procède par recherche de clés tout en sachant qu'il n'y aura que les éléments non nuls de la colonne qui seront concernés. Le plus important étant qu'au fil de la résolution de la matrice numérique, la matrice booléenne diminuera de taille et que la mémoire sera diminuée en conséquence. Ce qui veut dire que plus on approchera de la solution, plus il y aura de gains en calculs.
Je sais qu'il y a plus efficace mais pour un non spécialiste en python, ces explications restent abordables. Ce post est certes long mais vous comprendrez mon aversion pour les structures figées comme les tableaux avec ce changement de point de vue.
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Re: quelques fonctions d'arithmétique

Unread postby parisse » 22 Sep 2021, 07:25

Sur les booleens : en general ils sont utilises pour faire un test effectivement, mais on n'a alors pas de raison de les stocker dans un tableau. Mais ici je rappelle qu'on parlait du crible ou on stocke dans un tableau le fait d'etre premier ou pas et on a tout interet a en stocker 32 ou 64 dans un entier 32 ou 64 bits. C'est vrai egalement pour une matrice d'entiers modulo 2, ou on peut par exemple faire la reduction de Gauss en parallelisant 32 ou 64 operations a la fois avec l'instruction de ou exclusif.
D'autre part, meme si les fondeurs de microprocesseurs font des progres, les optimisations qui permettent d'eviter un test restent d'actualite quand on veut optimiser son code (comme je le fais dans Xcas). Par exemple si a et p sont des int 32 bits avec p>0, le code suivant (tres utilise en arithmetique modulo p)
Code: Select all
a += (a>>31)&p;

est plus rapide que:
Code: Select all
if (a<0) a+=p;

Sur les matrices: il n'y a pas de lien entre matrice et polynome, et aucune raison a priori qu'une matrice de booleen ait plus de false que de true. Si on sait pour une raison donnee qu'une matrice a beaucoup plus de 0 que d'elements non nuls alors on peut utiliser un type de stockage creux, avec le type std::map en C++ ou equivalent. Mais il faut vraiment avoir beaucoup plus de 0, parce que le cout de manipulation est bien plus eleve qu'avec un tableau. C'est je trouve un des gros problemes avec l'utilisation tres facile de bibliotheques puissantes, des gens non avertis utilisent des structures de donnees non maitrisees sans se rendre compte de l'impact que cela peut avoir.
User avatar
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 33%
 
Posts: 2648
Joined: 13 Dec 2013, 16:35
Gender: Not specified

Re: quelques fonctions d'arithmétique

Unread postby rentech7289 » 22 Sep 2021, 08:55

Mais ici je rappelle qu'on parlait du crible ou on stocke dans un tableau le fait d'etre premier

Le fait que ce soit un crible nous rapproche du cas des matrices, puisque plus le tableau grandit, moins il y reste de True puisqu'il y a plus de multiples de nombres premiers qui y entrent. La solution du dictionnaire ou même d'une liste est dans ce cas à tout à fait viable. L'unique problème étant jusqu'à quelle valeur doit-on stocker les nombres premiers.
Sur les matrices: il n'y a pas de lien entre matrice et polynome

Sur ce point je vous demande pardon,j'ai commis une énorme bévue et merci de me reprendre: je pensais à autre chose qu'aux systèmes d'équations linéaires. Il est vrai que la présentation de la résolution d'équations du second degré au lycée a laissé une trace indélébile.
aucune raison a priori qu'une matrice de booleen ait plus de false que de true

Mon hypothèse de départ étaient que tous les éléments de la matrice ait une valeur puisque c'est le seule cas où elle pleine. S'il y a encore des valeurs à stocker c'est que la matrice n'a pas les bonnes dimensions...
J'ai utilisé le terme nul pour parler de la valeur numérique, j'aurais préciser true != 0 et false=0. Et dans le cas de la résolution d'un système d'équations linéaires, il veut mieux au final que tous les éléments n'appartenant pas à la diagonale de la matrice ait 0 pour valeur, à moins que je ne me trompe. Ce qui donne une bonne raison pour avoir le moins de false possible dans la matrice booléenne. Quant à l'utilisation des bibliothèques puissantes je vois où vous voulez en venir mais ce n'est pas mon utilisation. Par structures de données je faisais allusion aux contenant de type dictionnaire et autres fichiers CSV, sans parler des bases de données de type-clé valeur pour lesquelles la matrice booléenne devient primordiale. En effet, dans ces cas de figure plus il y a de false moins il y a d'accès disque mais fondamentalement ça ne change rien au problème puisque dès le départ nous avons affaire à une matrice dont on connait les dimensions mais pas la solution...
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Previous

Return to Programmation Python

Who is online

Users browsing this forum: No registered users and 2 guests

-
Search
-
Social
-
Featured topics
Concours de rentrée 2021 - La Geste d'Alrys
Concours de rentrée 2021 - Synchro-donjon !
Comparaisons des meilleurs prix pour acheter sa calculatrice !
25€ remboursés par Casio sur l'achat de ta calculatrice fx-CP400 d'ici le 31 Octobre 2021
Journées APMEP 2021 à l'IUT de Bourges les 24-25 Octobre. Viens rencontrer Casio, NumWorks, TI et Vittascience.
Coque NumWorks édition limitée Octobre 2021 à gagner.
123456
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
553 utilisateurs:
>543 invités
>5 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)