ضرب دو عدد بزرگ

[baran_mehr]

چطور میتونم دو عدد خیلی بزرگ رو در هم ضرب کنم؟
مثلا بالای 10000 عدد(البته طوری که cpu نترکه)

[m_hasanpour]

با سلام و عرض ادب
دوست عزیز من ابن برنامه را به زبان پاسکال نوشتم. باید از آرایه استفاده کنی.
قابلیتهای این برنامه
1- جمع دو عدد بزرگ
2- تفریق دو عدد بزرگ
3- ضرب یک عدد 1 رقمی در یک عدد بزرگ
4- ضرب یک عدد 2 رقمی در یک عدد بزرگ

البته آرایه 2 بعدی نیز میتوانی استفاده کنی. وقتی اندیس اول عدد اول در آرایه a را در اندیس اول عدد دوم در آرایه b ضزب کردی اگر بزگتر از 9 شد عدد بدست آمده را بر 10 تقسیم کرده و باقیمانده را در اندیس اول آرایه c قرار داده و خارج قسمت را با استفاده از یک متغیر در اندیس دوم آرایه c جمع کن این روال را تا زمانی که به عدد صفر می‌رسی انجام بده.

با تشکر
موفق باشید

[tdkhakpur]

سلام
تالار C++‎ نمونه ای هست.(چمع و ضرب 300 رقمی).

[baran_mehr]

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

[tdkhakpur]

سلام
خوب دوست گرامی چه نوع پیشنهادی میخوایید بدیم شما که الگوریتم کار را خودتون میدونید.
ولی یک نظر هم به کار شما بدم و این هست که برای بدست آوردن بزرگترین عدد اول کار مناسبیه ولی من هم به فکرش افتادم ولی آخرش به کمبود فضای ذخیره سازی میرسه.
از دوستان اگر کسی فرمول ریاضی در مورد عدد اول دارند به مطالب اضافه کنند ممنون میشم.

[baran_mehr]

دوست من اون الگوریتمی که من تو ذهنم داریم به دو صورت هست:
اول:اینکه مثل یه ضرب عادی یکی یکی عدد ها رو بخونیم و در عدد دوم ضرب کنیم و هر بار یه صفر اضافه کنیم و بریم سراق عدد بعدی . در نهایت مجموع تمام ضرب ها رو بدست بیاریم. که این روش فوقلاده سنگینه
فرض کنید ما 2 تا عدد 5000 رقمی داریم اونوقت میشه 250000 هزار بار عمل ضرب که تازه از این حرفا بیشتر و بعدش جمع نتیجه هاست که اونم خودش خیلیه
اما مشکل اینجاست که این همه عدد کجا باید نگهداری بشن؟؟
و در مرحله بعد چطور باید این اعداد رو با هم جمع کرد؟؟ چون برای هر جمع دوباره باید از الگوریتم جمع استفاده کرد

[baran_mehr]

یه راه حل دیگه اینه که ما از یه ترفند استفاده کنیم.
روش دوم:به جای اینکه اعداد رو در هم ضرب کنیم از عمل جمع استفاده کنیم. فرض کنید 3 ضرب در 5 یعنی 3 را 5 بار با خودش جمع کنیم.3+3+3+3+3=15
این کار باعث میشه تا حجم کار نسبت به روش اول نصف بشه!!!
اما من میخوام از خود ضرب استفاده کنم.

[Saeed_m_Farid]

دوست من اون الگوریتمی که من تو ذهنم داریم به دو صورت هست:
اول:اینکه مثل یه ضرب عادی یکی یکی عدد ها رو بخونیم و در عدد دوم ضرب کنیم و هر بار یه صفر اضافه کنیم و بریم سراق عدد بعدی . در نهایت مجموع تمام ضرب ها رو بدست بیاریم. که این روش فوقلاده سنگینه
فرض کنید ما 2 تا عدد 5000 رقمی داریم اونوقت میشه 250000 هزار بار عمل ضرب که تازه از این حرفا بیشتر و بعدش جمع نتیجه هاست که اونم خودش خیلیه
اما مشکل اینجاست که این همه عدد کجا باید نگهداری بشن؟؟
و در مرحله بعد چطور باید این اعداد رو با هم جمع کرد؟؟ چون برای هر جمع دوباره باید از الگوریتم جمع استفاده کرد

