كيف يمكنني إضافة وطرح أعداد صحيحة 128 بت في C أو C ++ إذا كان مترجمي لا يدعمها؟

Question

أنا أكتب ضاغطا لمسافة طويلة من أرقام 128 بت. أرغب في تخزين الأرقام كاختلافات - تخزين الفرق فقط بين الأرقام بدلا من الأرقام نفسها لأنني أستطيع حزم الاختلافات في عدد أقل من بايت لأنها أصغر.

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

أي شخص لديه أي أفكار للقيام بذلك بكفاءة؟

Answer 1

إذا كان كل ما تحتاجه هو الإضافة والطرح، ولديك بالفعل قيم 128 بت في النموذج الثنائي، قد تكون المكتبة مفيدة ولكنها غير ضرورية بدقة. هذه الرياضيات تافهة للقيام بنفسك.

لا أعرف ما يستخدمه برنامج التحويل البرمجي الخاص بك لأنواع 64 بت، لذلك سأستخدم iNT64 و UINT64 كميات صحيحة مدتها 64 بتوقة وغير موقعة.

class Int128
{
public:
    ...
    Int128 operator+(const Int128 & rhs)
    {
        Int128 sum;
        sum.high = high + rhs.high;
        sum.low = low + rhs.low;
        // check for overflow of low 64 bits, add carry to high
        if (sum.low < low)
            ++sum.high;
        return sum;
    }
    Int128 operator-(const Int128 & rhs)
    {
        Int128 difference;
        difference.high = high - rhs.high;
        difference.low = low - rhs.low;
        // check for underflow of low 64 bits, subtract carry to high
        if (difference.low > low)
            --difference.high;
        return difference;
    }

private:
    INT64  high;
    UINT64 low;
};

Answer 2

إلقاء نظرة على بخاصة.

#include <stdio.h>
#include <gmp.h>

int main (int argc, char** argv) {
    mpz_t x, y, z;
    char *xs, *ys, *zs;
    int i;
    int base[4] = {2, 8, 10, 16};

    /* setting the value of x in base 10 */
    mpz_init_set_str(x, "100000000000000000000000000000000", 10);

    /* setting the value of y in base 16 */
    mpz_init_set_str(y, "FF", 16);

    /* just initalizing the result variable */
    mpz_init(z);

    mpz_sub(z, x, y);

    for (i = 0; i < 4; i++) {
        xs = mpz_get_str(NULL, base[i], x);
        ys = mpz_get_str(NULL, base[i], y);
        zs = mpz_get_str(NULL, base[i], z);

        /* print all three in base 10 */
        printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);

        free(xs);
        free(ys);
        free(zs);
    }

    return 0;
}

الناتج هو

x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001

x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401

x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745

x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01

Answer 3

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

أولا، النطاق الموقع رقم 128 بت هو -2¹²⁷ إلى 2¹²⁷-1 وليس -2¹²⁷ إلى 2¹²⁷ كما ينص في الأصل.

ثانيا، نظرا للطبيعة الدورية للحسابات المحدودة أكبر تفاضل مطلوب بين رقمين 128 بت هو -2¹²⁷ إلى 2¹²⁷-1، والتي لديها شرط أساسي من 128 بت، وليس 129. على الرغم من (2¹²⁷-1) - (-2¹²⁷) = 2¹²⁸-1 من بوضوح أكبر من 2 كحد أقصى¹²⁷-1 عدد صحيح إيجابي، يضمن الفائض الحسابي دائما أن أقرب مسافة بين أي اثنين نأرقام البيت دائما تقع ضمن النطاق من 0 إلى 2^ن-1 وبالتالي ضمنيا -2^ن-1 إلى 2^ن-1-1.

من أجل توضيح ذلك، دعونا أولا فحص كيف سينفذ المعالج 3 بت افتراضي إضافة ثنائية. كمثال، فكر في الجدول التالي الذي يصور النطاق غير المائع غير المطلق من عدد صحيح 3 بت.

