Как сделать так, чтобы мой коэффициент с плавающей точкой расширенного диапазона был более эффективным?

Question

Я делаю вычисление, которое часто включает такие значения, как 3.47493E + 17298.Это намного больше того, с чем может справиться double, и мне не нужна дополнительная точность, просто дополнительный диапазон показателей, поэтому я создал свою собственную небольшую структуру в C #.

В моей структуре используется long для значимого и знакаи int для показателя степени, поэтому у меня фактически есть:

1 знаковый бит 32 экспонентных бита (показатель дополнения к обычному 2) 63 значащих битов

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

Моя процедура умножения:

    public static BigFloat Multiply(BigFloat left, BigFloat right)
    {
        long shsign1;
        long shsign2;

        if (left.significand == 0)
        {
            return bigZero;
        }

        if (right.significand == 0)
        {
            return bigZero;
        }

        shsign1 = left.significand;
        shsign2 = right.significand;

        // scaling down significand to prevent overflow multiply

        // s1 and s2 indicate how much the left and right 
        // significands need shifting.
        // The multLimit is a long constant indicating the
        // max value I want either significand to be
        int s1 = qshift(shsign1, multLimit);
        int s2 = qshift(shsign2, multLimit);

        shsign1 >>= s1;
        shsign2 >>= s2;

        BigFloat r;

        r.significand = shsign1 * shsign2;
        r.exponent = left.exponent + right.exponent + s1 + s2;

        return r;
    }

И qshift:

Он просто выясняет, на сколько нужно сдвинуть val, чтобы сделать его меньшим по абсолютной величине, чем предел.

    public static int qshift(long val, long limit)
    {
        long q = val;
        long c = limit;
        long nc = -limit;

        int counter = 0;

        while (q > c || q < nc)
        {
            q >>= 1;
            counter++;
        }

        return counter;
    }

Answer 1

Это совершенно другая идея ...

Используйте аппаратное обеспечение с плавающей запятой, но дополните его своими собственными целочисленными показателями.Другими словами, BigFloat.significand будет числом с плавающей точкой вместо целого числа.

Тогда вы можете использовать ldexp и frexp, чтобы фактический показатель степени с плавающей точкой был равен нулю.Это должны быть одиночные машинные инструкции.

Таким образом, умножение BigFloat становится:

• r.significand = left.significand * right.significand
• r.exponent = left.exponent + right.exponent
• tmp = (фактическийпоказатель r.significand из frexp)
• r.exponent += tmp
• (используйте ldexp для вычитания tmp из фактического показателя r.significand)

К сожалению,последние два шага требуют frexp и ldexp, которые, как показывают результаты поиска, недоступны в C #.Таким образом, вам, возможно, придется записать этот бит на C.

...

Или, на самом деле ...

Использовать числа с плавающей запятой для значимостей, но просто сохранитьих нормализовали между 1 и 2. Итак, снова используйте поплавки для значений и умножьте их следующим образом:

r.significand = left.significand * right.significand;
r.exponent = left.exponent + right.exponent;
if (r.significand >= 2) {
    r.significand /= 2;
    r.exponent += 1;
}
assert (r.significand >= 1 && r.significand < 2);  // for debugging...

Это должно работать до тех пор, пока вы сохраняете инвариант, упомянутый в assert ().(Потому что если x между 1 и 2, а y между 1 и 2, то x * y находится между 1 и 4, поэтому на этапе нормализации просто нужно проверить, когда значимое и произведение находится между 2 и 4.)

Вам также нужно будет нормализовать результаты дополнений и т. Д., Но я подозреваю, что вы уже это делаете.

Хотя вам все-таки понадобится специальный случай нуля: -).

[править, чтобы конкретизировать frexp версию]

BigFloat BigFloat::normalize(BigFloat b)
{
    double temp = b.significand;
    double tempexp = b.exponent;
    double temp2, tempexp2;
    temp2 = frexp(temp, &tempexp2);
    // Need to test temp2 for infinity and NaN here
    tempexp += tempexp2;
    if (tempexp < MIN_EXP)
        // underflow!
    if (tempexp > MAX_EXP)
        // overflow!
    BigFloat r;
    r.exponent = tempexp;
    r.significand = temp2;
}

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

И затем есть все ключевые случаи, о которых нужно беспокоиться...

Вы, вероятно, хотите обработать недостаточное значение, возвращая ноль.Переполнение зависит от ваших вкусов;должно быть либо ошибкой, либо + -infinity.Наконец, если результатом frexp () является бесконечность или NaN, значение tempexp2 не определено, поэтому вы можете также проверить эти случаи.

Answer 2

Я не большой программист на C #, но вот несколько общих идей.

Во-первых, есть ли инструменты профилирования для C #? Если так, начните с этих ...

Скорее всего, время тратится в вашей функции qshift (); в частности, петля. Неправильно предсказанные ветви неприятны.

Я бы переписал это как:

long q = abs(val);
int x = q/nc;
(find next power of 2 bigger than x)

О последнем шаге см. этот вопрос и ответ .

Тогда вместо сдвига на qshift просто разделите на эту степень 2. (Есть ли в C # «найти первый набор» (он же. Ffs)? Если это так, вы можете использовать его, чтобы получить число сдвигов от степени 2 ; это должна быть одна инструкция.)

Определенно вставьте эту последовательность, если компилятор не сделает этого за вас.

Кроме того, я бы отказался от особых случаев для нуля, если только вы не умножаете на ноль лот . Линейный код хороший; условия плохие.

Answer 3

Если вы уверены, что переполнения не будет, вы можете использовать непроверенный блок .

Это удалит проверки переполнения и увеличит производительность.