پیدا کردن الگوریتم برای ضرب اعداد چند هزار رقمی

[™Ali]

با سلام

شاید برای شما هم همواره این سوال پیش اومده وقتی که مقدار Decimal تعریف شده برای زبان برنامه نویسی (در اینجا سی شارپ) حداکثر مقدار 79228162514264337593543950335 رو میتونه بپذیره پس اگر بخواهیم مقادیر بالاتر رو به صورت عدد به دست بیاریم، باید چکار کنیم ؟ (توجه کنید که در اینجا Double به دلیل ساده کردن نتیجه به کار ما نمیاد!)

به طور مثال چگونه 100 فاکتوریل رو به دست بیاریم :



93326215443944152681699238856266700490715968264381 62146859296389521759999322991560894146397615651828 62536979208272237582511852109168640000000000000000 00000000
یا 1000 فاکتوریل که دارای 2568 رقم است:



40238726007709377354370243392300398571937486421071 46325437999104299385123986290205920442084869694048 00479988610197196058631666872994808558901323829669 94459099742450408707375991882362772718873251977950 59509952761208749754624970436014182780946464962910 56393887437886487337119181045825783647849977012476 63288983595573543251318532395846307555740911426241 74743493475534286465766116677973966688202912073791 43853719588249808126867838374559731746136085379534 52422158659320192809087829730843139284440328123155 86110369768013573042161687476096758713483120254785 89320767169132448426236131412508780208000261683151 02734182797770478463586817016436502415369139828126 48102130927612448963599287051149649754199093422215 66832572080821333186116811553615836546984046708975 60290095053761647584772842188967964624494516076535 34081989013854424879849599533191017233555566021394 50399736280750137837615307127761926849034352625200 01588853514733161170210396817592151090778801939317 81141945452572238655414610628921879602238389714760 88506276862967146674697562911234082439208160153780 88989396451826324367161676217916890977991190375403 12746222899880051954444142820121873617459926429565 81746628302955570299024324153181617210465832036786 90611726015878352075151628422554026517048330422614 39742869330616908979684825901254583271682264580665 26769958652682272807075781391858178889652208164348 34482599326604336766017699961283186078838615027946 59551311565520360939881806121385586003014356945272 24206344631797460594682573103790084024432438465657 24501440282188525247093519062092902313649327349756 55139587205596542287497740114133469627154228458623 77387538230483865688976461927383814900140767310446 64025989949022222176590433990188601856652648506179 97023561938970178600408118897299183110211712298459 01641921068884387121855646124960798722908519296819 37238864261483965738229112312502418664935314397013 74285319266498753372189406942814341185201580141233 44828015051399694290153483077644569099073152433278 28826986460278986432113908350621709500259738986355 42771967428222487575867657523442202075736305694988 25087968928162753848863396909959826280956121450994 87170124451646126037902930912088908694202851064018 21543994571568059418727489980942547421735824010636 77404595741785160829230135358081840096996372524230 56085590370062427124341690900415369010593398383577 79394109700277534720000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000



راه حل : با اعداد همانند String (رشته) کار می کنیم.

ادامه دارد...

[™Ali]

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

این الگوریتم رو من ننوشتم. ولی واقعا سرعت خوبی داره. گرچه هنوز جا واسه کار داره و سرعتش به اندازه ای که انتظار میره بالا نیست. با این الگوریتم مقدار 1000 فاکتوریل در 8 ثانیه به دست میاد.

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




int loop = 0;

private string Multiply(string a1, string a2)
{
int tmp1 = 0;
int hafeze = 0;
long maxL = 0;
long sabet = 100000;
string[] sum = new string[sabet];
for (int i = 1; i <= a2.Length; i++)
{
for (int i2 = 1; i2 <= a1.Length; i2++)
{
tmp1 = int.Parse(a2.Substring(int.Parse((a2.Length - i).ToString()), 1)) * int.Parse(a1.Substring(int.Parse((a1.Length - i2).ToString()), 1));
tmp1 += hafeze;
hafeze = 0;
if (tmp1 < 10)
{
if (sum[i - 1] == null) sum[i - 1] = "";
sum[i - 1] = sum[i - 1].Insert(0, tmp1.ToString());
}
else
{
if (i2 == a1.Length)
{
if (sum[i - 1] == null) sum[i - 1] = "";
sum[i - 1] = sum[i - 1].Insert(0, tmp1.ToString());
}
else
{
if (sum[i - 1] == null) sum[i - 1] = "";
sum[i - 1] = sum[i - 1].Insert(0, (tmp1 % 10).ToString());
hafeze = tmp1 / 10;
}
}
loop++;

}
//if (sum[i - 1].Length > maxL) maxL = sum[i - 1].Length;

}
//----------------------------------------------------------------------00000000000000000
string c = "0";
for (long i = 1; i < a2.Length; i++)
{
sum[i] += c;
c += "0";
loop++;
}
//----------------------------------------------------------------------00000000000000000

for (long i = 0; i < sabet; i++)
{
if (sum[i] != null)
{
if (sum[i].Length > maxL) maxL = sum[i].Length;
}
loop++;
}

//----------------------------------------------------------------------
string value = "";
for (int i = 1; i <= maxL; i++)
{
tmp1 = 0;
for (int i2 = 1; i2 < a2.Length + 1; i2++)
{
if (sum[i] != "")
{
if (sum[i2 - 1].Length - i >= 0) tmp1 += int.Parse(sum[i2 - 1].Substring(sum[i2 - 1].Length - i, 1));
tmp1 += hafeze;
hafeze = 0;
}
loop++;
}
if (tmp1 < 10)
{
value = value.Insert(0, tmp1.ToString());

}
else
{
if (i == maxL)
{
value = value.Insert(0, tmp1.ToString());
}
else
{
value = value.Insert(0, (tmp1 % 10).ToString());
hafeze = tmp1 / 10;
}
}
loop++;
}
//----------------------------------------------------------------------
return value;
}

