Самый быстрый способ преобразования двоичного в десятичное?

Question

У меня есть четыре беззнаковых 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;
            }
        }
    }
}

Answer 1

Это зависит от того, что еще вы делаете с числами. Вы можете компенсировать небольшую потерю эффективности использования пространства и небольшую потерю эффективности арифметики с многократной точностью в обмен на очень эффективное преобразование в десятичное число и обратно. Ключ должен сделать многоточную арифметику с основанием, которое является степенью 10, а не степенью 2.

Например, вы можете использовать основание 10 000, где вы упаковываете одну цифру в 16-битное слово и выполняете арифметику с цифрами в 32-битных целых числах. (Если вы работаете на 64-битной машине, вы можете удвоить эту сумму и сделать базовую 1 000 000 000.) Этот вид кода относительно эффективен во времени, хотя и не так быстро, как использование родной силы двух, потому что вы не можете воспользоваться преимуществами бит переноса на оборудовании. И вы не можете представить столько целых чисел в одном и том же количестве бит. Но это быстрый способ преобразования в десятичную и из нее, потому что вы можете преобразовать отдельные цифры без какого-либо длинного деления.

Если вам нужно представить полный диапазон чисел от нуля до ((1 << 128) - 1)Вы можете сделать это, но добавьте дополнительную цифру, чтобы ваши цифры были больше.

Если оказывается, что вам действительно нужно дополнительное пространство / скорость (может быть, вы делаете много криптографических 128-битных вычислений), то метод simultanous div/mod by 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-битном слове.

Answer 2

Если ваши значения в основном меньше, чем ULLONG_MAX (18446744073709551615) Я бы попробовал использовать для них sprintf(buf,"%llu",ullong_val), Могу поспорить, что это довольно хорошо оптимизировано в стандартной библиотеке, но синтаксический анализ формата займет несколько циклов.

В противном случае я бы создал bigint_divmod1000000000 (или лучше название mod10to9) и используйте его. Было бы нужно в 9 раз меньше делений, чем bigint_divmod10,

Answer 3

Таблица поиска 8 бит. Вы можете иметь 4 таблицы поиска из 256 номеров. Первая от 0 до 256 для байтов младшего бита, вторая таблица - первая таблица, умноженная на 256 и так далее.

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

Номер примера 0x12345678 В первой справочной таблице есть под адресами (0x78 = 120), поэтому 0x010200 - это первое число во второй таблице в (0x56=87), это 0x0202000106 (0x56 в декабре 22016), в третьей таблице у вас будет 0x03040007080702 и меньше последней В метке 0x12 у вас есть 0x030001090809080808 (это не вписывается в 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 дополнений (имейте в виду, что, когда вам не нужно носить с собой owerflow, потому что они не могут возникнуть)
2. один проход в каждом шаге 3 операции 16 шагов, чтобы пройти.

пассивистская верхняя граница 6*16 = 100 операций.

РЕДАКТИРОВАТЬ:

Вот код на С ++, и он на 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;
}

Answer 4

Для дальнейшего использования вместо реализации типа uint128 я просто использовал символы строки напрямую. Это оказалось намного быстрее, чем переход от строки к uint128 и обратно.

Answer 5

Я знаю, что этот вопрос старый, но я хочу внести свой вклад, так как никто не может избежать цикла разделения. В этом примере используется 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

Answer 6

Самое быстрое ускорение будет происходить от включения преобразования, а не от вызова функций; это может быть так же просто, как маркировка bigint_divmod10() встроенный или используя профильную оптимизацию, предложенную вашим компилятором.