Умножение больших чисел

[Relrin]

Суть задачи в том, чтобы найти произведение двух 50-значных чисел. Попытка через 3 массива выйти (два для оперирования с числами, и третий для хранения результата) пока не привели к полной решаемости задачи. Какие-то числа считает правильно, какие-то не совсем так (например, 2*3=6 правильно считает, а скажем 15*3=35, что не правильно). Помогите пожайлуйста

Var
   buf        : integer;           //полученное число, в результате умножения
   des        : integer;           //счетчик "десяток"
   n,m        : integer;           //счетчики длины строки
   i,j,q      : integer;           //переменные для работы со строкой и массивами
   x1,x2      : string;            //сюда вводим числа в виде строк
   c,d: array[1..50]   of integer; //массивы для хранения и оперирования с числами 
   res: array[1..2500] of integer; //результат вычислений

begin
   write('Введите первое число: ');
   readln(x1);
   n:=length(x1);
   write('Введите второе число: ');
   readln(x2);
   m:=length(x2);
   //перенос первого числа в массив
   i:=1;
     repeat
      val(x1[i],c[i],q);
      i:=succ(i);
     until i>n;
   //перенос второго числа в массив  
   i:=1;
     repeat
      val(x2[i],d[i],q);
      i:=succ(i);
     until i>m;
   //умножение двух чисел (умножение "столбиком") 
   for i:=1 to length(x1) do
   begin
     for j:=1 to length(x2) do
     begin
      buf:=c[i]*d[j]+des+res[i+j-1];
      res[i+j-1]:=buf mod 10;
      des:=buf div 10;
     end;
    res[i+j]:=des;
   end;
   //вывод полученного числа 
   if res[1]=0 then
   for i:=2 to length(x1)-length(x2)+1 do write(res[i])
    else 
   for i:=1 to length(x1)-length(x2)+1 do write(res[i]);
   readln;
end.

[Sparky]

эм вот когда писала длинную вещественную арифметику, может поможет

public:
			int chislo[count];	//число
			bool znak;	//знак числа + true, - false
			int por;	//порядок числа
			int len;	//длина числа

longfloat operator *(longfloat a,longfloat b)
{
//=============================================================================================================
//			вычисление знака после умножения	
//=============================================================================================================
	bool z;	//знак в итоге
	if((a.znak && b.znak)||(!a.znak && !b.znak))
		z=true;
	else
		z=false;
//=============================================================================================================
//			инициализация результирующего числа
//=============================================================================================================
	longfloat new_float;
	for(int i=0;i<count;i++)
		new_float.chislo[i]=0;

	new_float.por=1; ///
	new_float.len=1;
	new_float.znak=true;
	a.znak=true;
	b.znak=true;

//=============================================================================================================
//		проверка одного из чисел на 0		
//=============================================================================================================
	bool flag1=true;	//показывает состоит ли первое число из 0
	bool flag2=true;	//показывает состоит ли второе число из 0

	for(int i=0;i<count;i++)
	{
		if(a.chislo[i]!=0)
			flag1=false;
		if(b.chislo[i]!=0)
			flag2=false;
	}

	if(flag1 || flag2)
	{
		new_float.por = 1;
		new_float.len = 1;
		new_float.znak=true;
		return new_float;
	}

	else
	{
//=============================================================================================================
//			вычисление порядка нового числа	
//=============================================================================================================
		int drobn=(a.len-a.por)+(b.len-b.por);
		if (b.len>a.len)
			swap(a,b);
//=============================================================================================================
//			умножение
//=============================================================================================================
		int mark=2;
		for(int j=count-1;j>=(count-b.len);j--)
		{
			for(int k=0;k<b.chislo[j];k++)
				new_float=new_float+a;
			int i=count-a.len-mark;
			for(i;i<count-1;i++)
			{
				a.chislo[i]=a.chislo[i+1];
				a.chislo[i+1]=0;
			}
			mark++;
		}
		new_float.por=new_float.len-drobn;
		if (new_float.por==0)
		{
			new_float.por=1;
			new_float.len++;
		}
//=============================================================================================================
//			обновление знака			
//=============================================================================================================
		new_float.znak=z;
		del(new_float);
		return new_float;
	}

}

[Aries]

Раз 15*3=35, то получается, что умножает только единицу на тройку и результат складывается с последним числом.

[Don Karleone]

Вот книга, если я не ошибаюсь, там рассматривается эта тема. Может тебе поможет.

[evg_m]

Раз 15*3=35, то получается, что умножает только единицу на тройку и результат складывается с последним числом.

скорее не учитывет перенос.
15
3
-----
15 потеряли вот эту единицу
3
-----
35

[Relrin]

