لماذا تربيع رقم أسرع من ضرب رقمين عشوائيين؟

Question

يضاعف رقمين ثنائيين يستغرق وقتًا في 2 ، ومع ذلك ، يمكن إجراء تربيع رقمًا أكثر كفاءة بطريقة أكثر. (مع وجود عدد من البتات) كيف يمكن أن يكون ذلك؟

أو هو غير ممكن؟ هذا هو الجنون!

Answer 1

1. توجد خوارزميات أكثر كفاءة من O (n^2) لضرب رقمين (انظر Karatsuba ، Pollard ، Schönhage -Strassen ، إلخ)

2. المشكلتان "ضربان رقمين N-bit التعسفي" و "مربع رقم N التعسفي" لهما نفس التعقيد.

نملك

4*x*y = (x+y)^2 - (x-y)^2

لذا ، إذا استغرق مرفق الأعداد الصحيحة N-bit وقت O (f (n)) ، فيمكن الحصول على منتج من أعداد صحيحة n-bit التعسفية في O (f (n)) أيضًا. (هذا هو 2x n-bit sums ، 2x n-bit المربعات ، 1x 2n-bit sum ، وتحول 1x 2n-bit)

ومن الواضح أن لدينا

x^2 = x * x

لذلك إذا كان ضرب اثنين من الأعداد الصحيحة n-bit يأخذ O (f (n)) ، فإن تربيع عدد صحيح n-bit يمكن القيام به في o (f (n)).

يوفر أي خوارزمية حساب المنتج (RESP The Square) خوارزمية لحساب المربع (RESP للمنتج) بنفس التكلفة غير المقارب.

كما لوحظ في إجابات أخرى ، يمكن تبسيط الخوارزميات المستخدمة للضرب السريع في حالة التربيع. سيكون المكسب ثابتًا أمام F (N) ، وليس على F (n) نفسه.

Answer 2

قد يكون تربيع رقم N أسرع من ضرب رقمين عشوائيين N. googling وجدت هذه المقالة. إنه يتعلق بحساب الدقة التعسفية ولكنه قد يكون ذا صلة بما يسألك. في ذلك ، يقول المؤلفون هذا:

في تربيع عدد صحيح كبير ، أي x^2 = (Xn-1 ، Xn-2 ، ... ، x1 ، x0)^2 العديد من مصطلحات المنتجات المتقاطعة للشكل Xi * xj و xj * xi متكافئ. يجب أن يتم حسابها مرة واحدة فقط ثم غادروا تحولت حتى تتضاعف. يتم إجراء عملية تربيع من الرقم N باستخدام مضاعفات محددة أحادية (N^2 + N)/2.

Answer 3

كما أشار الآخرون ، يمكن أن يكون التربيع حوالي 1.5x أو 2x أسرع من الضرب العادي بين الأرقام التعسفية. من أين تأتي الميزة الحسابية؟ إنه تناظر. دعنا نحسب مربع 1011 وحاول اكتشاف نمط يمكننا استغلاله. u0:u3 تمثل البتات في الرقم من الأكثر أهمية إلى الأقل أهمية.

    1011 //                               u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
   1011  //                     u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3       
  0000   //           u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3                 
 1011    // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3                           

إذا كنت تفكر في العناصر ui * ui ل i=0, 1, ..., 4 لتشكيل قطري وتجاهلها ، سترى أن العناصر ui * uj ل i ≠ j تتكرر مرتين.

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

Answer 4

أعتقد أنك قد تشير إلى الأسعار عن طريق التربيع . لا تستخدم هذه التقنية للضرب ، ولكن للرفع إلى Power X^n ، حيث قد تكون N كبيرة. بدلاً من مضاعفة X Times نفسها في الأوقات ، يقوم المرء بسلسلة من التربيع وإضافة العمليات التي يمكن تعيينها إلى التمثيل الثنائي لـ N. يتم تقليل عدد عمليات الضرب (والتي تكون أغلى من الإضافات للأعداد الكبيرة) من n إلى n سجل (ن) فيما يتعلق بخوارزمية الأسس الساذجة.

Answer 5

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

Answer 6

انا أملكه!

2 * 2

أغلى من

2 << 1

(التحذير كونه يعمل فقط لحالة واحدة.)

Answer 7

لنفترض أنك تريد توسيع الضرب (a+b)×(c+d). ينقسم إلى أربعة مضاعفات فردية: a×c + a×d + b×c + b×d.

ولكن إذا كنت تريد التوسع (a+b)², ثم يحتاج فقط إلى ثلاثة مضاعفات (ومضاعفة): a² + 2ab + b².

(لاحظ أيضًا أن اثنين من الضربات هي نفسها مربعات.)

نأمل أن يبدأ هذا فقط في إعطاء نظرة ثاقبة لبعض السرعات الممكنة عند أداء مربع على الضرب العادي.

