Большие числа на С++

[Natka]

Быстрое умножение длинных целых чисел

Главная идея быстрого умножения состоит в модификации выражения A×C×10N+(A×D+B×C)×10N/2+B×D таким образом, чтобы уменьшить количество операций умножения: A×C×10N+(AD+BC)×10N/2+B×D = A×C×10N+(A-B)×(D-C)×10N/2+B×D+(A×C+B×D)×10N/2. Видно, что теперь необходимо найти лишь три произведения N/2-значных чисел.

Задание.

1) Реализовать алгоритм сложения двух длинных целых чисел.
2) Реализовать алгоритм умножения двух длинных целых чисел.
3) Реализовать нерекурсивный алгоритм быстрого умножения.
а) в программе должен присутствовать механизм контроля используемой памяти (пиковый расход).
б) сделать модификацию алгоритма для перемножения чисел, разрядность которых не является степенью двойки.
4) Реализовать рекурсивный алгоритм быстрого умножения.
5) Написать тестовую программу для сравнения двух реализаций.
6) Написать тестовые программы для демонстрации правильности работы программ.
а) входные данные хранятся в файле mult.txt: в первой строке разрядность чисел, во второй и третьей - сами множители.
б) входные данные должны дублироваться на экране, результат перемножения тоже выводить на экран.
7) Разработать набор тестов для проверки правильности (включает не менее 10 тестовых случаев). Реализовать режим пакетной прогонки разработанных тестов.



Необходимо реализовать на С/С++. Помогите, пожалуйста!

 

[Creo]

Посмотри прикрепленный файл. Мот поможет чем.
Посмотреть вложение LONG.pdf

 

[sab0tage]

<!--QuoteBegin-Creo+19:12:2006, 09:20 -->
<span class="vbquote">(Creo @ 19:12:2006, 09:20 )</span><!--QuoteEBegin-->Посмотри прикрепленный файл. Мот поможет чем. smile.gif
Прикрепленный файл LONG.pdf ( 372.88 килобайт ) Кол-во скачиваний: 0

[snapback]51123" rel="nofollow" target="_blank[/snapback]​

[/quote]
Четко, сам учился по этому документу. С профом спорили, кто лучше программирует, а тут такой мануал.

Больше правдо на С не программирую, вот мой код, дарю компилировал под VS6.
Находил числа до 50Кб длинной. Профу принес распечатку 2 в 20000й степени, пару листов А4 мелким шрифтом.

#include <iostream.h>
#include <fstream.h>

struct NUM 
{
short int n[20000];	 /*this is a NUMber set.*/
int n_size;			/*this is a size of the NUMber*/
};

//put in the NUMber from the file
NUM fillNUMf(char filename[20])
{
NUM temp;
ifstream f;
int i,fr;
char fr1;
f.open (filename);
i=0;
while (!f.eof())
{
i++;
f>>fr1;
fr=fr1-48;
temp.n[i-1]=fr;
}
temp.n_size=i-1;
f.close();
return temp;
}

//put in the NUMber manually
NUM fillNUMk()
{
NUM temp;
short int inp;
int i,size;

cout <<" \nHuge Number Input. (enter value > 9 to stop):";

inp=0;
i=0;

while (inp<10)
{
cout<<"\n Enter the number posiotion " <<i <<" :";
cin >>inp;
temp.n[i]=inp;
i++;
} 

temp.n_size=i-1;
temp.n[i]=0;

return temp;
}

//display NUMber on console
void showNUMd(NUM temp)
{
int i;
cout<<"\nnum["<<temp.n_size<<"]";
for (i=0;i<temp.n_size;i++)
cout<< temp.n[i];
cout<<endl;
}

//save NUMber into file
void showNUMf(NUM temp, char filename[20])
{ int i;
char tes;
ofstream f;
f.open(filename);
for(i=0;i<temp.n_size;i++)
{
tes=temp.n[i]+48;
f<<tes;
}
f.close();
}

//inverts NUMber
NUM invertNUM(NUM temp)
{
int i,buf;
for(i=0;i<temp.n_size/2;i++)
{
buf=temp.n[i];
temp.n[i]=temp.n[temp.n_size-i-1];
temp.n[temp.n_size-i-1]=buf;
}
return temp;
}

//delets the zeroes at the beginning
NUM performNUM(NUM temp)
{
int i,pos;

i=0;
pos=0;

while (temp.n[i]==0) 
{	  pos++;
i++;
}

if (pos!=0)
{
temp.n_size=temp.n_size-pos;
for(i=0;i<=temp.n_size;i++)
temp.n[i]=temp.n[i+pos];
}
return temp;
}

//multiplication itself
NUM mul_(NUM NUM1, NUM NUM2)
{  
NUM res; 
int i,j,carry,temp;


NUM1=performNUM(NUM1);
NUM1=invertNUM(NUM1);
NUM2=performNUM(NUM2);
NUM2=invertNUM(NUM2);

res.n_size=NUM1.n_size+NUM2.n_size;
for(i=0;i<res.n_size;i++)
res.n[i]=0;

for(i=0;i<NUM2.n_size;i++)
{
carry=0;
for(j=0;j<NUM1.n_size;j++)
{
temp=NUM2.n[i]*NUM1.n[j]+res.n[i+j]+carry;
carry=temp/10;
res.n[i+j]=temp-(carry*10);
}
res.n[i+j]=carry;
}

res=invertNUM(res);
res=performNUM(res);
return res;
}

//finds an entered power of two;
void powerdemo()
{  NUM t0,t1,t2;
int i,power;

t1.n_size=1;
t1.n[0]=2;

t2.n_size=1;
t2.n[0]=2;

cout <<"Enter the power: ";
cin >>power;

for(i=2;i<=power;i++)
{
t0=mul_(t1,t2);
cout <<"2^" <<i <<endl;
//showNUMd(t0);
t1=t0;
}
showNUMf(t1,"c:/2^100000.txt");

}

//main module
void main()
{

NUM t0,t1,t2;
//t1=fillNUMf("c:/num1.txt");
//t2=fillNUMf("c:/num2.txt");
cout <<"\n 1st Number:";
cout <<"\n -----------";
t1=fillNUMk();
cout <<"\n 2nd Number:";
cout <<"\n -----------";
t2=fillNUMk();


cout <<"\nMultiplication in process\n";
t0=mul_(t1,t2);

cout <<"\n 1st Number:"; showNUMd(t1);
cout <<"\n 2nd Number:"; showNUMd(t2);
cout <<"\n The result of multiplication:";
showNUMd(t0);
//showNUMf(t0,"c:/res.txt");


//powerdemo();
}

 

[Homer37]

Программа была реализована? если да то напишите листинг умножения.

 

[European]

Некропостинг. Закрыто