توان باینری که به عنوان توان با مربع نیز شناخته می شود، یک الگوریتم قدرتمند است که برای محاسبه موثر توان های بزرگ اعداد استفاده می شود. این تکنیک به ویژه در زمینه های مختلف علوم کامپیوتر از جمله رمزنگاری، برنامه نویسی رقابتی و گرافیک کامپیوتری مفید است.

در این مقاله، مفهوم توان باینری را تحلیل می‌کنیم، نحوه عملکرد آن را درک می‌کنیم و آن را در کد پیاده‌سازی می‌کنیم.

توان باینری چیست؟

توان باینری روشی برای محاسبه \(a^n\) (a افزایش یافته به توان n) با استفاده از ضرب، به جای ضرب ساده \(O(n)\) است.

این بهبود قابل توجه در راندمان امکان محاسبه سریع توانهای بسیار بزرگ را حتی در هنگام کار با محاسبات مدولار فراهم می کند.

نمایی باینری چگونه کار می کند

ایده کلیدی پشت توان باینری این است که توان را به نمایش دودویی آن تقسیم کنیم و از ویژگی های توان برای ساده کردن محاسبه استفاده کنیم.

بیایید آن را مرحله به مرحله تجزیه کنیم:

توان n را به نمایش دودویی آن تبدیل کنید.

نتیجه را به صورت 1 و پایه را به صورت a مقدار دهی اولیه کنید.

در هر بیت از نمایش دودویی n از راست به چپ تکرار کنید: (a). اگر بیت فعلی 1 است، نتیجه را در پایه فعلی ضرب کنید. (ب). پایه را مربع کنید (در خودش ضرب کنید).

نتیجه نهایی را برگردانید.

برای مثال، بیایید \(3^{13}\) را محاسبه کنیم:

13 را به باینری تبدیل کنید: \(13_{10} = 1101_2\)

مقدار اولیه = 1، پایه = 3

از طریق بیت ها تکرار کنید:

بیت 1: نتیجه = \(1 *3 = 3\) ، پایه = \(3 *3 = 9\)

بیت 0: نتیجه = 3، پایه = \(9 * 9 = 81\)

بیت 1: نتیجه = \(3 *81 = 243\) ، پایه = \(81 *81 = 6561\)

بیت 1: نتیجه = \(243 * 6561 = 1,594,323\)

پس ، \(3^{13}=1,594,323.\)

چرا نمایی باینری کارآمد است؟

کارایی توان باینری از دو عامل اصلی ناشی می شود:

تعداد ضرب‌های کاهش‌یافته : به‌جای انجام ضرب‌های n-1 مانند روش ساده، فقط ضرب‌های \(O(log n)\) را انجام می‌دهیم. این به این دلیل است که ما اساساً بر اساس نمایش دودویی توان، مسئله را به مسائل فرعی کوچکتر تقسیم می کنیم.

استفاده مجدد از محاسبات قبلی : با مربع کردن پایه در هر مرحله، از نتایج محاسبات قبلی مجددا استفاده می کنیم که به طور قابل توجهی تعداد کلی عملیات مورد نیاز را کاهش می دهد.

برای نشان دادن این کارایی، محاسبه \(a^{1000000}\) را در نظر بگیرید. روش ساده به 999999 ضرب نیاز دارد، در حالی که توان باینری فقط به حدود 20 ضرب نیاز دارد (به عنوان \(\log_2(1000000) \تقریباً 20\)).

پیاده سازی الگوریتم

بیایید الگوریتم توان باینری را در پایتون پیاده سازی کنیم:

 def binary_exponentiation ( base, exponent ): result = 1 while exponent > 0 : # If the current bit is 1, multiply the result by the current base if exponent & 1 : result *= base # Square the base base *= base # Move to the next bit exponent >>= 1 return result # Example usage print(binary_exponentiation( 3 , 13 )) # Output: 1594323

بیایید الگوریتم را تجزیه کنیم:

result به 1 مقداردهی می کنیم که هویت ضرب است.

ما از یک حلقه while برای تکرار استفاده می کنیم تا زمانی که توان ۰ شود.

دیگر اخبار

نحوه ایجاد یک سیستم ذخیره سازی فایل غیرمتمرکز با Go را بیاموزید




ما تحلیل می کنیم که آیا کمترین بیت قابل توجه توان 1 با استفاده از عملگر بیتی AND & . اگر اینطور باشد، نتیجه را در پایه فعلی ضرب می کنیم.

پایه را با ضرب در خودش مربع می کنیم.

برای انتقال به بیت بعدی توان از عملگر shift سمت راست >>= استفاده می کنیم.

در نهایت نتیجه را برمی گردانیم.

تحلیل پیچیدگی زمانی

