Длинная арифметика.Произведение двух очень длинных чисел.Длина до 10^250.

Достаточно интересная задачка на произведение двух длинных чисел.Вроде бы алгоритм придумал и уже даже написал,но в коде есть косяки природы которых мне не ясна.Может кто знает в чем косяки?Не судите строго,знаю что выглядит не очень.

//
//  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;
}

Модератор: Отформатировано

ванмомас намбаван,

Начните с нормального форматирования кода.
С таким вырвиглазным форматированием не мудрено пропустить какую-то важную скобку или типа того.

ванмомас намбаван,

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

string q="",a,b,sum="";
    q.resize(10000000);

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

Ты научить нормально с памятью работать.

Ну я это решил как организовать.Сначала считаем произведение первого числа с единицами второго.Потом мы прибавляем к концу произведения(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.Вот собственно код где оно вылетает(я отметил комментарием это место):

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;//увеличили счетчик длины строки
}

Модератор: Отформатировано

ванмомас намбаван,
ничего интересного в ней нет. Интересно найти оптимальную реализацию, и обоснование. Лично я не нашёл. Не конкретно методы для реализации длинной арифметики, а именно решить вопросы касаемо того, как лучше это реализовать, а не как вообще реализовать.
Вы пишите "выглядит не очень" ? Что значит выглядит не очень ? Код не отформатирован. Не удобно разбираться в нем. Не не очень, а плохо выглядит этот код, хотя бы из-за форматирования. Вам Анатолий написал, а вы до сих пор не исправили. Не думаю что кто-то из тех кто может вам помочь специально отформатирует код за вас, и будет проверять. Вообщем ждем нормальный текст программы.


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

автор
Ну я это решил как организовать.Сначала считаем произведение первого числа с единицами второго

каким единицами ? У чисел разряды есть. А ещё есть числа, и цифры.

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

сдвигаете вы просто, зачем писать 20 слов чтобы это сказать ?

автор

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

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

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


Вообщем потрудитесь уважать тех у кого просите советы. Вы учитесь программированию, а не советы у наркоманов просите. Это конструктивные (и полезные для вас) замечания, а не просто критика. И пожалуйста обратите на них внимание. Ибо после совета Анатолия, вы снова привели ниже неотформатированный код.

SashaMercury,а как вы представляете себе отформатированный код?

Вот переделал полностью.

#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;
}

ванмомас намбаван
Вот переделал полностью.

А тебе известно, что разрядность произведения двух чисел равна сумме разрядностей
множителей?..

Posted via ActualForum NNTP Server 1.5

Несколько совершенно машинальных рефакторингов. Каждый день так делаю.
Не тестил. Тестируй сам козаче.

Особое thnks Дмитрию за замечание по разрядности результата.

#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;
}

mayton,спасибо.