7

符号なし 128 ビット整数をリトルエンディアン順で表す 4 つの符号なし 32 ビット整数があります。

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

この数値を 10 進文字列表現に変換し、ファイルに出力したいと思います。

現在、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の累乗の底で多倍長演算を実行することです。

たとえば、1桁を16ビットワードにパックし、32ビット整数の桁で算術演算を行うベース10,000を使用する場合があります。（64ビットマシンを使用している場合は、それを2倍にして、ベース1,000,000,000を実行できます。）この種のコードは、時間的には比較的効率的ですが、2のネイティブパワーを使用するほど高速ではありません。ハードウェアのキャリービット。また、同じビット数で多くの整数を表すことはできません。ただし、長い除算なしで個々の桁を変換できるため、10進数への変換と10進数からの変換は簡単です。

ゼロからまでの数値の全範囲を表す必要がある場合((1 << 128) - 1)でも、これを行うことができますが、数字を追加すると、数値が大きくなります。

本当に余分なスペース/速度が必要であることが判明した場合（おそらく、多くの暗号化128ビット計算を実行している場合）、10による同時div/modの方法が私が知っている最速の方法です。他の唯一のトリックは、小さな整数が一般的である場合、それらを特別に処理できることです。（つまり、最も重要な3つの32ビットワードがすべてゼロの場合は、ネイティブ除算を使用して変換します。）

私が見ていないこの関数を実装する賢い方法はありますか？

Dave HansonのCインターフェイスと実装には、多倍長演算に関する長い章があります。大きな数を1桁で割るのは、この効率的な実装を持つ特殊なケースです。

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進数への変換である場合は、10の累乗を底とする多倍長演算を実装します。マシンのネイティブワードサイズが32で、Cコードを使用している場合は、16ビットワードで10,000を使用します。

于 2009-11-07T22:10:06.297 に答える
3

あなたの値がほとんど（18446744073709551615）未満の場合、ULLONG_MAX私はそれらに使用しようとしますsprintf(buf,"%llu",ullong_val)。これは標準ライブラリではかなり最適化されていると思いますが、フォーマットの解析には数サイクルかかります。

それ以外の場合は、bigint_divmod1000000000（またはより適切な名前のmod10to9）関数を作成して使用します。必要な除算は。の9分の1ですbigint_divmod10。

于 2009-11-06T08:00:51.540 に答える
2

8 ビットのルックアップ テーブル。256 個の数値のルックアップ テーブルを 4 つ持つことができます。最初は LSB バイトの 0 ～ 256 で、2 番目のテーブルは最初のテーブルに 256 を掛けたものなどです。

あなたの数字が必要なときは、ルックアップテーブルから数字を合計してください。追加するときは、bunary として追加し、後で各バイトを 1 パスして owerflow を修正できます。

例番号 0x12345678 最初のルックアップ テーブルにはアドレス (0x78 = 120) の下にあるため、0x010200 は 2 番目のテーブルの下 (0x56=87) の最初の番号です。 0x12 でラベルを付けると、0x030001090809080808 になります (これは 32 ビット演算には適合しませんが、ご存知のとおり)

次に、この数値を (バイナリ バンバーとして) 合計し、1 つのパスに進みます。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.各ステップで1回のパス 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() インラインでマークを付けるか、コンパイラーが提供するプロファイルガイド付き最適化を使用するのと同じくらい簡単です。

于 2009-11-06T07:54:08.203 に答える