ریاضیات برتر
ریاضیات هم علم است و هم هنر, هنری در خدمت بشریت!
درباره وبلاگ


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

مدیر وبلاگ : ابوتراب پورحقانی

آیا تاکنون برایتان اتفاق افتاده است که بخواهید هنگام برنامه نویسی، توابع ریاضی را روی اعداد خیلی بزرگ اجرا کنید، مثلا دو عدد چند صد رقمی را با هم جمع کنید یا در هم ضرب کنید؟

همانطور که می دانید این کار در زبان های رایج برنامه نویسی به طور عادی مقدور نیست، زیرا این گونه زبانها اعداد را در چند بایت ذخیره میکنند. مثلا در زبان C++ بزرگترین عدد صحیحی که میتوان در یک متغیر ذخیره کرد عدد 1-264 است که از 10 به توان 20 کمتر است.

به نظرتان چگونه می توان بر این محدودیت غلبه کرد؟ آیا راهی عملی در این زمینه وجود دارد؟

جواب مثبت است. یکی از مدرن ترین و سریع ترین روشها برای ذخیره اعداد با طول دلخواه و کار با آنها استفاده از آرایه پویاست. در این روش، عدد را در آرایه ای پویا که هر مولفه آن از نوع unsigned long long int است ذخیره میکنند. سپس توابع مربوط به چهار عمل اصلی را بر حسب این آرایه تعریف میکنند و الی آخر.
به ظاهر انجام این کار ساده است. اما هنگام پیاده سازی این روش، مشکلات زیادی سر راه قرار دارد، مثلا باید به مباحث ریاضی خصوصا مباحث مربوط به نظریه اعداد مسلط باشید. همچنین به یکی از زبانهای برنامه نویسی مانند زبان C++ در حد حرفه ای وارد باشید.
اگر به دنبال کتابی مفید در این زمینه می گردید کافیست به کتاب Modern Computer Arithmetic که به زبان انگلیسی است مراجعه کنید تا با الگوریتم های مربوطه آشنا شوید.
اما زیاد نگران نباشید. اساتید برنامه نویسی در دنیا برای رفع این مشکل، کتابخانه های متنوع رایگانی به زبان C و C++ و ... نوشته اند، مانند CLN, MPIR , GMP و ... . با جستجو در اینترنت می توانید به رایگان هرکدام را که خواستید دانلود کنید.
در این مقاله قصد داریم قوی ترین کتابخانه در این زمینه را ،که GMP Library است، بررسی کنیم و اولین برنامه را به وسیله آن بنویسیم.
کتابخانه GMP Library در حال حاضر قوی ترین کتابخانه در زمینه محاسبات عددی در دنیاست که به زبان C و اسمبلی نوشته شده است. البته از C++ نیز پشتیبانی می کند. این کتابخانه اپن سورس بوده و تحت لیسانس GNU قرار دارد. جدیدترین نسخه این کتابخانه را می توان از سایت رسمی آن به نشانی gmplib.org دریافت کرد. در این سایت علاوه بر فایل کتابخانه، میتوان به فایل راهنمای آن و نیز فایل های اضافی دیگر نیز دسترسی پیدا کرد. توصیه می شود فایل راهنمای آن را به طور کامل مطالعه کنید. 
با توجه به اینکه کتابخانه GMP برای محاسبات بزرگ طراحی شده، طراحی آن به گونه ای است که در نهایت هر محاسبه ای را به محاسبه در اعداد طبیعی تبدیل میکند که این کار، سرعت محاسبات را بالا می برد. در بین فایلها و پوشه های کتابخانه GMP، توابع محاسباتی مربوط به اعداد طبیعی در پوشه mpn قرار دارد که متناسب با هر پردازشگری، دستورات اختتصاصی محاسبات در زبان اسمبلی برای آن پردازشگر نوشته شده است. در بین پوشه های موجود در پوشه mpn، پوشه ای به نام generic قرار دارد. در این پوشه می توان الگوریتم های محاسباتی مربوط به اعداد طبیعی را بر خلاف پوشه های مجاور (که به زبان اسمبلی نوشته شده اند) به زبان C یافت. دستورات و توضیحات طوری نوشته شده اند که همراه با فصل پانزده راهنمای GMP فصل Algorithms) ) میتوان الگوریتم های محاسباتی را درک کرد. البته کتاب Modern Computer Arithmetic نیز منبع خوبی در زمینه توضیح الگوریتم هاست.
این کتابخانه اصالتا برای سیستم عاملهای مبتنی بر یونیکس، مانند لینوکس، نوشته شده است اما می توان در سیستم عامل های دیگر مانند ویندوز نیز از آن استفاده کرد. مراحل نصب این کتابخانه در فایل راهنمای آن ،که به زبان انگلیسی می باشد، موجود است. با توجه به اینکه در زمینه نصب این کتابخانه در ویندوز مطالب به صورت کلی در فایل راهنمای آن آمده است، قصد داریم روش نصب و استفاده از آن را در ویندوز به طور کامل و ساده شرح دهیم.
1 – نصب در ویندوز برای محیط برنامه نویسی CodeBlocks
الف) ابتدا یک کامپایلر C++ مانند Mingw یا TDM GCC را نصب میکنیم. می توان CodeBlocks را به صورت کامل نصب کرد تا کامپایلر هم نصب شود(البته دقت کنید که در پوشه ای نصب کنید که فاصله خالی نداشته باشد مثلا در ریشه درایو C). همچنین دقت کنید آدرس کامپایلر نباید شامل فاصله خالی باشد مثلا آدرس کامپایلر به صورت c:\TDM-GCC-64 قابل استفاده است اما آدرس c:\program files\mingw برای مراحل بعدی قابل استفاده نیست چون در آدرس، فاصله خالی وجود دارد. کامپایلرها و برنامه فوق را به راحتی می توان با جستجو در اینترنت به دست آورد. همه اینها رایگان است.
ب) حال برنامه MSYS را نصب کنید. این برنامه از سایت mingw.org قابل دانلود است. این برنامه شبیه ساز محیط شل در لینوکس است. آدرس پیش فرض نصب را که c:\msys است، تغییر ندهید.
ج) در آخرین مرحله نصب برنامه فوق، از شما در مورد ادامه نصب می پرسد. حرف y را تایپ کنید. سپس می پرسد آیا یک کامپایلر مانند mingw به صورت نصب شده دارید. دوباره حرف y را تایپ کنید. حال آدرس کامپایلر را میپرسد که باید به شکلی که نشان داده، آدرس را تایپ کنید، مثلا c:/TDM_GCC-64. اگر این مراحل به شکلی که بیان شد نیامد کافیست از پوشه نصبی برنامه MSYS وارد پوشه  postinstall  شده و سپس فایل pi.bat را اجرا کنید.
د) حال در پوشه نصبی برنامه MSYS، پوشه ای به نام home وجود دارد. داخل این پوشه، پوشه ای به نام اسم کاربریتان در ویندوز مثلا Administrator وجود دارد. داخل این پوشه، فایل gmp-6.1.2.tar.bz2 را که قبلا از gmplib.org دانلود کرده اید کپی کنید. ممکن است شماره ها در این فایل عوض شده باشد. اما حتما پسوند bz2 را دانلود کنید. اگر پسوند bz2 را پیدا نکردید هر پسوندی که بود دانلود کنید و سپس در همین پوشه از حالت فشرده خارج کنید. در این صورت پوشه ای به نام gmp-6.1.2 در کنار فایل فشرده خواهید داشت. داخل این پوشه بروید. اگر تعداد زیادی فایل و پوشه، مانند gmp-impl.h و mpn و ... مشاهده کردید، این مرحله را درست انجام داده اید.
ه) حال برنامه MSYS را اجرا کنید. کافیست از منوی استارت آن را اجرا کنید یا در پوشه نصبی آن، فایل msys.bat را اجرا کنید. محیط shell باز می شود. محیط shell شبیه همان کنسول ویندوز یا همان محیط داس است که نوشته هایش رنگی است.
و) در محیط shell دستورات زیر را به ترتیب تایپ کرده و دکمه اینتر را بزنید. توضیح هر دستور جلوی آن گفته شده است. اگر در مرحله د) فایل gmp را از حالت فشرده خارج کرده اید از مراحل 1) و 2) صرفنظر کنید و به مرحله 3) بروید. در غیر این صورت مراحل را به ترتیب از مرحله 1) انجام دهید:
:ls این دستور لیست فایلها و پوشه های مسیر جاری را نشان می دهد. مطمئن شوید فایل gmp-6.1.2.tar.bz2 در این پوشه قرار دارد. اگر قرار نداشت یا فایل را در پوشه جاری کپی کنید یا با دستور cd به پوشه ای که در آن قرار دارد بروید.  مثلا دستور cd newfolder یا مثلا cd ... با دستور ls مطمئن شوید فایل gmp در پوشه جاری قرار دارد. با شروع برنامه MSYS، به صورت پیش فرض پوشه c:\msys\1.0\home\Administrator مورد اشاره قرار گرفته است، که Administrator پوشه ای است که در پوشه home هنگام نصب Msys ایجاد می شود و نام این پوشه شبیه نام کاربریتان در ویندوز است.
tar -xf gmp-6.1.2.tar.bz2: این دستور باعث میشود فایل gmp.6.1.2.tar.bz2 از حالت فشرده خارج شود و در پوشه ای با نام gmp.6.1.2 قرار گیرد. این دستور برای پسوندهای غیر از bz2 کار نمی دهد.
cd gmp-6.1.2: با این دستور به داخل پوشه ای که فایلهای gmp در آن قرار دارد بروید. ممکن است عددهای مربوط به بسته ای که در اختیار دارید متفاوت از این ورژن باشد. پس دستور را درست وارد کنید. میتوانید بعد از این دستور، دستور ls را وارد کنید. اگر تعداد زیادی فایل و پوشه مربوط به این کتابخانه دیدید این مرحله را درست انجام داده اید.
./configure : این دستور اولین و مهمترین دستور نصب است. اگر این دستور را به همین شکل و بدون پارامتر تایپ و اجرا کنید کتابخانه gmp برای زبان C تنظیم می شود. اما اگر دستور ./configure --enable-cxx را تایپ و اجرا کنید هم برای زبان C و هم C++ تنظیم می شود. اگر میخواهید پارامترهای دیگر را استفاده کنید به فایل راهنمای GMP، فصل دوم (Installing GMP) بخش اول (Build Options) مراجعه کنید. البته پارامترهای دیگری از جمله پارامتری برای ساخت dll ( که دستور کامل آن configure --disable-static --enable-share/. است) وجود دارد که می توانید مطالعه کنید. همچنین پارامترهای مربوط به سی پی یو های مختلف و سیتسم عامل های متفاوت وجود دارد. برای کار حرفه ای با GMP حتما مطالب فصل دوم راهنمای GMP را که مربوط به نصب GMP است به طور کامل مطالعه بفرمایید.
:make این دستور، فایلهای مورد نیاز را با توجه به تنظیمات مربوط به دستور قبلی می سازد.
make check: این دستور، فایلهای تولید شده را بررسی کرده و در صورت لزوم خطاها را نشان می دهد. این دستور برای بررسی صحت مراحل قبل است.
make install: این دستور کار نصب کتابخانه GMP را به طور کامل تمام می کند. با پایان این موفقیت آمیز این مرحله، کتابخانه GMP به طور کامل نصب شده و آماده استفاده است. به طور خلاصه دستورات به صورت زیر هستند:
ls
tar -xf gmp-6.1.2.tar.bz2
cd gmp-6.1.2
./configure
make
make check
make install
حال می توانید پنجره MSYS را ببندید.
توجه: مراحل 4 تا 7 زمان بر است. با صبر و حوصله آن را به انجام برسانید.