0 = 000B.
1 = 001b.
2 = 010b.
3 = 011b.
4 = 100b.
5 = 101b.
6 = 110b.
7 = 111B ---> [دورات العودة إلى 000B على تجاوز الفائض

من الجدول أعلاه، من الواضح بسهولة:

001b (1) + 010 (2) = 011b (3)

من الواضح أيضا أن تضيف أي من هذه الأرقام تكملة رقمية لها دائما^ن-1:

010b (2) + 101b ([تكملة 2] = 5) = 111b (7) = (2³-1)

بسبب تجاوز الفضاء الدوري الذي يحدث عند إضافة اثنين نأرقام -bit النتائج في (ن+1) ناتج، وبالتالي فإنه يتبع أن إضافة أي من هذه الأرقام مع تكمل رقمي + 1 ستؤدي دائما 0:

010b (2) + 110b ([تكملة 2] + 1) = 000B (0)

وبالتالي يمكننا أن نقول أن [تكملة ن] + 1 = -ن, ، لهذا السبب ن + [تكملة ن] + 1 = ن + (-ن) = 0. علاوة على ذلك، إذا كنا نعرف ذلك الآن ن + [تكملة ن] + 1 = 0، ثم ن + [تكملة ن - عاشر] + 1 يجب = ن - (ن-عاشر) = عاشر.

تطبيق هذا على غلة الجدول 3 بت الأصلي لدينا:

0 = 000B = [تكملة 0] + 1 = 0
1 = 001b = [تكملة 7] + 1 = -7
2 = 010b = [تكملة 6] + 1 = -6
3 = 011b = [تكملة 5] + 1 = -5
4 = 100B = [تكملة 4] + 1 = -4
5 = 101B = [تكملة 3] + 1 = -3
6 = 110B = [تكملة 2] + 1 = -2
7 = 111b = [تكملة 1] + 1 = -1 ---> [دورات العودة إلى 000B على تجاوز الفائض

ما إذا كانت التجريد التمثيلي إيجابي أو سلبي أو مزيج من الاثنين على حد سواء ضمنيا بحساب تكميلي تكملة موقعة، لدينا الآن 2^ن نأنماط البطل التي يمكن أن تخدم بسلاسة من 0 إلى 2^ن-1 والسلبي 0 إلى - (2^ن) -1 يتراوح كما هو مطلوب. في الواقع، تستخدم جميع المعالجات الحديثة مثل هذا النظام فقط من أجل تنفيذ دوائر Alu المشتركة لعمليات الإضافة والطرح. عندما يواجه وحدة المعالجة المركزية i1 - i2 تعليمات الطرح، فإنه يؤدي داخليا [تكمل + 1] تشغيل i2 وفي وقت لاحق يعالج المعاملات من خلال دائرة إضافة من أجل حساب i1 + [تكملة i2.

إذا طبقنا الجدول أعلاه إلى تسلسل الإدخال [-2^ن-1, 2^ن-1-1, -2^ن-1] كما قدم في رد Volte الأصلي، نحن قادرون الآن على حساب فرق مختلفة N

Diff # 1:
   (2^ن-1-1) - (-2^ن-1) =
   3 - (-4) = 3 + 4 =
(-1) = 7 = 111b

Diff # 2:
   (-2^ن-1) - (2^ن-1-1) =
   (-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b

بدءا من بذرةنا -2^ن-1, ، نحن قادرون الآن على إعادة إنتاج تسلسل الإدخال الأصلي من خلال تطبيق كل من مختلف الفرقات المذكورة أعلاه:

   (-2^ن-1) + (diff # 1) =
   (-4) + 7 = 3 =
   2^ن-1-1

   (2^ن-1-1) + (DIFF # 2) =
   3 + (-7) = (-4) =
   -2^ن-1

قد ترغب بالطبع في اعتماد نهج أكثر فلسفية لهذه المشكلة والتخمين حول السبب^ن الأرقام المتسلسلة بشكل صحيح تتطلب أكثر من 2^ن مختلف الفوارق المتسلسلة؟

taliadon.

Answer 4

يشمل Boost 1.53 الآن Multiprecision:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

// Requires Boost 1.53 or higher
// build: g++ text.cpp

int main()
{
    namespace mp = boost::multiprecision;

    mp::uint128_t a = 4294967296;
    mp::uint256_t b(0);
    mp::uint512_t c(0);

    b = a * a;
    c = b * b;

    std::cout << "c: " << c << "\n";
    return 0;
}

انتاج:

./a.out
c: 340282366920938463463374607431768211456

Answer 5

هناك الكثير من الأدبيات فيما يتعلق بالرياضيات الصحيحة الكبيرة. يمكنك استخدام إحدى المكتبات المتاحة بحرية (انظر الروابط) أو يمكنك تقويم خاصة بك. على الرغم من أنني يجب أن أحذرك، لأي شيء أكثر تعقيدا من الإضافة والطرح (والتحرر)، ستحتاج إلى استخدام الخوارزميات غير التافهة.

لإضافة وطرح، يمكنك إنشاء فئة / هيكل يحمل اثنين من الأعداد الصحيحة 64 بت. يمكنك استخدام الرياضيات المدرسية البسيطة للقيام بالإضافة والطرح. في الأساس، افعل ما تفعله بقلم رصاص وورقة لإضافة أو طرحه، مع دراسة حذرة لحمل / المقترض.

البحث عن عدد صحيح كبير. BTW الإصدارات الحديثة من VC ++، INTELC ++ ومجمعات الترجمة GCC لديها أنواع عدد صحيح 128 بت، على الرغم من أنني لست متأكدا من أنهم يمكن الوصول إليها بسهولة كما قد ترغب (يهدف إلى استخدامها باستخدام سجلات SSE2 / XMMS).

• http://en.wikipedia.org/wiki/arbitrary_precision_aritmetic.
• http://orion.math.iastate.edu/cbergman/crypto/bignums.html.
• http://www.mathgoodies.com/utorial/

Answer 6

tomsfastmath. هو قليلا مثل GMP (المذكورة أعلاه)، ولكنه هو المجال العام، وقد تم تصميمه من الأرض ليكون سريع للغاية (حتى يحتوي على تحسينات رمز التجميع ل X86 و X86-64 و ARM و SSE2 و PPC32 و AVR32).

Answer 7

تجدر الإشارة أيضا إلى ذلك: إذا كان الهدف هو مجرد تحسين ضغط دفق من الأرقام عن طريق معالجة مسبقا، فلن يتعين على الدفق المسبق مسبقا من الاختلافات الحسابية بالضبط. يمكنك استخدام XOR (^) بدلا من + و -. وبعد ميزة هي أن XOR 128 بت هي نفسها تماما مثل اثنين من XORs المستقلة على أجزاء 64 بت، لذلك فهي بسيطة وفعالة.