64-битная ошибка умножения с фиксированной точкой

Я реализую 64-битный числовой тип 31.32 со знаком с фиксированной точкой на С# на основе long. Пока все хорошо для сложения и вычитания. Однако у умножения есть раздражающий случай, который я пытаюсь решить.

Мой текущий алгоритм состоит из разбиения каждого операнда на его старшие и наименее значащие 32 бита, выполнения 4 умножений на 4 длинных числа и добавления соответствующих битов этих длинных чисел. Вот это в коде:

public static Fix64 operator *(Fix64 x, Fix64 y) {

    var xl = x.m_rawValue; // underlying long of x
    var yl = y.m_rawValue; // underlying long of y

    var xlow = xl & 0x00000000FFFFFFFF; // take the 32 lowest bits of x
    var xhigh = xl >> 32; // take the 32 highest bits of x
    var ylow = yl & 0x00000000FFFFFFFF; // take the 32 lowest bits of y
    var yhigh = yl >> 32; // take the 32 highest bits of y

    // perform multiplications
    var lowlow = xlow * ylow;
    var lowhigh = xlow * yhigh;
    var highlow = xhigh * ylow;
    var highhigh = xhigh * yhigh;

    // take the highest bits of lowlow and the lowest of highhigh
    var loResult = lowlow >> 32;
    var midResult1 = lowhigh;
    var midResult2 = highlow;
    var hiResult = highhigh << 32;

    // add everything together and build result
    var finalResult = loResult + midResult1 + midResult2 + hiResult;
    return new Fix64(finalResult); // this constructor just copies the parameter into m_rawValue
}

Это работает в общем случае, но не работает в ряде сценариев. А именно, результат отличается на 1,0 (десятичное значение), часто для очень малых или больших значений операндов. Вот некоторые результаты моих модульных тестов (FromRaw() — это метод, который создает Fix64 непосредственно из длинного значения без его смещения):

Failed for FromRaw(-1) * FromRaw(-1): expected 0 but got -1
Failed for FromRaw(-4) * FromRaw(6791302811978701836): expected -1.4726290525868535041809082031 but got -2,4726290525868535041809082031
Failed for FromRaw(2265950765) * FromRaw(17179869183): expected 2.1103311001788824796676635742 but got 1,1103311001788824796676635742

Я пытаюсь выработать логику этого на бумаге, но я немного застрял. Как я могу это исправить?


person Asik    schedule 24.12.2012    source источник
comment
Что ты делаешь с переносными битами? Кроме того, я не совсем понимаю перевод... каково, скажем, эквивалентное числовое значение 2265950765?   -  person mellamokb    schedule 25.12.2012
comment
Да, а как насчет переносных бит?   -  person Hot Licks    schedule 25.12.2012
comment
Я не знаком с правилами целочисленного продвижения C# — являются ли значения lowlow и т. д. 32-битными, или умножение 32x32 автоматически дает 64-битный результат?   -  person hobbs    schedule 25.12.2012
comment
@hobbs: xlow и ylow уже являются длинными, поэтому их произведение также будет длинным. Если вы умножите два 32-битных целых числа в C#, вы получите 32-битный результат с переполнением.   -  person mellamokb    schedule 25.12.2012
comment
@mellamokb xlow, ylow, xhigh и yhigh — это 64-битные целые числа, где первые 32 бита равны 0 (для -low) или 1 (для -high), а последние — младшие или старшие 32 бита x и y. Таким образом, биты переноса просто переходят в неиспользуемые старшие 32 бита. Преобразование из длинного просто (значение * (1L ‹‹ 32)). Преобразование обратно в long — это m_rawValue ›› 32. В основном то же правило применяется к типам с плавающей запятой, с некоторым округлением и приведением типов.   -  person Asik    schedule 25.12.2012


Ответы (2)


Алгоритм выглядит здравым, он отработал его «на бумаге» и кажется правильным. Вот мои проработанные записи для FromRaw(2265950765) * FromRaw(17179869183) (0,52758277510292828083038330078125 * 3,99999999976716935634613037109375 = 2,11033110017888247966766357421875)

x1 = 2265950765
y1 = 17179869183

xlow = 2265950765
xhigh = 0
ylow = 4294967295
yhigh = 3

lowlow = 9732184427755230675
lowhigh = 6797852295
highlow = 0
highhigh = 0

loResult = 2265950764
midResult1 = 6797852295
midResult2 = 0
hiResult = 0

finalResult = 9063803059

Теперь вот что, как я подозреваю, происходит: lowlow должен быть ulong, чтобы результат был правильным, но я думаю, что вы получаете значение со знаком. Интерпретируется как подписанный, lowlow заканчивается как -8714559645954320941 (слишком мало на 2^64), loResult заканчивается как -2029016532 (слишком мало на 2^32), finalResult заканчивается как 4768835763 (тоже слишком мало на 2^32) и результирующее значение равно 1,11033110017888247966766357421875, что ровно на 1 меньше, чем вы ожидаете.

Как правило, ваши значения следует рассматривать как имеющие подписанную «верхнюю половину» и неподписанную «нижнюю половину». highhigh подписано * подписано = подписано; lowhigh и highlow подписаны * unsigned = подписано; но lowlow без знака * без знака = без знака.

person hobbs    schedule 24.12.2012
comment
@StephenCanon ха! Невероятно видеть тебя здесь. Я не знаю, помните ли вы, но вы помогли мне с очень похожей проблемой несколько лет назад, поэтому я понимаю это сейчас :) - person hobbs; 25.12.2012
comment
Если xlow и ylow беззнаковые, я должен вставить приведение, чтобы сделать xlow * yhigh и xhigh * ylow, потому что C# не позволит мне умножить подписанные и беззнаковые длинные вместе. Должен ли я привести высокие значения к беззнаковым, а затем вернуть результат к подписанным? Это меня смущает. - person Asik; 25.12.2012
comment
@Dr_Asik: Их нужно привести к uint, а не ulong. Итак, вы хотите high1 * (long)(uint)low2 + high2 * (long)(uint)low1 - person Ben Voigt; 02.01.2013

Я не понимаю, почему FromRaw(-1) * FromRaw(-1) должен возвращать 0? Он должен вернуть +1

В общем об алгоритме: не разделяй, а просто умножай longs.

Предположим, вы умножаете 2.3*4.5. Вы получите 10.35. Но если вы умножите 23*45, вы получите 1035.

Цифры одинаковые!

Итак, чтобы умножить ваши числа, вы должны умножить m_rawValues, а затем сдвинуть биты вправо.

person Dims    schedule 24.12.2012
comment
нет, алгоритм перекрестного умножения правильный. Если вы умножаете, а затем сдвигаете, вы переполняетесь до того, как сдвигаете, и результаты неверны. Чтобы получить умножение 64x64=64, нужно разделить на четыре умножения 32x32=64. - person hobbs; 25.12.2012
comment
Необработанное значение -1 представляет собой -0,00...0024 что-то, наименьшее отрицательное значение, которое может представлять мой тип. Поэтому, если вы умножаете его само на себя, это дает слишком маленький результат, чтобы его можно было представить, и поэтому его следует округлить до 0. - person Asik; 25.12.2012