Answer 8

بادئ ذي بدء سؤال رائع! أتمنى أن يكون هناك المزيد من الأسئلة مثل هذا.

لذلك اتضح أن الطريقة التي توصلت إليها هي O (n log n) للضرب العام في التعقيد الحسابي فقط. يمكنك تمثيل أي رقم X

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0

أين

x_i, y_i \in {0,1}

من ثم

XY = sum _ {k=0} ^ m+n r_k 2^k

أين

r_k = sum _ {i=0} ^ k x_i y_{k-i}

وهو مجرد تطبيق مستقيم للأمام لـ FFT للعثور على قيم R_K لكل k في وقت سجل (n + m) (n + m).

ثم لكل R_K ، يجب أن تحدد حجم الفائض الكبير وإضافته وفقًا لذلك. لتربيع رقم يعني o (n log n) علم الحساب عمليات.

يمكنك إضافة قيم R_K بشكل أكثر كفاءة باستخدام خوارزمية Schönhage -Strassen للحصول على عملية B (n log log n) Bit Bit.

تم نشر الإجابة الدقيقة على سؤالك بالفعل بواسطة إريك بينفيل.

ولكن هل تستطيع احصل على ملزمة أفضل بكثير من O (n^2) لتربيع رقم ببساطة لأن هناك حدود أفضل بكثير لضرب الأعداد الصحيحة!

Answer 9

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

بالنسبة للأعداد الصحيحة للطول التعسفي ، يكون الضرب عادةً O (n²) ولكن هناك خوارزميات تقلل من ذلك بالنسبة للأعداد الصحيحة الكبيرة.

إذا افترضت نهج O (n²) البسيط للضرب أ بواسطة ب, ، ثم لكل بت في أ عليك أن تتحول ب وأضفه إلى تراكم إذا كان هذا البت واحد. لكل بت في أ تحتاج 3N التحولات والإضافات.

لاحظ أن

( x - y )² = x² - 2 xy + y²

لذلك

x² = ( x - y )² + 2 xy - y²

إذا كان كل ذ هي أكبر قوة لا تزيد عن x ، وهذا يعطي انخفاضًا إلى مربع أقل ، وتحولان وإضافات. مثل ن يتم تقليله في كل تكرار ، قد تحصل على كسب الكفاءة (يعني التماثل أنه يزور كل نقطة في مثلث بدلاً من مستطيل) ، لكنه لا يزال O (n²).

قد يكون هناك تناظر أفضل آخر لاستغلاله.

Answer 10

a^2 (a+b)*(a+b)+b^2 eg. 66^2 = (66+6) (66-6)+6^2 = 72*60+36 = 4356

للحصول على^n فقط استخدم قاعدة الطاقة

66^4 = 4356^2

Answer 11

أرغب في حل المشكلة عن طريق الضرب

تكون البتات (N-1) A (N-2) ........ A (1) A (0).

B Bits B (N-1) B (N-2) ........ B (1) B (0).

بالنسبة إلى مربع الرقم A ، ستكون بتات الضرب الفريدة التي تم إنشاؤها لـ A (0)-> A (0) .... A (N-1) A (1)-> A (1) .... A ( N-1) وهكذا ستكون العمليات الكلية

op = n + n-1 + n-2 ....... + 1 لذلك op = n^2 + n/2 ؛ لذلك سيكون التدوين المقارب O (n^2)

وللتكاثر من مضاعفات A و B N^2 ، سيتم إنشاء مضاعفات فريدة من نوعها بحيث يكون التدوين المقارب O (N^2)

Answer 12

الجذر التربيعي 2^ن هو 2^{ن / 2} أو 2^{n >> 1}, ، لذلك إذا كان رقمك هو قوة اثنين من كل شيء بسيط تمامًا بمجرد معرفة القوة. أن يكون مضاعفة أبسط: 2⁴ * 2⁸ هو 2⁴⁺⁸. لا يوجد أي معنى في هذه العبارات التي قمت بها.

Answer 13

إذا كان لديك رقم ثنائي A ، فيمكنه (دائمًا ، دليل على القارئ المتحمس) التعبير عنه كـ (2^n + b) ، يمكن تربيتها كـ 2^2n + 2^(n + 1) b + b ^2. يمكننا بعد ذلك تكرار التوسع ، حتى تكون هذه النقطة التي تساوي صفر. لم أتطلع إلى ذلك بشدة ، لكن بشكل حدسي ، يبدو الأمر كما لو كنت قادرًا على جعل وظيفة التربيع تتخذ خطوات خوارزمية أقل من الضرب للأغراض العامة.

Answer 14

أعتقد أنك مخطئ تمامًا في بياناتك

ضرب رقمين ثنائيين يأخذ n^2 الوقت

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

yet squaring a number can be done more efficiently somehow.

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

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