Длинная арифметика - решение математики , ...и не только

[Морской Ёж]

Длинная Арифметика

При написании программ на паскале часто приходится сталкиваться с такой проблемой, что стандартных типов не хватает для работы с большими числами. Даже типа int64, который есть в TMT паскале, может не хватить во многих случаях. Чтобы работать с большими числами существует прием, который называется длинной арифметикой. Для наглядного объяснения сразу начнем писать модуль для работы с длинной арифметикой. Для начала напишем следующее банальное выражение:

unit Long;
interface
const
  osn = 10000;   {Порядок каждого числа}
  MaxDig = 1000; {Максимальное количество элементов}
type
  TLong = array[0..MaxDig] of integer; {Длинное число}
implementation
end.

Длинное число хранится в массиве типа TLong. В каждом элементе хранится по i цифр длинного числа. i вычисляется по формуле:

i = lg(osn)

При osn = 10000 i равно 4.

В нулевом элементе массива хранится количество задействованных элементов, а само число записывается в массив в обратном порядке. То есть если мы запишем в массив А число 123456789, то массив будет выглядеть так:

a[0] = 3
a[1] = 6789;
a[2] = 2345;
a[3] = 1;

Теперь надо написать две самые необходимые процедуры. Это процедуры чтения и вывода длинных чисел.

procedure Long_Read(var f:text; var a:TLong); {Читает длинное число из консоли или из файла}
var                                 {откуда будет производиться чтение, зависит от переменной F}
  ch:char;
  i:integer;
begin
  FillChar(a,Sizeof(A),0);         {Заполняем массив нулями}
  repeat                           {Пропускаем НЕ цифры вначале файла}
    Read(f,ch);                    
  until ch in ['0'..'9'];
  while ch in ['0'..'9'] do        {Начинаем читать цифры}
    begin
      for i := a[0] downto 1 do
        begin
          a[i+1] := a[i+1]+(Longint(a[i])*10) div osn;  {Записываем цифры в массив}
          a[i]   := (Longint(a[i])*10) mod osn;
        end;
      a[1] := a[1]+Ord(ch)-ord('0');
      if a[a[0]+1]>0 then inc(a[0]); {Если элемент текущий элемент заполнили, то переходим к следующему}
      Read(f,ch)                   {Читаем след. символ}  
    end
end;
{-----------------------------------------------------------------------------------------}
procedure Long_Write(var f:text; const a:TLong);     {Выводит число в файл или в консоль}
var
  ls,s:string;
  i:integer;
begin
  Str(Osn div 10,ls);  {Преобразуем в стоку osn div 10}
  Write(f,A[A[0]]);    {Выводим последний элемент}
  for i := a[0]-1 downto 1 do
    begin
      Str(a[i],s);     {Преобразуем в стороку каждый след. элемент}
      while Length(s)<Length(ls) do s := '0'+s;  {Если длина строки не равна lg(osn), то ставим перед ней 0}
      Write(f,s);             {Печатаем строку}
    end;
  WriteLn
end;

Процедура Long_Read читает длинное число из текстового файла в переменную А, а Long_Write записывает число из А в файл.
Если поставить input(output для Long_Write) в качестве первого параметра, то чтение и запись будут выполняться с консоли.

Чтобы можно было с этими считанными числами что-то делать, надо написать процедуры сложения, вычитания, умножения, деления, операции больше, меньше и т. п.

Арифметические операции производятся столбиком (вспоминаем 3 класс). Операции "больше-меньше" реализованы на том же уровне, т.е. поразрядное сравнение. Все это скомпонованное, отлаженное, проверенное я кладу в модуле LongMath.pas, в который добавлены операции с комплексными числами.

...и вот на всякий случай маленький примерчик...

uses LongMath;
var
  a,b,c : TLong;
  x,y,z : TComplex;
  
begin
  WriteLn ('Введите 2 длинных числа:');
  Long_Read(input,a); {Читаем с клавиатура а и b}
  Long_Read(input,b);
  if Long_Equal(a,b) then WriteLn('Числа a и b равны') {Сравниваем числа}
  else
    begin
      if Long_Less(a,b) then WriteLn('a меньше b');
      if Long_Above(a,b) then WriteLn('a больше b');
    end;
  WriteLn ('Нажмите Ввод для продолжения');
  ReadLn;
 
  Long_Add(a,b,c);    {c := a+b}
  WriteLn('Сумма x и y равна '); {Выводим сумму на экран}
  Long_Write (output, c);
 
  WriteLn ('Нажмите Ввод для продолжения');
  readln;
end.

(V. Приведенный модуль работает с беззнаковыми числами, впрочем в задачах, в которых нужны именно ОЧЕНЬ большие числа, они почти всегда больше нуля.)

Сообщение отредактировано: Romtek - 24.11.04, 15:11

Прикреплённый файлLongMath.zip (2 Кбайт, скачиваний: 1478)

[Мыкв]

ИМХО, копирайты-то поставить надо. Это код из книги С.М.Окулова.

и const osn - имелся ввиду не порядок, а основание системы счисления, в которой оперируем.
MaxDig - мкасимальное количество цифр.