2進数を10進数に変換する最速の方法は?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
符号なし 128 ビット整数を表す 4 つの符号なし 32 ビット整数がリトル エンディアン順にあります。
typedef struct {
unsigned int part[4];
} bigint_t;
この数値を10進数の文字列表現に変換してファイルに出力したいと思います。
今、私が使っているのは、 bigint_divmod10 数値を 10 で割って余りを追跡する関数。この関数を繰り返し呼び出して、数値が 0 になるまで剰余を数字として出力します。かなり遅いです。これが一番早い方法でしょうか?もしそうなら、私が見ていないこの関数を実装するための賢い方法はありますか?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;
}
}
}
}
解決
それは、数字を使って他に何をしているかによって異なります。10 進数との間の非常に効率的な変換と引き換えに、スペース効率のわずかな損失と多精度演算の効率のわずかな損失をトレードオフできます。重要なのは、2 のべき乗ではなく 10 のべき乗を基数として多精度演算を行うことです。
たとえば、基数 10,000 を使用すると、1 桁を 16 ビット ワードにパックし、32 ビット整数の桁で演算を行うことができます。(64 ビット マシンを使用している場合は、これを 2 倍にして、1,000,000,000 を基数にすることができます。) この種のコードは、時間的には比較的効率的ですが、ネイティブの 2 の累乗を使用するほど高速ではありません。ハードウェア上のキャリービット。また、同じビット数で多くの整数を表すことはできません。ただし、長い除算を行わずに個々の数字を変換できるため、10 進数への変換や 10 進数からの変換には優れています。
0 から 0 までの全範囲の数値を表す必要がある場合 ((1 << 128) - 1), 、これを行うことはできますが、数字を 1 つ追加すると、数字が大きくなります。
本当に追加のスペース/速度が必要であることが判明した場合 (おそらく、暗号化 128 ビット計算を大量に実行している可能性があります)、10 による div/mod を同時に実行する方法が、私が知っている最速の方法です。他の唯一のトリックは、小さな整数が一般的である場合、それらを特別に処理できることです。(つまり、3 つの最上位 32 ビット ワードがすべて 0 の場合は、ネイティブの除算を使用して変換するだけです。)
私が見つけていないこの機能を実装する賢い方法はありますか?
デイブ・ハンソンの 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 を使用します。
他のヒント
自分の価値観がほとんどULLONG_MAX（18446744073709551615）未満であれば、私は彼らsprintf(buf,"%llu",ullong_val)のために使用しようと思います。私は、これはかなりうまく標準ライブラリに最適化された賭けが、フォーマットの解析は、しかし、いくつかのサイクルがかかります。
そうでなければ、私はbigint_divmod1000000000（またはより良い名前mod10to9）関数を作成し、それを使用したいです。それはbigint_divmod10より9倍少ない除算が必要になります。
8ビットのルックアップテーブル。 あなたは256個の数字の4つのルックアップテーブルを持つことができます。 第一、第二テーブルはように256を乗じた最初のテーブルであり、LSBバイトを0から256である。
ルックアップテーブルからSOあなたの数の合計を必要とする数字。 あなたはbunaryとして追加し、owerflowsを修正するために、各バイトの上に後から1つのパスを行くことができます追加するときます。
例 番号0x12345678の 第1のルックアップテーブルにADDRES（0x78と= 120）の下にあります そう0x010200は、最初の番号です （0x56 = 87）の下の第二のテーブルに0x0202000106（DECで0x56が22016）であります 3番目のテーブルにあなたは侯0x03040007080702を持っているでしょう そして0x12を最後lableの下には、
（これは32ビット演算に適合していますが、知っているallredyことはありません）0x030001090809080808を持っています次に、（バイナリbumbersなど）は、この数字を合計し、オーバーフローのためのバイトで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件の追加（彼らはOCURすることはできませんbecuaseあなたは、owerflowについて実行する必要がない場合があることに注意してください）
各ステップ3 operatins渡す16のステップ2.ワンパス。
passimistic上限6×16 = 100の操作。
EDITます：
ここでは、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()をマーク、またはあなたのコンパイラによって提供されるようプロファイルに基づく最適化を使用したような単純なことができます。
私はこの質問が古いですけど、私は分裂周期を回避する方法を置くどれも貢献したいです。この1は私がベンチマークをテストしていませんが、理論的には、他よりも高速であるべきであり、また、同様に捕虜機能で微調整することができ、POW2を使用します。
#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