[™Ali]

الگوریتم دوم رو خودم نوشتم.

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

1000 فاکتوریل رو در 9 ثانیه حساب میکنه بنابراین از الگوریتم اول کندتر هست. (البته فقط در حد یک ثانیه) ولی به نظرم از الگوریتم اول قابل فهم تر است و راحت تر می تونید در اون تغییراتی رو اعمال کنید.

به دلیل کمبود وقت هنوز بهینه سازی نهایی نشده. آخه دیروز این الگوریتم رو نوشتم و به دلیل آزمون راهنمایی و رانندگی عجله داشتم :D

Loop رو هم که توضیح دادم. چون در الگوریتم خودم واسه بررسی تعداد حلقه ها داشتم در الگوریتم قبلی هم وارد کردم.







int loop = 0;
private string NewMultiply(string num1, string num2)
{

ArrayList res = new ArrayList();
string mem, row;
int index = 0;

for (int mainIndex = num1.Length; mainIndex > 0; mainIndex--)
{
mem = "0";
row = "";

for (int subIndex = num2.Length; subIndex > 0; subIndex--)
{
string plus = ((int.Parse(num1[mainIndex - 1].ToString()) * int.Parse(num2[subIndex - 1].ToString()) + int.Parse(mem))).ToString();

if (plus.Length > 1)
{
mem = plus.Substring(0, 1);
row = row.Insert(0, plus.Substring(1, 1));

}

else
{
row = row.Insert(0, plus);
mem = "0";
}
loop++;

}

if (mem != "0")
row = row.Insert(0, mem);

for (int i = 0; i < index; i++)
{
loop++;
row = row.Insert(row.Length, "0");
}
res.Add(row);

index++;
}

mem = "0";
row = "";
int temp = 0;
index = 0;
string total = "";
Array.Sort(res.ToArray());



for (int n = 0; n < res[res.Count - 1].ToString().Length; n++)
{
foreach (string resString in res)
{
if (resString.Length - index > 0)
{
temp += Int32.Parse(resString.Substring(resString.Length - (index + 1), 1));
}
loop++;

}

total = (temp + Int32.Parse(mem)).ToString();

if (total.Length > 2)
{
row = row.Insert(0, total.Substring(1, 2));
mem = total.Substring(0, 1);
}
else
{
row = row.Insert(0, total.Substring(0, 1));
mem = "0";
}

index++;
temp = 0;
}
if (mem != "0")
row = row.Insert(0, mem);

return row;
}

[™Ali]

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

چون هنوز در ابتدای کار بودم، به ذهنم رسید که اسم برنامه رو Finding Way بذارم، پس زیاد گیر ندید :D
این برنامه SingleTheard هست ولی نسخه MultiTheard اون رو هم نوشتم که فعلا در حال تکمیل هست.

توجه :
از دوستان میخوام که روی این برنامه کار کنند و اگر می تونند الگوریتم ها رو بهبود ببخشند. هدف من محاسبه 1000 فاکتوریل در کمتر از یک ثانیه است.

محاسبه 2000 فاکتوریل (یک عدد 5736 رقمی) با این برنامه :


Only the registered members can see the link


سورس کد + فایل exe (برای دوستانی که نمی تونند برنامه رو کامپایل کنند) ضمیمه شد.

با تشکر علی :love:

[™Ali]

بالاخره وقت کردم و الگوریتم خودم رو بهبود بخشیدم!

به نحوی که الان 1000 فاکتوریل رو میشه در 4.5 ثانیه به دست آورد. (با الگوریتم قبلی 8 ثانیه طول می کشید)

تغییرات :

- استفاده از StringBuilder به جای String
- حذف کردن بعضی متغیرها
- اعتبار سنجی برای کاهش ردیف ها
- استفاده از یک Regex Expression برای حذف صفر های بی ارزش
- افزودن Comment به سورس کد جهت راهنمایی بیش تر !
- افزودن پارامتر Time Elasped
- حذف یک باگ در بعضی ضرب های بزرگ
- و چند مورد جزیی دیگه


الگوریتم اول رو هم کامل حذف کردم چون دیگه الگوریتم خودم تقریبا 2 برابر سرعت داره !

به طور مثال : در تصویر پست قبل مقدار 2000 فاکتوریل با الگوریتم اول در حدود 67 ثانیه محاسبه شد ولی با این الگوریتم جدید در حدود 36 ثانیه طول کشید.



Only the registered members can see the link


Source جدید ضمیمه شد. :love:

[mohammad1985]

علی عزیز اگه میشه بی زحمت کامپایل شده ورژن جدید رو هم بزار

[™Ali]

علی عزیز اگه میشه بی زحمت کامپایل شده ورژن جدید رو هم بزار

چشم !

کامپایل و ضمیمه شد.