将二进制转换为十进制的最快方法?

我有四个无符号的32位整数,表示无符号的128位整数,以小端序排列:

typedef struct { unsigned int part[4]; } bigint_t; 

我想将此数字转换为十进制字符串表示forms并将其输出到文件中。

现在,我正在使用bigint_divmod10函数将数字除以10,跟踪余数。 我重复调用这个函数,输出余数作为数字,直到数字为零。 这很慢。 这是最快的方法吗? 如果是这样,有没有一种聪明的方法来实现我没有看到的这个function? 我试过看GMP的get_str.c ,但我发现它非常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; } 

其中add函数定义为:

 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; iword[i]++; if (value->word[i]) { break; } } } } 

这取决于你对数字做了什么。 您可以牺牲空间效率的轻微损失和多精度算术效率的适度损失,以换取非常有效的十进制转换。 关键是使用10的幂而不是2的幂来进行多精度算术。

例如,您可以使用10,000的基数,将一个数字打包成16位字,然后对32位整数的数字进行算术运算。 (如果您使用的是64位计算机,则可以将其加倍并基于1,000,000,000。)这种代码在时间上相对有效,但不如使用2的本机function快,因为您无法利用硬件上的进位。 并且您不能以相同的位数表示尽可能多的整数。 但它是转换为十进制和从十进制转换的高手,因为您可以转换单个数字而无需任何长除法。

如果您需要表示从零到((1 << 128) - 1)的全部数字范围,您仍然可以执行此操作,但添加一个额外的数字,因此您的数字会更大。

如果事实certificate你真的需要额外的空间/速度(也许你正在进行大量的加密128位计算)那么同步div / mod by 10的方法是我所知道的最快的方法。 唯一的另一个技巧是,如果小整数是常见的,你可以专门处理它们。 (也就是说,如果三个最重要的32位字都是零,只需使用原生分区进行转换。)

有没有一种聪明的方法来实现我没有看到的这个function?

Dave Hanson的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代码,则在16位字中使用10,000。

如果您的值大多小于ULLONG_MAX (18446744073709551615),我会尝试使用它们sprintf(buf,"%llu",ullong_val) 。 我敢打赌,这在标准库中得到了很好的优化,但是解析格式会需要一些周期。

否则我会创建一个bigint_divmod1000000000 (或更好的名称mod10to9)函数并使用它。 它需要比bigint_divmod10少9倍的分bigint_divmod10

查找8位的表。 您可以拥有4个256个数字的查找表。 对于LSB字节,第一个是0-256,第二个表是第一个表乘以256,依此类推。

所以当你需要你的数字总结查询表中的数字。 添加时,您可以添加为bunary,然后在每个字节上进行一次传递以修复function流。

示例编号0x12345678在第一个查找表中有addres(0x78 = 120),所以0x010200是第二个表(0x56 = 87)下的第一个数字是0x0202000106(0x56中的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个步骤。

passimistic上限6 * 16 = 100次操作。

编辑:

这是c ++代码,比天真实现快30%。

 #include  #include  #include  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类型,而是直接使用了字符串的字符。 事实certificate这比从字符串到uint128并返回要快得多。

最直接的加速将来自内联转换而不是调用函数; 它可以像标记bigint_divmod10() 内联一样简单,也可以使用编译器提供的配置文件引导优化。

我知道这个问题已经过时了,但是我想做出贡献,因为没有人能避免分裂周期。 这个使用pow2,我还没有测试过基准,但理论上应该比其他任何一个都快,也可以在powfunction中进行调整。

 #include  #include  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< 

产量:36