سلام

اولاً مطمئن نیستم اون تعداد ارقام موردنظر شما که کم کم هم داره بیشتر میشه، با الگوریتمهای معمولی که تو دسترس هستند قابل انجام باشه؛ چون با انجام عمل ضرب روی n رقم شما باید ساختاری برای 2n رقم پیش بینی کنید و رفته رفته حجم عملیات زیاد میشه، واسه الگوریتم عملیات اعداد 10000 رقمی و بیشتر فکر کنم بهتره به ناسا سر بزنی! بگذریم ...

ساختار ذخیره پیشنهادی به نظر من باید بر پایه لیست پیوندی باشه؛ مثلاً تو ++C میشه از vector استفاده کرد که یه کلاس تقریبا مستقل از نوع داده است و در دلفی از dynamic array های بهینه شده، که نمونه اش رو مثلاً تو سایت Torry و یا مثلاً اینجا تو SourceForge میتونید پیدا کنید ...

من نمونه ای از دوتا برنامه اجرایی که تو BCB++6 و #C نوشته شدن رو میذارم اینجا (ولی فکر کنم سی بیلدریه نیاز به bpl ها داشته باشه، یعنی یا باید سی بیلدر نصب باشه یا bpl ها رو بذارید کنار برنامه) که اگه بدردتون میخوره بگید تا کل سورس رو هم بذارم، ولی مطمئن باشید که نه روش اول و نه روش دوم که شما مطرح کردید، جوابگوی 100 رقم هم نخواهند بود و مخصوصاً روش دوم پیشنهادی شما که اصلاً عملی نیست؛ روش کار همون ضرب تک تک عناصر و محاسبه carry out ها برای ارقام بعدی است ولی بصورت بهینه شده ...

کد ++C واسه اپراتور عمل ضرب کلاس اعداد بزرگ رو میذارم اینجا تا اگه خواستین بتونید ایده بگیرید، ولی تو دلفی این ساختار رو پیاده نکردم؛ اگه خواستید بگین تا کد ++C یا #C رو براتون آپ کنم...

//**************************************************  *************************



TBigInteger TBigInteger::operator * ( const TBigInteger &r ) const

{

    TBigInteger temp;

    if( !data || !r.data )

        return temp;

    if( *this == "0" || r == "0" )

    {

        temp.data = new char[ 1 ];

        if( temp.data )

        {

            temp.size = 1;

            temp.sign = false;

            temp.data[ 0 ] = '0';

            return temp;

        }

    }

    vector< unsigned > v( size + r.size );

    unsigned i, j, t, c;

    for( i = 0 ; i < size ; i++ )

    {

        c = 0;

        for( j = 0 ; j < r.size ; j++ )

        {

            t = v[ i + j ];

            v[ i + j ] = ( t + c + ( data[ i ] - '0' ) * ( r.data[ j ] - '0') ) % 10;

            c = ( t + c + ( data[ i ] - '0' ) * ( r.data[ j ] - '0' ) ) / 10;

        }

        if( c )

            v[ i + j ] = c;

    }

    for( i = 0 ; i < v.size() ; i++ )

        if( v[ v.size() - i - 1 ] != 0 )

            break;

    temp.data = new char[ v.size() ];

    if( temp.data )

    {

        temp.size = v.size() - i;

        temp.sign = ( sign && !r.sign ) || ( !sign && r.sign );

        for( j = 0 ; j < temp.size ; j++ )

            temp.data[ j ] = v[ j ] + '0';

    }

    return temp;

}

//**************************************************  *************************

[tdkhakpur]

