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

[™Ali]

با سلام

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

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

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

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

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

راه حل : با اعداد همانند 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 رقمی) با این برنامه :

برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

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

با تشکر علی برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[™Ali]

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

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

تغییرات :

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


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

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

برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

Source جدید ضمیمه شد. برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[mohammad1985]

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

[™Ali]

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

چشم !

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