خوارزمية لتقسيم أعداد كبيرة جدا

Question

أحتاج إلى كتابة خوارزمية (لا يمكنني استخدام أي مكتبة طرف ثالثة ، لأن هذه مهمة) لتقسيم (تقسيم عدد صحيح ، الأجزاء العائمة ليست مهمة) أعداد كبيرة جدًا مثل 100 - 1000 رقم. وجدت http://en.wikipedia.org/wiki/fourier_division الخوارزمية لكنني لا أعرف ما إذا كان هذا هو الطريق الصحيح للذهاب. هل لديك اي اقتراحات؟

1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end

Answer 1

Knuth ، Donald ، The Art of Computer Programming ، ISBN 0-201-89684-2 ، المجلد 2: خوارزميات ندوة ، القسم 4.3.1: الخوارزميات الكلاسيكية

Answer 2

أتصور أن تقسيم الطريقة "الطويلة" كما هو الحال في المدرسة الابتدائية سيكون طريقًا محتملًا. أفترض أنك تتلقى الرقم الأصلي كسلسلة ، لذا فإن ما تفعله هو تحليل كل رقم. مثال:

الخطوة 0:

   /-----------------
13 | 453453453435....

الخطوة 1: "كم مرة يذهب 13 إلى 4؟ 0

     0
   /-----------------
13 | 453453453435....

الخطوة 2: "كم مرة يذهب 13 إلى 45؟ 3

     03
   /-----------------
13 | 453453453435....
   - 39
     --
      6

الخطوة 3: "كم مرة يذهب 13 إلى 63؟ 4

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

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

Answer 3

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

if numerator is less than denominator then finish
shift denominator as far left as possible while it is still smaller than numerator
set bit in quotient for amount shifted
subtract shifted denominator from numerator
repeat
the numerator is now the remainder

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

من الصعب تنفيذ الانقسام الطويل لأن إحدى الخطوات في الانقسام الطويل هي التقسيم الطويل. إذا كان المقسوم INT ، فيمكنك القيام بتقسيم طويل إلى حد ما.

Answer 4

ربما يجب أن تجرب شيئًا مثل التقسيم الطويل ، ولكن باستخدام كلمات الكمبيوتر بدلاً من الأرقام.

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

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

Answer 5

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