التعسفي-الدقة الحسابية تفسير

Question

أنا أحاول أن أتعلم C و قد تأتي عبر عدم القدرة على العمل مع أعدادا كبيرة حقا (أي 100 أرقام, أرقام 1000 ، إلخ.).أنا على علم بأن هناك المكتبات للقيام بذلك ، ولكن أريد أن محاولة تنفيذ ذلك بنفسي.

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

Answer 1

انها كل مسألة تخزين كافية و خوارزميات لعلاج أرقام أجزاء أصغر.دعونا نفترض أن لديك مترجم في int يمكن أن يكون إلا من 0 إلى 99 كنت ترغب في التعامل مع الأرقام تصل إلى 999999 (سوف تقلق فقط عن أرقام إيجابية هنا أن يبقيه بسيط).

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

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

بالإضافة إلى ذلك على سبيل المثال: 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

العمل من الأقل أهمية الغاية:

• الأولي حمل = 0.
• 56 + 78 + 0 حمل = 134 = 34 1 حمل
• 34 + 00 + 1 حمل = 35 = 35 مع 0 حمل
• 12 + 00 + 0 حمل = 12 = 12 مع 0 حمل

هذا هو في الواقع كيف ذلك عموما يعمل على مستوى البت داخل وحدة المعالجة المركزية الخاصة بك.

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

لقد كتبت بالفعل المكتبات تفعل هذه الاشياء باستخدام الحد الأقصى من القوى العشرة التي يمكن أن تناسب عدد صحيح عند تربيع (لمنع فيضان عندما ضرب اثنين ints معا ، مثل 16-بت int يجري محدود إلى 0 إلى 99 لتوليد 9,801 (<32,768) عندما المربعة, أو 32 بت int باستخدام 0 من خلال 9,999 لتوليد 99,980,001 (<2,147,483,648)) والتي خففت كثيرا من الخوارزميات.

بعض الحيل لمشاهدة ل.

1/ عند إضافة أو ضرب الأرقام ، قبل تخصيص أقصى قدر من المساحة المطلوبة ثم خفض في وقت لاحق إذا كنت تجد أنه كثيرا.على سبيل المثال ، إضافة اثنين من 100-"أرقام" (حيث الرقم هو int) أرقام لن تعطيك أكثر من 101 أرقام.تتضاعف 12 رقم من 3 أرقام لن تولد أكثر من 15 خانة (إضافة الرقم التهم).

2/ لمزيد من سرعة تطبيع (تقليل التخزين المطلوبة) الأرقام إلا في حالة الضرورة القصوى - مكتبتي كان هذا بمثابة دعوة منفصلة بحيث يمكن للمستخدم أن تقرر بين السرعة والتخزين المخاوف.

3/ إضافة الإيجابية والسلبية رقم الطرح, طرح عدد سالب هو نفس مضيفا ما يعادل إيجابية.يمكنك حفظ قدرا كبيرا من التعليمات البرمجية من خلال وجود وطرح أساليب الاتصال ببعضهم البعض بعد ضبط علامات.

4/ تجنب طرح الأعداد الكبيرة من الصغيرة منها منذ كنت دائما في نهاية المطاف مع أرقام مثل:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

بدلا من طرح 10 من 11 ، ثم ينفي ذلك:

11
10-
--
 1 (then negate to get -1).

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

بالنسبة إضافة, إذا علامات مختلفة ، استخدام الطرح نفي:

-a +  b becomes b - a
 a + -b becomes a - b

بالنسبة الطرح, إذا علامات مختلفة ، استخدام إضافة النفي:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

أيضا معالجة خاصة لضمان نحن طرح أعداد صغيرة من كبيرة:

small - big becomes -(big - small)

الضرب يستخدم مستوى الدخول الرياضيات على النحو التالي:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

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

ShiftLeft و ShiftRight عمليات تستخدم بسرعة مضاعفة أو تقسيم LongInt قبل التفاف القيمة (10 ل "ريال مدريد" الرياضيات).في المثال أعلاه, نضيف 475 إلى الصفر 2 مرات (اخر رقم 32) للحصول على 950 (النتيجة = 0 + 950 = 950).

ثم غادرنا التحول 475 للحصول على 4750 و حق التحول 32 الحصول على 3.إضافة 4750 إلى الصفر 3 مرات للحصول على 14250 ثم يضاف إلى نتيجة 950 للحصول على 15200.

Shift الأيسر 4750 للحصول على 47500, صحيح تحول 3 إلى 0.لأن حق تحول 32 هو الآن صفر انتهينا و في الواقع 475 × 32 لا تساوي 15200.

شعبة هو أيضا صعبة ولكن على أساس الحسابية في وقت مبكر (في "gazinta" طريقة "يذهب إلى").النظر في ما يلي طويلة شعبة 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

لذلك 12345 / 27 هو 457 مع ما تبقى 6.التحقق من:

  457 x 27 + 6
= 12339    + 6
= 12345

هذا هو تنفيذها باستخدام السحب المتغير (في البداية صفر) لاسقاط قطاعات 12345 واحد في كل مرة حتى أنه أكبر من أو تساوي 27.

