C++: эмулированное деление/умножение с фиксированной точкой

Я пишу класс с фиксированной точкой, но столкнулся с небольшой загвоздкой... Умножение, деление частей, я не уверен, как эмулировать. Я нанес очень грубый удар оператору подразделения, но я уверен, что это неправильно. Вот как это выглядит на данный момент:

class Fixed
{
    Fixed(short int _value, short int _part) : 
        value(long(_value + (_part >> 8))), part(long(_part & 0x0000FFFF)) {};

    ...

    inline Fixed operator -() const  // example of some of the bitwise it's doing
    {
        return Fixed(-value - 1, (~part)&0x0000FFFF);
    };

    ...

    inline Fixed operator / (const Fixed & arg) const // example of how I'm probably doing it wrong
    {
        long int tempInt = value<<8 | part;
        long int tempPart = tempInt;
        tempInt  /= arg.value<<8 | arg.part;
        tempPart %= arg.value<<8 | arg.part;
        return Fixed(tempInt, tempPart);
    };

    long int value, part; // members
};

Я... не очень хороший программист, ха-ха!

«Часть» класса имеет ширину 16 бит (но выражается как длинная 32-битная, поскольку я полагаю, что ей потребуется место для возможных переполнений, прежде чем они будут исправлены), и то же самое касается «значения», которое является целочисленной частью. Когда «часть» превышает 0xFFFF в одной из своих операций, старшие 16 бит добавляются к «значению», а затем часть маскируется, поэтому остаются только младшие 16 бит. Это делается в списке инициализации.

Я ненавижу спрашивать, но если бы кто-нибудь знал, где я могу найти документацию для чего-то подобного, или даже просто «трюка» или как сделать эти два оператора, я был бы очень рад за это! Я тупица, когда дело доходит до математики, и я знаю, что кому-то приходилось делать/спрашивать об этом раньше, но поиск в Google на этот раз не привел меня в землю обетованную...


c++ multiplication bit-manipulation integer-division fixed-point
person Anne Quinn    schedule 17.02.2011    source источник
comment
Это домашнее задание? По сути, вы пытаетесь имитировать математику с плавающей запятой, но без использования байтовой записи с плавающей запятой? Вы смотрели, как IEEE обрабатывает это?   -  person Zac Howland    schedule 17.02.2011
comment
@ Зак К сожалению, нет, никогда не ходил в школу программирования или ничего, как вы можете сказать! Это для очень плохой попытки избежать арифметики с плавающей запятой в 2D-физическом движке, который я делаю. Но я сейчас гуглю IEEE, так что посмотрю!   -  person Anne Quinn    schedule 17.02.2011
comment
@Zac: OP говорит о «фиксированной» точке mul&division, а не о «плавающей» точке, есть разница. en.wikipedia.org/wiki/Fixed-point_arithmetic   -  person Tony The Lion    schedule 17.02.2011
comment
@Tony: Основные принципы, лежащие в основе обоих, одинаковы. Хотя, если это не используется в системе, в которой нет FPU, это, вероятно, будет менее эффективным, чем просто использование чисел с плавающей запятой.   -  person Zac Howland    schedule 17.02.2011
comment
@ZacHowland на самом деле нет. В системах с FPU простая целочисленная арифметика может быть быстрее, чем арифметика с плавающей запятой. Более того, может потребоваться большая точность, а не более широкий диапазон. Например, когда 24-битного значения одинарной точности немного меньше, чем достаточно, но операции с двойным значением длиннее, чем 32-битное целое число.   -  person phuclv    schedule 11.03.2015

Ответы (3)


arrow_upward
2
arrow_downward

Как говорит Ян, используйте одно целое число. Поскольку похоже, что вы указываете 16-битные целые и дробные части, вы можете сделать это с помощью простого 32-битного целого числа.

«Хитрость» заключается в том, чтобы понять, что происходит с «форматом» числа, когда вы выполняете над ним операции. Ваш формат будет описан как 16.16. Когда вы добавляете или вычитаете, формат остается прежним. Когда вы умножаете, вы получаете 32,32. Поэтому вам нужно 64-битное временное значение для результата. Затем вы выполняете сдвиг >>16, чтобы перейти к формату 48.16, затем берете нижние 32 бита, чтобы получить ответ в формате 16.16.

Я немного заржавел в делении -- в DSP, где я этому научился, мы избегали (дорогостоящего) деления везде, где это было возможно!

person Martin Stone    schedule 17.02.2011
comment
На самом деле это звучит правильно! Хорошо, используя только одно 32-битное целое число, не знаю, почему я не пошел с этим в первую очередь. И... ага, вы сделали так, чтобы часть умножения выглядела так легко. Я думал, что это будет целое испытание. Думаю, теперь мне нужно просто найти часть деления. Спасибо! - person Anne Quinn; 17.02.2011
comment
@Clairvoire: статья, на которую ссылался Зак, содержит подробности операции деления. в более общем случае, когда коэффициент умножения не равен 2^16 для обоих операндов. Это должно дать вам достаточно, чтобы продолжать. - person Martin Stone; 17.02.2011

arrow_upward
0
arrow_downward

Я бы рекомендовал использовать одно целое значение вместо отдельных целых и дробных частей. Чем сложение и вычитание являются аналогами целых чисел напрямую, и вы можете просто использовать 64-битную поддержку, которую имеют все распространенные компиляторы в наши дни:

  • Умножение:

    operator*(const Fixed &other) const {
    return Fixed((int64_t)value * (int64_t)other.value);
}

  • Разделение:

    operator/(const Fixed &other) const {
    return Fixed(((int64_t)value << 16) / (int64_t)other.value);
}

64-битные целые числа

  • В gcc должны быть доступны stdint.h (или cstdint, что помещает их в пространство имен std::), поэтому вы можете использовать типы, упомянутые выше. В противном случае это long long для 32-битных целей и long для 64-битных целей.
  • В Windows это всегда long long или __int64.
person Jan Hudec    schedule 17.02.2011
comment
Это испортит фиксированную точку, вам понадобится битовый сдвиг после умножения, чтобы вернуть ее. - person Ben Voigt; 17.02.2011
comment
Я должен был указать, но я бы хотел, чтобы деление вело себя так же, как работает обычное деление, без отбрасывания оставшейся части, но это дает мне представление! - person Anne Quinn; 17.02.2011

arrow_upward
0
arrow_downward

Чтобы все заработало, сначала реализуйте (унарный) inverse(x) = 1/x, а затем реализуйте a/b как a*inverse(b). Вы, вероятно, захотите представить промежуточные звенья в формате 32.32.

person MSalters    schedule 17.02.2011
comment
Никогда не думал об этой операции... Пытался понять, как это можно сделать, но это нужно было сделать в любом случае, чтобы разделить! Спасибо за внимание! - person Anne Quinn; 17.02.2011
comment
Самое простое решение — через (1<<31)/(x*65536) << 1. Первая часть в любом случае является константой, а (x*65536) - это просто переинтерпретация вашего числа 16,16 кадров в секунду как 32-битного целого числа. Результатом будет 32-битное целое число (1/x) * 65536, которое вы можете тривиально представить как обратное 16.16. Недостаток: <<31 / <<1 означает, что LSB потерян. - person MSalters; 17.02.2011