انجام عملیات ریاضی با اعداد بزرگ و طولانی: جمع ، ضرب ، توان

تاریخ نگارش مطلب: 2013/09/21 نویسنده: فرهاد دلیرانی

خیلی از وقت ها وقتی می خواهیم برنامه ای بنویسیم احتیاج داریم با اعداد خیلی بزرگ و سنگین کار کنیم که از محدوده ی نوع های زبان برنامه نویسیمون خارج است حتی در محدوده double هم قرار نمی گیره .اون موقع است که برناممون دچار مشکل می شه و متغییر هامون سرریز می کنند . در این مطلب می خواهیم با کدنویسی راه حلی برای این مسئله ایجاد کنیم.

فهرست مطالب

1 مسئله محاسبات با اعداد بسیار بزرگ
- 1.1 پیاده سازی برنامه محاسبات اعداد بزرگ
- 1.2 کد نهایی و کامل

مسئله محاسبات با اعداد بسیار بزرگ

برای حل این مشکل معمولا برنامه نویسان کلاس ها و تابع هایی را می نویسند البته بعضی زبان های برنامه نویسی امکانات خوبی در اختیار می گذارند مانند پایتون که می شه باه راحتی با اعداد خیلی بزرگ کار کرد من قبلا در پستی هایی جداگانه “پروژه ماشین حساب با عملیات روی اعداد ۱۰۰۰ رقمی با c” و “الگوریتم تقسیم اعداد بزرگ (fifty digit division)” به این مشکل ها پرداخته بودم ولی اون برنامه ها زیاد سریع نبودن و برای اعداد ۱۰۰۰ رقمی بودن و محدودیت اعداد داشتند.

پیاده سازی برنامه محاسبات اعداد بزرگ

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

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

تابع tipper

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

//
void Tipper(string& Num)
{
int i;
char ch;
for (i = 0; i < (int(Num.size() / 2)); i++) {
ch = Num.at(i);
Num.at(i) = Num.at((Num.size() - 1) - i);
Num.at((Num.size() - 1) - i) = ch;
}
}
//

void Tipper(string& Num)

