Pow, log, exp et sqrt à point fixe rapide

ci-Dessous est un exemple C mise en œuvre de l'Argile S. Turner point fixe logarithme de base 2 de l'algorithme de[1]. L'algorithme ne nécessite aucune sorte de table de recherche. Cela peut être utile sur les systèmes où les contraintes de mémoire sont étroites et où le processeur n'a pas de FPU, comme c'est le cas avec de nombreux microcontrôleurs. Journal de la base e et log base 10 sont alors également supportés en utilisant la propriété logarithmes qui, pour n'importe quelle base n:

          log (x)
             y
log (x) = _______
   n      log (n)
             y

où, pour cet algorithme, o égale 2.

une caractéristique intéressante de cette implémentation est qu'elle prend en charge la précision variable: la précision peut être déterminée à l'exécution, au détriment de la portée. De la façon dont je l'ai implémenté, le processeur (ou compilateur) doit être capable de faire des maths 64 bits pour contenir des résultats intermédiaires. Il peut être facilement adapté pour ne pas nécessiter de soutien 64 bits, mais la gamme sera réduire.

en utilisant ces fonctions, soit une valeur à point fixe spécifié precision. Par exemple, si precision est de 16, alors x doit être gradué de 2^16 (65536). Le résultat est une valeur à point fixe avec le même facteur d'échelle que l'entrée. Une valeur de retour INT32_MIN représente l'infini négatif. Une valeur de retour INT32_MAX indique une erreur et errno sera réglé à EINVAL, indiquant que la précision d'entrée était invalide.

#include <errno.h>
#include <stddef.h>

#include "log2fix.h"

#define INV_LOG2_E_Q1DOT31  UINT64_C(0x58b90bfc) // Inverse log base 2 of e
#define INV_LOG2_10_Q1DOT31 UINT64_C(0x268826a1) // Inverse log base 2 of 10

int32_t log2fix (uint32_t x, size_t precision)
{
    int32_t b = 1U << (precision - 1);
    int32_t y = 0;

    if (precision < 1 || precision > 31) {
        errno = EINVAL;
        return INT32_MAX; // indicates an error
    }

    if (x == 0) {
        return INT32_MIN; // represents negative infinity
    }

    while (x < 1U << precision) {
        x <<= 1;
        y -= 1U << precision;
    }

    while (x >= 2U << precision) {
        x >>= 1;
        y += 1U << precision;
    }

    uint64_t z = x;

    for (size_t i = 0; i < precision; i++) {
        z = z * z >> precision;
        if (z >= 2U << precision) {
            z >>= 1;
            y += b;
        }
        b >>= 1;
    }

    return y;
}

int32_t logfix (uint32_t x, size_t precision)
{
    uint64_t t;

    t = log2fix(x, precision) * INV_LOG2_E_Q1DOT31;

    return t >> 31;
}

int32_t log10fix (uint32_t x, size_t precision)
{
    uint64_t t;

    t = log2fix(x, precision) * INV_LOG2_10_Q1DOT31;

    return t >> 31;
}

Le code de cette application a également la vie à Github, ainsi qu'un exemple/programme de test qui illustre comment utiliser cette fonction pour calculer et afficher les logarithmes à partir des nombres lus à partir de l'entrée standard.

[1] C.S. Turner, "A Fast Binaire Logarithm Algorithm", IEEE Signal Processing Mag., pp. 124,140, Sep. 2010.

Un bon point de départ est Le Livre de Jack Crenshaw,"Mathématiques boîte à outils pour la Programmation en Temps Réel". Il a une bonne discussion des algorithmes et implémentations pour diverses fonctions transcendantes.

Vérifier mon point fixe sqrt mise en œuvre en utilisant uniquement les opérations sur entiers. C'était amusant d'inventer. Assez vieux maintenant.

https://groups.google.com/forum/?hl=fr%05aacf5997b615c37&fromgroups#!topic/comp.lang.c/IpwKbw0MAxw/discussion

sinon cochez la case CORDIC ensemble d'algorithmes. C'est la façon d'implémenter toutes les fonctions que vous avez énumérées et les fonctions trigonométriques.

EDIT : je publié la source revue sur GitHub ici