Сейчас осталась маленькая накладка. Когда например считаю число, скажем 3*4, то в результате выходит 12, но выводит только 2, как добавить недостающий знак? (Внизу код умножения)
Подсчеты типа 3*15, 125*4, и т.д. считает правильно!

   for i:=length(x1) downto 1 do
   begin
     for j:=length(x2) downto 1 do
     begin
      buf:=c[i]*d[j]+des;
        if buf>9 then
        begin
         res[i+j-1]:=buf mod 10;
         des:=buf div 10;
        end
         else
         begin
          res[i+j-1]:=buf;
          des:=0;
         end;    
     end;
   end;

[evg_m]

после цикла тоже надо проверять des и сохранять при необходимости

[Kingdom_Reborn]

Да задача то элементарная! Я на первом курсе решал задачу деления двух длинных чисел. И решение проверялось на тестах, все тесты прошли.

Вот по поводу умножения (на Delphi 7):

const
  MaxLen = 1000;
  BASE = 10000;
  BASE_DIG = 4;

type
  TLong = record
    Length: Integer;
    Coef: Array[0..MaxLen] of Integer;
  end;

// Обнуляет число типа TLong
procedure Zero(var A: TLong);
begin
  FillChar(A.Coef, SizeOf(A.Coef), 0);
  A.Length := 1;
end;

// возвращает произведение длинного числа на короткое
function Mul(const A: TLong; const B: Longint): TLong;
overload;
var
  C: TLong;
  I: Integer;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
    C.Coef[I] := A.Coef[I] * B;
  for I := 0 to A.Length - 1 do
  begin
    Inc(C.Coef[I + 1], C.Coef[I] div BASE);
    C.Coef[I] := C.Coef[I] mod BASE;
  end;
  C.Length := A.Length;
  if C.Coef[A.Length] <> 0 then Inc(C.Length);
  Mul := C;
end;

// возвращает произведение двух длинных чисел
function Mul(const A, B: TLong): TLong;
overload;
var
  C: TLong;
  I, J: Integer;
  temp, carry: Integer;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
  begin
    carry := 0;
    for J := 0 to B.Length - 1 do
    begin
      temp := A.Coef[I] * B.Coef[J] + C.Coef[I + J] + carry;
      carry := temp div BASE;
      C.Coef[I + J] := temp - carry * BASE;
    end;
    C.Coef[I + B.Length] := carry;
  end;
  I := A.Length + B.Length - 1;
  while (I > 0) and (C.Coef[I] = 0) do
    Dec(I);
  C.Length := I + 1;
  Mul := C;
end;

// конвертация строки в число типа TLong
function Convert(S: String): TLong;
var
  I, K, d: Integer;
  _S: String;
  C: TLong;
begin
  Zero(C);
  d := Length(S);
  while d mod BASE_DIG <> 0 do  // добавляем нули слева
  begin
    S := '0' + S;
    Inc(d);
  end;
  K := 0;
  _S := '';
  for I := d downto 1 do
  begin
    _S := Concat(S[I], _S);
    if (I - 1) mod BASE_DIG = 0 then
    begin
      C.Coef[K] := StrToInt(_S);
      Inc(K);
      _S := '';
    end;
  end;
  C.Length := K;
  Convert := C;
end;

// печать длинного числа
procedure Print(const A: TLong);
var
  I: Integer;
  d: Integer;
begin
  for I := A.Length - 1 downto 0 do
  begin
    if I <> A.Length - 1 then
    begin
      d := Length(IntToStr(A.Coef[I]));
      if d < BASE_DIG then
        while d <> BASE_DIG do
        begin
          Write('0');
          Inc(d)
        end;
    end;
    Write(A.Coef[I]);
  end;
  WriteLn;
end;

Как пользоваться, думаю, понимаете - берёте длинное число как строку, конвертируете с помощью процедуры Convert в TLong, а потом передаёте в функции...

P. S. Размеры чисел могут быть огроменные (см. MaxLen и BASE).

[Utkin]

Главная проблема - Ваши числа по настоящему большие. Если мне надо хранить сто знаков - Ваш массив займет 1000. Это не было бы такой проблемой, если бы все числа были бы нужного размера. Но основная фишка в том, что числа часто имеет разное число разрядов и хранить лишние нули непозволительная роскошь .
Юзайте динамические массивы, для человеческой реализации. Был бы я преподом, поставил незачет.

[Serge_Bliznykov]

Юзайте динамические массивы, для человеческой реализации. Был бы я преподом, поставил незачет.

Далеко не всё так однозначно, коллега.
1) динамические массивы появились только в Delphi, а в том же Pascal их просто не было.
2) динамические массивы (в общем случае) медленнее, чем статические (правда, основные затраты времени там тратятся на изменение длины массива, но и в работе они тоже медленнее)
3) заданное ограничение вполне оправдано. Тем более исходя из задания.
4) и, последнее, зачем усложнять учебную задачу?