Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250. / 14 сообщений из 14, страница 1 из 1
06.01.2015, 02:47
    #38848837
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Достаточно интересная задачка на произведение двух длинных чисел.Вроде бы алгоритм придумал и уже даже написал,но в коде есть косяки природы которых мне не ясна.Может кто знает в чем косяки?Не судите строго,знаю что выглядит не очень.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
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.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
//
//  main.cpp
//  сложение цифр

#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main(int argc, const char * argv[]) {
	// insert code here...
	// freopen("input.txt","r", stdin);
	//freopen("output.txt","w", stdout);
	string q = "", a, b, sum = "";
	q.resize(10000000);

	cin >> a;   //вводим первое число 
	cin >> b;   //вводим втрое число
	b = '0' + b;   //что бы не было выхода за границы массива
	a = '0' + a;   //что бы не было выхода за границы массива
	while (a.length() > b.length()) //добавляем нули к строке что бы были одинаковой длины
	{
		b = '0' + b;
	}

	while (a.length() < b.length()) //добавляем нули к строке что бы были одинаковой длины
	{
		a = '0' + a;
	}

	int k = 0;
	int t = 0;
	int l = 0;
	int ss = 0;
	string suml = "";
	sum.resize(10000000);
	for (int x = (b.length() - 1); x >= 0; --x) //перебираем элементы второго числа
			{

		for (int i = (a.length() - 1); i >= 0; --i) //перебираем элементы первого числа
				{
			if (l != 0) //если мы запоминали число что бы прибавить к текущему разряду 
					{
				k = (int(a[i]) - 48) * b[x] + l; //считаем произведение текущих разрядов с учетом числа которое мы запомнили
				l = 0;
			} else
				//если мы числа не запоминали
				k = (int(a[i]) - 48) * (b[x] - 48); //считаем произведение текущих разрядов

			if (k >= 10)   //если произведение текущих разрядов больше 10

					{
				l = k / 10; //число которое мы запомнили и будем прибавлять к разрядам

				sum[t] = char(k % 10 + 48); //записываем в конечную строку произведение текущих разрядов 
			} else   //в другом случае
			{

				sum[t] = char(k + 48); //записываем в конечную строку произведение текущих разрядов 
			}
			++t;   //увеличили счетчик длины строки

		}
		//-----------------------------------------------------------------------------------------------------------------------------------------------
		//------------------------------БЛОК СУМИРОВАНИЯ ПРОИЗВЕДЕНИЯ ПРЕДЫДУЩИХ И ТЕКУЩИХ РАЗРЯДОВ-------------------------------------------------------
		//-----------------------------------------------------------------------------------------------------------------------------------------------
		int n1 = 0;
		int n2 = 0;
		int u = 0;
		string yard = "";
		yard.resize(10000000);
		suml.resize(10000000);
		//т.к мы записываем произведения и считаем сумму предыдущих разрядов наоборот то для начал мы должны ее перевернуть
		if (x != (b.length() - 1)) {
			for (int i = n1 - 1; i >= 0; --i)

			{

				yard[u] = suml[i];	//переворачиваем строку
				++u;
			}
			suml = yard;
			yard = "";
			u = 0;
		}

		for (int i = (t - 1); i >= 0; --i)

		{

			yard[u] = sum[i];	//переворачиваем строку
			++u;
		}
		sum = yard;
		yard = "";
		u = 0;

		//------------------тут мы и производим суммирование --------------------------------------------------------------------

		for (int y = 0; y < ss; ++y) {
			sum[t] = '0';
			t = t + 1;
		}

		sum = '0' + sum;
		suml = '0' + suml;
		while (n1 > t) {
			sum = '0' + sum;
			++t;
		}
		while (t > n1) {
			suml = '0' + suml;
			++n1;
		}

		for (int c = t; c >= 0; --c) {
			if ((l >= '0') && (l <= '9')) {
				k = int(l) + int(suml[c]) + int(sum[c]) - 3 * 48;
				l = ' ';
			} else
				k = int(suml[c]) + int(sum[c]) - 2 * 48;

			if (k >= 10)

			{

				l = '1';

				q[n2] = char(k - 10 + 48);

			} else {

				q[n2] = char(k + 48);
			}
			++n2;
			++n1;
		}

		suml = q;
		q = "";

		++ss;
		sum = "";
		t = 0;
	}
	//удаление лишних нулей
	while (suml[suml.length() - 1] == '0') {
		suml.erase(suml.length() - 1, 1);

	}
	//вывод,опять же в обратном порядке так как мы записывали все наоборот
	for (int i = suml.length() - 1; i >= 0; --i) {

		cout << suml[i];

	}
	cin >> sum;	//просто что бы окно не закрывалось:)

	return 0;
}



Модератор: Отформатировано
...
Рейтинг: 0 / 0
06.01.2015, 06:27
    #38848856
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
ванмомас намбаван,

Начните с нормального форматирования кода.
С таким вырвиглазным форматированием не мудрено пропустить какую-то важную скобку или типа того.
...
Рейтинг: 0 / 0
06.01.2015, 10:33
    #38848930
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
ванмомас намбаван,

