c++ - paso - ¿Cuál es la mejor manera de hacer matemáticas de punto fijo?

punto fijo matematicas

Question

Necesito acelerar un programa para Nintendo DS que no tiene una FPU, así que tengo que cambiar la matemática de coma flotante (que es emulada y lenta) a punto fijo.

La forma en que comencé fue cambiando los flotantes a los enteros y cada vez que necesitaba convertirlos, usaba x >> 8 para convertir la variable de punto fijo x en el número real yx << 8 para convertir a punto fijo. Pronto descubrí que era imposible hacer un seguimiento de lo que debía convertirse y también me di cuenta de que sería difícil cambiar la precisión de los números (8 en este caso).

Mi pregunta es, ¿cómo debería hacer esto más fácil y aún más rápido? ¿Debería hacer una clase FixedPoint, o solo una definición o tipo de FixedPoint8 con algunas funciones / macros para convertirlas, o alguna otra cosa? ¿Debería poner algo en el nombre de la variable para mostrar que es un punto fijo?

Answer 1

¿Su código de coma flotante realmente hace uso del punto decimal? Si es así:

En primer lugar, debe leer el artículo de Randy Yates sobre Intro to Fixed Point Math: http://www.digitalsignallabs.com/fp.pdf

Luego necesita hacer un "perfil" en su código de coma flotante para calcular el rango apropiado de valores de punto fijo requeridos en puntos "críticos" en su código, por ejemplo U (5,3) = 5 bits a la izquierda, 3 bits a la derecha, sin firmar.

En este punto, puede aplicar las reglas aritméticas en el documento mencionado anteriormente; las reglas especifican cómo interpretar los bits que resultan de las operaciones aritméticas. Puede escribir macros o funciones para realizar las operaciones.

Es útil mantener la versión de punto flotante para comparar los resultados de punto flotante vs punto fijo.

Answer 2

Cualquiera que sea la forma en que decida ir (me inclinaría hacia un typedef y algunas macros de CPP para la conversión), deberá tener cuidado de convertir hacia adelante y hacia atrás con cierta disciplina.

Puede encontrar que nunca necesita convertir de ida y vuelta. Solo imagine que todo en el sistema completo es x256.

Answer 3

Cuando me encontré por primera vez con los números de punto fijo encontré el artículo de Joe Lemieux, Fixed-point Math in C , muy útil, y sugiere una forma de representar los valores de punto fijo.

Sin embargo, no terminé usando su representación sindical para números de punto fijo. En su mayoría tengo experiencia con el punto fijo en C, por lo que tampoco he tenido la opción de usar una clase. En su mayor parte, creo que la definición del número de bits de fracción en una macro y el uso de nombres de variables descriptivos hace que sea bastante fácil trabajar con ella. Además, he descubierto que es mejor tener macros o funciones para la multiplicación y especialmente la división, o rápidamente se obtiene un código ilegible.

Por ejemplo, con 24.8 valores:

 #include "stdio.h"

/* Declarations for fixed point stuff */

typedef int int_fixed;

#define FRACT_BITS 8
#define FIXED_POINT_ONE (1 << FRACT_BITS)
#define MAKE_INT_FIXED(x) ((x) << FRACT_BITS)
#define MAKE_FLOAT_FIXED(x) ((int_fixed)((x) * FIXED_POINT_ONE))
#define MAKE_FIXED_INT(x) ((x) >> FRACT_BITS)
#define MAKE_FIXED_FLOAT(x) (((float)(x)) / FIXED_POINT_ONE)

#define FIXED_MULT(x, y) ((x)*(y) >> FRACT_BITS)
#define FIXED_DIV(x, y) (((x)<<FRACT_BITS) / (y))

/* tests */
int main()
{
    int_fixed fixed_x = MAKE_FLOAT_FIXED( 4.5f );
    int_fixed fixed_y = MAKE_INT_FIXED( 2 );

    int_fixed fixed_result = FIXED_MULT( fixed_x, fixed_y );
    printf( "%.1f/n", MAKE_FIXED_FLOAT( fixed_result ) );

    fixed_result = FIXED_DIV( fixed_result, fixed_y );
    printf( "%.1f/n", MAKE_FIXED_FLOAT( fixed_result ) );

    return 0;
}

