Я реализую 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
Я пытаюсь выработать логику этого на бумаге, но я немного застрял. Как я могу это исправить?
2265950765
? - person mellamokb   schedule 25.12.2012lowlow
и т. д. 32-битными, или умножение 32x32 автоматически дает 64-битный результат? - person hobbs   schedule 25.12.2012xlow
иylow
уже являются длинными, поэтому их произведение также будет длинным. Если вы умножите два 32-битных целых числа в C#, вы получите 32-битный результат с переполнением. - person mellamokb   schedule 25.12.2012