it-swarm-es.tech

¿Cuál es la mejor manera de hacer matemáticas de punto fijo?

Necesito acelerar un programa para Nintendo DS que no tiene una FPU, así que necesito cambiar las matemáticas de punto flotante (que son emuladas y lentas) a punto fijo.

La forma en que comencé fue cambiar los flotadores a int y cada vez que necesitaba convertirlos, usaba x >> 8 para convertir la variable de punto fijo x al número real y x << 8 para convertir a punto fijo. Pronto descubrí que era imposible hacer un seguimiento de lo que era necesario convertir 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 debo hacer esto más fácil y rápido? ¿Debo hacer una clase FixedPoint, o simplemente un FixedPoint8 typedef o struct con algunas funciones/macros para convertirlos, o algo más? ¿Debo poner algo en el nombre de la variable para mostrar que es de punto fijo?

45
Jeremy Ruten

Puede probar mi clase de punto fijo (Último disponible @ https://github.com/eteran/cpp-utilities )

// From: https://github.com/eteran/cpp-utilities/edit/master/Fixed.h
// See also: http://stackoverflow.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 un reemplazo cercano a la caída 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 para esto es solo una dependencia de encabezado, no una dependencia de 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.

47
Evan Teran

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

Por lo tanto, debe escribir una clase FixedPoint8 . Probar y depurar a fondo. Si tiene que convencerse de su rendimiento en comparación con el uso de enteros simples, mídalo.

Le ahorrará muchos problemas al mover la complejidad del cálculo de 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 la antigua 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 algún lugar de Internet: comenzaría a buscar en las bibliotecas Boost .

31
Antti Kissaniemi

¿Su código de coma flotante realmente utiliza el punto decimal? Si es así:

Primero debe leer el artículo de Randy Yates sobre Introducción a Matemáticas de punto fijo: http://www.digitalsignallabs.com/fp.pdf

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

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 frente a punto fijo.

9
ryu

El cambio de representaciones de punto fijo se denomina comúnmente "escala".

Si puede 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 alinea. Si hay una penalización de rendimiento usando clases, entonces necesita un enfoque más tradicional de estilo C. El enfoque OOP) le dará seguridad de tipo forzada por el compilador que la implementación tradicional solo se aproxima.

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

Para realizar un seguimiento de las variables que se escalan, debe usar una convención consistente. Haga una notación al final de cada nombre de variable para indicar si el valor está escalado o no, y escriba 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 un trabajo extra usar tanta notación, pero observe cómo puede decir 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 Apps húngaro que Joel menciona en esta publicación .

6
Bart

No usaría coma flotante en una CPU sin un 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 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 entera seguida de una reducción de escala como (0.72 * 2 se convierte en 72 * 200 se convierte en 14400 se convierte en 144 (scaleback) se convierte en 1.44).

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

Saludos, Pax.

6
paxdiablo

Cuando encontré por primera vez números de punto fijo, encontré el artículo de Joe Lemieux, Matemáticas de punto fijo en C , muy útil, y sugiere una forma de representar valores de punto fijo.

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

Por ejemplo, con valores de 24.8:

 #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;
}

Que 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 hice esto en C. En C++ podría hacer algo mucho más limpio utilizando la sobrecarga del operador. En realidad, también podrías hacer que ese código C sea mucho más bonito ...

Supongo que esta es una forma larga de decir: creo que está bien usar un enfoque typedef y macro. Mientras 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 todos los flotadores con matemática de punto fijo, entonces probablemente estarás mejor con una clase.

5
ryan_s

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

4
Ana Betts

De cualquier manera que decida ir (me inclinaría hacia un typedef y algunas macros CPP para la conversión), deberá tener cuidado de convertir de un lado a otro con cierta disciplina.

Es posible que nunca necesite convertir de un lado a otro. Solo imagine que todo en todo el sistema es x256.

1
jfm3
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...
};
1
cibyr