Lo cual escribe

9.0 4.5

Tenga en cuenta que hay todo tipo de problemas de desbordamiento de enteros con esas macros, solo quería mantener las macros simples. Este es solo un ejemplo rápido y sucio de cómo he hecho esto en C. En C ++ podrías hacer algo mucho más limpio usando la sobrecarga del operador. En realidad, fácilmente podrías hacer ese código C mucho más bonito también ...

Supongo que esta es una forma larga de decir: creo que está bien usar un enfoque typedef y macro. Siempre que tenga claro qué variables contienen valores de punto fijo, no es demasiado difícil de mantener, pero probablemente no será tan bonito como una clase de C ++.

Si estuviera en su posición, trataría de obtener algunos números de perfil para mostrar dónde están los cuellos de botella. Si hay relativamente pocos, vaya con typedef y macros. Sin embargo, si decides que necesitas un reemplazo global de todas las carrozas con matemáticas de punto fijo, entonces probablemente estarás mejor con una clase.

Answer 4

El cambio de representaciones de puntos fijos se denomina comúnmente ''escalado''.

Si puedes hacer esto con una clase sin penalización de rendimiento, entonces ese es el camino a seguir. Depende en gran medida del compilador y de cómo se inserta. Si hay una penalización de rendimiento usando clases, entonces necesitas un enfoque más tradicional de estilo C. El enfoque de OOP le proporcionará seguridad de tipo implementada por el compilador que la implementación tradicional solo se aproxima.

@cibyr tiene una buena implementación de OOP. Ahora para el más tradicional.

Para mantener un registro de las variables escaladas, debe usar una convención consistente. Haga una anotación al final de cada nombre de variable para indicar si el valor está escalado o no, y escriba las macros SCALE () y UNSCALE () que se expanden a x >> 8 yx << 8.

#define SCALE(x) (x>>8)
#define UNSCALE(x) (x<<8)

xPositionUnscaled = UNSCALE(10);
xPositionScaled = SCALE(xPositionUnscaled);

Puede parecer mucho trabajo utilizar tanta notación, pero observe cómo puede ver de un vistazo que cualquier línea es correcta sin mirar otras líneas. Por ejemplo:

xPositionScaled = SCALE(xPositionScaled);

obviamente está mal, por inspección.

Esta es una variación de la idea húngara de Apps que Joel menciona en esta publicación .

Answer 5

En las implementaciones modernas de C ++, no habrá penalización de rendimiento por usar abstracciones simples y magras, como clases concretas. El cálculo de punto fijo es precisamente el lugar donde usar una clase diseñada adecuadamente lo salvará de muchos errores.

Por lo tanto, debe escribir una clase FixedPoint8 . Pruébalo y depúralo a fondo. Si tiene que convencerse de su rendimiento en comparación con el uso de enteros simples, mida.

Le ahorrará muchos problemas al mover la complejidad del cálculo del punto fijo a un solo lugar.

Si lo desea, puede aumentar aún más la utilidad de su clase convirtiéndola en una plantilla y reemplazando el antiguo FixedPoint8 con, digamos, typedef FixedPoint<short, 8> FixedPoint8; Pero en su arquitectura de destino esto probablemente no sea necesario, así que evite la complejidad de las plantillas al principio.

Probablemente haya una buena clase de punto fijo en Internet, comenzaría a buscar en las bibliotecas de Boost .

Answer 6

La versión original de Tricks of the Game Programming Gurus tiene un capítulo completo sobre la implementación de matemática de punto fijo.

Answer 7

No usaría ningún punto flotante en una CPU sin hardware especial para manejarlo. Mi consejo es tratar TODOS los números como enteros escalados a un factor específico. Por ejemplo, todos los valores monetarios están en centavos como enteros en lugar de dólares como flotantes. Por ejemplo, 0.72 se representa como el entero 72.

