بيثون طويل الضرب

Question

أنا في حاجة إلى خوارزمية أسرع من الضرب الطويل الثيانية الطبيعي الحالي.

حاولت العثور على تنفيذ Karatsuba لائق، لكنني لا أستطيع ذلك.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

كما تراه، لا شيء معقد، فقط عدد قليل من الضربات. ولكن عليها التعامل مع الأرقام مع ما يصل إلى 100000 أرقام في أقل من 2.5 ثانية.

أود بعض القصاصات من وظيفة أو مجرد رابط لبعض تنفيذ وظيفة الضرب أسرع، أو أي شيء يساعد.

Answer 1

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

Answer 2

أنا مؤلف مكتبة Decint (عدد صحيح عشري) لذلك سأقدم بعض التعليقات.

تم تصميم مكتبة DESINT على وجه التحديد للعمل مع أعداد صحيحة كبيرة جدا تحتاج إلى تحويلها إلى تنسيق عشري. المشكلة مع التحويل إلى التنسيق العشري هي أن معظم المكتبات التعسفية الدقة تخزن القيم في ثنائي. هذا هو الأسرع والأكثر كفاءة لاستخدام الذاكرة ولكن التحويل من ثنائي إلى عشري عادة ما يكون بطيئا. يستخدم Python's Binary للتحويل العشري خوارزمية o (n ^ 2) ويحصل ببطء بسرعة كبيرة.

يستخدم DESINT RADIX عشري كبير (عادة 10 ^ 250) ويخزن عدد كبير جدا في كتل من 250 رقما. تحويل عدد كبير جدا إلى التنسيق العشري يعمل الآن في O (N).

الساذج، أو المدرسة الدراسية، الضرب لديه وقت تشغيل O (N ^ 2). يستخدم Python الضرب Karatsuba الذي يحتوي على وقت تشغيل O (N ^ 1.585). يستخدم DESINT مزيجا من Caratsuba و Cook-Cook و Nussbaumer Confolution للحصول على وقت تشغيل O (N * LN (N)).

على الرغم من أن Decint يحتوي على أعلى مستوى كبير، فإن مزيج من الضرب O (N * LN (N)، سيكون التحويل O (N) أسرع في النهاية من الضرب أو تحويل Python's O (N ^ 1.585) و O (N ^ 2).

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

أنا سعيد لأنك وجدت ديكور مفيدة.

Answer 3

15.9 مللي ثانية على جهاز الكمبيوتر المحمول البطيء. إنها الطباعة التي تبطئك. التحويل إلى الأرقام الثنائية إلى العشرية بطيئة للغاية، وهي خطوة مطلوبة من الطباعة بها. إذا كنت بحاجة إلى إخراج الرقم، فيجب أن تجرب Decint Christophed المذكورة بالفعل.

سوف يكون الترمط أبطأ في القيام بضرب ولكن جعل الطباعة أسرع بكثير

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

هنا مثال مع إصدار تعديل قليلا من التعليمات البرمجية الخاصة بك. لاحظ أن تحويل سلسلة 100000 رقما إلى فترة طويلة يأخذ بالفعل ~ 1SEC على هذا الكمبيوتر

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

Answer 4

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