أسرع طريقة لتحويل ثنائي إلى عشري؟

Question

لدي أربعة أعداد صحيحة غير موقعة 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;
}

حيث يتم تعريف وظيفة إضافة على النحو التالي:

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;
            }
        }
    }
}

Answer 1

ذلك يعتمد ماذا تفعل مع الأرقام. يمكنك التجارة عن خسارة طفيفة في كفاءة الفضاء وفقدان متواضع في كفاءة الحساب المتعدد المتعدد في مقابل تحويل فعال للغاية من وإلى عشري. المفتاح هو القيام الحساب المتعدد المتعدد مع قاعدة قوة 10 بدلا من قوة 2.

على سبيل المثال، قد تستخدم 10،000 قاعدة، حيث تقوم بتعبئة رقم واحد في كلمة 16 بت وتقدم حسابك على الأرقام في الأعداد الصحيحة 32 بت. (إذا كنت على آلة 64 بت، فيمكنك مضاعفة ذلك واختبار قاعدة 1،000،000،000.) هذا النوع من التعليمات البرمجية فعال نسبيا، على الرغم من أنه ليس بسرعة كبيرة مثل استخدام القوة الأصلية لشخصين لأنك لا تستطيع الاستفادة من تحمل قليلا على الأجهزة. ولا يمكنك تمثيل العديد من الأعداد الصحيحة في نفس عدد البتات. لكنها أزيز عند التحول من وإلى عشرية، لأنك تحصل على تحويل الأرقام الفردية دون أي قسم طويل.

إذا كنت بحاجة إلى تمثيل مجموعة كاملة من الأرقام من الصفر إلى ((1 << 128) - 1), ، لا يزال بإمكانك القيام بذلك، ولكن أضف رقما إضافيا، بحيث تكون الأرقام الخاصة بك أكبر.

إذا اتضح أنك تحتاج حقا إلى مساحة / سرعة إضافية (ربما تقوم بعمل الكثير من الحسابات 128 بت التشفير)، فإن طريقة DIV / MOD SMULTANOUS من 10 هي أسرع طريقة أعرفها. الحيلة الأخرى الوحيدة هي أنه إذا كانت الأعداد الصحيحة الصغيرة شائعة، يمكنك التعامل معها خصيصا. (أي، إذا كانت الكلمات الثلاثة الأكثر أهمية 32 بت كلها صفرية، فما عليك سوى استخدام القسم الأصلي للتحويل.)

هل هناك طريقة ذكية لتنفيذ هذه الوظيفة التي لا أرىها؟

ديف هانسون واجهات 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;
}

للتفاهم الكامل، فإنه يساعد حقا في الحصول على الكتاب، ولكن مصدر الرمز لا يزال أسهل كثيرا لفهمه من شفرة مصدر جنو. ويمكنك بسهولة تكييفه لاستخدام قاعدة 10،000 (يستخدم حاليا قاعدة 256).

ملخص: إذا كان اختناق أدائك هو التحول إلى عشري، فينفع الحساب المتعدد مع قاعدة قوة 10. وبعد إذا كان حجم الكلمة الأصلية الخاصة بجهاز الجهاز هو 32 وتستخدم رمز C، استخدم 10000 في كلمة 16 بت.

Answer 2

إذا كانت قيمك أقل من ذلك ULLONG_MAX (18446744073709551615) سأحاول استخدامها sprintf(buf,"%llu",ullong_val). وبعد أراهن أن هذا أمر محسن جيدا في المكتبة القياسية، لكن تحليل التنسيق سيستغرق بعض الدورات.

خلاف ذلك كنت أنشئ bigint_divmod1000000000 (أو اسم أفضل اسم mod10to9) وظيفة واستخدام ذلك. سيحتاج إلى تقسيم 9 مرات أقل من bigint_divmod10.

Answer 3

Lookup Table of 8 بت. يمكنك الحصول على 4 طاولات بحث من 256 أرقام. الأول هو من 0-256 ل LSB بايتس، الجدول الثاني هو الجدول الأول مضروبة في 256 وما إلى ذلك.

لذلك عندما تحتاج إلى رقم رقمك من أرقام البحث عن طاولة البحث. عند إضافة، يمكنك إضافة كحنة وأذهب لاحقا عبر كل بايت لإصلاح Oirflows.

مثال رقم المثال 0x12345678 في طاولة البحث الأولى هناك ضمن Addres (0x78 = 120) لذلك 0x010200 هو الرقم الأول في الجدول الثاني تحت (0x56 = 87) هو 0x0202000106 (0x56 في ديسمبر هو 22016) في الجدول الثالث الذي سيكون لديك 0x03040007080702 وحضرا Lable في 0x12 لديك 0x030001090808080880808080808 (هذا لا يصلح في حساب 32 بت، لكنك تعرف)

ثم قم بتلخيص هذه الأرقام (كمساعدين ثنائيين) وتذهب بايت بايت بواسطة بايت لرمز الفائض في حلقة شيء مثل

s=carry+val[i];
val[i]=val[i]&10
carry=s/10; 
//you can put last two operations in table

إذا عدنا العمليات اللازمة لهذا.

1. (النظر في الجداول وإضافة) 4 طاولات البحث. 16 إضافات (ضع في اعتبارك أنه عندما لا تحتاج إلى تحمل حوالي owerflow، becuase لا يمكن أن OCUR)
2. تمرير واحد في كل خطوة 3 Operatins 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;
}

Answer 4

للمرجع المستقبلي، بدلا من تنفيذ نوع UINT128، استخدمت فقط أحرف السلسلة مباشرة. تحول هذا إلى أن يكون أسرع بكثير من الذهاب من سلسلة إلى UINT128 والعودة.

Answer 5

سيأتي أكثر سرعة السرعة الفورية من إبطال التحويل بدلا من الدعوة؛ يمكن أن يكون بسيطة مثل العلامات bigint_divmod10() في النسق, أو استخدام التحسين الموجه الشخصي على النحو الذي يقدمه برنامج التحويل البرمجي الخاص بك.

Answer 6

أعرف أن هذا السؤال قديم، لكنني أرغب في المساهمة حيث لا شيء يضع طريقة تجنب دورة التقسيم. هذا واحد يستخدم 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.