Что это за хрень ?

Код: plaintext
1.
2.
string q="",a,b,sum="";
    q.resize(10000000);



Ты всё время применяешь этот трюк. Шваркнуть в буфер строки 10 миллионов байт, и потом не иметь проблем с доступом к памяти, потому что памяти дофига -- не большая заслуга.

Ты научить нормально с памятью работать.
...
Рейтинг: 0 / 0
06.01.2015, 14:52
    #38849208
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Ну я это решил как организовать.Сначала считаем произведение первого числа с единицами второго.Потом мы прибавляем к концу произведения(sum) нужное кол-во нулей(по правилам умножения в столбик смещаем),когда мы считаем единицы ,например,то это кол-во равно нулю.потом мы прибавляем это к сумме прошлых произведений(suml) ,когда мы считали единицы то это был первый раз и соответственно в сумме прошлых произведений ноль.Потом мы присваиваем то что у нас в сумме(q) вышло сумме прошлых произведений(suml=q) и делаем пустой строку текущего произведения(sum).Дальше мы идем по циклу опять только теперь мы умножаем перовое число уже на десятки второго и так далее в цикле.У меня ошибка вот тут(код ниже),говорит string subscript out of range.Это уже при умножении на 10ки после того как я сделал строку пустой sum="".там выходит sum=char(k+48) и когда у нас k=2(при умножении единиц первого числа 12ти на дестяки второго числа тоже 12ти) то оно записывает в sum 2024 0_о ,откуда оно его берет - загадка(может не правильно сделал sum пустой).А когда мы умножаем десятки первого на десятки второго и k=1,то оно пишет ошибку string subscript out of range.Вот собственно код где оно вылетает(я отметил комментарием это место):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
for (int i=(a.length()-1);i>=0;--i) //перебираем элементы первого числа
{
	if (l!=0) //если мы запоминали число что бы прибавить к текущему разряду 
	{
		k=(int(a[i])-48)*b[x]+l; //считаем произведение текущих разрядов с учетом числа которое мы запомнили
		l=0;
	} else //если мы числа не запоминали

	k=(int(a[i])-48)*(b[x]-48);//считаем произведение текущих разрядов

	if (k>=10)//если произведение текущих разрядов больше 10

	{
		l=k/10; //число которое мы запомнили и будем прибавлять к разрядам
		sum[t]=char(k%10+48);//записываем в конечную строку произведение текущих разрядов 
	}
	else //в другом случае
	/* тут оно вылетает */sum[t]=char(k+48);//записываем в конечную строку произведение текущих разрядов 

	++t;//увеличили счетчик длины строки
}


Модератор: Отформатировано
...
Рейтинг: 0 / 0
07.01.2015, 20:35
    #38849866
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
ванмомас намбаван,
ничего интересного в ней нет. Интересно найти оптимальную реализацию, и обоснование. Лично я не нашёл. Не конкретно методы для реализации длинной арифметики, а именно решить вопросы касаемо того, как лучше это реализовать, а не как вообще реализовать.
Вы пишите "выглядит не очень" ? Что значит выглядит не очень ? Код не отформатирован. Не удобно разбираться в нем. Не не очень, а плохо выглядит этот код, хотя бы из-за форматирования. Вам Анатолий написал, а вы до сих пор не исправили. Не думаю что кто-то из тех кто может вам помочь специально отформатирует код за вас, и будет проверять. Вообщем ждем нормальный текст программы.


Вам yard нужен только для того чтобы сделать реверс строки ? Исправьте, и не нагружайте код побочной ерундой. Реверс можно сделать проще, и оптимальней.

авторНу я это решил как организовать.Сначала считаем произведение первого числа с единицами второго
каким единицами ? У чисел разряды есть. А ещё есть числа, и цифры.

авторПотом мы прибавляем к концу произведения(sum) нужное кол-во нулей(по правилам умножения в столбик смещаем),
сдвигаете вы просто, зачем писать 20 слов чтобы это сказать ?

авторкогда мы считаем единицы ,например,то это кол-во равно нулю.потом мы прибавляем это к сумме прошлых произведений(suml) ,когда мы считали единицы то это был первый раз и соответственно в сумме прошлых произведений ноль.Потом мы присваиваем то что у нас в сумме(q) вышло сумме прошлых произведений(suml=q) и делаем пустой строку текущего произведения(sum).Дальше мы идем по циклу опять только теперь мы умножаем перовое число уже на десятки второго и так далее в цикле.

Переходим к следующей итерации. "Идём по циклу" больше ассоциируется с тем? что вы идёте внутри цикла далее, нежели то, что вы скорее всего имеете ввиду.

То что вы написали дальше, я уже не хочу разбирать.


