La mise en œuvre efficace de logarithme naturel (ln) et l'exponentiation
En gros, je suis à la recherche pour la mise en œuvre de log()
et exp()
fonctions de la bibliothèque C <math.h>
. Je travaille avec 8 bits microcontrôleurs (OKI 411 et 431). J'ai besoin de calculer Température Cinétique Moyenne. La condition est que nous devrions être en mesure de calculer MKT aussi vite que possible et avec aussi peu de mémoire pour le code que possible. Le compilateur est livré avec log()
et exp()
fonctions dans <math.h>
. Mais l'appel de l'une de fonction et lier avec la bibliothèque causes de la taille du code à augmenter de 5 kilo-octets, ce qui ne rentre pas dans l'une des micro-nous travailler avec (OKI 411), parce que notre code a déjà été consommée ~12K de disponible ~15K code de la mémoire.
La mise en œuvre, je suis à la recherche ne doit pas utiliser les autres fonctions de la bibliothèque C (comme pow(), sqrt (), etc). C'est parce que toutes les fonctions de la bibliothèque sont emballés dans un la bibliothèque et même, si une fonction est appelée, l'éditeur de liens apportera toute la 5K bibliothèque de code de la mémoire.
MODIFIER
L'algorithme doit être correcte jusqu'à 3 décimales.
oublié de l'ajouter. merci pour le rappel. j'ai édité ma question. 🙂
Aussi, ce sont l'entrée et la sortie des formats numériques? Point fixe comme 8.8? Il semble que vous aurait avantage à stocker un décalage par rapport à 273 kelvins, c'est à dire Celsius.
l'entrée/sortie n'est pas tout souci. qu'entendez-vous par "parti pris par rapport à 273K'?
Car 273 est un grand nombre par rapport à la valeur de la température en degrés Celsius, vous pouvez obtenir plus de précision à partir de la même bits en stockant Celsius au lieu de Kelvin. En fait, cette illustre pourquoi l'entrée/sortie est un sujet de préoccupation. Comme Alexei mentionne, la plage de température influe sur le choix de la formule.
OriginalL'auteur Donotalo | 2012-03-21
Vous devez vous connecter pour publier un commentaire.
La série de Taylor pour e^x converge très rapidement, et vous pouvez ajuster votre mise en œuvre de la précision dont vous avez besoin. (http://en.wikipedia.org/wiki/Taylor_series)
La série de Taylor pour le journal n'est pas aussi beau...
ln
sera dans la gamme [0.94, 0.98]. je suppose que la série de taylor est assez bon pour l'approximation deln
trop.Je suis en retard pour la fête ici. Juste être conscient que la gamme que vous avez spécifié est dans le "pas gentil" partie de la série de Taylor pour le logarithme népérien: en.wikipedia.org/wiki/Natural_logarithm#Series
OriginalL'auteur dsharlet
À l'aide de la série de Taylor n'est pas le plus simple ni le plus rapide moyen de le faire. La plupart des professionnels implémentations sont à l'aide de l'approximation des polynômes. Je vais vous montrer comment générer un dans L'érable (c'est un programme de calcul formel), à l'aide de la L'algorithme de Remez.
Pour les 3 chiffres de précision exécuter les commandes suivantes dans l'Érable:
Sa réponse est le polynôme suivant:
Avec le maximum d'erreur: 0.000061011436
Nous avons généré un polynôme qui se rapproche de la ln(x), mais seulement à l'intérieur de l' [1..2] de l'intervalle. Une augmentation de l'intervalle n'est pas sage, car ce qui permettrait d'augmenter la durée maximale d'erreur encore plus. Au lieu de cela, procédez de la manière suivante décomposition:
Donc d'abord trouver la plus haute puissance de 2, ce qui est encore plus petit que le nombre (Voir: Quelle est la manière la plus rapide/la plus efficace de trouver le plus de bits (msb) en un entier en C?). Ce nombre est en fait le logarithme en base 2. Diviser avec cette valeur, alors la suite est dans le 1..2 intervalle. À la fin nous aurons à ajouter n*ln(2) pour obtenir le résultat final.
Un exemple de mise en œuvre pour le nombre >= 1:
Bien que si vous prévoyez de l'utiliser uniquement dans le [1.0, 2.0] intervalle, alors la fonction est comme:
Je dirais ]0; 1] avec un autre polynôme, et l'utilisation d'un if/else pour décider de les utiliser. C'est que polynomyal (pour cette faible précision):
-8.6731532+(129.946172+(-558.971892+(843.967330-409.109529*x)*x)*x)*x
En fait, vous pouvez trouver pourquoi ce n'est pas sélectionné en tant que droit de réponse. + avec quelques recherches, on peut trouver de prêts à aller de mise en œuvre dans les mathématiques soleil de mise en œuvre de bibliothèque (msol).
OriginalL'auteur Crouching Kitten
Serait de la table de base avec une interpolation entre les valeurs de l'approche de travail? Si les plages de valeurs limitée (ce qui est probable pour votre cas je doute que les relevés de température ont vaste gamme) et de haute précision n'est pas nécessaire, il peut travailler. Doit être facile à tester sur machine normale.
Ici est l'un des nombreux sujets sur la table de la représentation de fonctions: Le calcul de vs les tables de recherche pour le sinus de la valeur de la performance?
Il peut être une option pour essayer (peut également ne pas fonctionner pour votre besoin de précision) - exp/ln fonctions sont continues, de sorte que vous mai besoin de beaucoup moins de points pour la précision du résultat. Je ne vois pas directement la température utilisée comme argument d'exp/ln dans la formule, les plages pour les arguments sont différents, il est difficile de prédire si clairsemée table de travail.
OriginalL'auteur Alexei Levenkov
Si vous n'avez pas besoin de mathématiques à virgule flottante pour quoi que ce soit d'autre, vous pouvez calculer une approximation de fractions de base-2 log assez facilement. Commencez par changer votre valeur vers la gauche jusqu'à 32768 ou plus et de stocker le nombre de fois que vous l'avez fait dans
count
. Ensuite, répéter un certain nombre de fois (en fonction de votre choix le facteur d'échelle):Si la boucle est répétée 8 fois, puis le logarithme de base 2 du nombre sera count/256. Si une dizaine de fois, le comte/1024. Si onze, le comte/2048. Effectivement, cette fonction fonctionne en calculant la puissance entière de deux logarithme de n**(2^répétitions), mais avec des valeurs intermédiaires mis à l'échelle pour éviter le débordement.
N'cet algorithme ont un nom?
Je ne sais pas de nom pour elle. J'ai trouvé ça quand j'ai besoin de mesurer la constante de temps RC du circuit donné deux ADC lectures connu de l'intervalle de temps (calculer le journal de chaque lecture, et de prendre de prendre de l'échelle des réciproque de la différence), mais je serais choqué si j'ai été le premier à utiliser cette approche. Pour voir ce que l'algorithme est en train de faire, il peut être utile d'examiner ce qui se passerait si elle est utilisée en précision arbitraire entiers et au lieu de transférer les n droit de 16 bits à chaque fois, il a déplacé la 32768 gauche en 16 bits.
Le but de la fonction est alors de trouver la valeur de
count
tels que sin0
est la valeur de départ den
,n0**rounds * 2**count
serait dans la gamme2**(16*rounds-1) and
2**(16*tours)-1`.Dans le cas où vous n'êtes pas au courant de la raison de ce regain d'intérêt pour cette réponse: space.stackexchange.com/questions/30952/...
OriginalL'auteur supercat
En plus Accroupi Chaton de la réponse qui m'a donné l'inspiration, vous pouvez construire une pseudo-récursive (au plus 1 auto-appel) logarithme d'éviter d'utiliser des polynômes. En pseudo-code
C'est assez efficace et précis, puisqu'sur [1; 2) le développement en série de taylor converge BEAUCOUP plus vite, et nous obtenons un nombre de 1 <= < 2 avec le premier appel à ln si notre avis est positif, mais pas dans cette gamme.
Vous pouvez trouver 'b' pour votre impartiale exposant à partir de données contenues dans le float x, et 'a' à partir de la mantisse du float x (a est exactement la même float x, mais maintenant, avec l'exposant biased_0 plutôt que de l'exposant biased_b). LN2 devrait être conservé comme une macro en hexadécimal à virgule flottante de la notation de l'OMI. Vous pouvez également utiliser http://man7.org/linux/man-pages/man3/frexp.3.html pour cela.
Aussi, le truc
pour "mémoire-casting" double non signé long, plutôt que de "valeur-casting", est très utile de savoir lorsque vous traitez avec des chars de la mémoire-sage, que les opérateurs au niveau du bit va provoquer des avertissements ou des erreurs selon le compilateur.
- 1
au développement de Taylor? Le problème que je vois est que la mantisse est un nombre entier, et non pas dans le[1; 2)
gamme, et lefrexp
effectivement fait quelques calculs pour normaliser la valeur.C'est une version simplifiée de mon code, j'ai quelques optimisations à portée de main. - y = x - 1 <=> ln(1 + y) = ln(x) est utilisée pour appeler taylor_expansion que ln(1 + y) = ln(x) = taylor(y) = y - y^2/2 + y^3/3... C'est juste une facilité de mise en œuvre, mais il est vrai qu'il pourrait être un peu déroutant au premier abord.
- J'ai aussi un else if (1.9 <= x < 2) le retour de ln(x * 2 / 3) + ln (3/2); l'article pour prévenir les chiffres très proches de leur plafond de la prise de fonction de temps (essayez de l'algorithme avec une valeur comme 1e+23 (qui est plus proche de 9.9999999999999 e+22), vous verrez sans cette petite correction de quelques cas sont apocalyptically lent. Notez que j'ai garder 2/3 et ln(3/2) que macro hexadécimal à virgule flottante constantes.) Gotta get qui journal de converger ! x)
- comme pour frexp, je vais à la maison: =>
u64 extract = *(u64*)(&d)
; =>norm = (extract & (0x8000000000000000 | 0xFFFFFFFFFFFFF)) | 0x3FF0000000000000;
etd = *(double*)(&norm);
pour mon fraction normalisée (exp == 0) =>exp = ((extract << 1) >> 53) - 1023
pour mon exposant. Vous pouvez vérifier pour d'autres valeurs particulières en tant que bien lors du démarrage de votre journal (c +inf retours +inf, 1. retourne 0., etc.). Notez que => servir pour signifier un \n dans mon commentaire de texte en clair ici xdOriginalL'auteur Tristan Duquesne