ضرب اعداد بزرگ

[aidinwashere]

کسی الگوریتمی براش بلده؟ حالا یا dynamic یا هرچی
به هر زبانی فقط بایذ دو عدد مثلا 20 رقمی رو بتونه در هم ضرب کنه.

[حامد مصافی]

سلام
دو عدد Ab و Cd رو در نظر بگیرید اگر این دو رقم را به یکدیگر ضرب کنیم رقم یکان D*b خواهد بود و رقم دهگان (c*b) + (a*d) خواهد بود و رقم صدگان نیز C*a است ( مانده بر ده باید محاسبه شود)

ارقام بزرگ تر نیز از همین قانون تبعیت می کنند برای مثال Abc * Def که ارقام آن از چپ به راست به ترتیب زیر خواهند بود
C*f
B*f + E*c
A*f + B*e + C*d
A*e + B*d
A*d


امیدوارم جوابتو گرفته باشی. در غیر اینصورت یه Pm بهم بده

[Sepidar]

const

 MaxDigits=100;

type

 TDigit=byte;

 TBigNum:array [1..MaxDigits] of TDigit;



 .

 .

 .

 .

 .

 

function mul(Num1,Num2:TBigNum;var Ans:TBigNum):TDigit;

var

 OverFlow:TDigit;

 i,C:integer;

begin

 C:=0;

 for i:=1 to MaxDigits do begin

   C:=Num1[i]*Num2[i]+OverFlow;

   Ans[i]:=(C mod 10);

   OverFlow:=C div 10;

 end;

 

 Result:=OverFlow;

end;

[mss_eng]

کسی الگوریتمی براش بلده؟ حالا یا dynamic یا هرچی
به هر زبانی فقط بایذ دو عدد مثلا 20 رقمی رو بتونه در هم ضرب کنه.

من یه راهنماییت میکنم. امیدوارم مفید باشه.

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

[alirezah]

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

[mr_esmaily]

سلام

//verylong.h



const int SZ =200 ;     //maximum digits



class verylong

{

private:

	string vlstr;

	int vlen;

	verylong  multdigit(const int)const;

	verylong mult10(const verylong) const;

public :

	verylong() : vlen(0)

	{	}

	verylong(string& const s) : vlstr(s) , vlen(s.lenght())

	{	}

verylong (const unsigned long n)

{

		char temp[SZ];

		ltoa(n,temp,10);

		strrev(temp);

		vlstr=temp;

		vlen=vlstr.lenght();

}

verylong operator *(const verylong)const;

};



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

//verylong.cpp



#include “verylong.h”



verylong verylong::operator *(const verylong v) const

{

	verylong pprod;

	verylong tempsum;

	for(int j=0;j<v.vlen;j++)

	{

		int digit=v.vlstr[j] – ‘0’;

		pprod=multdigit(digit);

		for(int k=0;k<j;k++)

			pprod=mult10(pprod);

		tempsum=tempsum+pprod;

	}

	return tempsum;

		

}



verylong verylong::mult10(const verylong v) const

{

	char temp[SZ];

	for(int j=v.vlen-1;j>=0;j--)

		temp[j+1]=v.vlstr[j];

	temp[0]=’0’;

	temp[v.vlen+1]=’\0’;

	return verylong(temp);

	

}



verylong verylong::multdigit(const int d2) const

{

	int j;

	char temp[SZ];

	int carry=0;

	for(j=0;j<vlen;j++)

	{

		int d1=vlstr[j]-‘0’;

		int digitprod=d1 * d2;

		digitprod += carry;

		if(digitprod >= 10)

		{

			carry=digitprod/10;

			digitprod-=carry*10;

		}

		else

			carry=0;

		temp[j]=digitprod+’0’;

}

if(carry != 0)

	temp[j++]=carry + ‘0’;

temp[j]=’\0’;

return verylong(temp);



	

}

override کردن بقیه عملگرها با خودت.

[mr_esmaily]

سلام
متاسفانه تگ کد , کد مربوطه رو , بصورت بالا نمایش میده.

[manager]

الگوریتمی هست که احتمالا کسائی که با استاد خرسند درس طراحی الگوریتم داشته باشند با هاش برخورد کردند این الگوریتم به نام a la russe هست و دارای زمان مصرفی mn (برای اعداد بزرگ) هست :

procedure russe(m,n)

X[1] <- m

Y[1] <- n

i <- 1

while X[i]>1 do

    X[i+1] <- X[i] div 2

    Y[i+1] <- Y[i] + Y[i]

    i <- i + 1

end

total <- 0

while i>0 do

    if X[i] is odd then

        total <- Y[i] + total

    i <- i - 1

end

return total

end

برای حل این مسئله راه حل های بسیار زیادی وجود داره که این بهترنشون نیست //

[زینبVIN]

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

main()

{

clrscr();

int a[20],b[20],c[21],i,j,d;

char x,y;

i=0;

j=0;

d=0;

printf("enter first number      ");

while(i<20)

{

x=getch();

a[i]=x-48;

printf("%d ",a[i]);

i++;

}

printf("\n\n\n");

printf("enter secound number    ");

while(j<20)

{

y=getch();

b[j]=y-48;

printf("%d ",b[j]);

j++;

}

for(i=19;i>=0;i--)

{

c[i]=(a[i]+b[i]+d)%10;

d=(a[i]+b[i])/10;

 }

printf("\n\n\n");

printf(" the sum of numbers is  ");

if((a[0]+b[0])>9)

{

printf("%d ",(a[0]+b[0])/10);

}

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

{

printf("%d ",c[i]);

}

getch();

}

[AbdollahSoft]

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

سلام به شما

مي خواستم بدونم امكانش هست اين برنامه رو داشته باشم . ممنون مي شم اگه لطف كنين

[Reza,M]

با سلام
آيا از دوستان كسي ميتونه بهترين حالت Thershold (آستانه) را براي اين الگوريتم بدست بياره ؟

[فرشته موسی زاده]

چطور mn میشه پیچیدگیش؟

[mrbm_2007]

منم یه ایده دارم
اگر بجای مبنای 10 مبنا رو روی 100 یا حتی 10000 بذاریم چی؟ البته نه اینکه مثل مبنای 16 برای هر عدد یک نماد هم اختصاص داده بشه یعنی یه آرایه داشته باشیم که هر خونش یه عدد 0تا 9999 باشه و در مبنای 10000 همون عدد 20 رقمی رو تشکیل بده
حالا می شه به راحتی این اعداد را که کوچکتر از 10000 هستند رو در هم ضرب کرد (بدون نیاز به کد اضافی) و بقیه مراحل ضرب هم مثل ضرب معمولی فقط توی یه مبنای بزرگ تر
شاید بگید خوب که چی؟
به نظر من این روش نسبت به حالتی که عدد رو توی یه آرایه 20 تایی در مبنای 10 بریزیم خیلی سریع تره
نظر شما چیه؟

[aram_2]

می تونید دو عدد رو با لگاریتم به یه میدان دیگه ببرید و کارتون رو راحت انجام بدید.
log(x*y)=log(x)+log(y)

[shadi.talk]

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

100 digits.rar