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

نمایش نتایج: از شماره 1 تا 7 از مجموع 7
Like Tree7نفر پسندیدند
  • 6 ارسال توسط Hossein
  • 1 ارسال توسط Hossein

موضوع: الگوریتم استراسن در سی++ با توضیح خط به خط

  1. #1
    بنیانگذار
    تاریخ عضویت
    2010 January
    محل سکونت
    زیر سایه خدا
    سن
    37
    ارسال ها
    1,308
    تشکر
    2,923
    تشکر شده 2,205 بار در 886 پست
    نوشته های وبلاگ
    37


    1 امتياز مثبت از 1 راي
    آيا اين پست براي شما سودمند بود؟ بله | خیر

    الگوریتم استراسن در سی++ با توضیح خط به خط

    سلام . دقیقا دو سال و 39 روز پیش این برنامه رو برای درس طراحی الگوریتممون نوشتم (استاد حسامی فرد) و چون میخواستم به اشتراک بزارمش توضیحاتش انگلیسیه .
    البته یک ورژن دیگه اش هم همون زمان ساختم که خط به خطش رو توضیح داده بودم برای همکلاسیام . اون رو هم وقتی پیدا کردم اینجا قرارش میدم .
    امیدوارم که بدردتتون بخوره . اگر سوالی دارید بپرسید

    Info
    یک نکته : در استاندارد جدید سی++ شما میتونید آرایه ها رو با اندازه متغییر بسازید مثل سی شارپ و دیگه مجبور نیستید از پوینترها و راهی که پایین من رفتن استفاده کنید (ویژوال استودیو 2010 تا حدودی این استاندارد رو رعایت میکنه و شما نبایستی مشکلی داشته باشید تو این زمینه - اگر احیانا بمشکل برخوردید میتونید از gcc استفاده کنید ( یا CodeBlocks رو دنبود کنید و از اون استفاده کنید )

    نکته دوم : این فایلی که ضمیمه میکنم پروژه CodeBlocks هست . اما برای اجراش در ویژوال استودیو شما هیچ مشکلی ندارید کافیه یه پروژه خالی سی++ (win32 console) بسازید و بعد main.cpp رو استفاده کنید . - ورژن ویژوال استودیو 2008 هم قرار داده شد )



    خب این هم پروژه استراسن با توضیحات فارسی که صحبتش رو کردم :
    پیشاپیش بخاطر نحوه نگارش توضیحات عذر میخوام جوونی و هزار و یک جاهلی



    //بسم الله الرحمن الرحیم
    //Strassen Algorithm Implementation in C++
    //Seyyed Hossein Hasan pour
    //Mazandaran University of Science and Technology
    //Release date May 9 2010
    //قبل از شروع بکار امیدوارم که توضیحاتم بجای راحت تر کردن فهم این پروژه . این کار رو سخت تر نکنه .
    //باز هم میگم اگر جایی رو بد توضیح دادم (خودم خبر توضیح دادنمو دارم :دی)حتما بگید تا بگم چه اتفاقی داره می افته .
    //تعارف رو هم بزارید کنار. سوال کنید تا جوابش رو پیدا کنید .
    //ایشالله که همه موفق و سربلند باشن
    //سید حسین حسن پور
    //شب پنج شنبه کذایی بعد از امتحان کوفتی طراحی الگوریتم
    //ساعت 23:08 شب
    //خونمون:دی
    //در ضمن یه نکته مهم . شما پروژه رو کامپایل که کردید خارج از محیط ویژوال استودیو برنامه رو ران و تست کنید
    //این ویژوال استودیوی مسخره یه باگ مسخره تر از خودش داره که باعث میشه موقع ران کردن برنامه تو خودش الگوریتم استراسن
    //خیلی خیلی وقت میگیره یا بگیره یا اصلا هر دوش:دی!
    //شما به این توجه نکنید . وقتی کامپایل شد . ویژوال استودیو رو ببندید و خودتون فایل رو اجرا کنید و نتیجه رو ببنید .
    //همین . اگه نمیگفتم خوابم نمیبرد:دی
    //شب خوش

    /*
    بسم الله الرحمن الرحیم
    من میخوام از سیر تا پیااز این پروژه رو توضیح بدم . کمربندها رو ببنید اگر هم ندارید برید ببنید بیایید:
    هم نکات برنامه نویسی عنوان میشه هم الگوریتم .
    بستین ؟ :دی خوب بریم
    */
    //توضیحات اینکلود ها
    /*
    همونطور که خیلی هاتون میدونید تو سی++ وقتی از تابعی میخواهیم استفاده کنیم باید هدر اون رو معرفی کنیم
    این هدرها به کامپایلر زبون نفهم میفهمونن که وقتی ما اسم یه تابع رو آوردیم این کجا بتونه تعریف این تابع رو پیدا کنه
    و در نتیجه برنامه رو کامپایل کنه .
    خوب حالا من محل استفاده هر کدوم از این هدر ها رو زیرش مینویسم .
    */
    #include <iostream>
    //این هدر به کامپایلر میفهمونه که ما تو برناممون از
    //cin یا cout
    //و چندتا تابع دیگه استفاده میکنیم

    #include <cstdlib>
    //این هدر فایل تعاریف یک سری توابع پرکاربرد رو در خودش داره که عموما هم بقول معروف کلی هستن
    //مثلا ما برای اینکه بتونیم تابع
    //system();
    //استفاده کنیم اینو نوشتیم . ما با تابع سیستم میتونیم هر برنامه ای رو که تو سیستتمون هست اجرا کنیم . نه تنها برنامه بلکه دستوراتی که
    //تو خود کامند پرامپت ویندوز استفاده کنیم هم میشه توش استفاده کرد.
    //نحوه استفاده هم اینطوریه که اسم دستور رو بصورت یه رشته به این تابع میدیم و السلام

    #include <iomanip>
    //این هدر برای اعمال تغییرات روی ورودی و خروجی ها به کمکمون میاد.
    //ما چون میخواستیم از تابع
    //setw()
    //که مخفف کلمه set width
    // هست استفاده کردیم . این تابع یه عددی رو میگیره و بر اساس اون جمله ای که میخواهیم تو خروجی چاپ کنیم رو تو صفحه حرکت میده
    //و مثلا اگه بگیم Setw(10)
    //10تا میره جلو و متن مارو رو صفحه چاپ میکنه .

    #include <ctime>
    //این هدر هم عین گاو پیشونی سفیده . اسمش روشه خوب . برای کار با توابعهی که با زمان کار داریم ازش استفاده میکنیم .

    #include <windows.h>
    //این هم از قبلی ضایعتر! وقتی که بخواهیم تو برناممون مضخصا از توابع و یا فانکشن ها و یا ای پی آی های ویندوز استفاده کنیم اینو مینویسیم.

    using namespace std;
    //این یوزینگ هم مثل همون چیزیه که ما تو سی شارپ باهاش مواجه هستیم . با همین یه خط به کامپایلر زبون نفهم میفهمونیم که
    //تمام توابعی که ما توی برنامه نوشتیم همشون از توابع استاندارد هستن و گیر بیخود بما نده . نوشتن این دستور
    //تو برنامه های 32 بیتی امروزه لازمه . شما نمیخواد بدونید چرا . فعلا همین قدر بدونید که برای در دسترس بودن تمایم توابع
    //کتابخانه استاندارد نوشتن این خط ضروریه .
    //)اگر هم واقعا دلتون میخواد بدونید شخصا بپرسید . میترسم بگم گیرپاژ کنید!)

    //اینجا هم توابعی هست که قراره ما در برناممون استفاده کنیم .
    //شکل این توابع همون اول به کامپایلر نشون داده میشه تا این برای خودش یه علامتی بسازه که جلوتر تو برنامه به یه چیز عجیب غربی مواجه شد بتونه بفهمه این یه تابع هست

    //تابع استراسن . 4 تا پارامتر داره . پارامتر اول اندازه ماتریس هاست . پارامتر دوم ماتریس اول . پارامتر سوم ماتریس دوم و پارامتر سوم هم ماتریس نتیجه هست
    //احتمالا میپرسید که چرا برای سه تا ماتریس یه اندازه فرستادیم . جواب اینه که خیر سرمون مثلا گفتیم که ماتریس ها همه هم اندازه هستند
    //یعنی یه 1024 در 1024 قراره ضرب بشه یا یه 8999 در یه 8999 قراره ضرب بشه . ضرب دوتا ماتریس 1024 در 1024 هم یه ماتریس 1024 میخواد دیکه . بیشتر که نمیخواد . برای همین .
    int Strassen(int n, int** MatrixA, int ** MatrixB, int ** MatrixC);//Multiplies Two Matrices recrusively.
    //این تابع هم سه تا ماتریس میگیره . که دو تا ماتریس اول رو با هم جمع میکنه و تو ماتریس سوم نتیجه رو قراره میده . پارامتر چهارم هم طول این ماتریس هاست .جلوتر میبینیم که چرا اینجوری زشت کد نوشتیم .
    int ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//Adds two Matrices, and places the result in another Matrix
    //این هم عین بالا کار میکنه . هیچ فرقی نداره .
    int SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//subtracts two Matrices , and places the result in another Matrix
    //این هم مشخصه که چیه . یه تابع برای ضرب معمولی ماتریس هاست . دو تا ماتریس اول رو میگیره با هم ضرب میکنه نتیجه رو میزاره تو ماتریس سوم . پارامتر آخری هم طبق معمول همون اندازه ماتریس ها هستش
    int MUL(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//Multiplies two matrices in conventional way.
    //تو این تابع ما دوتا ماتریس رو مقدار دهی میکنیم . یعنی به این تابع دوتا ماتریس میدیم و این میاد با اعداد رندوم اونو پر میکنه
    void FillMatrix( int** matrix1, int** matrix2, int length);//Fills Matrices with random numbers.
    //این هم از اسمش مشخصه . محتویات یه ماتریس رو ور میداره رو صفحه نمایش نشون میده . .یه ماتریس به عنوان ووردی گرفته به اضافه سایز ماتریس .
    void PrintMatrix( int **MatrixA, int MatrixSize );//prints the Matrix content.

    //این هم یه متغییر سراسری هست که تمام بخش های برنامه میتونن ازش استفاده کنن . برای اینکه همه جا بهش دسترسی داشته باشن اینو اینجا نوشتم .
    //این متغییر آستانه هاست . آستانه همون شرط پایه تابع بازگشتی استراسن ماست که وقتی اندازه ارایه های ورودی با این آستانه ما برابر میشن . به این معناست که
    //از این به بعد رو بصورت معمولی ضرب کن . دیگه به آستانه (یا حد)بهینه گی الگوریتم استراسن رسیدی اگه این آستانه رو رد کنی و همینجوری الگوریتم استراسن رو ادامه بدی سربارت بیشتر میشه . این یعنی معنی آستانه و وظیفش تو الگوریتم استراسن
    int threshold = 32;

    //این هم تابع مشهور مین ! معرف حضور که هست ؟ :دی
    int main()
    {

    //یه متغییری ساختیم که اندازه ماتریس رو که از کاربر گرفتیم بندازیم توش .
    int MatrixSize = 0;

    // اینجا هم سه تا آرایه دو بعدی تعریف میکنیم .
    //درسته شکلش زشته اما جلوتر دلیلشو میبینیم .
    //برای هر بعدش یه ستاره میزاریم .
    //اینجا ما یه آرایه دو بعدی میخواهییم پس دوتا ستاره لازم داریم .
    // جنس آرایه ها یا بعبارت بهتر ماتریس هامون هم از نوع اینتیجر !! تعریف کردیم . چرا ؟ چون عشقم کشید . رم مفت ندارم که حروم کنم :دی
    int** MatrixA;
    int** MatrixB;
    int** MatrixC;

    // کلاک اندرلاین تی که این پایین میبینید یه نوع خاص هست که ما وقتی با کلاک سی پی یو سرکار داریم ازش استفاده میکنیم .
    //ما اینجا دوتا متغییر تعریف میکنیم که یکی کلاک سی پی یو رو قبل از اینکه وارد یه تابعی بشیم میگیره و ذخیره میکنه تو خودش
    //و متغییر دیگه دقیقا وقتی کارتابع تموم شد کلاک سی پی یو رو دوباره میگیره .

    clock_t startTime_For_Normal_Multipilication ;//این متغییر برای ذخیره کلاک سی پی یو وقتی که تابع ضرب معمولی شروع میشه هست
    clock_t endTime_For_Normal_Multipilication ;//این متغییری هست که وقتی تابع ضرب معمولی تموم میشه آمار کلاک سی پی یو رو میگیره .

    // این ها هم مثل بالا . با این تفاوت که اینها آمار کلاک ها رو برای تابع استراسن ذخیره میکنن
    clock_t startTime_For_Strassen ;
    clock_t endTime_For_Strassen ;

    //این متغییر تایم اندرلاین تی هم مثل بالاییه کارش ذخیره کردن زمان تو خودشه . البته ما ازش استفاده نکردیم . بیخود اینحا افتاده
    //)قبلا استفاده کرده بودم پاکش کردم .
    time_t start,end;

    //اینجا جالبه. یادتون میاد بالا گفته بودم که یه تابعی داریم که ماتریس ها رو بصورت رندوم پر میکنه . ؟
    //تو اون تابع ما از تابع Rand()
    //استفاده کردیم . است تابع اصولا کاری که میکنه اینه یه سری داره که به ازای مقادیر مختلف مقدار مختلفی برمیگردونه .
    //یعنی چی ؟ یعنی این
    //y = x*2+5;
    //به ازای ایکسی که میدید ایگرگ عوض میشه دیگه درسته ؟ خوب این تابعه هم دقیقا همین کارو میکنه .
    //حالا برای اینکه ما بصورت رندوم عدد تولید کنیم از تابع زیر استغاده میکنیم برای مقدار دهی به اون .
    //تابع srand()
    //یه عدد از نوع اینتیجر میگیره . ما میتونیم اینجا بدیم 2 میتونیم بدیم 400 اما این کارو نمیکنیم . چرا ؟ چون اگه این کارو بکنیم
    //مثل این میمونه که تو فرمول بالا همش به ایکس بدیم 400 ! خوب ایگرگ همش یه عدد میشه! درسته ؟ ما میخواهییم هربار که برنامه رو اجرا میکنیم این به اصطلاح ایگرگ ما یه عدد متفاوت بشه .
    //این کار فقط یه راه داره و اونم اینه که مقدار ایکس ما تو هر بار اجرای برنامه تغییر کنه .
    //ما بجای اینکه خودمون ایکس رو وارد کنیم . میایم یه کلک رشتی میزنیم .
    //زمان سیستم از عهد بوق(1970 دقیقا) رو با فرمت ثانیه میگیریم میدیم به تابع زیری .
    //اینجوری هربار که برنامه رو اجرا میکنیم . میدونیم که زمان قطعا افزایش پیدا کرده . و در نتیجه عددی که نشاتگر زمان ما به ثانیه هست هم فرق کرده .
    //تابع time(0)
    //که مال هدر سی تایم هست این کار رو برای ما انجام میده . برای همین هم بود که بالا فراخونیش کردیم و گفتیم که ضایع است:دی .

    srand(time(0));
    //اینجا هم ما یک سری متن داریم که میخواهیم نمایش بدیم .
    //حتما دقت کردین دیگه .
    //setw رو میگم
    //اون عدد رو اگه خواستید تغییر بدید تا نتیجش رو تو صفحه ببنید .
    cout<<setw(45)<<"In the name of GOD";
    cout<<endl<<setw(60)<<"Strassen Algorithm Implementation in C++ "
    <<endl<<endl<<setw(50)<<"By Seyyed Hossein Hasan Pour"
    <<endl<<setw(60)<<"Mazandaran University of Science and Technology"
    <<endl<<setw(40)<<"May 9 2010";

    //اینجا هم گفتیم که بنده خدا اندازه ماتریس ها رو وارد کن .
    //با cin
    //متغییر ها رو مقدار دهی میکنیم . )یعنی هرچی که کاربر وارد کرد رو بریز تو متغییر
    cout<<"\nPlease Enter your Matrix Size(must be in a power of two(eg:32,64,512,..): ";
    cin>>MatrixSize;
    //اینجا هم گفتیم که اون آستانه رو خودت وارد کن . تا نتیجه کارایی ماتریس استراسن رو خودت ببنی وقتی که آستانه کمو زیاد میشه.
    //در ضمن گفتیم که این استانه هم باید یه عدد توان دو باشه . مثل 2 4 8 و ..غیره . یعنی 2 به توان یه عددی بشه اون! اکی؟
    cout<<"Please Enter your threshold (Astane: 2,4,8,16,32,64,...)";
    cin>>threshold;

    //این هم همینجوری مقدار دهی کردیم برای قشنگی .
    int N = MatrixSize;//for readiblity.

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

    //قدم اول . ما قبلا یه متغییری ساخته بودیم که پشتش دوتا ستارش داشت و ا زنوع اینتیجر هم تعریفش کرده بودیم درسته ؟
    //این ستاره ها یعنی اشاره گر بودن . یعنی
    //int * A ما یه اشاره گر از نوع اینتیجر ساختیم .
    // که قراره به یه جایی اشاره کنه که توش یه مقداری هست .
    //حالا ما اینو داریم
    //int ** A
    //این یعنی اینکه من یه اشاره کر از نوع اشاره گر به اینتیجر دارم . !
    //سخت شد نه ! مهم نیست . آسون میشه .
    //خط بالا معنیش اینه که
    //خود متغغیر آ یه اشاره گر هست که باز خودش به چیزی که اشاره میکنه که اشاره گره )یعنی اشاره گر داره به اشارهگر اشاره میکنه

    //بسه . برگردیم سر پروژمون .
    //ما با خط زیر به کامپایلر زبون نفهم میگیم که سفله من یه آرایه یه بعدی میخوام از نوع اینتیجر .
    // تو این مرحله ما با استفاده از اشاره کر ها یه آرایه یه بعدی میسازیم . قدم بعدی اینه که بعد دومشو بسازیم .
    //بزارید ساده تر بگم . یه آرایه دو بعدی . یه سطر داره و یه ستون درسته ؟
    //خوب ما اول سطر یا سطر هاشو میسازیم . به هر تعداد که خواستیم و بعدش میریم سراغ ستونهاش.
    //خط زیری میشه سطر های آرایه ما . اندازه آرایه هم که تو براکت هست هم میشه تعداد سطرهایی که میخواهین آرایتون داشته باشه .
    //پس ما برای آرایه های آ ب و س سطرهاشو ساختیم با دستورات زیر.
    MatrixA = new int *[MatrixSize];
    MatrixB = new int *[MatrixSize];
    MatrixC = new int *[MatrixSize];

    //خیلی خوب حالا نوبته ساخت ستونها برای آرایه هامونه . (ماتریسهامون).خوب ؟

    // مگه ما نمیگیم که جلوی هر سطر چندتا ستون هست .
    //بزارید بهتر بگم
    //ما مگه برای هر سطرمون چند تا ستون نداریم ؟ خیلی خوب الان هم همین کارو میکنیم .
    //به همون کامپایلر زبون نفهم میگیم که جلوی هر سطر ما یه آرایه دیگه بسازه که انقدر (که ما مشخص میکنیم )خونه داشته باشه .
    //سطرهامون رو هم با اندیس مشخص میکنیم
    //چرا اینجوری شده؟
    //ما مگه بالا یه آرایه از اشارهگر ها نساخته بودیم ؟
    //خیلی خوب . چون آرایه ساختیم پس میتونیم اینجوری بهش دسترسی داشته باشیم
    //اینجوری >>A[]
    //و خوب اندازشم که داده بودیم مگه نه؟ مگه نگفته بودیم که یه آرایه با این تعداد خونه برامون بساز ؟
    //A = new int *[تعداد خونه های آرایمون]
    //که از قضا گفتیم این تعداد خونه میشه تعداد سطر های ما تو آرایه دو بعدی ؟
    //خیلی خوب پس ما میتونیم بنویسم >>A[512];
    //خیلی خوب . حالا ما میخواهییم ستون این آرایمون رو هم درست کنیم .
    // مگه نگفتیم هر سطر
    //n تا
    //ستون داره ؟
    // و ستون ها هم جلوش ردیفن ؟
    //
    // ستون1 ستون2 ستون3 ستون4 ستون5
    //
    //سطر n m o p q
    //
    //خیلی خوب . حالا خوب به سطر نگاه کنید . آیا سطر خودش یه آرایه یه بعدی نیست ؟ که 5 تا خونه داره ؟
    //دنکته هم همینه . ما اول برناممون اومدیم مثلا 50 تا از این سطر ها ساختیم
    //و میخواهیم مثل بالا هر کدوم از این سطر ها رو تبدیل یه یک آرایه کنیم .
    //اگه این کارو بکنیم یه چیزی مثل این درست میشه
    // ستون1 ستون2 ستون3 ستون4 ستون5
    //
    //سطر1 n m o p q
    //سطر2 k l m n o
    //سطر3 z x c v v
    //....
    //بنظر شما شکل بالا مثل چیه ؟ بنظر من که یه آرایه دو بعدیه درسته ؟

    //خیلی خوب . حالا کار ما ساده شده . کاری که باید بکنیم اینه که سطر ها یکی یکی یه آرایه جلوشون بسازیم .
    //میدونیم که سطرهای ما خودشون یه خونه از یه آرایه هستن .
    //خیلی خوب پس میشه با یه حلقه فور به همشون دست پیدا کرد .
    // بعدش دیگه ساده هست.
    //برای همینه که یه حلقه فور ساختیم . که از صفر شروع میشه و تا شماره آخرین خونه این ارایه ها ادامه پیدا میکنه
    // و اندیس این حلقه فور هم هر بار به یک خونه اشاره میکنه .
    //و بعد ما با دستور >>new int [ تعداد ستون ]
    //یه آرایه برای هر خونه میسازیم که تعداد خونه هاش برابر چیزی هست که ما مشخص میکنیم . . چون ما میخواهیم ستون بسازیم . پس تعداد ستون های دلخواه آرایمون رو میدیم
    //تو حلقه زیر این کار رو برای هر سه ماتریس یک جا انجام دادیم .
    for (int i = 0; i < MatrixSize; i++)
    {
    MatrixA[i] = new int [MatrixSize];
    MatrixB[i] = new int [MatrixSize];
    MatrixC[i] = new int [MatrixSize];
    }

    //اینجا هم ماتریس های آ و ب خودمون رو مقدار دهی میکنیم .
    //توضیح این تابع رو اون پایین با هم دنبال میکنیم ..این که این تابع چجوری کارشو انجام میده.
    FillMatrix(MatrixA,MatrixB,MatrixSize);


    //*******************conventional multiplication test
    //اینجا هم اول اومدیم این دوتا ماتریس رو با هم دیگه بصورت معمولی ضرب کردیم .
    //تا ببنیم که کلا چقدر زمان صرف شد تا این دوتا ماتریس با هم ضرب بشن .
    //برای اینکه بفهمیم چقدر زمان مصرف میشه . قبل از اجرای تابع یا فراخونی کردن اون تعداد کلاک سی پی یو رو که از اول برنامه ما شروع به افزایش کرده رو میگیریم یه جا ذخیره میکنیم
    cout<<"Phase I started: "<< (startTime_For_Normal_Multipilication = clock());
    //حالا تابع رو فراخونی میکنیم .
    //ممکنه 10 20 ثانیه و یا حتی چند ساعت بسته به اندازه ماتریسمون طول بکشه و در این حین کلاک سی پی یو هم همینجور افزایش پیدا میکنه
    MUL(MatrixA,MatrixB,MatrixC,MatrixSize);
    //حالا که تابع کارش تموم شد . هرچقدر تا حالا کلاک سی پی یو افزایش پیدا کرده رو بریز تو یه متغغیر دیگه .
    //حالا ما اگه اینو از اون متغییر بالایی کم کنیم . تعداد کلاک هایی که از شروع تابع ضرب تا پایانش گذشته رو خواهیم داشت .
    cout<<"\nPhase I ended: "<< (endTime_For_Normal_Multipilication = clock());

    //اینجا هم متحویات ماتریس نتیجه رو نمایش میدیم ) که مثلا ببینیم واقعا ضرب درست انجام شده یا نه
    cout<<"\nMatrix Result... \n";
    //این کار با استفاده از تابع پرینت که بالا معرفی کردیم انجام میشه .
    //من غیر فعالش کردم . چون برای ماتریس های بزرگ زمان خیلی زیادی طول میکشه تا محتویات ماتریس روی صفحه مانیتور نمایش داده بشه .
    //برای تست هم که شده میتونید اینو یکبار فعال کنید و نتیجه رو ببنید .
    //PrintMatrix(MatrixC,MatrixSize);

    //*******************Strassen multiplication test
    //اینجا هم مثل بالا داریم عمل میکنیم حالا برای تست الگوریتم استراسن . که وقتی فراخونی شد برای ضرب دوماتریس چقدر زمان صرف میکنه
    cout<<"\nMultiplication started: "<< (startTime_For_Strassen = clock());

    Strassen( N, MatrixA, MatrixB, MatrixC );

    cout<<"\nMultiplication: "<<(endTime_For_Strassen = clock());


    cout<<"\nMatrix Result... \n";
    //PrintMatrix(MatrixC,MatrixSize);

    //این آخر هم یه سری اطلاعات نمایش دادیم که مثلا اندازه یا سایز ماتریس هایی که در هم ضرب کردیم چند بود و هر کدوم از الگوریتم ها
    //چقدر زمان بردند برای ضرب دو ماتریس.
    //یه نکته : تو سی پلاس پلاس یه ثابتی هست که اگه ما تعداد کلک های سی پی یو مون رو بر اون تقسیم کنیم مقدار ثانیه رو بما میده
    //و اون ثابت هم اینه
    //CLOCKS_PER_SEC
    //
    cout<<"Matrix size "<<MatrixSize;
    cout<<"\nNormal mode "<<(endTime_For_Normal_Multipilication - startTime_For_Normal_Multipilication)<<" Clocks.."<<(endTime_For_Normal_Multipilication - startTime_For_Normal_Multipilication)/CLOCKS_PER_SEC<<" Sec";
    cout<<"\nStrassen mode "<<(endTime_For_Strassen - startTime_For_Strassen)<<" Clocks.."<<(endTime_For_Strassen - startTime_For_Strassen)/CLOCKS_PER_SEC<<" Sec\n";
    //اینجا هم یه دستور ویندوزی رو فراخونی کردم با نام
    //Pause
    //این باعث میشه که بعد از اتمام برنامه . ! برنامه زپرتی بیرون نیاد . و آخرش یه پیام لطفا یک کلیدی را برای خروج فشار دهید رو به کاربر نشون بده .
    //همین .
    system("Pause");
    return 0;

    }

    //حالا هم میرسیم به الگوریتم استراسن .
    /*
    قبل از اینکه شروع کنیم به صحبت و یا بهتر بگم توضیح اینکه این جا داریم چه میکنیم . این نکته ضرورریه که بدونیم
    اصلا الگوریتم استراسن داره چیکار میکنه . من پیشنهاد میکنم قبلش حتما کتاب نئوپولیتان و نعیمی پور رو حتما یه نگاهی
    بهش بندازید تا ببینید قضیه از چه قراره . بعد که متوجه الگوریتم شدید بیایید اینجا . اگرم حسش نیست خیلی خوب خودم میگم
    البته بصورت کاملا ام پی تری:دی
    نحوه کار در الگوریتم استراسن به این شکل هست که ما دوتا ماتریس داریم که میخواهییم اینها رو د رهم ضرب کنیم و نتیه
    رو در ماتریس سومی ذخیره کنیم . استراسن راه حلی رو پیشنهاد داده که طی اون ما برای ضرب دو ماتریس اول اون دوتا ماتریس
    رو به 4 تا ماتریس کوچیکتر تقسیم میکنیم .
    هر ماتریس کوچیک که از این به بعد اونها رو با زیرماتریس خطاب میکنیم . اندازه ای برابر با 1/4 ماتریس بزرگ ما خواهند داشت
    ماتریس زیر رو در نظر بگیرید .
    تعداد اعضاش برابر هست با 64 تا . یعنی 8 در 8

    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0


    حالا میخواهیم این ماتریس رو به 4 تا ماتریس کوچیکتر بطور مساوری تقسیم کنیم .

    من الان ماتریس رو به دو قسمت مساوی تقسیم کردم

    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    .
    و حالا به چهار قسمت مساوی تقسیم شد

    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0

    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0



    بذارید قشنگترش کنیم
    اگه ماتریس اصلیمون اسمش آ باشه .
    درسته که من اینطوری شکلشو بکشم ؟

    A
    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    حالا اگه اینو نصفش کنم به دوتا تیکه مساوی آیا اگه من شکلشو اینطوری بکشم شما ایرادی میگیرید از من /؟

    A1 A2
    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    حالا اگه به چهار قسمت مساوی تقسیمش کنم و شکلشو اینطوری رسم کنم چی ؟

    A1 A2
    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    A3 A4
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    خیلی خوب . استراسن هم همینو میگه . میگه ما دو ماتریس داریم که میخواییم اونا رو با هم ضرب کنیم .
    به یکی میگیم ماتریس آ و به یکی دیگه میگیم ماتریس ب

    ماتریس آ رو به 4 قسمت مساوی تقسیم میکنیم و اینجوری اسمگذاری میکنیم

    A11 A12
    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    A21 A22
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    بنظر شما این شماره گذاریا شکل چیه ؟ چه چیزی رو میخوان برسونن؟اجازه بدید یک باری دیگه اونارو براتون بنویسم .

    A11,A12
    A21,A22
    ماتریس زیر رو دنظر بکیرید

    [1,2]
    [3,4]

    اگه بخواهیین به عدد یک دسترسی پیدا کنید چی مینویسید؟مثلا اسم ماتریس هم باشه آ
    حتما مینویسید
    A[1,1] درسته ؟
    پس A11
    هم یعنی بخش اول ماتریس
    A12 هم یعنی بخش دوم ماتریس
    بعبارت بهتر
    11 نشانگر سطر اول و ستون اول هست
    12 نشانگر سطر اول و ستون دوم هست
    21 نشانگر سطر دوم و ستون اول هست
    22 و این هم سطر و ستون دوم رو نشون میده .

    فکر میکنم دلیل این نوع نام گزاری رو متوجه شده باشید . بله دلیلش فقط بهتر کردن درک ما از اینکه چه اتفاقی داره می افته هست
    و اینکه این تیکه های ماتریس رو با این دید ببینید که انگار هر زیر ماتریس یه عضو از ماتریس بزرگه .
    ما چجوری یه عضو رو خیلی راحت تو محاسباتمون دخالت میدیم . جمع میکنیم . کم میکنیم و ... . استراسن میگه با این دید بریم جلو .
    و این بلاها رو سر این زیر ماتریسا بیاریم . و وقتی کارمون تموم میشه . این زیر ماتریس ها هم تغییر میکنن در حین جمع و کم و ضرب و اینا درسته
    و وقتی این ها تغییر کنن . چه اتفاقی می افته . بله ماتریس بزرگ ما هم کامل میشه .
    ما یه همچین سیری رو طی میکنیم .
    ما با زیر ماتریسا مثل شکل زیر بخورد میکنیم
    [A11,A12]
    [A21,A22]
    و هر کدوم از این عنصر ها رو تو ضرب و تقسیم و جمع و کم شرکت میدیم
    و این در حالیه که در اصل ما داریم این ها رو ضرب و جمع و کم و ... میکنیم

    A11,A12
    A21,A22

    >>

    A11 A12
    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0
    A21 A22
    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0


    یعنی وقتی آ11 ما حساب میشه . ربع اول ماتریس ما حساب شده و وقتی آ12 ما حساب میشه ربع دوم ماتریس بزرگ ما حساب میشه .

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

    */
    int Strassen(int N, int **MatrixA, int **MatrixB, int **MatrixC)
    {
    //خوب استراسن گفته برای اینکه الکوریتمشو بتونیم استفاده کنیم به 4 تا چیز نیاز داریم .
    // دو تا ماتریس که قراره با هم ضرب بشن
    //یه ماتریس که قراره نتیجه ضرب توش قرار بگیره
    // و شماره چهار هم اندازه ماتریس بعنوان ورودی
    //اندازه ماتریس رو برای اون آستانه میخواد که بالای برنامه توضیح دادم براتون .
    //که اگه اندازه ماتریس ها از یه حد خاصی کمتر شد دیگه الگوریتم استراسن ادامه پیدا نکنه و ماتریس ها رو بصورت معمولی در هم ضرب کنیم .
    //ما علاوه بر اون از این اندازه ماتریس استفاده میکنیم تا زیر ماتریس هامون رو هم بسازیم .
    //چون میدونید که این یک تابع بازگشتی هست و هربار که فراخونی میشه آرایه ها یا ماتریس ها بسته به ورودی های تابع اندازشون تغییر میکنه

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

    int HalfSize = N/2;
    int newSize = N/2;

    //کسی میدونه چرا من اندازه ماتریس ها رو تقسیم بر دو کردم ؟
    /*
    به این شکل نگاه کنید خودتون متوجه میشید .
    این یه ماتریس 8 در 8 هست درسته ؟ ما به چهار قسمت مساوی تقسیمش کردیم درسته؟
    خوب سطر و ستونش رو خوب ببینید .
    دقیقا از وسط نصف شدن .

    (Matrix_Asli)

    1 2 3 4 5 6 7 8
    2 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0
    4 0 0 0 0 0 0 0

    5 0 0 0 0 0 0 0
    6 0 0 0 0 0 0 0
    7 0 0 0 0 0 0 0
    8 0 0 0 0 0 0 0

    یعنی ستون چهارتا رفتیم جلو و ماتریس اصلی رو شکافتیم
    بعد 4تا سطر اومدیم پایین و باز ماتریس اصلی رو شکافتیم . نتیجه حاصل چیه ؟
    چهارتا زیر ماتریس بدست اومد .
    بعنوان مثال زیرماتریس اول اینجوری از ماتریس اصلی بدست میاد

    for ( int satr = 1; satr <= 8/2; satr++)
    {
    for( int soton = 1; soton <= 8/2; soton++)
    {
    A11[satr][soton] = Matrix_Asli[satr][soton];
    }
    }

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

    for ( int satr = 1; satr <= 8/2; satr++)
    {
    for( int soton = 8/2+1; soton <= 8; soton++)
    {
    A12[satr][soton] = Matrix_Asli[satr][soton];
    }
    }

    و همینطور برای بقیه ماتریس ها .

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

    */


    //اینجا همون جایی هست که اندازه ماتریس های ورودی رو با آستانه میسنجه . اگه کمتر یا مساوی با آستانه بود اندازه ماتریس
    //های ورودی ضرب بصورت معمولی ادامه پیدا میکنه درغیر اینصورت بصورت استراسنی ضرب میکنیم .

    if ( N <= threshold )// specifying this threshhold is very important. set this to N<=2 and see the results yourself
    {
    MUL(MatrixA,MatrixB,MatrixC,N);
    }
    else
    {

    //این هم که قبلا توضیح دادم بالا . برای ساخت آرایه دو بعدی تو سی++ زمانی که دو قابلیت زیر رو بخواهیم استفاده میشه
    //1.هر وقت بخواهیم آرایه دو بعدی داشته باشیم که هر اندازه ای دلمون خواست بتونیم بهش بدیم
    //2.هر وقت بخواهیم آرایه دوبعدی داشته باشیم که تو زمان اجرا بتونیم اندازشو کم و زیاد کنیم
    // اینجوری آرایه دو بعدی رو تعریف می کنیم و میسازیم .

    //اینا چهارتا زیر ماتریس برای ماتریس آ هستن
    int** A11;
    int** A12;
    int** A21;
    int** A22;

    //اینا هم چهارتا زیر ماتریس برای ماتبریس ب هستن
    int** B11;
    int** B12;
    int** B21;
    int** B22;

    //اینا هم چهارتا زیر ماتریس برای ماتریس حاصل هستن . یعنی ماتریس س .
    int** C11;
    int** C12;
    int** C21;
    int** C22;

    //اینا هم ماتریس هایی هستن که استراسن بااستفاده از اینا ضرب دو نا ماتریس رو انجام میده . با کم و جمع و ضرب کردم ایناها با زیر ماتریسای دیگه این کارو میکنه.

    //نکته مهمی که باید بدونید اینه که اندازه همه این ماتریسا با هم برابره! چرا که قراره با هم ضرب و جمع و ...بشن
    //که اگه برابر نباشن نمیشه ضرب و جمع و ... کرد .

    int** M1;
    int** M2;
    int** M3;
    int** M4;
    int** M5;
    int** M6;
    int** M7;

    //اینا هم دوتا ماتریس کمکی هستن برای نگه داشتن نتیجه جمع و کم یا ضرب این ماتریسای بالا.که خواهیم دید کجا و چجوری استفاده میشن.
    int** AResult;
    int** BResult;

    //اینجا مثل قبل اول آرایه یه بعدیشون میکنیم .
    // و بعد با استفاده از حلقه فور تبدیلشون میکنیم به آرایه دو بعدی .
    // اندازه هاشون هم که مشخصه دیکه . لازم به کفتن نیست.

    //making a 1 diminsional pointer based array.
    A11 = new int *[newSize];
    A12 = new int *[newSize];
    A21 = new int *[newSize];
    A22 = new int *[newSize];

    B11 = new int *[newSize];
    B12 = new int *[newSize];
    B21 = new int *[newSize];
    B22 = new int *[newSize];

    C11 = new int *[newSize];
    C12 = new int *[newSize];
    C21 = new int *[newSize];
    C22 = new int *[newSize];

    M1 = new int *[newSize];
    M2 = new int *[newSize];
    M3 = new int *[newSize];
    M4 = new int *[newSize];
    M5 = new int *[newSize];
    M6 = new int *[newSize];
    M7 = new int *[newSize];

    AResult = new int *[newSize];
    BResult = new int *[newSize];

    int newLength = newSize;

    //تبدیل کردن اینها به آرایه های دو بعدی .
    //من بالا برای اینکه کد خوانایی بیشتری داشته باشه اومدم یه متغییر دیگه تعریف کردم
    //با نام نیو لنث ! که یعنی طول جدید که نشانگر طول ستون یا بهتر بگم تعداد ستون این آرایه هست . همین .
    //بازم میگم . همونطوری که میبینید نیازی به این کار نبود فقط برای قشنگی این کارو کردم .
    //making that 1 diminsional pointer based array , a 2D pointer based array
    for ( int i = 0; i < newSize; i++)
    {
    A11[i] = new int[newLength];
    A12[i] = new int[newLength];
    A21[i] = new int[newLength];
    A22[i] = new int[newLength];

    B11[i] = new int[newLength];
    B12[i] = new int[newLength];
    B21[i] = new int[newLength];
    B22[i] = new int[newLength];

    C11[i] = new int[newLength];
    C12[i] = new int[newLength];
    C21[i] = new int[newLength];
    C22[i] = new int[newLength];

    M1[i] = new int[newLength];
    M2[i] = new int[newLength];
    M3[i] = new int[newLength];
    M4[i] = new int[newLength];
    M5[i] = new int[newLength];
    M6[i] = new int[newLength];
    M7[i] = new int[newLength];

    AResult[i] = new int[newLength];
    BResult[i] = new int[newLength];


    }

    //اینجا هم داریم زیر ماتریس های آ و ب رو مقدار دهی میکنیم .
    //بجای یه حلقه فور اینجوریکه همه رو با هم مقداردهی میکنیم . ما میتونستیم خیلی راحت این کار رو بکنیم
    //اینها هیچ فرقی با هم ندارن .
    //منظورم حلقه فور بعدی که بعد این کامنتا هست.
    /*
    //A11[][]
    for (int i = 0; i<N/2; i++)
    {
    for (int j = 0; j<N/2; j++)
    {
    A11[i][j] = MatrixA[i][j];
    }
    }

    //A12[][]
    for (int i = 0; i<N/2; i++)
    {
    for (int j = N/2; j<N; j++)
    {
    A12[i][j] = MatrixA[i][j];
    }
    }

    //A21[][]
    for ( int i = N/2; i<N; i++)
    {
    for ( int j = 0; j<N/2; j++)
    {
    A21[i][j] = MatrixA[i][j];
    }
    }

    //A22[][]
    for ( int i = N/2; i<N; i++)
    {
    for ( int j = N/2; j< N; j++)
    {
    A22[i][j] = MatrixA[i][j];
    }
    }

    //B11[][]
    for (int i = 0; i<N/2; i++)
    {
    for (int j = 0; j<N/2; j++)
    {
    B11[i][j] = MatrixB[i][j];
    }
    }

    //B12[][]
    for (int i = 0; i<N/2; i++)
    {
    for (int j = N/2; j<N; j++)
    {
    B12[i][j] = MatrixB[i][j];
    }
    }

    //B21[][]
    for ( int i = N/2; i<N; i++)
    {
    for ( int j = 0; j<N/2; j++)
    {
    B21[i][j] = MatrixB[i][j];
    }
    }

    //B22[][]
    for ( int i = N/2; i<N; i++)
    {
    for ( int j = N/2; j< N; j++)
    {
    B22[i][j] = MatrixB[i][j];
    }
    }

    */

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

    //splitting input Matrixes, into 4 submatrices each.
    for (int i = 0; i < N / 2; i++)
    {
    for (int j = 0; j < N / 2; j++)
    {
    A11[i][j] = MatrixA[i][j];
    A12[i][j] = MatrixA[i][j + N / 2];
    A21[i][j] = MatrixA[i + N / 2][j];
    A22[i][j] = MatrixA[i + N / 2][j + N / 2];

    B11[i][j] = MatrixB[i][j];
    B12[i][j] = MatrixB[i][j + N / 2];
    B21[i][j] = MatrixB[i + N / 2][j];
    B22[i][j] = MatrixB[i + N / 2][j + N / 2];

    }
    }


    //اینجا هم دیگه خود کتاب رو نگاه میکنیم . و گفته که چجوری
    //M1 ..M7 رو حساب کنیم
    //ما به این ام ها نیاز داریم تا بتونیم بعد از اینکه ام ها رو بدست اوردیم ماتریس حاصل رو پر کنیم .
    // هر ام که دیدیم خودش یه ماتریسه . پس وقتی که تو کتاب خیلی راحت نوشته آ11 رو با مثلا ام جمع کنید و بعد ضرب . ما برای جمع کردنشون
    //از یه تابع استفاده میکنیم . و نتیجه جمع رو در یک ماتریس موقتی مثل آریزالت قرار میدیم و بعد از اون استفاده میکنیم .
    //
    //here we calculate M1..M7 matrices .
    //M1[][]
    ADD( A11,A22,AResult, HalfSize);
    ADD( B11,B22,BResult, HalfSize);
    //توی فرمول گفته که بعد از اینکه آ11و آ22 رو با هم جمع کردی بعد ب11 و ب22 رو هم با هم جمع کردی حاصل اینها رو
    //در هم ضرب کن و در ام1 قرار بده .
    //ما اینجا هر وقت بخواهییم ضربی انجام بدیم بین دوتا ماتریس دیگه از ضرب معمولی استفاده نمیکنیم
    //اونها رو به شیوه استراسن ضرب میکنیم .
    //پس اندازه ماتریس های جدید و اون ماتریس هایی که قراره با هم ضرب بشن و ماتریسی که قراره نتیجه ضرب رو تو خودش ذخیره کنه
    //همه رو بعنوان پارامتر میفرستیم .
    //فقط یادتون باشه که دیگه اندازه ماتریس اصلی رو نفرستید . ! ما داریم دوتا ماتریس دیگه رو ضرب میکنیم
    //پس باید اندازه اینها رو بدیم . از قضیا اینا اندازشون
    //N/2 هست
    //خیلی خوب .
    Strassen( HalfSize, AResult, BResult, M1 ); //now that we need to multiply this , we use the strassen itself .

    //این کار رو برای همه ام ها انجام میدیم .
    //این جمع و ضرب ها هم همه تو کتاب اومده . و ما با نگاه کردن به اونها
    //معادلش رو در برنامه نویسی پیاده سازی میکنیم
    // من سمت راست هر تابع معادل اون چیزی که تو کتاب نوشته شده رو اوردم .
    // و جلوی تابع استراسن هم نشوتم که مثلا این داره کار ضرب رو انجام میده .
    //M2[][]
    ADD( A21,A22,AResult, HalfSize); //M2=(A21+A22)B11
    Strassen(HalfSize, AResult, B11, M2); //Mul(AResult,B11,M2);

    //M3[][]
    SUB( B12,B22,BResult, HalfSize); //M3=A11(B12-B22)
    Strassen(HalfSize, A11, BResult, M3); //Mul(A11,BResult,M3);

    //M4[][]
    SUB( B21, B11, BResult, HalfSize); //M4=A22(B21-B11)
    Strassen(HalfSize, A22, BResult, M4); //Mul(A22,BResult,M4);

    //M5[][]
    ADD( A11, A12, AResult, HalfSize); //M5=(A11+A12)B22
    Strassen(HalfSize, AResult, B22, M5); //Mul(AResult,B22,M5);


    //M6[][]
    SUB( A21, A11, AResult, HalfSize);
    ADD( B11, B12, BResult, HalfSize); //M6=(A21-A11)(B11+B12)
    Strassen( HalfSize, AResult, BResult, M6); //Mul(AResult,BResult,M6);

    //M7[][]
    SUB(A12, A22, AResult, HalfSize);
    ADD(B21, B22, BResult, HalfSize); //M7=(A12-A22)(B21+B22)
    Strassen(HalfSize, AResult, BResult, M7); //Mul(AResult,BResult,M7);

    //حالا که ام ها همه بدست اومد . حالا زیر ماتریس های سی 1 تا سی 4 رو با توجه به اون چیزی که تو کتاب اومده
    //بدست میاریم .
    //C11 = M1 + M4 - M5 + M7;
    ADD( M1, M4, AResult, HalfSize);
    SUB( M7, M5, BResult, HalfSize);
    ADD( AResult, BResult, C11, HalfSize);

    //C12 = M3 + M5;
    ADD( M3, M5, C12, HalfSize);

    //C21 = M2 + M4;
    ADD( M2, M4, C21, HalfSize);

    //C22 = M1 + M3 - M2 + M6;
    ADD( M1, M3, AResult, HalfSize);
    SUB( M6, M2, BResult, HalfSize);
    ADD( AResult, BResult, C22, HalfSize);


    //بعد از اینکه سی 11 تا سی22 بدست اومد (یعنی تمام زیر ماتریس ها)مقدار دهی شدن
    //وقتشه که این زیر ماتریس ها تو ماتریس اصلی قرار بگیرن.
    //با حلقه فور زیری این کارو انجام میدیم .
    //این حلقه دقیقا عین همون حلقه ای هست که ما ازش استفاده کردیم تا یه ماتریس بزرک رو به چهارتا زیر ماتریس
    //تقسیم کنیم . حالا همونو برعکس کردیم . همین .
    //at this point , we have calculated the c11..c22 matrices, and now we are going to
    //put them together and make a unit matrix which would describe our resulting Matrix.
    for (int i = 0; i < N/2 ; i++)
    {
    for (int j = 0 ; j < N/2 ; j++)
    {
    MatrixC[i][j] = C11[i][j];
    MatrixC[i][j + N / 2] = C12[i][j];
    MatrixC[i + N / 2][j] = C21[i][j];
    MatrixC[i + N / 2][j + N / 2] = C22[i][j];
    }
    }


    //در آخر هم همه فضاهایی که از رم گرفته بودیم برای ساخت آرایه ها با اندازه های متفاوت .به رم برمیگردونیم
    //اگه ما اینکارو نکنیم حتی اگه برنامه تموم هم بشه این فضاها همینجوری اشغال شده باقی میمونن! و باعث اتلاف رم میشن
    //برای همین همونطوری که ساخته بودیمشون . حالا بصورت معکوس پاکشون هم میکنیم .

    // dont forget to free the space we alocated for matrices,

    for (int i = 0; i < newLength; i++)
    {
    delete[] A11[i];delete[] A12[i];delete[] A21[i];
    delete[] A22[i];

    delete[] B11[i];delete[] B12[i];delete[] B21[i];
    delete[] B22[i];
    delete[] C11[i];delete[] C12[i];delete[] C21[i];
    delete[] C22[i];
    delete[] M1[i];delete[] M2[i];delete[] M3[i];delete[] M4[i];
    delete[] M5[i];delete[] M6[i];delete[] M7[i];
    delete[] AResult[i];delete[] BResult[i] ;
    }
    delete[] A11;delete[] A12;delete[] A21;delete[] A22;
    delete[] B11;delete[] B12;delete[] B21;delete[] B22;
    delete[] C11;delete[] C12;delete[] C21;delete[] C22;
    delete[] M1;delete[] M2;delete[] M3;delete[] M4;delete[] M5;
    delete[] M6;delete[] M7;
    delete[] AResult;
    delete[] BResult ;


    }//end of else


    return 0;
    }

    //تابع ادد هم 4 تا پارارمتر میگیره . دو تا ماتریس برای جمع کردن و یکی برای ذخیره حاصل . و آخری هم طول آرایه ها
    // ما گفته بودیم که آرایه دو بعدی ساختیم دیکه درسته ؟
    //پس میتونیم این شکلی ازش استفاده کنیم
    //A[i][j]
    //اما فقط یه مشکلی هست . تعداد سطر و ستونش مشخص نیست! برای همین ما طول آرایه رو میفرستیم
    //و چون آرایه ما تعداد سطر و ستونش با هم برابره با یه متغییر کارمون راه می افته .
    //دو ثانیه به این تابع نگاه کنید همه چیز مشخصه .
    int ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
    {
    for ( int i = 0; i < MatrixSize; i++)
    {
    for ( int j = 0; j < MatrixSize; j++)
    {
    MatrixResult[i][j] = MatrixA[i][j] + MatrixB[i][j];
    }
    }
    return 0;
    }

    //این هم مثل بالایی
    //ماتریس سایزی که میبینید در اصل اندازه ماتریس نیست ها .
    //من اسمشو بد انتخاب کردم .
    //این در اصل نشانگر تعداد سطر و ستون ماست . چون سطر و ستون ما با هم برابره پس من گفتم خوب بگم
    //اندازه ماتریس تا جور در بیاد همین.!
    int SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
    {
    for ( int i = 0; i < MatrixSize; i++)
    {
    for ( int j = 0; j < MatrixSize; j++)
    {
    MatrixResult[i][j] = MatrixA[i][j] - MatrixB[i][j];
    }
    }
    return 0;
    }

    //این هم برای ضرب کردن دوتا ماتریس بصورت معمولی هست .
    //طولشو فرستادیم تا بدونیم چندتا سطر و چندتا ستون دارن!
    //مشخصه دیگه چیکار میکنه دیگه نه ؟
    int MUL( int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
    {
    for (int i=0;i<MatrixSize ;i++)
    {
    for (int j=0;j<MatrixSize ;j++)
    {
    MatrixResult[i][j]=0;
    for (int k=0;k<MatrixSize ;k++)
    {
    MatrixResult[i][j]=MatrixResult[i][j]+MatrixA[i][k]*MatrixB[k][j];
    }
    }
    }
    return 0;
    }

    //این هم تابعی برایر کردن ماتریس های آ و ب بصورت رندوم
    void FillMatrix( int** MatrixA, int** MatrixB, int length)
    {
    for(int row = 0; row<length; row++)
    {
    for(int column = 0; column<length; column++)
    {
    //نکته این تابع فقط همینه .
    //rand() %5
    //اون 5 بازه تولید اعداد تصادفی هست .
    //یعنی وقتی من نوشتم
    //rand() %5
    //یعنی اعداد بین 0 تا 5 بصورت رندوم انتخاب میشن .
    //اگه بنویسم
    //1 + rand() %5
    //این یعنی اعداد تصادفی از 1 تا 5 تولید بشن .
    //همین.
    //
    MatrixB[row][column] = (MatrixA[row][column] = rand() %5);
    //matrix2[row][column] = rand() % 2;//ba hazfe in khat 50% afzayeshe soorat khahim dasht
    }

    }
    }

    //این هم برای نمایش محتویات یه ماتریسه .
    void PrintMatrix(int **MatrixA,int MatrixSize)
    {
    cout<<endl;
    for(int row = 0; row<MatrixSize; row++)
    {
    for(int column = 0; column<MatrixSize; column++)
    {

    //اینجا گفتیم که محتویات هر خونه ماتریس رو با فاصله 1 تب نمایش بده
    cout<<MatrixA[row][column]<<"\t";
    //بعد گفتیم که اگه یه سطر نمایش داده شد برای نمایش سطر بعدی برو خط زیری شروع بکار کن.همین.
    if ((column+1)%((MatrixSize)) == 0)
    cout<<endl;
    }

    }
    cout<<endl;
    }
    //و من مُردم بس که نوشتم :دی




    این هم همون پروژه ولی باتوضیحات انگلیسی ( که دلیلش قبلا عنوان کردم ) :

    متن پنهان



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

    موضوعات مشابه:
    فایل های پیوست شده
    Shojaee, Pouya, Meysam.M و 3 نفر دیگر این نویسه را می پسندند.
    توکل بخدا
    http://DeepLearning.ir
    اولین و تنها مرجع یادگیری عمیق ایران


    هرکس از ظن خود شد یار من
    از درون من نجست اسرار من




  2. #2
    عضو تازه وارد
    تاریخ عضویت
    2013 May
    ارسال ها
    13
    تشکر
    10
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    سلام ببخشید من گیج شدم خطا تووهم تو هم که نمیشه خوند
    میشه یک مثال بزننین تو اجرا کردن چجوریه
    من اینجوری بگین بهتر میفهمم چیه؟؟؟
    ممنون


  3. #3
    بنیانگذار
    تاریخ عضویت
    2010 January
    محل سکونت
    زیر سایه خدا
    سن
    37
    ارسال ها
    1,308
    تشکر
    2,923
    تشکر شده 2,205 بار در 886 پست
    نوشته های وبلاگ
    37


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    نقل قول نوشته اصلی توسط parniyan7rang نمایش پست ها
    سلام ببخشید من گیج شدم خطا تووهم تو هم که نمیشه خوند
    میشه یک مثال بزننین تو اجرا کردن چجوریه
    من اینجوری بگین بهتر میفهمم چیه؟؟؟
    ممنون
    سلام.
    اینجا گفته شده دیگه :

    //اینجا هم گفتیم که بنده خدا اندازه ماتریس ها رو وارد کن . //با cin
    //متغییر ها رو مقدار دهی میکنیم . )یعنی هرچی که کاربر وارد کرد رو بریز تو متغییر
    cout<<"\nPlease Enter your Matrix Size(must be in a power of two(eg:32,64,512,..): ";
    cin>>MatrixSize;
    //اینجا هم گفتیم که اون آستانه رو خودت وارد کن . تا نتیجه کارایی ماتریس استراسن رو خودت ببنی وقتی که آستانه کمو زیاد میشه.
    //در ضمن گفتیم که این استانه هم باید یه عدد توان دو باشه . مثل 2 4 8 و ..غیره . یعنی 2 به توان یه عددی بشه اون! اکی؟
    cout<<"Please Enter your threshold (Astane: 2,4,8,16,32,64,...)";

    cin>>threshold;


    کافیه شما اندازه ماتریس ها تون رو ابتدا وارد کنید . مثلا 2048 بعد آستانه رو هم وارد کنید . آستانه همون حد و اندازه ای هست که برنامه دیگه اون رو به بخشهای کویچکتر تقسیم نمیکنه و میاد مستقیما از ضرب معمولی برای محاسبه اون ماتریس استفاده میکنه . هر اندازه ای بالاتر از استانه به ماتریس های کوچیکتر شکسته میشه انقدر این کار انجام میشه تا به اندازه استانه برسن .
    تو کتابهای درسی و غیره همه استانه رو 64 در نظر گرفتن (اگه درست یادم مونده باشه ) که این اشتباهه . آستانه بر اساس ورودی شما میتونه متغییر بشه و با برنامه بالا میتونید این قضیه رو تست کنید و ببینید چقدر در زمان اتمام کار ضرب ماتریسها موثر هست .

    برنامه بصورت خودکار میاد و ماتریس ها رو مقدار دهی میکنه با اعداد رندوم (توسط تابع FillMatrix ) که دیگه شما خودتون مجبور نباشید هی ورودی بدید. اگه میخوایید به ماتریستون خودتون عدد بدید و پرش کنید این کار رو میتونید تو همون تابع FillMatrix انجام بدید.

    توکل بخدا
    http://DeepLearning.ir
    اولین و تنها مرجع یادگیری عمیق ایران


    هرکس از ظن خود شد یار من
    از درون من نجست اسرار من




  4. #4
    عضو تازه وارد
    تاریخ عضویت
    2013 May
    ارسال ها
    13
    تشکر
    10
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    استانه یعنی چی؟؟؟


  5. #5
    بنیانگذار
    تاریخ عضویت
    2010 January
    محل سکونت
    زیر سایه خدا
    سن
    37
    ارسال ها
    1,308
    تشکر
    2,923
    تشکر شده 2,205 بار در 886 پست
    نوشته های وبلاگ
    37


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    نقل قول نوشته اصلی توسط parniyan7rang نمایش پست ها
    استانه یعنی چی؟؟؟
    آستانه یعنی همون حد

    اینجا هم ما یه حدی رو مشخص میکنیم تو الگوریتم میگیم اگه مثلا اندازه ماتریس ما بود مثلا 8 در 8 بیاد بصورت همون ضرب معمولی - اینا رو ضرب کن در هم . چون اگه بخواییم این ماتریس های 8 در 8 رو بصورت استراسن هی تقسیم کنیم به تیکه های کوچیکتر و بصورت بازگشتی فراخونیش کنیم برعکس زمان بیشتری طول میکشه و بصرفه نیست . برای همین اومدن گفتن ما این تقسیم کردن ماتریس به ماتریسای کوچیکتر رو تا یه حد (اندازه ) خاصی انجام بدیم از اون حد به پایین رو ضرب معمولی انجام بدیم .

    -نکته :
    یادتون باشه که استراسن وظیفش تقسیم ماتریس بزرگ به ماتریسهای کوچیکتر و بدست اوردن نتیجه ضرب اونهاست . اگه ما بخواییم همه ماتریس ها رو با روش استراسن ضرب کنیم اتقاقا زمان بیشتری صرف میشه . برای اینکه این اتفاق نیوفته ما
    میایم ماتریسهایی با اندازه مناسب که ضرب معمولیشون سریع انجام میشه رو بصورت معمولی انجام میدیم و بقیه رو بصورت استراسن انجام میدیم .

    parniyan7rang این نویسه را میپسندد.

  6. #6
    عضو تازه وارد
    تاریخ عضویت
    2013 May
    ارسال ها
    13
    تشکر
    10
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    ببخشید این همه سوال میکنم چون واقعا نه استاد خوبی داریم نه برنامه نویس خوبی هستم...
    یک سوال دیگه؟؟؟
    multiplication started:559 یعنی چی؟؟؟البته برای ماتریس 4در 4
    بعد یکسوال دیگه مگه در اصل قانون استراسن این نیست که بیاد به ماتریسای کوچکتر تبدیلش کنه؟؟؟
    بعد شما میگین تا یک حد خاصی که رسید ضرب معمولی انجام میده ..چیو در چی ضرب میکنه ما که فقط اومدیم بهش اندازه ماتریسو دادیم اون عددارواز کجا میاره تو ستونا وسطرا قرار میده...


  7. #7
    عضو تازه وارد
    تاریخ عضویت
    2017 December
    ارسال ها
    1
    تشکر
    0
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    سلام
    فک نمیکنم سخت باشه جاواش رو هم نوشت نه؟

    دمتون گرم

    ویرایش توسط hamidrezarashidian : 31st December 2017 در ساعت 09:56 PM

 

 

کاربران برچسب خورده در این موضوع

کلمات کلیدی این موضوع

علاقه مندی ها (Bookmarks)

علاقه مندی ها (Bookmarks)

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  


Powered by vBulletin
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0
Persian Language By Ustmb.ir
این انجمن کاملا مستقل بوده و هیچ ارتباطی با دانشگاه علوم و فنون مازندران و مسئولان آن ندارد..این انجمن و تمامی محتوای تولید شده در آن توسط دانشجویان فعلی و فارغ التحصیل ادوار گذشته این دانشگاه برای استفاده دانشجویان جدید این دانشگاه و جامعه دانشگاهی کشور فراهم شده است.لطفا برای اطلاعات بیشتر در رابطه با ماهیت انجمن با مدیریت انجمن ارتباط برقرار کنید
ساعت 09:26 PM بر حسب GMT +4 می باشد.