it-swarm-pt.tech

Qual é a melhor maneira de fazer matemática de ponto fixo?

Preciso acelerar um programa para o Nintendo DS que não possui uma FPU), portanto, preciso alterar a matemática do ponto flutuante (que é emulada e lenta) para o ponto fixo.

Como comecei, mudei floats para ints e sempre que precisei convertê-los, usei x >> 8 para converter a variável de ponto fixo x para o número real e x << 8 para converter em ponto fixo. Logo descobri que era impossível acompanhar o que precisava ser convertido e também percebi que seria difícil alterar a precisão dos números (8 neste caso).

Minha pergunta é: como devo tornar isso mais fácil e rápido? Devo criar uma classe FixedPoint, ou apenas um typedef ou estrutura FixedPoint8 com algumas funções/macros para convertê-las ou algo mais? Devo colocar algo no nome da variável para mostrar que é ponto fixo?

45
Jeremy Ruten

Você pode experimentar minha classe de ponto fixo (Últimas disponíveis em --- 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

Ele foi projetado para ser uma gota quase em substituição aos flutuadores/duplos e tem uma precisão que pode ser escolhida. Ele usa o boost para adicionar todas as sobrecargas necessárias do operador matemático, então você precisará disso também (acredito que para isso é apenas uma dependência de cabeçalho, não uma dependência de biblioteca).

BTW, o uso comum pode ser algo como isto:

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

A única regra real é que o número precise somar um tamanho nativo do sistema, como 8, 16, 32, 64.

47
Evan Teran

Nas implementações modernas de C++, não haverá penalização de desempenho pelo uso de abstrações simples e enxutas, como classes concretas. A computação em ponto fixo é precisamente o local em que o uso de uma classe projetada corretamente o salvará de muitos bugs.

Portanto, você deve escrever uma classe FixedPoint8 . Teste e depure-o completamente. Se você precisar se convencer de seu desempenho em comparação ao uso de números inteiros simples, meça-o.

Isso evitará muitos problemas, movendo a complexidade do cálculo de ponto fixo para um único local.

Se quiser, você pode aumentar ainda mais a utilidade da sua classe, transformando-a em um modelo e substituindo a antiga FixedPoint8 com, digamos, typedef FixedPoint<short, 8> FixedPoint8; Mas, na arquitetura de destino, isso provavelmente não é necessário; portanto, evite a complexidade dos modelos primeiro.

Provavelmente existe uma boa classe de ponto fixo em algum lugar da Internet - eu começaria a procurar nas bibliotecas Boost .

31
Antti Kissaniemi

Seu código de ponto flutuante realmente usa o ponto decimal? Se então:

Primeiro, você deve ler o artigo de Randy Yates sobre Introdução à matemática de ponto fixo: http://www.digitalsignallabs.com/fp.pdf

Em seguida, é necessário criar um "perfil" no código de ponto flutuante para descobrir o intervalo apropriado de valores de ponto fixo exigido em pontos "críticos" do código, por exemplo U (5,3) = 5 bits para a esquerda, 3 bits para a direita, sem sinal.

Nesse ponto, você pode aplicar as regras aritméticas no documento mencionado acima; as regras especificam como interpretar os bits que resultam de operações aritméticas. Você pode gravar macros ou funções para executar as operações.

É útil manter a versão do ponto flutuante por perto, para comparar os resultados do ponto flutuante versus o ponto fixo.

9
ryu

Alterar representações de pontos fixos é comumente chamado de 'escala'.

Se você pode fazer isso com uma classe sem penalização de desempenho, esse é o caminho a seguir. Depende muito do compilador e de como ele é incorporado. Se houver uma penalidade de desempenho usando classes, você precisará de uma abordagem mais tradicional no estilo C. A abordagem OOP fornecerá segurança de tipo imposta pelo compilador, aproximada apenas pela implementação tradicional.

O @cibyr possui uma boa OOP implementação. Agora, a mais tradicional.

Para acompanhar quais variáveis ​​são dimensionadas, é necessário usar uma convenção consistente. Faça uma notação no final de cada nome de variável para indicar se o valor está dimensionado ou não e escreva as macros SCALE () e UNSCALE () que se expandem para x >> 8 e x << 8.

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

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

Pode parecer um trabalho extra usar tanta notação, mas observe como você pode dizer rapidamente que qualquer linha está correta sem olhar para outras linhas. Por exemplo:

xPositionScaled = SCALE(xPositionScaled);

está obviamente errado, pela inspeção.

Essa é uma variação da idéia dos aplicativos húngaros que Joel menciona neste post .

6
Bart

Eu não usaria ponto flutuante em uma CPU sem hardware especial para lidar com isso. Meu conselho é tratar TODOS os números como números inteiros dimensionados para um fator específico. Por exemplo, todos os valores monetários estão em centavos como números inteiros, em vez de dólares como valores flutuantes. Por exemplo, 0,72 é representado como o número inteiro 72.

Adição e subtração são, então, uma operação inteira muito simples, como (0,72 + 1 se torna 72 + 100 se torna 172 se torna 1,72).

A multiplicação é um pouco mais complexa, pois precisa de uma multiplicação de números inteiros seguida de uma escala regressiva, como (0,72 * 2 se transforma em 72 * 200 se torna 14400 se torna 14400 se torna 144 (escalonamento) se torna 1,44).

Isso pode exigir funções especiais para executar matemáticas mais complexas (seno, cosseno, etc), mas mesmo essas podem ser aceleradas usando tabelas de pesquisa. Exemplo: como você está usando a representação 2 fixa, há apenas 100 valores no intervalo (0,0,1] (0-99) e sin/cos se repete fora desse intervalo, portanto, você só precisa de uma tabela de pesquisa com 100 números inteiros.

Saúde, Pax.

6
paxdiablo

Quando encontrei números de pontos fixos, encontrei o artigo de Joe Lemieux, Matemática de ponto fixo em C , muito útil, e sugere uma maneira de representar valores de pontos fixos.

Eu não acabei usando a representação sindical dele para números de ponto fixo. Eu tenho principalmente experiência com ponto fixo em C, então também não tive a opção de usar uma classe. Na maioria das vezes, porém, acho que definir o número de bits de fração em uma macro e usar nomes de variáveis ​​descritivos facilita bastante o trabalho. Além disso, descobri que é melhor ter macros ou funções para multiplicação e principalmente divisão, ou você obtém rapidamente códigos ilegíveis.

Por exemplo, com 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;
}