اول:اینکه مثل یه ضرب عادی یکی یکی عدد ها رو بخونیم و در عدد دوم ضرب کنیم و هر بار یه صفر اضافه کنیم و بریم سراق عدد بعدی . در نهایت مجموع تمام ضرب ها رو بدست بیاریم. که این روش فوقلاده سنگینه
فرض کنید ما 2 تا عدد 5000 رقمی داریم اونوقت میشه 250000 هزار بار عمل ضرب که تازه از این حرفا بیشتر و بعدش جمع نتیجه هاست که اونم خودش خیلیه
اما مشکل اینجاست که این همه عدد کجا باید نگهداری بشن؟؟
و در مرحله بعد چطور باید این اعداد رو با هم جمع کرد؟؟ چون برای هر جمع دوباره باید از الگوریتم جمع استفاده کرد

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

 

125453 ---> تعداد اعداد مساوی 6 هست

*

5465    ---> تعداد اعداد مساوی 4 هست

----------------------------

لذادر فوق 4 آرایه برای ضرب احتیاج دارید که مقدار فضای این آرایه ها باید برابر 6*2 باشد دلیلش هم این هست که ما حداکثر مقدار را درنظر میگیریم.
در نهایت به عمل جمع نیاز هست که این 4 آرایه 6*2 تایی را که نتایج ضرب داخلش قرار دارد با هم جمع کند که خودش در نهایت به یک آرایه دیگر برای نتیجه نیاز دارد.

[baran_mehr]

عزیز دلم ناسا خودش میاد برنامه نویسای اینجا رو میبره اونوقت ما بریم اونجا؟؟؟ وووووااااا
tdkhakpur جان همونطور که گفتید میزان فضای مورد نیاز خیلی بالاست.تازه اگر دو عدد با هم برابر باشند(تعداد ارقام)اونوقت اوضاع خیلی سخت تر میشه.
همینطور که خودتون گفتید ما اول باید ضرب کنیم و بعد جمع، یعنی دو تا الگوریتم!!! راهی به ذهنتون نمیرسه که کار رو سبکتر کنه؟؟
برای من حل این مساله خیلی مهم نیست،بیشتر میخوام بدونم بهترین راه حل چیه.

[tdkhakpur]

.
همینطور گفتید ما اول باید ضرب کنیم و بعد جمع، یعنی دو تا الگوریتم!!! راهی به ذهنتون نمیرسه که کار رو سبکتر کنه؟؟
برای من حل این مساله خیلی مهم نیست،بیشتر میخوام بدونم بهترین راه حل چیه.

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

[baran_mehr]

منظورتون رو چندان متوجه نشدم؟؟
اخه ما برای نگهداری جوابها هم نیاز به فضا داریم!! بزارید توضیح بدم:
فرض کنید ما ضرب ها رو انجام دادیم و حالا میرسی به جمع کردن ضربها، به عنوان مثال چند تا عدد زیر که همگی در ارایه هستن:
1234464645465454644
54987746343216546444
887654343225245435354
2312164448765465465445
554846478732465465465465
93464654645654646548797877
حالا وقتی میخوای اولی رو با دومی جمع کنیم باید جواب رو یک جا نگه داریم. بعد نتیجه با عدد بعدی و ...
اینجا یکم قضایا رو پیچیده میکنه

[tdkhakpur]

سلام

1234464645465454644             >1

54987746343216546444            >2

887654343225245435354          >3

2312164448765465465445        >4 

خوب در بالا به فرض 4 عمل ضرب انجام شده شما اولی را دارید حالا دومی باید یک رقم به چچ باید بره یعنی

 

54987746343216546444 ---> 549877463432165464440

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

 

1234464645465454644           >            1234464645465454644

54987746343216546444          >        549877463432165464440

887654343225245435354        >     88765434322524543535400

2312164448765465465445      > 2312164448765465465445000 

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

[baloochco]

سلام میشه سورس BigIntEXE روکامل واسم ایمیل کنی فوری فوری

با تشکر
amin.balooch@gmail.com

[صبا فدایی]

سلام همین برناه رو به زبان c ندارید؟