Вообщем потрудитесь уважать тех у кого просите советы. Вы учитесь программированию, а не советы у наркоманов просите. Это конструктивные (и полезные для вас) замечания, а не просто критика. И пожалуйста обратите на них внимание. Ибо после совета Анатолия, вы снова привели ниже неотформатированный код.
...
Рейтинг: 0 / 0
07.01.2015, 22:34
    #38849912
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
SashaMercury,а как вы представляете себе отформатированный код?
...
Рейтинг: 0 / 0
07.01.2015, 22:35
    #38849914
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Вот переделал полностью.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
#include <iostream>
#include <cstring>
#include <stdio.h>

using namespace std;

int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
   int  s_offset, n_result;
   char s1[255],s2[255],result[255]={0};
   bool ost = true; 
   cin>>s1;cin>>s2;
   for(int s1_count = strlen(s1)-1; s1_count >= 0; s1_count--)
     { 
      for(int s2_count = strlen(s2) - 1; s2_count >= 0; s2_count--)
      {
       ost = true;
       s_offset = strlen(s2) - s2_count + strlen(s1) - s1_count - 2;
       n_result = (s1[s1_count] - 48)*(s2[s2_count] - 48);
       for(int z_offset = 0; ost&&(s_offset+z_offset < 255); z_offset++)
        {
         if(result[s_offset+z_offset] == 0) result[s_offset+z_offset] = '0';
         n_result = n_result+result[s_offset + z_offset] - 48;
         result[s_offset+z_offset] = 48 + n_result%10;
         n_result = n_result/10; if(n_result == 0) ost = false;
        }
      }
     }
  
   for(int i = 254; i >= 0; i--) if(result[i]!=0) cout<<result[i];
   cout<<endl;
}
...
Рейтинг: 0 / 0
07.01.2015, 22:52
    #38849921
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
ванмомас намбаванВот переделал полностью.
А тебе известно, что разрядность произведения двух чисел равна сумме разрядностей
множителей?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
07.01.2015, 23:10
    #38849936
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Несколько совершенно машинальных рефакторингов. Каждый день так делаю.
Не тестил. Тестируй сам козаче.

Особое thnks Дмитрию за замечание по разрядности результата.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
#include <iostream>
#include <cstring>
#include <stdio.h>

#define MAXSZ 255
#define BASE 10

using namespace std;

// After tiny refactoring.


// TODO: Is it possible to use std::string instead char* ? (Mayton)
// TODO: Is it possible to translate all calculations into decimal system? (Mayton)

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int s_offset, n_result;
	char s1[MAXSZ];
	char s2[MAXSZ];
	// TODO: Is it correct? MAXSZ? Or MAXSZ * 2 ? (Thnk's to Dimitry Sibiryakov)
	char result[MAXSZ] = { 0 };
	bool ost = true;
	cin >> s1;
	cin >> s2;
	for (int i = strlen(s1) - 1; i >= 0; i--) {
		for (int j = strlen(s2) - 1; j >= 0; j--) {
			ost = true;
			s = strlen(s2) - j + strlen(s1) - i - 2;
			n = (s1[i] - '0') * (s2[j] - '0');
			for (int k = 0; ost && (s + k < MAXSZ);
					k++) {
				if (result[s + k] == 0){
					result[s + k] = '0';
				}
				n = n + result[s + k] - '0';
				result[s + k] = '0' + n % BASE;
				n = n / BASE;
				if (n == 0){
					ost = false;
				}
			}
		}
	}

	for (int i = MAXSZ - 1; i >= 0; i--){
		if (result[i] != 0){
			cout << result[i];
		}
	}
	cout << endl;
}
...
Рейтинг: 0 / 0
07.01.2015, 23:42
    #38849946
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
mayton,спасибо.
...
Рейтинг: 0 / 0
07.01.2015, 23:43
    #38849948
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
mayton// TODO: Is it correct? MAXSZ? Or MAXSZ * 2 ? (Thnk's to Dimitry Sibiryakov)
Точная формула максимально возможного произведения будет (10 x+1 -1)*(10 y+1 -1), что раскладывается в 10 x+y+2 -10 x -10 y +1, что ограничивает его разрядность сверху числом x+y+1. То есть при обозначенной в сабже максимальной разрядности обеих множителей в 250, результат может иметь максимум 501 цифру.
...
Рейтинг: 0 / 0
07.01.2015, 23:57
    #38849953
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Тут интересно пишут. Об оценке сложности умножения.

https://ru.wikipedia.org/wiki/Умножение_Карацубы
...
Рейтинг: 0 / 0
08.01.2015, 00:10
    #38849960
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Dimitry Sibiryakovпри обозначенной в сабже максимальной разрядности обеих
множителей в 250, результат может иметь максимум 501 цифру.
А, блин, математик из меня как из дерьма пуля. 500 цифр максимум, без вариантов.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
08.01.2015, 10:49
    #38850056
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
Dimitry SibiryakovDimitry Sibiryakovпри обозначенной в сабже максимальной разрядности обеих
множителей в 250, результат может иметь максимум 501 цифру.
А, блин, математик из меня как из дерьма пуля. 500 цифр максимум, без вариантов.


Ну как бы это всё в документации к любой СУБД написано, numeric/decimal все почти поддерживают.
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250. / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]