كيفية تنفيذ int كبير في C++

Question

أرغب في تنفيذ فصل دراسي كبير في لغة C++ كتمرين برمجة، وهو فصل يمكنه التعامل مع أرقام أكبر من عدد صحيح طويل.أعلم أن هناك العديد من التطبيقات مفتوحة المصدر موجودة بالفعل، لكني أرغب في كتابة تطبيقي الخاص.أحاول التعرف على النهج الصحيح.

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

أنا أبحث عن نهج عام ونصائح بدلاً من كود العمل الفعلي.

Answer 1

الأشياء التي يجب مراعاتها بالنسبة لفئة int كبيرة:

1. العوامل الرياضية:+، -، /، *، ٪ ، ٪ لا تنسى أن صفك قد يكون على جانبي المشغل ، وأن المشغلين يمكن أن يكونوا متسلقين ، وأن أحد المعاملات يمكن أن يكون int ، تعويم ، مزدوج ، إلخ ، إلخ.

2. مشغلي الإدخال/الإخراج:>> ، << هذا هو المكان الذي تكتشف فيه كيفية إنشاء فصولك بشكل صحيح من إدخال المستخدم ، وكيفية تنسيقه للإخراج أيضًا.

3. التحويلات/الممثلين:اكتشف الأنواع/الفئات التي يجب أن تكون فئة int الكبيرة قابلة للتحويل إليها ، وكيفية التعامل مع التحويل بشكل صحيح.ستشمل القائمة السريعة المزدوجة والتعويم ، وقد تشمل int (مع فحص الحدود المناسبة) والمعقدة (على افتراض أنه يمكنه التعامل مع النطاق).

Answer 2

تحدي ممتع.:)

أفترض أنك تريد أعدادًا صحيحة ذات طول تعسفي.أقترح النهج التالي:

خذ بعين الاعتبار الطبيعة الثنائية لنوع البيانات "int".فكر في استخدام عمليات ثنائية بسيطة لمحاكاة ما تفعله الدوائر الموجودة في وحدة المعالجة المركزية لديك عند إضافة أشياء.إذا كنت مهتمًا بمزيد من التعمق، ففكر في القراءة مقالة ويكيبيديا هذه عن المضافين النصفيين والمضافين الكاملين.ستفعل شيئًا مشابهًا لذلك، ولكن يمكنك النزول إلى هذا المستوى المنخفض - ولكن لكوني كسولًا، اعتقدت أنني سأتخلى عن ذلك وأجد حلاً أبسط.

ولكن قبل الخوض في أي تفاصيل خوارزمية حول الجمع والطرح والضرب، دعونا نجد بعض بنية البيانات.الطريقة البسيطة هي بالطبع تخزين الأشياء في ملف std::vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

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

ولكن الآن إلى بعض الخوارزميات حول العمل على الأرقام.يمكنك القيام بذلك على المستوى المنطقي، لكننا سنستخدم قوة وحدة المعالجة المركزية السحرية لحساب النتائج.لكن ما سنأخذه من الرسم التوضيحي المنطقي لـ Half- وFullAdders هو الطريقة التي يتعامل بها مع الحمل.على سبيل المثال، فكر في كيفية تنفيذ += عامل التشغيل.لكل رقم في BigInt<>::value_، يمكنك إضافة هذه الأرقام ومعرفة ما إذا كانت النتيجة تنتج شكلاً من أشكال الحمل.لن نقوم بذلك بطريقة حكيمة، ولكننا نعتمد على طبيعة BaseType لدينا (سواء كان طويلًا أو صحيحًا أو قصيرًا أو أيًا كان):يفيض.

بالتأكيد، إذا قمت بإضافة رقمين، فيجب أن تكون النتيجة أكبر من الرقم الأكبر من تلك الأرقام، أليس كذلك؟إذا لم يكن الأمر كذلك، فإن النتيجة فاضت.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

العملية الحسابية الأخرى تسير بشكل مماثل.تبا، يمكنك حتى استخدام وظائف stl std::plus وstd::minus وstd::times وstd::divides، ...، لكن انتبه إلى الحمل.:) يمكنك أيضًا تنفيذ الضرب والقسمة باستخدام عاملي الجمع والطرح، ولكن هذا بطيء جدًا، لأن ذلك سيؤدي إلى إعادة حساب النتائج التي حسبتها بالفعل في الاستدعاءات السابقة لعلامة الجمع والطرح في كل تكرار.هناك الكثير من الخوارزميات الجيدة المتاحة لهذه المهمة البسيطة، يستخدم ويكيبيديا أو الويب.