ثم نحن ببساطة طرح 27 من هذا حتى نصل أدناه 27 - عدد من الطرح هو الجزء إضافة إلى السطر العلوي.

عندما لا يكون هناك المزيد من شرائح لاسقاط لدينا النتيجة.

---

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

فإنه لا يكون بدلا من المؤسف misfeature في أنه سوف ببساطة الخروج إذا نفدت الذاكرة (بدلا فادح لغرض عام المكتبة في رأيي) ولكن إذا كنت يمكن أن ننظر إلى الماضي ، انها جيدة جدا في ما يفعل.

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

لقد وجدت أيضا أن مجالس الإدارة في MPIR (شوكة GMP) هي أكثر قابلية المناقشات حول التغييرات المحتملة - يبدو أنهم أكثر المطور-مجموعة ودودة.

Answer 2

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

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

      123
    x  34
    -----
      492
+    3690
---------
     4182

ولكن هذه الطريقة بطيئة للغاية (O (ن ^ 2)، ن يكون عدد الأرقام). بدلا من ذلك، حزم bignum الحديثة تستخدم إما تحويل فورييه المنفصل أو الرقمية تحويل لتحويل هذا إلى ((ن) ن قانون الجنسية) عملية أساسا O.

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

إذا كنت ترغب بعض الخلفية النظرية، وأنا أوصي قراءة الفصل الأول من كتابه ياب، و<لأ href = "http://cs.nyu.edu/yap/book/berlin/" يختلط = "noreferrer" > "مشاكل أساسية من حسابي الجبر" . كما سبق ذكره، المكتبة برنامج الرصد العالمي bignum هي مكتبة ممتازة. للأرقام الحقيقية، لقد استعملت mpfr ويرضوا.

Answer 3

ولا إعادة اختراع العجلة: قد تتحول إلى أن تكون الساحة!

استخدم مكتبة طرف ثالث، مثل GNU MP ، وهذا هو تجريب واختبار.

Answer 4

يمكنك أن تفعل ذلك في الأساس بنفس الطريقة التي كنت تفعل مع ورقة و قلم رصاص...

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

يمكنك عادة استخدام الوحدة الأساسية من حساب

• بايت تحتوي مع 0-99 أو 0-255
• 16 بت الكلمات contaning تذبل 0-9999 أو 0--65536
• 32 بت الكلمات التي تحتوي على...
• ...

كما تمليه الهندسة.

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

Answer 5

ويمكنك أن تفعل ذلك مع مستوى المدارس الثانوية في الرياضيات. على الرغم من أن تستخدم المزيد من خوارزميات متقدمة في الواقع. هكذا على سبيل المثال إضافة رقمين 1024 بايت:

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

والنتيجة سوف يجب أن تكون أكبر من one place في حالة إضافة إلى رعاية القيم القصوى. انظر في هذا:

9
   +
9
----
18

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

وإشارة جيدة حول هذا الموضوع هي التعقيد الحسابي العمليات الرياضية . فإنه يقول لك مقدار المساحة المطلوبة لكل عملية تريد تطبيق. على سبيل المثال، إذا كان لديك رقمين N-digit، فأنت بحاجة 2N digits لتخزين نتيجة الضرب.

وعلى وقال ميتش ، أو أنها حتى الآن ليست مهمة سهلة لتنفيذ! أنصحك أن نلقي نظرة على TTMath إذا كنت تعرف C ++.

Answer 6

واحد من المراجع في نهاية المطاف (IMHO) هو نث TAOCP المجلد الثاني. وهذا ما يفسر الكثير من خوارزميات لتمثيل الأرقام والعمليات الحسابية على هذه التأكيدات.

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Answer 7

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

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

• متجر علامة بت على حدة.

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

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

• حتى عندما قمت بتخزين أرقام كسلسلة الفردية الأرقام العشرية شعبة (أيضا وزارة الدفاع/rem ops) يمكن القيام به للحصول على ما يقرب من 13 الأرقام العشرية في النتيجة.هذا هو أكثر كفاءة بكثير من الانقسام الذي يعمل على 1 فقط أرقام عشرية في وقت واحد.

• لحساب عدد صحيح قوة عدد صحيح ، حساب تمثيل ثنائي الأس.ثم استخدام المتكررة تربيع العمليات لحساب القوى حسب الحاجة.

• العديد من العمليات (العوملة ، بريماليتي الاختبارات ، إلخ.) سوف تستفيد من powermod العملية.أن عند حساب وزارة الدفاع(أ^ع ، ن) ، والحد من نتيجة mod N في كل خطوة من الأسي حيث p وقد تم التعبير عن ذلك في شكل ثنائي.غير حساب^p أولا ثم محاولة تقليل وزارة الدفاع N.

Answer 8

وهنا بسيط (ساذج) مثال فعلت في PHP.

وأنا نفذت "إضافة" و "ضرب" والتي تستخدم للحصول على مثال الأس.

http://adevsoft.com/simple-php -arbitrary الدقة، صحيح-كبير-الأسطوانات-سبيل المثال /

ورمز القصاصة

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}