Blue Caterpillar: Eh bien, vous ne nous abattez pas. Nous nous asseyons, nous savons: ils attendent notre transformation. Quoi? Mais rien! Nous nous asseyons, fumons, attendons ...
Poupée Alice: Quoi?
Chenille bleue: Quoi, pourquoi! Des transformations. La maison en fumée, la fumée en dame et la dame en mère. Voilà. N'intervenez pas, ne sautez pas en avant, sinon vous vous transformerez prématurément en une sorte de papillon.
En parcourant le code sur l'un des forums dédiés à Arduino, j'ai trouvé une façon amusante de travailler avec un nombre à virgule flottante (PT). Le deuxième nom commun pour les nombres dans ce format est la virgule flottante, mais l'abréviation (PP) qui apparaît dans ce cas provoque personnellement des associations complètement différentes pour moi, nous allons donc utiliser cette option. La première impression (du code vu) est quel type de déchets est écrit ici (je dois dire que le second est le même, bien qu'il y ait des nuances, mais plus à ce sujet plus tard), mais la question se pose - comment est-ce vraiment nécessaire - la réponse à laquelle est donnée dans texte supplémentaire.
Première partie - Questionnement
Nous formulons le problème - nous devons imprimer sur la console (transformer en une représentation symbolique) un nombre à virgule flottante, sans utiliser les options d'impression, qui sont prévues à cet effet. Pourquoi voulons-nous le faire par nous-mêmes -
- l'utilisation du format% f implique la connexion de la bibliothèque pour travailler avec une virgule flottante et une version étendue de la fonction prntf (ou plutôt, rend impossible l'utilisation de sa version tronquée), ce qui conduit à une augmentation significative de la taille du module exécutable,
- une solution standard nécessite un temps considérable (elle fonctionne toujours avec un nombre à double précision), ce qui peut être inacceptable dans cette situation particulière,
- Eh bien (enfin, mais non le moindre), c'est juste intéressant.
Pour commencer, considérez l'option qui a été proposée dans le document ci-dessus, quelque chose comme:
for (float Power10=10000.0; Power10>0.1; Power10/=10.0; ) {char c=(int)(Fdata/Power10); Fdata -=Power10*c; };
et nous convenons qu'il résout complètement le problème. De plus, ce n'est pas une mauvaise option, car sa vitesse peut être tout à fait acceptable. Examinons de plus près ce moment - nous voyons la division des nombres PT, mais si nous approfondissons l'essence de la question, il s'avère qu'elle est presque aussi rapide que la division des entiers de la profondeur de bits correspondante. En fait, avant d'évaluer les performances de l'algorithme, vous devez évaluer les performances de diverses opérations élémentaires, ce que nous ferons.
Deuxième partie - Évaluation du rendement des opérations élémentaires
La première opération intéressante est l'ajout (soustraction, en termes de temps passé, ils sont équivalents) d'entiers de nombres et nous pouvons supposer qu'il faut une unité de temps (cycle d'horloge) avec la mise en garde suivante - cela n'est vrai que pour les données "natives". Par exemple, pour l'AVR de la série MK, il s'agit d'un mot de 8 bits, pour le MSP430, il s'agit d'un mot de 16 bits (et, bien sûr, de plus petite taille), pour Cortex-M, il s'agit d'un mot de 32 bits et ainsi de suite. Ensuite, l'opération d'ajout de nombres avec une longueur de H fois plus que le nombre natif peut être estimée comme H cycles. Il existe des exceptions, par exemple, AddW dans les contrôleurs AVR, mais cela n'annule pas la règle.
L'opération suivante est la multiplication des entiers (mais pas la division, elle diffère en termes de vitesse) et pour lui tout n'est pas si simple. Tout d'abord, la multiplication peut être implémentée dans le matériel et, par exemple, dans AVR MEGA, elle nécessite 2 cycles d'horloge, et dans les 51 améliorés jusqu'à 6 (pour multiplier les nombres natifs).
Mais considérons le cas lorsqu'il n'y a pas d'implémentation matérielle et que nous devons implémenter la multiplication sous la forme d'un sous-programme. Étant donné que lors de la multiplication des nombres de bits H, un produit de 2 bits est obtenu, alors l'estimation de la version classique avec décalages peut être trouvée comme suit: nous avons besoin de décalages H du facteur avec 1 cycle d'horloge par décalage, les décalages H du deuxième facteur 2H de long avec 2 cycles d'horloge par décalage, puis H prendra des décisions et , en moyenne, N / 2 additions de nombres d'une longueur de 2H, en conclusion, l'organisation d'un cycle de 2 mesures. Le total + 2 + + 2 / 2 + 2 = 7 ticks, et effectuer des opérations arithmétiques de leur part ne prend que N ticks (wow efficacité, bien que nous ayons réussi à contourner le moteur).
Autrement dit, pour multiplier deux nombres 8p par 8p MK, 56 cycles sont nécessaires, et pour multiplier les nombres 16p, il y a déjà 112 cycles (légèrement moins, mais nous négligeons la valeur exacte) cycles, ce qui est un peu plus que ce que nous voulions. Heureusement, la direction des décalages peut être modifiée et il existe un moyen unique de multiplication, qui ne nécessitera que H décalages du nombre de 2H chiffres et H / 2 ajouts de nombres natifs, ce qui améliore le temps de fonctionnement de l'algorithme de multiplication à 0 + 2 + 1 + 1/2 + 2 = 5.5 - bien sûr, cela ne peut pas être comparé à l'implémentation matérielle, mais au moins un gain sans perte de fonctionnalité. Il y a des améliorations à cet algorithme, par exemple, l'analyse de 2 bits par cycle, mais elles ne changent pas fondamentalement la situation - le temps de multiplication par ordre de grandeur dépasse le temps d'addition.
Mais avec la division, la situation est pire - même la division implémentée matériellement perd presque deux fois plus à la multiplication, et il y a des MK avec multiplication matérielle, mais sans division matérielle. Dans certaines conditions, la division peut être remplacée par la multiplication par l'inverse, mais ces conditions sont spécifiques et donnent un résultat similaire - deux itérations de multiplication sont nécessaires suivies de la somme, il y a donc une perte double. Si nous implémentons la division en tant que sous-programme, alors les décalages H du diviseur 2H de long, les soustractions H du divisible 2H de long, les décalages H du résultat, l'organisation 2H du cycle sont nécessaires, mais tout cela est précédé d'un alignement, qui prendra encore 5H cycles, donc le chiffre total est 2 + 2 + 1 + 2 + 5 = 12, ce qui est environ 2 fois pire que la multiplication.
Eh bien, regardons maintenant les opérations PT, et ici la situation est quelque peu paradoxale - l'opération de multiplication nécessite presque autant de temps que pour les entiers (correspondant à la capacité en bits, en règle générale, 24 bits), car nous devons multiplier la mantisse et simplement additionner les commandes, la normalisation ne fonctionne pas requis. La division est également bonne, divisez la mantisse et soustrayez les ordres, la normalisation n'est à nouveau pas nécessaire. Par conséquent, pour ces deux opérations, la perte par rapport aux entiers n'est pas trop importante, bien qu'elle ait une place.
Mais l'opération d'addition et de soustraction nécessite, tout d'abord, l'alignement des ordres (et ce sont des décalages et il peut y en avoir beaucoup, bien qu'il y ait des nuances), puis l'opération elle-même et (lors de la soustraction) la normalisation (lors de l'ajout aussi, mais cela ne prend pas plus d'un décalage ), ce qui est une perte de temps, donc les opérations de cette classe pour PT sont beaucoup plus lentes que pour les entiers, surtout en termes relatifs.
Revenons à nos moutons et convenons que, sur la base des estimations précédentes, la méthode proposée peut ne pas être trop longue, d'autant plus qu'elle donne immédiatement le résultat, mais elle a une limitation importante - elle est applicable à une plage très limitée de valeurs PT d'entrée. Par conséquent, il cherchera une solution universelle (plus ou moins).
Faites immédiatement une réserve que notre solution ne devrait pas utiliser des opérations à virgule flottante en général (du mot du tout) pour souligner les mérites de notre option. Et à la question perplexe de savoir comment un certain nombre de ce type apparaîtra si les opérations ne sont pas disponibles, nous répondons - cela peut bien apparaître, par exemple, lors de la lecture d'informations à partir d'un capteur de lumière (comme c'était le cas dans l'exemple d'origine), qui produit des données au format PT.
Comment exactement le nombre de PT est organisé, vous pouvez facilement le trouver sur de nombreux sites, il y avait un article récent sur Habré, cela ne devrait pas poser de problème. Néanmoins, un certain nombre de questions présentent un intérêt pour le format PT dans le style «si j'étais le réalisateur» - pourquoi il en est ainsi, et non autrement. Je donnerai mes réponses à certains d'entre eux, si quelqu'un en sait plus, veuillez commenter.
La première question est pourquoi la mantisse est-elle stockée en code direct et non en code supplémentaire? Ma réponse est parce qu'il est plus facile de travailler avec une mantisse normalisée avec un bit caché (facultatif).
La deuxième question est pourquoi la commande est stockée avec un décalage, et non autrement? Ma réponse est parce que dans ce cas, il est facile de comparer les modules de deux PT sous forme d'entiers, avec d'autres méthodes, c'est plus compliqué.
La troisième question est de savoir pourquoi le signe négatif est codé par un plutôt que par zéro, car il serait alors possible de comparer simplement les deux points sous forme d'entiers? Ma réponse est que je ne sais pas, c'est juste "c'est tellement habituel ici".
Troisième partie - Explications requises
Dans le paragraphe précédent, je pourrais donner des termes incompréhensibles, donc un peu sur la représentation des nombres. Bien sûr, ils sont différents, sinon il ne serait pas nécessaire d'en discuter. Immédiatement, nous notons que dans la mémoire de MK (la même chose est vraie pour les ordinateurs, bien que je ne sois pas si catégorique sur les architectures les plus modernes - elles sont si compliquées que tout peut être attendu) il n'y a pas de nombres, il n'y a que des unités de stockage élémentaires - des bits regroupés en octets et plus en mots. Lorsque nous parlons de la représentation d'un nombre, cela signifie que nous interprétons un ensemble de bits d'une longueur spécifique d'une manière ou d'une autre, c'est-à-dire que nous définissons une loi par laquelle nous pouvons trouver un certain nombre correspondant à un ensemble donné de bits, et rien de plus.
D'innombrables lois peuvent être inventées, mais certaines d'entre elles auront un certain nombre de propriétés utiles en termes de conduite de diverses opérations, elles seront donc plus souvent appliquées dans la pratique. L'une de ces propriétés, qui est implicitement implicite, par exemple, est le déterminisme, et l'autre est l'indépendance vis-à-vis de l'environnement - des propriétés qui sont, à première vue, évidentes, bien qu'il y ait des nuances. D'autres propriétés du type de correspondance biunivoque font déjà l'objet de discussions et ne prennent pas toujours place dans une représentation concrète. Le sujet de la représentation des nombres en soi est inhabituellement fascinant; pour Knut (dans le volume deux), il est entièrement divulgué, de sorte qu'il dépasse les profondeurs et que nous dépassions la surface.
Sous l'hypothèse que l'ensemble de bits a une longueur n (nous les numérotons dans une rangée de 0 à n-1) et qu'ils sont pondérés uniformément avec un pas de 2 et que le bit le moins significatif (avec le numéro 0) a un poids de 1 (ce qui, en règle générale, n'est pas du tout nécessaire, nous Nous nous sommes habitués à de telles choses, et elles nous semblent évidentes) nous obtenons une représentation binaire du nombre, dans lequel la formule de réduction ressemble à ceci: le nombre affiché par l'ensemble de bits
(2) = (0)*2^0 + (1)*2^1 + ... + (-1)*2^(-1) ou en cascade
2() = (0)+2*((1)+2*(...+2*((-1))..))) , ci-après, B (k) désigne un bit avec le nombre k. Notez que sous une représentation différente n'impose aucune restriction sur l'emplacement des octets du nombre en mémoire, mais il serait plus logique de placer l'octet bas dans les adresses inférieures (c'est avec quelle facilité et naturellement j'ai résolu «l'argument éternel des Slaves entre eux» concernant la fin la plus pratique pour casser un œuf).
Avec cette interprétation d'un ensemble de bits de longueur n (= 8), nous obtenons une représentation pour les nombres de 0 à (2 ^ n) -1 (= 255) (ci-après entre parenthèses, il y aura une valeur spécifique pour un ensemble de 8 bits), qui a un certain nombre de remarquables et propriétés utiles, c'est pourquoi il est devenu répandu. Malheureusement, il présente également un certain nombre d'inconvénients, dont l'un est que nous ne pouvons pas représenter des nombres négatifs dans un tel record en principe.
Vous pouvez offrir une variété de solutions à ce problème (la représentation des nombres négatifs), parmi lesquelles il existe également une importance pratique, elles sont énumérées ci-dessous.
Une représentation avec un décalage est décrite par la formule H = N2 (n) - décalage (C), où N2 est le nombre obtenu en notation binaire avec n bits, et C est une valeur présélectionnée. Ensuite, nous représentons des nombres de 0-C à 2 ^ (n) -1-C, et si nous choisissons C = 2 ^ (n-1) -1 (= 127) (c'est complètement facultatif, mais très pratique), alors nous obtenons la plage de 0- (2 ^ (n-1) -1) (= - 127) à 2 ^ (n-1) (= 128). Le principal avantage de cette représentation est la monotonie (d'ailleurs, augmenter) sur tout l'intervalle, il y a aussi des inconvénients, parmi lesquels on met en évidence l'asymétrie (il y en a d'autres liés à la complexité des opérations sur le nombre dans cette représentation), mais les développeurs de la norme IEEE 457 (c'est la norme pour PT) a transformé cette faille en vertu (en utilisant une valeur supplémentaire pour coder la situation nan), ce qui souligne une fois de plus la fidélité du dicton cool: «Si vous êtes plus élevé que l'adversaire, alors c'est votre avantage. Si l'adversaire est plus grand que vous, alors c'est aussi votre avantage. »
Notez que puisque le nombre total de combinaisons possibles d'un nombre quelconque de bits est pair (si vous n'avez pas de combinaisons interdites pour des raisons religieuses), la symétrie entre les nombres représentatifs positifs et négatifs est fondamentalement inaccessible (ou plutôt réalisable, mais sous certaines conditions supplémentaires, dont plus) .
Représentation sous la forme d'un code direct lorsque l'un des bits (le plus significatif) représente le signe codé du nombre H = (-1) ^ B (n-1) * P2 (n-1) a une plage de 0- (2 ^ (n-1) -1) (= -127) à 2 ^ (n-1) -1 (= 127). Il est intéressant de noter que je viens de déclarer l'impossibilité fondamentale de la symétrie, et la voici clairement - le nombre positif maximum représentable est égal au module du nombre négatif minimum représentable. Ce résultat est obtenu en ayant deux représentations pour zéro (00 ... 00 et 10 ... 00), ce qui est généralement considéré comme le principal inconvénient de cette méthode. C'est vraiment un inconvénient, mais pas aussi terrible qu'on le croit généralement, car il y en a d'autres plus importants qui limitent son utilisation.
La représentation en code inverse, lorsque dans la représentation directe, nous inversons tous les bits de la valeur pour les nombres négatifs H = (1-B (n-1)) * P2 (n-1) + B (n-1) * (2 ^ (n -1) -CH2 (n-1)) - c'est à partir de la définition, vous pouvez faire une formule beaucoup plus compréhensible H = Ch2 (n-1) -B (n-1) * (2 ^ (n-1) -1), ce qui nous permet de représenter des nombres de 0-2 ^ (n-1) +1 (= - 127) à 2 ^ (n-1) -1 (= 127). On peut voir que cette représentation est déplacée, mais le déplacement change pas à pas, ce qui rend cette représentation non monotone. Encore une fois, nous avons deux zéros, ce qui n'est pas très effrayant, l'occurrence de transfert circulaire lors de l'addition est bien pire, ce qui crée certains problèmes dans la mise en œuvre de l'ALU.
Pour éliminer le dernier inconvénient de la représentation précédente est inhabituellement simple, il suffit de changer le décalage d'un, puis on obtient = = 22 (n-1) -B (n-1) * 2 ^ (n-1) et on peut représenter des nombres de 0-2 ^ ( n-1) (= - 128) à 2 ^ (n-1) -1 (= 127). Il est facile de voir que la représentation est asymétrique, mais zéro est unique. La propriété suivante est beaucoup plus intéressante: «il est tout à fait évident que» le transfert en anneau ne se produit pas pour une opération de type addition, ce qui est la raison (avec d'autres caractéristiques agréables) de la distribution universelle de cette méthode particulière de codage des nombres négatifs.
Établissons un tableau de valeurs intéressantes pour différentes méthodes de codage des nombres, notant par H la valeur 2 ^ (n-1) (128)
| Bits | 00..00 | 11/01 | 10..00 | 11.11 |
|---|
| H (n) | 0 | H-1 (127) | H (128) | 2 * H-1 (255) |
| H (n-1) | 0 | H-1 (127) | 0 | H-1 (127) |
| Décalage. N | -H + 1 (-127) | 0 | 1 | H (128) |
| Direct | 0 | H-1 (127) | 0 | -H + 1 (-127) |
| Inverser | 0 | H-1 (127) | -H + 1 (-127) | 0 |
| Addition | 0 | H-1 (127) | -H (-128) | -1 |
Eh bien, pour conclure le sujet, nous donnons des graphiques pour les représentations énumérées, à partir desquels leurs avantages et leurs inconvénients sont immédiatement visibles (bien sûr, tout ce qui ne fait pas rappeler le dicton intéressant "L'avantage de la présentation graphique des informations est visuel, il n'a pas d'autres avantages").
Quatrième partie - Résoudre réellement le problème d'origine (mieux vaut tard que jamais).
Petite digression
Pour commencer, je voulais imprimer le PT au format hexadécimal (et finalement je l'ai fait), mais de manière assez inattendue / complètement inattendue (je devais remplacer), je suis tombé sur le résultat suivant. Que pensez-vous sera imprimé à la suite de l'exécution des opérateurs:
printf("%f %x", 1.0,1.0); printf("%f %x",2.0,2.0); printf("%x %d",1.0,1.0); printf("%x %d",2.0,2.0);
, faites également attention à la construction suivante et à son résultat:
printf("%x %x %f",1.0,1.0);
Je ne donnerai pas d'explications à ce phénomène, "assez malin".
Cependant, comment imprimer correctement la représentation hexadécimale de PT? La première solution est évidente - l'union, mais la seconde est pour les fans d'une seule ligne printf ("% x", * ((int *) (& f))); (Je m'excuse si quelqu'un a été offensé par des crochets supplémentaires, mais je n'ai jamais pu, et je n'ai jamais eu l'intention de m'en souvenir, les priorités des opérations, d'autant plus que les crochets ne génèrent pas de code, donc je continuerai à faire de même). Et voilà, la solution de la tâche - nous voyons une chaîne de caractères, 0x45678, qui détermine uniquement le nombre souhaité pour nous, mais de telle manière que nous (je ne sais pas pour vous, je ne peux certainement) rien dire d'intelligible sur ce nombre. Je pense que l'académicien Karnal, qui aurait pu signaler une erreur dans la bande perforée avec le code source, aurait géré cette tâche, mais tout le monde n'est pas si avancé, alors nous allons continuer.
Nous essaierons d'obtenir des informations sous une forme plus compréhensible.
Pour ce faire, nous revenons au format du PT (ci-après, je ne considère que le flottant), qui est un ensemble de bits à partir duquel vous pouvez extraire (selon certaines règles) trois ensembles de bits pour représenter trois nombres - signe (s), mantisse (m) et ordre (p), et le nombre souhaité codé par ces nombres sera déterminé par la formule suivante: Cs * Chm * Chn. Ici, les symboles désignent les nombres représentés par l'ensemble de bits correspondant.Par conséquent, pour trouver le nombre souhaité, nous devons connaître les lois par lesquelles nous extrayons ces trois ensembles de l'ensemble de bits d'origine, ainsi que le type de codage pour chacun d'eux.
Pour résoudre ce problème, nous nous tournons vers la norme IEEE et découvrons que le signe est un bit (senior) de l'ensemble d'origine et la formule de codage Cs = (- 1) ^ B (0). L'ordre occupe les 8 bits supérieurs suivants, est écrit en code avec un décalage de 127, et représente une puissance de deux, puis Cn = 2 ^ (C2 (8) -127). Mantissa prend l'ordre suivant de 23 chiffres et représente le nombre Chm = 1 + Ch2 (23) / 2 ^ 23.
Nous avons maintenant toutes les données nécessaires et nous pouvons résoudre complètement la tâche - créer une chaîne de caractères qui, avec une certaine lecture, représentera un nombre égal à celui codé. Pour ce faire, nous devons, par des opérations simples, extraire les nombres ci-dessus, puis les imprimer, en fournissant les attributs nécessaires. Nous supposons que nous sommes en mesure de convertir un entier ne dépassant pas 32 bits en une chaîne de caractères, ce qui n'est pas compliqué.
Malheureusement, nous ne sommes qu'au début du voyage, car peu de lecteurs de cet article dans le dossier «+ 1.625 * 2 ^ 3» reconnaissent le nombre malchanceux, qui est codé par la décimale plus courante «13», et devinez dans le dossier «1.953125 * 2 ^ 9 "le simple" 1E3 "ou" 1 * 10 ^ 3 "ou le très familier" 1000 "sont capables d'unités de personnes en général, je ne leur appartiens certainement pas. Il est étrange de voir comment cela s'est produit, car nous avons terminé la tâche initiale, qui montre une fois de plus avec quelle prudence vous devez traiter les formulations. Et le fait n'est pas que la notation décimale est meilleure ou pire que le binaire (dans ce cas, le deuce est basé sur le degré), mais que nous sommes habitués à la décimale car l'enfance et la refonte des gens est beaucoup plus difficile que le programme, nous allons donc donner notre entrée aux plus familiers.
Du point de vue des mathématiques, nous avons une opération simple - il y a un enregistrement PT = (- 1) ^ s * m * 2 ^ n, et nous devons le convertir sous la forme PT = (-1) s '* m' * 10 ^ n '. Nous égalisons, transformons et obtenons (l'une des options possibles) les solutions s '= s', m '= m, n' = n * log (2). Si nous laissons de côté les crochets de la nécessité de multiplier par un nombre explicitement irrationnel (cela peut être fait si le nombre est rationalisé, mais nous en parlerons plus tard), alors le problème semble être résolu jusqu'à ce que nous voyions la réponse, parce que si l'enregistrement est comme «+1.953125 * 2 ^ 9 "nous semble obscur, le record" + 1.953125 * 10 ^ 2.70927 "est encore moins acceptable, même s'il semblait qu'il n'y avait nulle part pire.
— 10 '= * 10^{ * lg(2)}, '= [ * lg(2)], . (1.953125*10^0.7 0927)*10^2=«10*10^2», , , .
, :
- () (lg(2)) ( );
- ( );
- (10) (...);
- (« , ...»).
, , , 1. , * lg(2), «» , =0 ( =/lg(10)). , « », « ». . , , ' = * lg(2) * [lg(2) *256 + 1/2] / 256 , 1/2/77 = 1/144, , 1/100. — , . [4.501]=5, [4.499]=4 , , 0.002/4.5=0.04%, 1/4=25%. , , . , , , , , , .
'=*77/256
, . 24 , 2^-24=2^-4*2^-20=16^-1*(2^10)^-2~(10)^-1*(10^3)^-2=10^-7, 7 . 24 ( ). , 32 ( ) , 100 (256) , .
' = * 10^{ * lg(2)}— 1) , 2) , , , , , . — , , , .
« , , »
q(10^x) = Δ(10^x)/10^x = (10^(x +Δx) — 10^x)/10^x = 10^Δx -1 = 10^(x*qx)-1,
10^(x*qx) >~ 10^(x*0) + (10^(x*0))'*qx = 1 + x*ln(10)*10^(0)*qx = 1+x*ln(10)*qx,
— , , =127, 292 , , .
, 24 32 ( , ), , (*lg(2)) 32 , , 1'292'914'005/2^32. , , (int)((lg(2)*float(2^32))+0.5), 04d104d42, , .
, , , , .
10 0 1 . , , , , , ''=lg(2)*i+(''-lg(2)*i), 2 , ( ), lg(2) 10^'' ( ).
, lg(2) , , . , , , , 10-7 9 , 1+9*2=19 32- , . '=*lg(2) , .
32- 1+19+1=21
— , — , . , — ( ) , , .
— — (2^8=256) ['] ( 10) {'} ( ), . — =*2^=*10^'*(2^/10^')=(*(2^/10^'))*10^'.
256*3 ( 24 , ) + 256*1 ( 10 2) = 1 . 24*24 ( 32*32), .
, ( , ). , , ( 256 10) . , ,
2 ^ -n / 10 ^ -n '= 1 / (2 ^ n / 10 ^ n')! = 2 ^ n / 10 ^ n ',dommage. , . , — 18 , , , , 512 . — , , , , .
- , ( ) . ( )
=*2^=*2^(0+1)=*10^'*(2^(0+1)/10^')=*(2^0/10^')*2^1*10^',
0- , 1=-0. , .
— , 0 ? , — 10 . — 32*32, 24 , 8 8 . 256/8*4=32*4=128 — 8 .
0, , 32/2=16 , , ( ) .
, adafruit
const UINT8 Bits[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; ... data = data | Bits[n];
, 1 << n AVR . , , .
, , , ( godbolt, , , ) , .
( , 1 )
ldi r18,lo8(4) sbrs r25,1 ldi r18,lo8(1) sbrc r25,0 lsl r18 sbrs r25,2 swap r18
, , 8:7 8 (, , 16 — — « , , , »). — , : « „ 12 “ (» ", , ).
= * 2^=( * [/8]) * 2^(%8) * 10^[/8],
- - . , 32*32(24*24) . 32 10 , ( , ) .
— ,
const uint32_t Data[32] PROGMEM = { 0xF82345,… }
, , , . , , , ( )
#define POWROUD(pow) ((uint8_t)((pow & 0x07)*log(2)+0.5)) #define MULT(pow) (2^pow / 10^POWROUND(pow)) #define MULTRAW(pow) (uint32_t((MULT(pow) << 24) +0.5)) #define BYTEMASK 0xFF #define POWDATA(pow) ((POWROUND(pow) & BYTEMASK)| (MULTRAW(pow) & (~BYTEMASK))) const uint32_t Data[(BYTEMASK/8)+1] = { POWDATA(0x00),POWDATA(0x08), ..POWDATA(0xF8)}
, , , .
, , , , . . :
1.953125*2^9=1.953125*2^(8+1)=1.953125*42949673/256/256/256(2.56)*2*10^2=10*10^2
1000. , , , , , , , .