الگوریتم تقسیم و حل

[yas1213]

الگوریتمی که عملیات زیر را انجام دهد:z=10^m
u divide z, u rem z,u*z
uعدد صحیح بزرگ و mعدد صحیح غیر منفی
divide خارج قسمت تقسیم
rem باقی مانده

[pesar irooni]

برای ضرب دو عدد روشی وجود داره بنام روش ضرب روسی که به این صورت کار میکنه:
ضرب کننده را مرتب تقسیم بر دو میکنیم تا به عدد 1 برسیم و همه رو تو یه ستون مینویسیم
سپس ضرب شونده رو در ستونی روبروی ضرب کننده مینویسیم تا یه جدول با دو ستون داشته باشیم و در هر مرحله ضرب شونده رادر 2 ضرب میکنیم (یعنی به راست شیفت میدیم)
سپس سطرهایی که در آن ضرب کننده عدد زوج است را از جدول حذف میکنیم و سطرهای باقیمانده در ستون ضرب شونده را با هم جمع میکنیم تا جواب به دست بیاد.
مثلا برای ضرب دو عدد 39 *18 که جواب 702 میشه داریم:

multiplier multiplicand result
39 18 18
19 36 36
9 72 72
4 144 00
2 288 00
1 576 576
---
702

[pesar irooni]

روش تقسیم و حل به ما میگوید که برای به توان رساندن یک عدد میتوان از روش زیر استفاده کرد تا اینکه یک عدد را مرتبا در خودش ضرب کنیم
مثلا باید توجه کنیم که 8^2 برابر است با 4^2 * 4^2
پس کافیست ما فقط 4^2 را محاسبه کنیم و تنها یک ضرب انجام دهیم و نیازی نیست که 8 بار 2 را در خودش ضرب کنیم. برای محاسبه 4^2 هم از همین روش استفاده میکنیم
رابطه بازگشتیش به صورت زیره:

a^n ={a^n/2 * (a^n/2) if n is even , a^n/2 * (a^n/2) * (a) if n is odd}
الگوریتمش هم به این صورت میشه:


def recPower(a, n):
// raises a to the int power
if n == 0 then
return 1
else
factor = recPower(a, n/2)
if n%2 == 0 then // n is even
return factor * factor
else // n is odd
return factor * factor * a

[yas1213]

سوال گفته z=10^m والگوریتمی که u*z را انجام بده کنار u یه چند تا صفر میاره!!!
و همینطور برای divide & rem !
ولی شما ضرب دو عدد بزرگ یا به توان رسوندنو گفتین!

[pesar irooni]

الگوریتم توان که فرقی نمیکنه پایه توان چی باشه. حالا شما 10 بزار!!!!

والگوریتمی که u*z را انجام بده کنار u یه چند تا صفر میاره!!!
منظورتون رو متوجه نمیشم. الگوریتم روسی که گفتم صحیح کار میکنه. شاید برنامه اش رو اشتباه نوشتی.
اما الگوریتمی که ضرب دو عدد رو حساب کنه به روش تقسیم و غلبه همون الگوریتم معروف ضرب دو چند جمله ای به روش تقسیم و حل که از مرتبه n^log3 یا n^1.58 هست.
به این صورت:
فرض میکنیم دو عدد A و B رو میخواهیم در هم ضرب کنیم و نصف سمت راست عدد A رو Ar و نصف سمت چپ اون رو Al مینامیم. مثلا عدد 4578 اینطوری میشه Al=45 و Ar=78
حالا با استفاده از فرمولهای زیر میتونیم دو عدد رو با 3 ضرب و 6 جمع و تفریق با اعدادی به نصف اندازه قبلی حساب کنیم.
اگه فرض کنیم عدد حاصل بصورت زیر باشه :

C(x) = A(x)*B(x)
C(x) = [Al(x) + Ar(x) * x^(n/2)]*[Bl(x) + Br(x) * X^(n/2)]
C(x) = Al * Bl + [Al * Br + Ar * Bl] * X^(n/2) + Ar * Br * X^(n)
حالا اگه فرض کنیم :


Rl = Al * Bl
Rm = Al * Br + Ar * Bl
Rr = Ar * Br
میتونیم جمله وسط عبارت C رو بصورت Rm - Rl - Rr بنویسیم که کلید اصلی این الگوریتمه؛ یعنی ما تونستیم از یک ضرب با استفاده چند تا جمع و تفریق صرف نظر کنیم:

Al * Br + Ar * Bl = Rm - Rl - Rr
و در نتیجه

C(x) = Rl(x) + [Rm(x) - Rl(x) - Rr(x)] * X^(n/2) + Rr(x) * X^(n)
که دارای فرمول بازگشتیه T(n) = 3 T(n/2) + O(n^2) میباشه.
مثال خیلی کمکمیکنه که راحت تر بفهمیم :

1234*5618 = (12 * 10^2 + 34) * (56 * 10^2 + 18)
= 12 * 56 * 10^4 + (46 * 74 - 12 * 56 - 34 * 18) * 10^2 + 34 * 18
حالا ضرب دو عدد چهار رقمی به 3 ضرب دو عدد دورقمی تبدیل شد که این اعداد دو رقمی هم به همین ترتیب ضرب میکنیم تا جواب بدست بیاد.

[djsohrab2007]

یعنی وقتی ما میزنیم 1000 / 5 کامپیوتر چه جوری این را حساب میکنه ؟
من میخوام یک برنامه بنویسم که دو عدد 30 رقمی را برهم تقسیم کنه ولی اونی که نوشتم برای حساب تقسیم 2 عدد 5 رقمی هم کلی فکر می کنه !!!!!! برای همین دنبال این هستم که ببینم کامپیوتر برای تقسیم چی تعریف کرده.
یک چیز دیگه :
می خوام عملیات ریاضی مثل توان رسوندن دو عدد 200 رقمی و یا ضرب و تقسیمشان را انجام بدم کسی راه حلی به ذهنش می رسه ؟
:عصبانی++:

[Mohammad_Has]

شما برای ضرب دو عدد با رقم های بیشتر از 12 رقم که قابل محاسبه واسه کامپیوتر و ماشین حساب نیست می تونین از روش دستی خودمون استفاده کنین. یعنی همون روشی که ما دو عدد رو روی کاغذ ضرب می کنیم رو با کمی تغییر که قابل پیاده سازی به صورت کد باشه رو استفاده کنین. من با اسمبلی یه برنامه نوشتم که به همین روش می تونه یک عدد 127 رقمی رو در یک عدد 128رقمی ضرب کنی و در آنی نتیجه رو نشون بده که نتیجش یک عدد 255 رقمی می شه. به راحتی می شه این مقدار رو هم افزایش داد.