{

int i;

char ch;

for (i = 0; i < (int(Num.size() / 2)); i++) {

ch = Num.at(i);

Num.at(i) = Num.at((Num.size() - 1) - i);

Num.at((Num.size() - 1) - i) = ch;

}

تابع sum

تابع بعدی تابع جمع sum است که برای اعداد صحیح بزرگ تر مساوی صفر است

//	Sum for heavy number
string sum(string Num1, string Num2)
{
int i;
int MaxLen;
int sum = 0;
int r = 0;
char ch;
string Num3;
Tipper(Num1);
Tipper(Num2);
if (Num1.size() < Num2.size()) {
MaxLen = Num2.size();
}
else {
MaxLen = Num1.size();
}
for (i = 0; i < MaxLen; i++) {
sum = 0;
if (i < int(Num1.size())) {
sum += Num1.at(i) - 48;
}
if (i < int(Num2.size())) {
sum += Num2.at(i) - 48;
}
ch = ((sum + r) % 10) + 48;
Num3.push_back(ch);
r = (sum + r) / 10;
}
if (r != 0) {
ch = r + 48;
Num3.push_back(ch);
}
Tipper(Num3);
return Num3;
}
// End of Sum for heavy number

// Sum for heavy number

string sum(string Num1, string Num2)

{

int i;

int MaxLen;

int sum = 0;

int r = 0;

char ch;

string Num3;

Tipper(Num1);

Tipper(Num2);

if (Num1.size() < Num2.size()) {

MaxLen = Num2.size();

}

else {

MaxLen = Num1.size();

}

for (i = 0; i < MaxLen; i++) {

sum = 0;

if (i < int(Num1.size())) {

sum += Num1.at(i) - 48;

}

if (i < int(Num2.size())) {

sum += Num2.at(i) - 48;

}

ch = ((sum + r) % 10) + 48;

Num3.push_back(ch);

r = (sum + r) / 10;

}

if (r != 0) {

ch = r + 48;

Num3.push_back(ch);

}

Tipper(Num3);

return Num3;

}

// End of Sum for heavy number

تابع ضرب یا multiplication

تابع بعدی تابع ضرب multiplication است این تابع دقیقا مثل ضرب کردن اعداد توسط خودمون عمل می کند و در آن از تابع جمع sum استفاده شده است ، ورودی این تابع اعداد دو رشته است و خروجی اش هم به صورت رشته است:

//Multiplication for heavy number
string multiplication(string Num1, string Num2)
{
int i;
int j;
int t;
int r = 0;
int mult = 0;
char ch;
string Num3;
string Sum = "0";
Tipper(Num1);
Tipper(Num2);
if (Num1.size() > Num1.size()) {
Num1.swap(Num2);
}
for (i = 0; i < int(Num1.size()); i++) {
r = 0;
for (t = 0; t < i; t++) {
Num3.push_back('0');
}
for (j = 0; j < int(Num2.size()); j++) {
mult = (Num1.at(i) - 48) * (Num2.at(j) - 48);
ch = ((mult + r) % 10) + 48;
Num3.push_back(ch);
r = (mult + r) / 10;
}
if (r != 0) {
ch = r + 48;
Num3.push_back(ch);
}
Tipper(Num3);
Sum = sum(Sum, Num3);
Num3.clear();
}
return Sum;
}
//end Multiplication for heavy number

//Multiplication for heavy number

string multiplication(string Num1, string Num2)

{

int i;

int j;

int t;

int r = 0;

int mult = 0;

char ch;

string Num3;

string Sum = "0";

Tipper(Num1);

Tipper(Num2);

if (Num1.size() > Num1.size()) {

Num1.swap(Num2);

}

for (i = 0; i < int(Num1.size()); i++) {

r = 0;

for (t = 0; t < i; t++) {

Num3.push_back('0');

}

for (j = 0; j < int(Num2.size()); j++) {

mult = (Num1.at(i) - 48) * (Num2.at(j) - 48);

ch = ((mult + r) % 10) + 48;

Num3.push_back(ch);

r = (mult + r) / 10;

}

if (r != 0) {

ch = r + 48;

Num3.push_back(ch);

}

Tipper(Num3);

Sum = sum(Sum, Num3);

Num3.clear();

}

return Sum;

}

//end Multiplication for heavy number

تابع توان یا power

این تابع هم تابع توان power است که در آن از تابع ضرب استفاده شده است ورودی اول که رشته است پایه توان است و عدد بعدی که از نوع int است عددی است که پایه باید به توان آن برسد:

//Power for heavy number
string power(string Num1, int Num2)
{
int i;
string result = "1";
for (i = 0; i < Num2; i++) {
result = multiplication(result, Num1);
}
return result;
}
//end Power for heavy number

//Power for heavy number

string power(string Num1, int Num2)

{

int i;

string result = "1";

for (i = 0; i < Num2; i++) {

result = multiplication(result, Num1);

}

return result;

}

//end Power for heavy number

کد نهایی و کامل

اینم کد کلی برنامه که برای مثال در آن ۲ به توان ۱۰۰۰ را حساب می کند :

// Heavy Number.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
//
void Tipper(string& Num)
{
int i;
char ch;
for (i = 0; i < (int(Num.size() / 2)); i++) {
ch = Num.at(i);
Num.at(i) = Num.at((Num.size() - 1) - i);
Num.at((Num.size() - 1) - i) = ch;
}
}
//
//	Sum for heavy number
string sum(string Num1, string Num2)
{
int i;
int MaxLen;
int sum = 0;
int r = 0;
char ch;
string Num3;
Tipper(Num1);
Tipper(Num2);
if (Num1.size() < Num2.size()) {
MaxLen = Num2.size();
}
else {
MaxLen = Num1.size();
}
for (i = 0; i < MaxLen; i++) {
sum = 0;
if (i < int(Num1.size())) {
sum += Num1.at(i) - 48;
}
if (i < int(Num2.size())) {
sum += Num2.at(i) - 48;
}
ch = ((sum + r) % 10) + 48;
Num3.push_back(ch);
r = (sum + r) / 10;
}
if (r != 0) {
ch = r + 48;
Num3.push_back(ch);
}
Tipper(Num3);
return Num3;
}
// End of Sum for heavy number
//Multiplication for heavy number
string multiplication(string Num1, string Num2)
{
int i;
int j;
int t;
int r = 0;
int mult = 0;
char ch;
string Num3;
string Sum = "0";
Tipper(Num1);
Tipper(Num2);
if (Num1.size() > Num1.size()) {
Num1.swap(Num2);
}
for (i = 0; i < int(Num1.size()); i++) {
r = 0;
for (t = 0; t < i; t++) {
Num3.push_back('0');
}
for (j = 0; j < int(Num2.size()); j++) {
mult = (Num1.at(i) - 48) * (Num2.at(j) - 48);
ch = ((mult + r) % 10) + 48;
Num3.push_back(ch);
r = (mult + r) / 10;
}
if (r != 0) {
ch = r + 48;
Num3.push_back(ch);
}
Tipper(Num3);
Sum = sum(Sum, Num3);
Num3.clear();
}
return Sum;
}
//end Multiplication for heavy number
//Power for heavy number
string power(string Num1, int Num2)
{
int i;
string result = "1";
for (i = 0; i < Num2; i++) {
result = multiplication(result, Num1);
}
return result;
}
//end Power for heavy number
int main()
{
cout << "5 ^ 1000 = " << endl
<< power("2", 1000) << endl;
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

// Heavy Number.cpp : Defines the entry point for the console application.

#include "stdafx.h"

#include <iostream>

#include <string>

using namespace std;

void Tipper(string& Num)

{

int i;

char ch;

for (i = 0; i < (int(Num.size() / 2)); i++) {

ch = Num.at(i);

Num.at(i) = Num.at((Num.size() - 1) - i);

Num.at((Num.size() - 1) - i) = ch;

}

// Sum for heavy number

string sum(string Num1, string Num2)

{

int i;

int MaxLen;

int sum = 0;

int r = 0;

char ch;

string Num3;

Tipper(Num1);

Tipper(Num2);

if (Num1.size() < Num2.size()) {

MaxLen = Num2.size();

}

else {

MaxLen = Num1.size();

}

for (i = 0; i < MaxLen; i++) {

sum = 0;

if (i < int(Num1.size())) {

sum += Num1.at(i) - 48;

}

if (i < int(Num2.size())) {

sum += Num2.at(i) - 48;

}

ch = ((sum + r) % 10) + 48;

Num3.push_back(ch);

r = (sum + r) / 10;

}

if (r != 0) {

ch = r + 48;

Num3.push_back(ch);

}

Tipper(Num3);

return Num3;

}

// End of Sum for heavy number

//Multiplication for heavy number

string multiplication(string Num1, string Num2)

{

int i;

int j;

int t;

int r = 0;

int mult = 0;

char ch;

string Num3;

string Sum = "0";

Tipper(Num1);

Tipper(Num2);

if (Num1.size() > Num1.size()) {

Num1.swap(Num2);

}

for (i = 0; i < int(Num1.size()); i++) {

r = 0;

for (t = 0; t < i; t++) {

Num3.push_back('0');

}

for (j = 0; j < int(Num2.size()); j++) {

mult = (Num1.at(i) - 48) * (Num2.at(j) - 48);

ch = ((mult + r) % 10) + 48;

Num3.push_back(ch);

r = (mult + r) / 10;

}

if (r != 0) {

ch = r + 48;

Num3.push_back(ch);

}

Tipper(Num3);

Sum = sum(Sum, Num3);

Num3.clear();

}

return Sum;

}

//end Multiplication for heavy number

//Power for heavy number

string power(string Num1, int Num2)

{

int i;

string result = "1";

for (i = 0; i < Num2; i++) {

result = multiplication(result, Num1);

}

return result;

}

//end Power for heavy number

int main()

{

cout << "5 ^ 1000 = " << endl

<< power("2", 1000) << endl;

return 0;

}

اینم حاصل ۲ به توان ۱۰۰۰ :

امیدوارم از حل این سوال لذت برده باشید اگر راهی داشتید یا برنامه ای برای این سوال نوشته اید حتما آن را برای ما ایمیل کنید یا در نظرات بنویسید ، کد شما در همین صفحه قرار خواهد گرفت با تشکر فراوان از این که ما را دنبال می کنید.

۲۹

الگوریتم ها و هوش مصنوعی, داده ساختار ها, سی پلاس پلاس - ++C

۲۹ نظر

Banoo
2018/01/25 در 03:52
با عرض سلام و خسته نباشیدو تشکر بابت سایت عالیتون.
پاسخ
f.ebrahimi
2017/12/27 در 14:03
سلام و خسته نباشید. این برنامه با کلاس پیاده سازی شده؟
پاسخ
- حامد آهنگری
  2017/12/27 در 17:20
  سلام
  خیر. اما خودتون می تونید با کمی تغییر و استفاده از توابع تعریف شده، کلاس مورد نظرتون رو بسازید
  پاسخ
suzan
2017/10/30 در 22:57
سلام وقتتون بخیر اقای دلیرانی میخواستم راجب برج هانوی توضیح بدین و بگین چطور برنامه بنویسم براش بصورت گرافیکی نمایش بدیم بی زحمت در ضمن سایت بسیار خوب و مفیدی دارید ممنونم ازتون
پاسخ
- فرهاد دلیرانی
  2017/10/30 در 23:38
  الان خیلی درگیر هستم. متاسفانه وقت نمی کنم. ولی یک پست در بلاگ هست در این مورد:
  https://open-mind.ir/1393/%d8%a8%d8%b1%d8%ac-%d9%87%d8%a7%d9%86%d9%88%db%8c/
  همین طور توی گیت هاب هم به آدرس زیر:
  https://github.com/search?utf8=%E2%9C%93&q=Tower+of+Hanoi&type=
  صدها پیاده سازی برج هانوی هست با زبان های مختلف برنامه نویسی و روش های مختلف.
  که می تونی یکیشون رو که مد نظرت هست رو بخونی و یاد بگیری و پیاده سازی کنی.
  همین طور یادداشت کردم که برج هانوی رو گرافیکی بعد در سایت هر وقت تونستم بنویسم.
  با تشکر
  پاسخ
راضیه
2017/10/30 در 13:05
سلام ما استادمون یه پروژه داره که باید ساختار داده که اعداد صحیح بزرگ را نایش بده و جمع و تفریق و تقسیم و ضرب روشون انجام بدیم و در نهایت چاپشون کنیم طوری که تو برنامه از تابع درونی استفاده نکنیم و نوع داده هامونم از نوع intباشند فقط چطور این برنامه رو بنویسم میشع راهنمایی کنید .تشکر*
پاسخ
- حامد آهنگری
  2017/10/30 در 13:21
  سلام.
  با توجه به جزییات پروژه استادتون، باید با استفاده آرایه ای از int ها رقم های اعداد بزرگ رو نگه داری کنید (هر رقم در یک خانه از آرایه قرار می گیرد). در کد ارائه شده در این مطلب، از آرایه کاراکترها (رشته) برای نگه داری هر رقم استفاده شده است (هر رقم به عنوان یک کاراکتر در آرایه ذخیره شده).
  موفق باشید
  پاسخ
محسن
2016/12/15 در 13:59
واقعا عالی بود
پاسخ
CH CH
2016/11/11 در 12:06
سایتتون فوق العاده ست. ممنون بابت زحماتتون
پاسخ
ali
2015/12/14 در 20:15
با سلام
آیا نمی شود در برنامه از رشته ها استفاده نکرد ؟
یعنی به جای Num1.size از کاربر طول عدد را بپرسیم ؟
یا اگر کاربر به جای رشته ها از آرایه ها استفاده کنیم هزینه برنامه کاهش می یابد یا افزایش ؟؟
پاسخ
- فرهاد دلیرانی
  2015/12/14 در 20:53
  هر کاراکتر یک بایت است در نتیجه یک آرایه ی ۵ تایی از کاراکتر ها ۵ بایت می شود
  در حالی که int در حالت عادی ۴ بایت است در نتیجه یک آرایه ۵ تا از آن ها می شود ۲۰ بایت
  پاسخ
سعید
2015/03/18 در 13:30
سلام
میتونید یه برنامه برای ضرب دو عدد ۵۰ رقمی بنویسید.
اگر تونستید بنویسید بهم میل بزنید
ممنون
پاسخ
- فرهاد دلیرانی
  2015/03/18 در 15:15
  سلام
  الگوریتم تقسیم اعداد بزرگ ۵۰ رقمی (fifty digit division)
  پروژه ماشین حساب با عملیات روی اعداد ۱۰۰۰ رقمی با زبان c
  پاسخ
َamir ali
2014/12/13 در 01:50
سایتت خیلی عالیه .مرسی…
فقط یه سوال.
میشه راهنماییم کنی جمع وتفریق ۲ عدد بزرگ که ممکنه منفی باشن چطوریه؟(برنامه نویسی c)
پاسخ
- فرهاد دلیرانی
  2014/12/13 در 14:33
  این یک برنامه ساده و کوچک است تا کلیت کار را نشان بدهد ، ولی اگر می خواهید پیشترفته ترش کنید بهتر است ساختمان داده ای جدید در نظر بگیرید و یک خانه با توجه به منفی بودن و یا مثبت بودن در نظر بگیرید و با توجه به علامت ها عملیات مورد نظر خود را پیاده سازی کنید . کلا چهار حالت داریم : هر دو مثبت باشند که در این صورت همان جمع می شود.هر دو منفی باشند که باز مثل حالت قبل هر دو را جمع می کنید بعد علامت را منفی می کنیم یکی مثبت باشد و دیگری منفی که همان منها می شود
  پاسخ
vahid
2014/06/06 در 23:35
سلام.با تشکر از این پست مفیدتون.می خواستم خواهش کنم اگر امکان داره تابع های تقسیم و تفریق وجمع وضرب رو با تحلیل کامل که بتونم با نرم افزار توربو سی اجرا کنم قرار بدید.
ممنون
پاسخ
فرزین
2014/05/19 در 20:31
سلام
من دانشجوی کامپیوتر هستم، استاد درس ساختمان داده همین رو به عنوان پروژه به ما گفته، ضرب دو عدد ۲۰ رقمی با استفاده از لیست های پیوندی. اگه امکانش باشه من رو راهنمایی کنید. استاد گفته اول اعداد رو شش رقم شش رقم بشکنیم و داخل لیست پیوندی قرار بدیم، بعد ضرب کنیم، اگه راهنماییم کنید ممنون میشم.
پاسخ
- فرهاد دلیرانی
  2014/05/22 در 03:29
  به پست link list در همین بلاگ بروید و بجای آرایه لینک لیست بفرستید تو تابع
  پاسخ
amir
2014/02/01 در 21:39
دستت درد نکنه، یه دو هفته رو این سوال کار کردم، بعدش بی خیال شدم، تا این که این پست رو خوندم. ممنون
پاسخ
- فرهاد دلیرانی
  2014/02/02 در 02:42
  خوشحال شدیم تونستیم کمک کنیم.
  پاسخ
mehrnoush
2013/11/16 در 10:57
عدد ها باید به صورت رشته ای وارد بشن ؟ واسه جمع و تفریق میگم .
#include “stdafx.h” واسه چیه ؟
پاسخ
- فرهاد دلیرانی
  2013/11/17 در 19:50
  مهرنوش @ include “stdafx.h #” یک کتاب خانه است است که کامپایلر ویژوال استدیو به آن نیاز دارد . ولی کامپایلر هایی مثل مثل کد بلاک به آن نیاز ندارند.
  بله باید به صورت رشته وارد شوند البته این برنامه فقط جمع دارد برای منها می توانید به این پست مراجعه کنید
  http://open-mind.ir/?p=87
  پاسخ
  - mehrnoush
    2013/11/18 در 09:53
    misheh begin t , r , ch , mult vaseh chiyan ? r hamoun carry ye ? ch ham yeh temp vaseh negahdashtan meghdare zarb gaei k anjam misheh ? mult ham k akherin meghdare zarb ro negah midareh , dorosteh ? t vaseh chiyeh ?
    پاسخ
mohammad
2013/09/24 در 23:22
اگه تفریق و تقسیمش هم بذاری و تبدیل به کلاسش کنی خوب می شود
پاسخ
- فرهاد دلیرانی
  2013/09/25 در 10:15
  mohammad @ بله قصد همین کار را داریم ولی به مرور زمان .
  پاسخ
  - samira
    2014/03/21 در 17:30
    سلام.با تشکر از این پست مفیدتون.می خواستم خواهش کنم اگه امکان داره تابع های تقسیم و تفریق رو هم قرار بدید.
    ممنون
    پاسخ
    - فرهاد دلیرانی
      2014/03/21 در 23:16
      در این پست ها می توانید منها و جمع و تقسیم را پیدا کنید:
      http://open-mind.ir/?p=87
      http://open-mind.ir/?p=135
      پاسخ
      - مریم
        2015/05/29 در 23:06
        سلام اقای دلیرانی ممنون بابت برنامه ها.میخواستم ببینم شما کلاس تدریس برنامه نویسی هم دارید؟
      - فرهاد دلیرانی
        2015/05/30 در 00:52
        تشکر ، خیر کلاس برای آموزش برنامه نویسی ندارم ولی در آینده حتما ویدیو های آموزشی درست می کنیم و به صورت رایگان در اختیار خوانندگان می گذاریم.