La suma y la resta son entonces una operación entera muy simple tal como (0.72 + 1 se convierte en 72 + 100 se convierte en 172 se convierte en 1.72).

La multiplicación es un poco más compleja ya que necesita una multiplicación de números enteros seguida de una reducción de escala como (0.72 * 2 se convierte en 72 * 200 se convierte en 14400 se convierte en 144 (regresión escalar) se convierte en 1.44).

Eso puede requerir funciones especiales para realizar operaciones matemáticas más complejas (seno, coseno, etc.), pero incluso esas pueden acelerarse mediante el uso de tablas de búsqueda. Ejemplo: ya que está utilizando la representación fija-2, solo hay 100 valores en el rango (0.0,1) (0-99) y sin / cos repetición fuera de este rango, por lo que solo necesita una tabla de búsqueda de 100 enteros.

Saludos, Pax.

Answer 8

Puedes probar mi clase de punto fijo (Latest available @ https://github.com/eteran/cpp-utilities )

// From: https://github.com/eteran/cpp-utilities/edit/master/Fixed.h
// See also: http://.com/questions/79677/whats-the-best-way-to-do-fixed-point-math
/*
 * The MIT License (MIT)
 * 
 * Copyright (c) 2015 Evan Teran
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#ifndef FIXED_H_
#define FIXED_H_

#include <ostream>
#include <exception>
#include <cstddef> // for size_t
#include <cstdint>
#include <type_traits>

#include <boost/operators.hpp>

namespace numeric {

template <size_t I, size_t F>
class Fixed;

namespace detail {

// helper templates to make magic with types :)
// these allow us to determine resonable types from
// a desired size, they also let us infer the next largest type
// from a type which is nice for the division op
template <size_t T>
struct type_from_size {
    static const bool is_specialized = false;
    typedef void      value_type;
};

#if defined(__GNUC__) && defined(__x86_64__)
template <>
struct type_from_size<128> {
    static const bool           is_specialized = true;
    static const size_t         size = 128;
    typedef __int128            value_type;
    typedef unsigned __int128   unsigned_type;
    typedef __int128            signed_type;
    typedef type_from_size<256> next_size;
};
#endif

template <>
struct type_from_size<64> {
    static const bool           is_specialized = true;
    static const size_t         size = 64;
    typedef int64_t             value_type;
    typedef uint64_t            unsigned_type;
    typedef int64_t             signed_type;
    typedef type_from_size<128> next_size;
};

template <>
struct type_from_size<32> {
    static const bool          is_specialized = true;
    static const size_t        size = 32;
    typedef int32_t            value_type;
    typedef uint32_t           unsigned_type;
    typedef int32_t            signed_type;
    typedef type_from_size<64> next_size;
};

template <>
struct type_from_size<16> {
    static const bool          is_specialized = true;
    static const size_t        size = 16;
    typedef int16_t            value_type;
    typedef uint16_t           unsigned_type;
    typedef int16_t            signed_type;
    typedef type_from_size<32> next_size;
};

template <>
struct type_from_size<8> {
    static const bool          is_specialized = true;
    static const size_t        size = 8;
    typedef int8_t             value_type;
    typedef uint8_t            unsigned_type;
    typedef int8_t             signed_type;
    typedef type_from_size<16> next_size;
};

// this is to assist in adding support for non-native base
// types (for adding big-int support), this should be fine
// unless your bit-int class doesn''t nicely support casting
template <class B, class N>
B next_to_base(const N& rhs) {
    return static_cast<B>(rhs);
}

struct divide_by_zero : std::exception {
};

template <size_t I, size_t F>
Fixed<I,F> divide(const Fixed<I,F> &numerator, const Fixed<I,F> &denominator, Fixed<I,F> &remainder, typename std::enable_if<type_from_size<I+F>::next_size::is_specialized>::type* = 0) {

    typedef typename Fixed<I,F>::next_type next_type;
    typedef typename Fixed<I,F>::base_type base_type;
    static const size_t fractional_bits = Fixed<I,F>::fractional_bits;

    next_type t(numerator.to_raw());
    t <<= fractional_bits;

    Fixed<I,F> quotient;

    quotient  = Fixed<I,F>::from_base(next_to_base<base_type>(t / denominator.to_raw()));
    remainder = Fixed<I,F>::from_base(next_to_base<base_type>(t % denominator.to_raw()));

    return quotient;
}

template <size_t I, size_t F>
Fixed<I,F> divide(Fixed<I,F> numerator, Fixed<I,F> denominator, Fixed<I,F> &remainder, typename std::enable_if<!type_from_size<I+F>::next_size::is_specialized>::type* = 0) {

    // NOTE(eteran): division is broken for large types :-(
    // especially when dealing with negative quantities

    typedef typename Fixed<I,F>::base_type     base_type;
    typedef typename Fixed<I,F>::unsigned_type unsigned_type;

    static const int bits = Fixed<I,F>::total_bits;

    if(denominator == 0) {
        throw divide_by_zero();
    } else {

        int sign = 0;

        Fixed<I,F> quotient;

        if(numerator < 0) {
            sign ^= 1;
            numerator = -numerator;
        }

        if(denominator < 0) {
            sign ^= 1;
            denominator = -denominator;
        }

            base_type n      = numerator.to_raw();
            base_type d      = denominator.to_raw();
            base_type x      = 1;
            base_type answer = 0;

            // egyptian division algorithm
            while((n >= d) && (((d >> (bits - 1)) & 1) == 0)) {
                x <<= 1;
                d <<= 1;
            }

            while(x != 0) {
                if(n >= d) {
                    n      -= d;
                    answer += x;
                }

                x >>= 1;
                d >>= 1;
            }

            unsigned_type l1 = n;
            unsigned_type l2 = denominator.to_raw();

            // calculate the lower bits (needs to be unsigned)
            // unfortunately for many fractions this overflows the type still :-/
            const unsigned_type lo = (static_cast<unsigned_type>(n) << F) / denominator.to_raw();

            quotient  = Fixed<I,F>::from_base((answer << F) | lo);
            remainder = n;

        if(sign) {
            quotient = -quotient;
        }

        return quotient;
    }
}

// this is the usual implementation of multiplication
template <size_t I, size_t F>
void multiply(const Fixed<I,F> &lhs, const Fixed<I,F> &rhs, Fixed<I,F> &result, typename std::enable_if<type_from_size<I+F>::next_size::is_specialized>::type* = 0) {

    typedef typename Fixed<I,F>::next_type next_type;
    typedef typename Fixed<I,F>::base_type base_type;

    static const size_t fractional_bits = Fixed<I,F>::fractional_bits;

    next_type t(static_cast<next_type>(lhs.to_raw()) * static_cast<next_type>(rhs.to_raw()));
    t >>= fractional_bits;
    result = Fixed<I,F>::from_base(next_to_base<base_type>(t));
}

// this is the fall back version we use when we don''t have a next size
// it is slightly slower, but is more robust since it doesn''t
// require and upgraded type
template <size_t I, size_t F>
void multiply(const Fixed<I,F> &lhs, const Fixed<I,F> &rhs, Fixed<I,F> &result, typename std::enable_if<!type_from_size<I+F>::next_size::is_specialized>::type* = 0) {

    typedef typename Fixed<I,F>::base_type base_type;

    static const size_t fractional_bits = Fixed<I,F>::fractional_bits;
    static const size_t integer_mask    = Fixed<I,F>::integer_mask;
    static const size_t fractional_mask = Fixed<I,F>::fractional_mask;

    // more costly but doesn''t need a larger type
    const base_type a_hi = (lhs.to_raw() & integer_mask) >> fractional_bits;
    const base_type b_hi = (rhs.to_raw() & integer_mask) >> fractional_bits;
    const base_type a_lo = (lhs.to_raw() & fractional_mask);
    const base_type b_lo = (rhs.to_raw() & fractional_mask);

    const base_type x1 = a_hi * b_hi;
    const base_type x2 = a_hi * b_lo;
    const base_type x3 = a_lo * b_hi;
    const base_type x4 = a_lo * b_lo;

    result = Fixed<I,F>::from_base((x1 << fractional_bits) + (x3 + x2) + (x4 >> fractional_bits));

}
}

/*
 * inheriting from boost::operators enables us to be a drop in replacement for base types
 * without having to specify all the different versions of operators manually
 */
template <size_t I, size_t F>
class Fixed : boost::operators<Fixed<I,F>> {
    static_assert(detail::type_from_size<I + F>::is_specialized, "invalid combination of sizes");

public:
    static const size_t fractional_bits = F;
    static const size_t integer_bits    = I;
    static const size_t total_bits      = I + F;

    typedef detail::type_from_size<total_bits>             base_type_info;

    typedef typename base_type_info::value_type            base_type;
    typedef typename base_type_info::next_size::value_type next_type;
    typedef typename base_type_info::unsigned_type         unsigned_type;

public:
    static const size_t base_size          = base_type_info::size;
    static const base_type fractional_mask = ~((~base_type(0)) << fractional_bits);
    static const base_type integer_mask    = ~fractional_mask;

public:
    static const base_type one = base_type(1) << fractional_bits;

public: // constructors
    Fixed() : data_(0) {
    }

    Fixed(long n) : data_(base_type(n) << fractional_bits) {
        // TODO(eteran): assert in range!
    }

    Fixed(unsigned long n) : data_(base_type(n) << fractional_bits) {
        // TODO(eteran): assert in range!
    }

    Fixed(int n) : data_(base_type(n) << fractional_bits) {
        // TODO(eteran): assert in range!
    }

    Fixed(unsigned int n) : data_(base_type(n) << fractional_bits) {
        // TODO(eteran): assert in range!
    }

    Fixed(float n) : data_(static_cast<base_type>(n * one)) {
        // TODO(eteran): assert in range!
    }

    Fixed(double n) : data_(static_cast<base_type>(n * one))  {
        // TODO(eteran): assert in range!
    }

    Fixed(const Fixed &o) : data_(o.data_) {
    }

    Fixed& operator=(const Fixed &o) {
        data_ = o.data_;
        return *this;
    }

private:
    // this makes it simpler to create a fixed point object from
    // a native type without scaling
    // use "Fixed::from_base" in order to perform this.
    struct NoScale {};

    Fixed(base_type n, const NoScale &) : data_(n) {
    }

public:
    static Fixed from_base(base_type n) {
        return Fixed(n, NoScale());
    }

public: // comparison operators
    bool operator==(const Fixed &o) const {
        return data_ == o.data_;
    }

    bool operator<(const Fixed &o) const {
        return data_ < o.data_;
    }

public: // unary operators
    bool operator!() const {
        return !data_;
    }

    Fixed operator~() const {
        Fixed t(*this);
        t.data_ = ~t.data_;
        return t;
    }

    Fixed operator-() const {
        Fixed t(*this);
        t.data_ = -t.data_;
        return t;
    }

    Fixed operator+() const {
        return *this;
    }

    Fixed& operator++() {
        data_ += one;
        return *this;
    }

    Fixed& operator--() {
        data_ -= one;
        return *this;
    }

public: // basic math operators
    Fixed& operator+=(const Fixed &n) {
        data_ += n.data_;
        return *this;
    }

    Fixed& operator-=(const Fixed &n) {
        data_ -= n.data_;
        return *this;
    }

    Fixed& operator&=(const Fixed &n) {
        data_ &= n.data_;
        return *this;
    }

    Fixed& operator|=(const Fixed &n) {
        data_ |= n.data_;
        return *this;
    }

    Fixed& operator^=(const Fixed &n) {
        data_ ^= n.data_;
        return *this;
    }

    Fixed& operator*=(const Fixed &n) {
        detail::multiply(*this, n, *this);
        return *this;
    }

    Fixed& operator/=(const Fixed &n) {
        Fixed temp;
        *this = detail::divide(*this, n, temp);
        return *this;
    }

    Fixed& operator>>=(const Fixed &n) {
        data_ >>= n.to_int();
        return *this;
    }

    Fixed& operator<<=(const Fixed &n) {
        data_ <<= n.to_int();
        return *this;
    }

public: // conversion to basic types
    int to_int() const {
        return (data_ & integer_mask) >> fractional_bits;
    }

    unsigned int to_uint() const {
        return (data_ & integer_mask) >> fractional_bits;
    }

    float to_float() const {
        return static_cast<float>(data_) / Fixed::one;
    }

    double to_double() const        {
        return static_cast<double>(data_) / Fixed::one;
    }

    base_type to_raw() const {
        return data_;
    }

public:
    void swap(Fixed &rhs) {
        using std::swap;
        swap(data_, rhs.data_);
    }

public:
    base_type data_;
};

// if we have the same fractional portion, but differing integer portions, we trivially upgrade the smaller type
template <size_t I1, size_t I2, size_t F>
typename std::conditional<I1 >= I2, Fixed<I1,F>, Fixed<I2,F>>::type operator+(const Fixed<I1,F> &lhs, const Fixed<I2,F> &rhs) {

    typedef typename std::conditional<
        I1 >= I2,
        Fixed<I1,F>,
        Fixed<I2,F>
    >::type T;

    const T l = T::from_base(lhs.to_raw());
    const T r = T::from_base(rhs.to_raw());
    return l + r;
}

template <size_t I1, size_t I2, size_t F>
typename std::conditional<I1 >= I2, Fixed<I1,F>, Fixed<I2,F>>::type operator-(const Fixed<I1,F> &lhs, const Fixed<I2,F> &rhs) {

    typedef typename std::conditional<
        I1 >= I2,
        Fixed<I1,F>,
        Fixed<I2,F>
    >::type T;

    const T l = T::from_base(lhs.to_raw());
    const T r = T::from_base(rhs.to_raw());
    return l - r;
}

template <size_t I1, size_t I2, size_t F>
typename std::conditional<I1 >= I2, Fixed<I1,F>, Fixed<I2,F>>::type operator*(const Fixed<I1,F> &lhs, const Fixed<I2,F> &rhs) {

    typedef typename std::conditional<
        I1 >= I2,
        Fixed<I1,F>,
        Fixed<I2,F>
    >::type T;

    const T l = T::from_base(lhs.to_raw());
    const T r = T::from_base(rhs.to_raw());
    return l * r;
}

template <size_t I1, size_t I2, size_t F>
typename std::conditional<I1 >= I2, Fixed<I1,F>, Fixed<I2,F>>::type operator/(const Fixed<I1,F> &lhs, const Fixed<I2,F> &rhs) {

    typedef typename std::conditional<
        I1 >= I2,
        Fixed<I1,F>,
        Fixed<I2,F>
    >::type T;

    const T l = T::from_base(lhs.to_raw());
    const T r = T::from_base(rhs.to_raw());
    return l / r;
}

template <size_t I, size_t F>
std::ostream &operator<<(std::ostream &os, const Fixed<I,F> &f) {
    os << f.to_double();
    return os;
}

template <size_t I, size_t F>
const size_t Fixed<I,F>::fractional_bits;

template <size_t I, size_t F>
const size_t Fixed<I,F>::integer_bits;

template <size_t I, size_t F>
const size_t Fixed<I,F>::total_bits;

}

#endif

Está diseñado para ser casi un reemplazo en reemplazo de flotadores / dobles y tiene una precisión elegible. Hace uso de boost para agregar todas las sobrecargas necesarias del operador matemático, por lo que también necesitará eso (creo que es solo una dependencia del encabezado, no una dependencia de la biblioteca).

Por cierto, el uso común podría ser algo como esto:

using namespace numeric;
typedef Fixed<16, 16> fixed;
fixed f;

La única regla real es que el número debe sumar un tamaño nativo de su sistema, como 8, 16, 32, 64.

Answer 9

template <int precision = 8> class FixedPoint {
private:
    int val_;
public:
    inline FixedPoint(int val) : val_ (val << precision) {};
    inline operator int() { return val_ >> precision; }
    // Other operators...
};