powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
14 сообщений из 14, страница 1 из 1
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38848837
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Достаточно интересная задачка на произведение двух длинных чисел.Вроде бы алгоритм придумал и уже даже написал,но в коде есть косяки природы которых мне не ясна.Может кто знает в чем косяки?Не судите строго,знаю что выглядит не очень.
Код: 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
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38848856
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаван,

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

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

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



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

Ты научить нормально с памятью работать.
...
Рейтинг: 0 / 0
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849208
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну я это решил как организовать.Сначала считаем произведение первого числа с единицами второго.Потом мы прибавляем к концу произведения(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
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849866
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаван,
ничего интересного в ней нет. Интересно найти оптимальную реализацию, и обоснование. Лично я не нашёл. Не конкретно методы для реализации длинной арифметики, а именно решить вопросы касаемо того, как лучше это реализовать, а не как вообще реализовать.
Вы пишите "выглядит не очень" ? Что значит выглядит не очень ? Код не отформатирован. Не удобно разбираться в нем. Не не очень, а плохо выглядит этот код, хотя бы из-за форматирования. Вам Анатолий написал, а вы до сих пор не исправили. Не думаю что кто-то из тех кто может вам помочь специально отформатирует код за вас, и будет проверять. Вообщем ждем нормальный текст программы.


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

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

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

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

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

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


Вообщем потрудитесь уважать тех у кого просите советы. Вы учитесь программированию, а не советы у наркоманов просите. Это конструктивные (и полезные для вас) замечания, а не просто критика. И пожалуйста обратите на них внимание. Ибо после совета Анатолия, вы снова привели ниже неотформатированный код.
...
Рейтинг: 0 / 0
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849912
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,а как вы представляете себе отформатированный код?
...
Рейтинг: 0 / 0
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849914
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот переделал полностью.
Код: 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
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849921
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаванВот переделал полностью.
А тебе известно, что разрядность произведения двух чисел равна сумме разрядностей
множителей?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849936
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Несколько совершенно машинальных рефакторингов. Каждый день так делаю.
Не тестил. Тестируй сам козаче.

Особое 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
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849946
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,спасибо.
...
Рейтинг: 0 / 0
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849948
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.
    #38849953
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут интересно пишут. Об оценке сложности умножения.

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


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


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