پیچیدگی زمانی توان باینری \(O(log n)\) است که در آن n توان است. این به این دلیل است که:

تعداد بیت ها در نمایش باینری n \(\lfloor \log_2 n\rfloor + 1\ است.

ما حداکثر دو ضرب را در هر بیت انجام می دهیم (یکی برای مربع کردن پایه، و به طور بالقوه یکی برای به روز رسانی نتیجه).

پس ، تعداد کل ضرب‌ها حداکثر \(2(\lfloor \log_2 n \rfloor + 1)\) است که به \(O(\log n)\) ساده می‌شود.

نمونه مسائل و راه حل ها

بیایید به برخی از مسائل الگوریتمی که می‌توانید با استفاده از توان باینری به طور موثر حل کنید، همراه با توضیحات مفصل در مورد راه‌حل‌ها و نحوه رسیدن به استفاده از توان باینری نگاهی بیاندازیم.

مسئله 1: توان مدولار

مشکل : محاسبه \(3^{1000000} \bmod 1000000007\).

رویکرد :

ما تشخیص می دهیم که این مشکل شامل یک توان بسیار بزرگ (1000000) است که محاسبه آن با استفاده از توان ساده غیرعملی است.

همچنین متوجه می‌شویم که باید مدول نتیجه را یک عدد اول بزرگ (1000000007) پیدا کنیم.

این ترکیب یک توان بزرگ و محاسبات مدولار نشانگر واضحی است که باید از توان باینری مدولار استفاده کنیم.

راه‌حل : تابع توان باینری خود را طوری تغییر می‌دهیم که محاسبات مدولار را شامل شود:

 def mod_binary_exponentiation ( base, exponent, mod ): result = 1 base %= mod while exponent > 0 : if exponent & 1 : result = (result * base) % mod base = (base * base) % mod exponent >>= 1 return result print(mod_binary_exponentiation( 3 , 1000000 , 1000000007 )) # Output: 624098969

توضیح :

ما result به 1 مقداردهی اولیه می کنیم و base روی base % mod قرار می دهیم تا مواردی را که پایه اولیه بزرگتر از مدول است رسیدگی کنیم.

حلقه اصلی مشابه الگوریتم توان دودویی اصلی کار می کند، اما با دو تفاوت کلیدی:

الف هنگام به روز رسانی result ، ما (result * base) % mod انجام می دهیم. این تضمین می کند که result هرگز از mod تجاوز نمی کند، از سرریز اعداد صحیح جلوگیری می کند و نتیجه ماژولار صحیح را حفظ می کند.

ب هنگام مربع کردن base ، ما (base * base) % mod به همین دلیل انجام می دهیم.

عملیات بیتی ( exponent & 1 و exponent >>= 1 ) دقیقاً مانند الگوریتم اصلی کار می کند و به ما امکان می دهد نمایش دودویی توان را به طور موثر پردازش کنیم.

با اعمال عملیات مدول در هر مرحله، اطمینان حاصل می کنیم که تمام نتایج میانی در محدوده [0، mod-1] باقی می مانند. این به دلیل ویژگی های محاسبات مدولار امکان پذیر است:

$$(a⋅b)modm=((amodm)⋅(bmodm))modm$$

بیشتر بخوانید

هیوندای اینستر در هلند عرضه می‌شود، خودرو کوچک کره‌ای‌ها به دنبال فتح بازار قاره سبز

حل این مشکل با توان ساده به دلیل نتیجه عظیم غیرممکن خواهد بود، اما توان باینری مدولار آن را با نگه داشتن همه نتایج میانی قابل مدیریت می کند.

مسئله 2: توان ماتریس

مشکل : با توجه به یک ماتریس 2x2 A، An را محاسبه کنید که n = 1000000 باشد.

رویکرد :

مشاهده می کنیم که باید یک ماتریس را به توان بسیار بزرگ (1000000) برسانیم.

ضرب ماتریس تداعی است، که به ما امکان می دهد از همان اصل قدرت باینری برای اعداد استفاده کنیم.

ما تشخیص می دهیم که این یک سناریوی عالی برای اعمال توان باینری به ماتریس ها است.

راه حل : می توانیم از توان باینری روی ماتریس ها استفاده کنیم. در اینجا پیاده سازی پایتون با توضیحات است:

 import numpy as np def matrix_multiply ( A, B, mod ): return np.array([[(A[ 0 ][ 0 ]*B[ 0 ][ 0 ] + A[ 0 ][ 1 ]*B[ 1 ][ 0 ]) % mod, (A[ 0 ][ 0 ]*B[ 0 ][ 1 ] + A[ 0 ][ 1 ]*B[ 1 ][ 1 ]) % mod], [(A[ 1 ][ 0 ]*B[ 0 ][ 0 ] + A[ 1 ][ 1 ]*B[ 1 ][ 0 ]) % mod, (A[ 1 ][ 0 ]*B[ 0 ][ 1 ] + A[ 1 ][ 1 ]*B[ 1 ][ 1 ]) % mod]]) def matrix_power ( A, n, mod ): result = np.eye( 2 , dtype=int) while n > 0 : if n & 1 : result = matrix_multiply(result, A, mod) A = matrix_multiply(A, A, mod) n >>= 1 return result A = np.array([[ 1 , 1 ], [ 1 , 0 ]]) n = 1000000 mod = 1000000007 result = matrix_power(A, n, mod) print(result) # Output: [[690749268 297612485] # [297612485 393136783]]

توضیح :

matrix_multiply(A, B, mod) :

این تابع ضرب ماتریسی دو ماتریس 2x2 A و B را انجام می دهد.

هر عنصر از ماتریس به دست آمده با استفاده از فرمول ضرب ماتریس استاندارد محاسبه می شود و به دنبال آن یک عملیات مدول برای حفظ مقادیر قابل مدیریت است.

matrix_power(A, n, mod) :

این تابع توان باینری را برای ماتریس ها پیاده سازی می کند.

ما با result به عنوان ماتریس هویت 2x2 (ایجاد شده با استفاده از np.eye(2, dtype=int) ) شروع می کنیم.

حلقه اصلی از همان الگوی قدرت باینری اسکالر پیروی می کند: a. اگر بیت فعلی n 1 باشد، result در جریان A ضرب می کنیم. ب A را مربع می کنیم (با ضرب آن در خودش). ج n را به سمت راست تغییر می دهیم تا به بیت بعدی برویم.

همه ضرب‌های ماتریس با استفاده از تابع matrix_multiply انجام می‌شوند که محاسبات مدولار را در خود جای داده است.

این تکنیک توان ماتریسی به ویژه برای حل روابط عود خطی در زمان لگاریتمی قدرتمند است، همانطور که در اینجا با دنباله فیبوناچی نشان داده شده است.

مشکلات تمرین

در اینجا چند مشکل برای حل آنها با استفاده از توان باینری وجود دارد:

توان مدولار : \(7^{1234567} \bmod 1000000009\) را محاسبه کنید. (نکته: از تابع mod_binary_exponentiation از مسئله 1 در مثال ها استفاده کنید.)

آخرین رقم : رقم آخر را پیدا کنید. (نکته: الگوی آخرین ارقام توان های 2 را مشاهده کنید و از توان باینری با مدول 10 استفاده کنید.)

برج برق : 3 رقم آخر \(2^{2^{20}}\) را محاسبه کنید. (نکته: از خاصیت حساب مدولار استفاده کنید که \(a^b \bmod m = a^{b \bmod \phi(m)} \bmod m\) که \(\phi\) تابع totient اویلر است. شما' ابتدا باید \(2^{20} \bmod \phi(1000)\) محاسبه شود.)

زنجیره های ماتریس : با توجه به یک ماتریس 2x2 A = [[1, 2], [3, 4]]، دو رقم آخر مجموع همه عناصر در \(A^{1000000}\) را محاسبه کنید. (نکته: مانند مسئله 2 از مثال ها از توان ماتریس استفاده کنید، اما فقط دو رقم آخر هر عنصر را دنبال کنید. باید عناصر را پس از توان نهایی جمع کنید.)

دنباله فیبوناچی : 1000000 امین مدول عدد فیبوناچی 1000000007 را بیابید. (نکته: از شکل ماتریس دنباله فیبوناچی ([[1, 1], [1, 0]] استفاده کنید) و قدرت ماتریس را همانطور که در مسئله 2 از مثال ها نشان داده شده است اعمال کنید. )

نتیجه گیری

توان باینری یک تکنیک قدرتمند است که می تواند برای طیف گسترده ای از مسائل مربوط به توان های بزرگ اعمال شود. همانطور که در مثال ها و مسائل تمرینی دیدیم، به ویژه در محاسبات مدولار، عملیات ماتریس و حل روابط تکراری مفید است.

با تمرین این مشکلات، درک عمیق تری از نحوه اعمال قدرت باینری در سناریوهای مختلف به دست خواهید آورد. به یاد داشته باشید، نکته کلیدی این است که تشخیص دهید چه زمانی یک مشکل شامل بالا بردن چیزی به یک قدرت بزرگ است، خواه یک عدد، یک ماتریس یا حتی ساختار پیچیده‌تر باشد.

اگر این توضیح در مورد الگوریتم نمایی دودویی برای شما مفید بود، ممکن است از آموزش‌های برنامه‌نویسی و مفاهیم عمیق‌تری که در وبلاگم پوشش می‌دهم لذت ببرید.

خبرکاو