2- استفاده از GMP در CodeBlocks:
برای استفاده از این کتابخانه در CodeBlocks ،باید این کتابخانه را به کامپایلر CodeBlocks که همان کامپایلر مرحله الف در قسمت قبلی است معرفی کنیم. برای این کار وارد منوی Settings->Compile… در برنامه CodeBlocks شوید. کامپایلر مرحله الف را به عنوان کامپایلر پیش فرض انتخاب کنید و روی گزینه Set as default کلیک کنید.. حال در سربرگ Linker settings با استفاده از دکمه Add تمام فایلهای با پسوند .a را که در پوشه .libs واقع در پوشه کتابخانه نصبی GMP قرار دارد به کامپایلر اضافه کنید. مثلا:  C:\msys\1.0\home\Administrator\gmp-6.1.2\.libs\libgmp.a.
سپس در سربرگ Search Directories وارد سربرگ Compiler شوید و با استفاده از دکمه Add آدرس فایل gmp.h را در پوشه نصبی GMP به کامپایلر اضافه کنید. مثلا C:\msys\1.0\home\Administrator\gmp-6.1.2.
با انجام مراحل فوق، CodeBlocks قادر به استفاده از این کتابخانه خواهد بود.

3- اولین مثال در CodeBlocks:
کافیست وارد منوی File->New->Project… شده و یک پروژه از نوع Console application بسازید (برای ساخت این نوع پروژه کافیست مراحل آن را که ساده است دنبال کنید. ترجیحا در مرحله انتخاب زبان، زبان برنامه نویسی را C++ انتخاب کنید تا بتوان از قابلیتهای همزمان C و C++ بهره جست). حال در فایل فایل main.cpp به جای چند دستور که به صورت پیش فرض قرار دارد کافیست کدهای نمونه زیر را وارد کنید:
#include <iostream>
#include <gmp.h>

