Самый быстрый способ преобразовать двоичную систему счисления в десятичную?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть четыре 32-разрядных целых числа без знака, представляющих 128-разрядное целое число без знака, в младшем порядке окончания:
typedef struct {
unsigned int part[4];
} bigint_t;
Я бы хотел преобразовать это число в десятичное строковое представление и вывести его в файл.
Прямо сейчас я использую bigint_divmod10 функция деления числа на 10, отслеживающая остаток.Я вызываю эту функцию несколько раз, выводя остаток в виде цифры, пока число не станет равным нулю.Это довольно медленно.Это самый быстрый способ сделать это?Если да, то есть ли умный способ реализовать эту функцию, который я не вижу?Я пробовал смотреть на GMP get_str.c, но я нахожу это довольно непроницаемым.
Редактировать:вот самый быстрый код, который я смог придумать для функции divmod10:
static unsigned uint128_divmod10(uint128 *value)
{
unsigned int a = value->word[3];
unsigned int b = value->word[2];
unsigned int c = value->word[1];
unsigned int d = value->word[0];
unsigned int diva = a / 5;
unsigned int divb = b / 5;
unsigned int divc = c / 5;
unsigned int divd = d / 5;
value->word[3] = diva;
value->word[2] = divb;
value->word[1] = divc;
value->word[0] = divd;
unsigned int moda = a - diva*5;
unsigned int modb = b - divb*5;
unsigned int modc = c - divc*5;
unsigned int modd = d - divd*5;
unsigned int mod = 0;
mod += moda;
unsigned int carryb = mod*858993459;
mod += modb;
if (mod >= 5) {
mod -= 5;
carryb++;
}
unsigned int carryc = mod*858993459;
mod += modc;
if (mod >= 5) {
mod -= 5;
carryc++;
}
unsigned int carryd = mod*858993459;
mod += modd;
if (mod >= 5) {
mod -= 5;
carryd++;
}
uint128_add(value, carryd, 0);
uint128_add(value, carryc, 1);
uint128_add(value, carryb, 2);
if (value->word[0] & 1) {
mod += 5;
}
uint128_shift(value, -1);
return mod;
}
где функция добавления определяется как:
static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
unsigned int a = value->word[pos];
value->word[pos] += k;
if (value->word[pos] < a) {
// overflow
for (int i=pos+1; i<4; i++) {
value->word[i]++;
if (value->word[i]) {
break;
}
}
}
}
Решение
Это зависит от того, что еще вы делаете с числами.Вы можете компенсировать небольшую потерю эффективности использования пространства и умеренную потерю эффективности арифметики с множественной точностью в обмен на очень эффективное преобразование в десятичную систему счисления и обратно.Ключевым моментом является выполнение арифметических операций с множественной точностью с основанием, равным степени 10, а не степени 2.
Например, вы можете использовать базу 10 000, где вы упаковываете одну цифру в 16-битное слово и выполняете арифметические действия над цифрами в 32-битных целых числах.(Если вы работаете на 64-битной машине, вы можете удвоить это значение и получить основание 1 000 000 000.) Этот тип кода относительно эффективен по времени, хотя и не так быстр, как использование собственной степени двойки, потому что вы не можете воспользоваться преимуществами бит переноса на аппаратном обеспечении.И вы не можете представить столько целых чисел в одном и том же количестве бит.Но это просто чудо при преобразовании в десятичную дробь и обратно, потому что вы можете конвертировать отдельные цифры без длинного деления.
Если вам нужно представить полный диапазон чисел от нуля до ((1 << 128) - 1), вы все равно можете это сделать, но добавьте дополнительную цифру, чтобы ваши числа были больше.
Если окажется, что вам действительно нужно дополнительное пространство/скорость (возможно, вы выполняете много криптографических 128-битных вычислений), то метод одновременного деления/модификации на 10 будет самым быстрым методом, который я знаю.Еще одна хитрость заключается в том, что если небольшие целые числа являются обычным явлением, вы можете обрабатывать их особым образом.(То есть, если все три наиболее значимых 32-битных слова равны нулю, для преобразования просто используйте собственное деление.)
Есть ли умный способ реализовать эту функцию, которого я не вижу?
Дэйв Хэнсон C-интерфейсы и реализации есть длинная глава, посвященная арифметике с множественной точностью.Деление большого числа на одну цифру — это особый случай, который имеет следующую эффективную реализацию:
int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Для полного понимания действительно полезно иметь книгу, но исходный код по-прежнему намного проще понять, чем исходный код GNU.И вы можете легко адаптировать его для использования базы 10 000 (в настоящее время используется база 256).
Краткое содержание:если вашим узким местом в производительности является преобразование в десятичное число, реализуйте арифметика с множественной точностью с основанием, равным степени 10.Если собственный размер слова вашей машины составляет 32 и вы используете код C, используйте 10 000 в 16-битном слове.
Другие советы
Если ваши значения в основном меньше, чем ULLONG_MAX (18446744073709551615) Я бы попробовал использовать для них sprintf(buf,"%llu",ullong_val).Могу поспорить, что это довольно хорошо оптимизировано в стандартной библиотеке, но анализ формата займет несколько циклов.
В противном случае я бы создал bigint_divmod1000000000 (или лучше назовите mod10to9) и используйте ее.Для этого потребуется в 9 раз меньше делений, чем bigint_divmod10.
Таблица подстановки из 8 бит.У вас может быть 4 таблицы подстановки по 256 чисел.Первая - от 0-256 для байт LSB, Вторая таблица - это первая таблица, умноженная на 256 и так далее.
ПОЭТОМУ, когда вам понадобится ваш номер, суммируйте числа из таблицы поиска.При добавлении вы можете добавлять как bunary, а позже выполнять один проход по каждому байту, чтобы исправить flowerflows.
Пример номер 0x12345678 В первой таблице поиска есть адрес (0x78 = 120) таким образом, 0x010200 - это первое число во второй таблице ниже (0x56 = 87) равно 0x0202000106 (0x56 в декабре равно 22016) в третьей таблице у вас, вероятно, будет 0x03040007080702 и под последней меткой в 0x12 у вас есть 0x03000109080808 (это не вписывается в 32-битную арифметику, но вы все это знаете)
Затем суммируйте эти числа (в виде двоичных чисел) и выполните один проход, байт за байтом для переполнения код в цикле for выглядит примерно так
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Если мы посчитаем операции, необходимые для этого.
1. (поиск в таблицах и добавление) 4 таблицы подстановки.16 дополнений (имейте в виду, что когда вам не нужно переносить информацию о flowerflow, потому что они могут не появиться)
2.за один проход на каждом шаге 3 требуется пройти 16 шагов.
пассивная верхняя граница 6*16 = 100 операций.
Редактировать:
Вот код на c ++, и он на 30% быстрее, чем наивная реализация.
#include <iostream>
#include <stdint.h>
#include <array>
static uint64_t lu[4][256];
constexpr uint64_t lookup_value(uint64_t n) {
uint64_t r = 0;
uint64_t t = 1;
while (n) {
uint64_t rem = n % 10;
n /= 10;
r += rem * t;
t *= 256;
}
return r;
}
void make_lu() {
uint64_t step = 1;
for (int j = 0; j < 4; ++j) {
uint64_t n = 0;
for (int i = 0; i < 256; ++i) {
lu[j][i] = lookup_value(n);
n += step;
}
step *= 256;
}
}
struct DivMod {
uint8_t div;
uint8_t rem;
};
static DivMod dm[256];
void make_dm() {
for (int i = 0; i < 256; ++i) {
dm[i].div = i / 10;
dm[i].rem = i % 10;
}
}
void init() {
make_lu();
make_dm();
}
uint64_t b2d(uint64_t n) {
uint64_t r = 0;
for (int i = 0; i < 4; ++i) {
r += lu[i][(n >> (i * 8)) & 0xff];
}
uint64_t r2 = 0;
uint64_t of = 0;
for (int i = 0; i < 8; ++i) {
uint64_t v = ((r >> (i * 8)) & 0xff) + of;
DivMod &x = dm[v];
of = x.div;
r2 += uint64_t(x.rem) << (i * 8);
}
return r2;
}
int main() {
init();
uint64_t n;
std::cin >> n;
std::cout << std::hex << b2d(n) << "\n";
return 0;
}
На будущее: вместо реализации типа uint128 я просто использовал символы строки напрямую.Это оказалось намного быстрее, чем переход от строки к uint128 и обратно.
Самое непосредственное ускорение будет достигнуто за счет встраивания преобразования, а не вызова функций;это может быть так же просто, как маркировка bigint_divmod10() в соответствии, или с помощью оптимизации на основе профиля, предлагаемой вашим компилятором.
Я знаю, что этот вопрос старый, но я хочу внести свой вклад, поскольку никто не смог избежать цикла разделения.Этот использует pow2, я не тестировал тест, но теоретически он должен быть быстрее, чем любой другой, а также его можно настроить в функции pow.
#include <iostream>
#include <cmath>
using namespace std;
#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})
int main(){
int r[]={1,0,0,1,0,0};
cout<<MathBintodec(r,6)<<endl;
}
Выход:36