Que escreve

 9,0 
 4,5 

Observe que existem todos os tipos de problemas de estouro inteiro com essas macros, eu só queria manter as macros simples. Este é apenas um exemplo rápido e sujo de como eu fiz isso em C. No C++, você poderia tornar algo muito mais limpo usando a sobrecarga do operador. Na verdade, você poderia facilmente tornar esse código C muito mais bonito também ...

Eu acho que essa é uma maneira cansativa de dizer: eu acho que é bom usar uma abordagem de typedef e macro. Desde que você tenha certeza sobre quais variáveis ​​contêm valores de pontos fixos, não é muito difícil manter, mas provavelmente não será tão bonito quanto uma classe C++.

Se eu estivesse na sua posição, tentaria obter alguns números de perfis para mostrar onde estão os gargalos. Se houver relativamente poucos deles, escolha um typedef e macros. Se você decidir que precisa de uma substituição global de todos os carros alegóricos com matemática de ponto fixo, provavelmente estará melhor com uma classe.

5
ryan_s

A versão original de Truques dos gurus da programação de jogos possui um capítulo inteiro sobre a implementação de matemática de ponto fixo.

4
Ana Betts

Qualquer que seja o caminho que você decida seguir (eu me inclinaria para um typedef e algumas macros de CPP para conversão), será necessário ter cuidado para converter para frente e para trás com alguma disciplina.

Você pode achar que nunca precisa se converter. Imagine que tudo em todo o sistema é 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