Как эффективно переместить десятичную точку в числе, пока не достигнет некоторого порога

Question

Скажем, у меня есть двойной x, значение которого> 0 и <1 миллион.Я хочу переместить десятичную точку влево до> 1 миллиона и <10 миллионов.Так, например, 23.129385 становится 2313938.5. </p>

Сейчас я просто умножаю на 10 до достижения условия остановки.Однако я много выполняю этот алгоритм, поэтому, если я смогу каким-то образом его оптимизировать, это будет полезно.Решение с постоянным временем, не зависящее от величины x, очевидно, является идеальным, но до сих пор я не смог придумать его.

Answer 1

В некоторых языках, таких как C ++ с frexp , двоичный показатель экспоненты очень дешево представлен как целое число.

Если вам так повезло, вы можете получить предварительно вычисленную таблицу поиска pow2to10 от 2k возможных двоичных показателей до степени 10, что может быть. Иметь другую справочную таблицу lookup10 для степеней 10. Теперь ваши вычисления выглядят следующим образом:

frexp(x , &n);
int i = pow2to10[n];
if (lookup10[i+1] <= x) {
    i++;
}
double result = x * lookup10[i];

Теперь вместо серии умножений у вас есть 3 поиска в массивах, одно сравнение и одно умножение. Если вы выполняете это в узком цикле, сохраните pow2to10 как массив short int, попробуйте урезать диапазоны до того, что вам нужно, и поиски будут в структуре данных, которая может поместиться в кэш L1.

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

Answer 2

Вы не говорите, какой язык или какой тип процессора, или как распределяются числа (например, если большинство из них меньше 5, но редко несколько большие или ..);однако ...

Самая быстрая скалярная версия, о которой я могу подумать (при условии, что C и современные процессоры 80x86 могут быть):

    // x is between 1 and 999999

    unsigned long x_int = x;        // Integer comparisons are possibly faster
    double multiplier;

    if(x_int < 1000) {
        // x is between 1 and 999
        if(x_int < 100) {
            // x is between 1 and 99
            if(x_int < 10) {
                // x is between 1 and 9
                multiplier = 1000000;
            } else {
                // x is between 10 and 99
                multiplier = 100000;
            }
        } else {
            // x is between 100 and 999
            multiplier = 10000;
        }
    } else {
        // x is between 1000 and 999999
        if(x_int < 10000) {
            // x is between 1000 and 9999
            multiplier = 1000;
        } else {
            // x is between 10000 and 999999
            if(x_int < 100000) {
                // x is between 10000 and 99999
                multiplier = 100;
            } else {
                // x is between 100000 and 999999
                multiplier = 10;
            }
        }
    }
    x *= multiplier;

Это добавляет до 2 или 3 ветвей и одно умножение назначение. Примечание: для современных 80x86 конечную ветвь можно заменить инструкцией CMOVcc.

Если вы делаете это много;тогда следующим шагом будет попытка использовать SIMD для одновременного выполнения нескольких значений (с последующей многопоточностью / многопроцессорностью).