وبطبيعة الحال، يجب عليك تنفيذ عوامل التشغيل القياسية مثل operator<< (فقط قم بنقل كل قيمة في value_ إلى اليسار بمقدار n بت، بدءًا من value_.size()-1...اه وتذكر الحمل :), operator< - يمكنك أيضًا التحسين قليلاً هنا، من خلال التحقق من العدد التقريبي للأرقام size() أولاً.وما إلى ذلك وهلم جرا.ثم اجعل صفك مفيدًا، من خلال befriendig std::ostream operator<<.

نأمل أن يكون هذا النهج مفيدا!

Answer 3

وهناك قسم كامل على هذا: [فن برمجة الحاسوب، VOL.2: Seminumerical الخوارزميات، القسم 4.3 متعددة الدقة الحسابية، ص 265-318 (ED.3)]. قد تجد مواد أخرى مثيرة للاهتمام في الفصل 4، علم الحساب.

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

وتحد سؤال لك: كيف كنت تنوي اختبار التطبيق الخاص بك وكيف تقترح لإثبات أنه من الحساب هو الصحيح؟

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

والمتعة!

Answer 4

سوف

وبالإضافة إلى ذلك ربما يتعين القيام به في معيار خوارزمية الوقت الخطية
ولكن لتكاثر قد تتمكن من محاولة http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 5

وبمجرد أن يكون لديك أرقام من الرقم في صفيف، يمكنك أن تفعل الجمع والضرب تماما كما كنت تفعل لهم الكتابة العاديه.

Answer 6

لا تنس أنك لا تحتاج إلى تقييد نفسك ل0-9 كما الأرقام، أي بايت استخدامها أرقام (0-255) ويمكنك الاستمرار في القيام بعملية حسابية يد طويلة نفسه كما تفعل لأرقام عشرية. حتى انك تستطيع استخدام مجموعة من فترة طويلة.

Answer 7

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

وعلى سبيل المثال، إذا كان لديك بنية

typedef struct {
    int high, low;
} BiggerInt;

وبعد ذلك يمكنك تنفيذها يدويا العمليات المحلية في كل من "الأرقام" (ارتفاع وانخفاض، في هذه الحالة)، لأنها تدرك الظروف تجاوز:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

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

Answer 8

ومثل قال آخرون، أن تفعل ذلك على الطراز القديم طريقة يد طويلة، ولكن الابتعاد عن القيام بذلك فقط في قاعدة 10. فما استقاموا لكم فاستقيموا أقترح القيام بذلك فقط في قاعدة 65536، وتخزين الأشياء في مجموعة من صفقات الشراء.

Answer 9

استخدم الخوارزميات التي تعلمتها في 1 من خلال الصف 4th.
نبدأ مع عمود منها، ثم عشرات، وهكذا دواليك.

Answer 10

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

وكانت رقائق سلسلة موتورولا 68K هذا. ليس ذلك أنا بالمرارة أو أي شيء.

Answer 11

وبلدي بداية سيكون لديك مجموعة التعسفية الحجم من الأعداد الصحيحة، وذلك باستخدام 31 بت و32n'd كما تجاوز.

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

وربما يكون هناك نهج أكثر تطورا. ولكن هذا سيكون نهج ساذج من المنطق الرقمي.

Answer 12

ويمكن محاولة تنفيذ شيء من هذا القبيل:

http://www.docjar.org/html/ المعهد / جافا / الرياضيات / BigInteger.java.html

وأنت كنت بحاجة 4 بت فقط لرقم واحد 0-9

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

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

وليس لدي أي اختبارات السرعة ولكن بالنظر إلى إصدار جافا من BigInteger يبدو أن تقوم به عدد ضخم من العمل.

وبالنسبة لي أن أفعل أدناه

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

Answer 13

وطرح 48 من سلسلة الخاص بك من عدد صحيح والطباعة للحصول على عدد من أرقام كبيرة. ثم تنفيذ العملية الحسابية الأساسية.    وإلا لكنت سوف تقدم حلا كاملا.