using namespace std;

int main()
{
    mpz_t x,y,z;
    mpz_init_set_str(x, "31415926534850840558979323845806862643383279502884", 10);
    mpz_init_set_str(y, "56977755575576795769759769579555556797979797567957", 10);
    mpz_init(z);
    cout << "x = " << mpz_get_str(NULL,10,x) << endl;
    cout << "y = " << mpz_get_str(NULL,10,y) << endl;
    mpz_mul(z,x,y);
    cout << "z = " << mpz_get_str(NULL,10,z) << endl;
    mpz_init(z);
    cout << "z = " << mpz_get_str(NULL,10,z) << endl;
    return 0;
}

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

برای نوشتن برنامه های پیچیده تر در GMP کافیست به فایل راهنمای GMP که از سایت رسمی آن یعنی gmplib.org قابل دریافت است مراجعه کرده و برنامه مورد نظرتان را بنویسید.

نکته مهم: اگر نمی خواهید مراحل بالا را برای نوشن برنامه با استفاده از GMP طی کنید میتوانید دو فایل mini-gmp.c و mini-gmp.h را از پوشه mini-gmp برداشته و کنار فایل برنامه نویسی خود کپی کنید و برنامه ای شبیه به برنامه زیر بنویسید:
#include <iostream>
#include "mini-gmp.c"

using namespace std;

int main()
{

    mpz_t x;
    mpz_init_set_str (x, "999855679798712000097979999879798797979999099", 10);

    char *str = mpz_get_str(NULL, 10, x);

    cout << "str = " << str << endl;
    return 0;
}
البته استفاده از این روش چند عیب دارد: اولا، این روش محدود به اعداد صحیح است. ثانیا، بخاطر اینکه از دستورات اسمبلی استفاده نمی کند 10 برابر کندتر از برنامه اصلی است. اما برای شروع کار و آشنایی، مفید است و نیازی به نصب GMP ندارد.
موفق باشید.





نوع مطلب : ریاضیات، محاسبات پیچیده، کتابخانه های برنامه نویسی، 
برچسب ها : محاسبات، محاسبات پیچیده، GMP، برنامه نویسی، الگوریتم های محاسباتی،
لینک های مرتبط : کتابخانه GMP، کامپایلر TDM GCC، ابزار برنامه نویسی MinGW، نرم افزار CodeBlocks،
نظرات پس از تایید نشان داده خواهند شد.


آمار وبلاگ
  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :
 



در این وب
در كل اینترنت

 
 
 
شبکه اجتماعی فارسی کلوب | Buy Website Traffic | Buy Targeted Website Traffic