이진수를 십진수로 변환하는 가장 빠른 방법은 무엇입니까?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
부호 없는 128비트 정수를 나타내는 부호 없는 32비트 정수 4개가 리틀 엔디안 순서로 있습니다.
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;
}
}
}
}
해결책
숫자로 무엇을 하고 있는지에 따라 다릅니다.소수점으로의 변환과 십진수 변환의 대가로 약간의 공간 효율성 손실과 다중정밀도 산술 효율성의 약간의 손실을 절충할 수 있습니다.핵심은 2의 거듭제곱이 아닌 10의 거듭제곱인 밑을 사용하여 다중정밀도 산술을 수행하는 것입니다.
예를 들어, 한 자리를 16비트 단어로 묶고 32비트 정수로 숫자에 대한 산술을 수행하는 10,000진법을 사용할 수 있습니다.(64비트 시스템을 사용하는 경우 이를 두 배로 늘려 1,000,000,000을 기본으로 할 수 있습니다.) 이러한 종류의 코드는 시간 측면에서 상대적으로 효율적이지만 2의 기본 거듭제곱을 사용하는 것만큼 빠르지는 않습니다. 하드웨어의 캐리 비트.그리고 동일한 비트 수에서는 많은 정수를 표현할 수 없습니다.하지만 긴 나눗셈 없이 개별 숫자를 변환할 수 있기 때문에 십진수로 변환하거나 십진수로 변환하는 데 능숙합니다.
0부터 숫자의 전체 범위를 표현해야 하는 경우 ((1 << 128) - 1), 여전히 이 작업을 수행할 수 있지만 숫자를 추가하면 숫자가 더 커집니다.
추가 공간/속도가 정말로 필요한 것으로 판명되면(암호화 128비트 계산을 많이 수행할 수도 있음) 10으로 동시 div/mod를 수행하는 방법이 내가 아는 가장 빠른 방법입니다.유일한 다른 비결은 작은 정수가 공통적인 경우 이를 특별히 처리할 수 있다는 것입니다.(즉, 가장 중요한 32비트 단어 3개가 모두 0인 경우 기본 나눗셈을 사용하여 변환하면 됩니다.)
제가 볼 수 없는 이 기능을 구현하는 영리한 방법이 있나요?
데이브 핸슨의 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). 나는 이것이 표준 라이브러리에서 다소 최적화되어 있지만 형식의 구문 분석은 약간의주기가 필요합니다.
그렇지 않으면 나는 a를 만듭니다 bigint_divmod1000000000 (또는 더 나은 이름 mod10to9) 기능을 사용하고 사용하십시오. 9 배 덜 분열이 필요합니다 bigint_divmod10.
8 비트의 조회 테이블. 256 숫자의 4 개의 조회 테이블을 가질 수 있습니다. 첫 번째는 LSB 바이트의 경우 0-256에서, 두 번째 테이블에 첫 번째 테이블에 256 등을 곱합니다.
따라서 숫자가 필요할 때 조회 테이블에서 숫자를 합산하십시오. 추가 할 때는 번리로 추가하고 나중에 각 바이트를 통과하여 owerflows를 고정 할 수 있습니다.
예제 번호 0x12345678 첫 번째 조회 테이블에는 addres (0x78 = 120) 아래에 있으므로 0x010200은 (0x56 = 87) 아래의 두 번째 테이블에서 첫 번째 숫자입니다. 0x12에서 lable 0x030001090809080808이 있습니다 (이것은 32 비트 산술에 맞지 않지만 Allredy가 알고 있음)
그런 다음이 숫자를 요약하고 (바이너리 범 버로) OVERFLOW CODE를 위해 바이트로 바이트를 하나씩 이동하십시오.
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
이를 위해 필요한 작업을 계산하는 경우.
1. (테이블을 찾고 추가) 4 조회 테이블. 16 첨가물 (Owerflow를 가지고 다닐 필요가 없을 때는 OCU가 할 수 없다는 점을 명심하십시오).
2. 각 3 단계에서 1 개의 패스를 통과 할 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;
}
향후 참조를 위해 UINT128 유형을 구현하는 대신 문자열의 문자를 직접 사용했습니다. 이것은 문자열에서 uint128로 돌아가서 뒤로가는 것보다 훨씬 빠른 것으로 판명되었습니다.
가장 즉각적인 속도는 함수를 호출하는 대신 변환을 인화하는 데서 나옵니다. 마킹만큼 간단 할 수 있습니다 bigint_divmod10() 인라인, 또는 컴파일러가 제공하는 프로필 유도 최적화 사용.
나는이 질문이 오래되었음을 알고 있지만, 디비전주기를 피하는 방법은 없기 때문에 기여하고 싶습니다. 이것은 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
