7

我有四个无符号 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;
}

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

6 回答 6

4

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

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

如果您需要表示从 0 到 的整个数字范围((1 << 128) - 1)，您仍然可以这样做，但添加一个额外的数字，这样您的数字会更大。

如果事实证明你真的需要额外的空间/速度（也许你正在做很多加密的 128 位计算），那么同时 div/mod by 10 的方法是我所知道的最快的方法。唯一的另一个技巧是，如果小整数很常见，您可以专门处理它们。（也就是说，如果三个最重要的 32 位字都为零，则只需使用本机除法进行转换。）

有没有一种聪明的方法来实现我没有看到的这个功能？

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。

于 2009-11-07T22:10:06.297 回答
3

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

否则我会创建一个bigint_divmod1000000000（或更好的名字 mod10to9）函数并使用它。它需要的除数比bigint_divmod10.

于 2009-11-06T08:00:51.540 回答
2

8位查找表。您可以有 4 个 256 个数字的查找表。首先是从 0-256 的 LSB 字节，第二个表是第一个表乘以 256，依此类推。

因此，当您需要您的号码时，请从查找表中汇总数字。当您添加时，您可以添加为 bunary 并稍后通过每个字节来修复 owerflows。

示例编号 0x12345678 在第一个查找表中有地址（0x78 = 120），所以 0x010200 是第二个表中的第一个数字（0x56=87）是 0x0202000106（12 月中的 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 次加法（请记住，当您不需要进行溢出时，因为它们不会发生）
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;
}
于 2009-11-06T08:36:34.000 回答
0

为了以后参考，我没有实现 uint128 类型，而是直接使用了字符串的字符。事实证明，这比从字符串到 uint128 再返回要快得多。

于 2009-11-07T07:40:56.543 回答
-1

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

于 2009-11-06T07:54:08.203 回答
-1

我知道这个问题很老，但我想做出贡献，因为没有人能避免分裂周期。这个使用 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

于 2013-07-03T03:43:07.853 回答