Алгоритм для преобразования бесконечно долгой основы 2^32 число к печатаемой основе 10
Они заставляют компилятор испускать соответствующие подсказки ответвления где поддержка оборудования их. Это обычно просто означает вертеть несколько битов в коде операции инструкции, таким образом, размер кода не изменится. ЦП запустит выбирающие инструкции с предсказанного местоположения, и сбросит конвейер и запустится, если это окажется неправильным, когда ответвление достигнуто; в случае, где подсказка корректна, это сделает ответвление намного быстрее - точно, сколько быстрее будет зависеть от аппаратных средств; и то, насколько это влияет на производительность кода, будет зависеть от того, какая пропорция подсказки времени корректна.
, Например, на ЦП PowerPC ответвление, которому не подсказывают, могло бы взять 16 циклов, правильно подсказал, что 8 и неправильно подсказали 24. В самых внутренних циклах хороший вывод подсказок может иметь огромное значение.
Мобильность не является действительно проблемой - по-видимому, определение находится в заголовке на платформу; можно просто определить, "вероятно", и "вряд ли" ни к чему для платформ, которые не поддерживают статические подсказки ответвления.
4 ответа
Если у вас есть доступ к 64-битной арифметике, это проще. Я бы сделал что-то вроде:
int32_t divideBy10(int32_t* number) {
uint32_t r = 0;
uint32_t d;
for (int i=0; i<SIZE; ++i) {
d = (number[i] + r*0x100000000) / 10;
r = (number[i] + r*0x100000000) % 10;
number[i] = d;
number[i] = r;
}
void convertTo10Text(int32_t* number, char* buf) {
do {
digit = divideBy10(number);
*buf++ = digit + '0';
} while (!isEqual(number, zero));
reverse(buf);
}
isEqual () и reverse () осталось реализовать. DivineBy10 делит на 10 и возвращает остаток.
По сути, вам нужна классическая десятичная печать с использованием создания цифр путем многократного деления вашего числа на десять (в вашем основании 2 ^ 32) и использования остатка в виде цифр. У вас может не быть процедуры деления на (что угодно, не говоря уже о 10), что, вероятно, является ключевым источником вашей проблемы.
Если вы работаете на C или C ++, вы можете получить полный пакет арифметических операций с бесконечной точностью из ] Пакет GNU Bignum . Подобные пакеты доступны для большинства других широко используемых языков.
Конечно, если у вас слишком много свободного времени, вы всегда можете реализовать мультипрецизионное деление самостоятельно. Вы уже заимствуете терминологию у Кнута; он также предоставляет алгоритмы множественной точности в получисленных алгоритмах.
Если это .NET, взгляните на эту реализацию класса BigInteger .
Как насчет использования длинных удвоений? Тогда вы получите 80 бит в мантиссе, но я думаю, что точность теряется при использовании чисел с плавающей запятой.