Форум на Исходниках.RU

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

Arsuit — Sun, 04 Jun 2006 07:34:59 +0000

Arsuit: Посмотрел я на свою бывшую статью и ужаснулся... Решил все полностью переписать. Вот гляньте, что я пока написал. Оформлю я все пото, когда допишу все до конца. пока прошу просто посмотреть, почитать, дополнить.

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

Что нужно знать, чтобы понять весь изложенный здесь материал:
1. Что такое одномерные массивы
2. Что такое системы счисления, остатки.
3. Уметь складывать, вычитать, умножать, делить числа столбиком.

Начальные сведения.

Когда вы пишите программы на каком либо языке программирования, бывает такое, что стандартных типов данных не хватает, для решения той или иной задачи. Такое бывает, например, если программа использует какой-либо комбинаторный алгоритм, или просто калькулятор длинных чисел.… Здесь уже стандартных типов данных (longint, int64 для паскаля/дельфи и long long для СИ) не хватит. Есть, конечно, типы с плавающей точкой (double, extended), но и их иногда может не хватить…

Именно для таких случаев существует замечательный способ, который называется длинной арифметикой. Длинная арифметика подразумевает собой хранение длинного числа поразрядно, в одномерном массиве. При том способ хранения может быть разный. Некоторые хранят в одном элементе по одной цифре, другие же хранят в одном элементе несколько цифр в целях экономии памяти, т. к. процессор выполняет арифметические операции с различными числами за одно и то же время (это относится к сравнительно коротким числам, которые хранятся в стандартных типах). Я предпочитаю хранить несколько цифр (при этом я считаю, что оптимальное число цифр – 4), и ниже будут примеры, реализующие именно этот способ. Но выбирать, чем пользоваться, все же вам. Однако стоит отметить, что в этом способе ЗНАЧИТЕЛЬНО усложняется процедура чтения длинного числа. Кроме всего прочего, число в массиве записывается «задом на перед» - так удобнее. То есть если у меня есть число 123456789012345, и я храню в элементе по 4 цифры, то оно у меня будет выглядеть так:
2345’8901’4567’123.

В паскале длинные числа стоит описывать так:

const

osn=10000; //основание. Так как в элементе массива мы храним 4 цифры, то можно сказать, что оно записано в osn-ичной системе счисления.

max=100; //кол-во элементов массива

type

TLong=array[0..max] of integer; // собственно сам массив с длинным числом.

Для удобства в нулевом элементе храним кол-во занятых элементов массива (как в стандартном типе string).

Чтение/вывод

Дальнейшее знакомство с длинными числами наверное стоит начать с процедур чтения/вывода длинного числа. Именно с этого как правило приходится начинать писать длинную арифметику (если конечно эти процедуры вообще нужны).

Чтение.
Для тех, кто хранит в одном элементе массива одну цифру тут все совсем просто. Читаем посимвольно число, преобразуем символы в цифры, записываем в массив. Затем массив переворачиваем (ведь мы храним число «задом на перед», вы не забыли?). Пример:

Procedure Long_read(var a:tlong);

var

c:char;

i,j:integer;

a:array[1..100] of byte;

begin

fillchar(a,sizeof(a),0);

repeat

read(c);

until c in ['0'..'9'];//пропускаем не цифры

i := 1;

while c in ['0'..'9'] do//пока цифры

begin

inc(i);

a[i]:=ord(c)-ord('0'); //преобразуем символ в цифру

read(c); //читаем еще символ.

end;

a[0]:=i;

j := i;

i := 1;

while i<j do //переворачиваем.

begin

swap(a[i],a[j]);

inc(i);

dec(j);

end;

Процедура Swap меняет значения переменных.
Если же вы все таки надумали хранить в одном элементе несколько цифр, то алгоритм чтения будет другой. Мы читаем из входного файла по одной цифре начиная с начала массива, и по ходу дела перемещаем все вправо.

procedure longread(var a:tlong);

var

c:char;

i:longint;

begin

fillchar(a,sizeof(a),0); //заполняем массив нулями.

repeat

read(c);

until c in ['0'..'9']; //пропускаем не символы.

while c 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(c)-ord('0'); // в конец первого разряда записываем полчтенную цифру.

if a[a[0]+1]>0 then inc(a[0]); // если мы заняли еще один элемент массива, то увеличиваем нулевой элемент

read(c); //читаем очередной символ.

end;

P.S. извиняюсь, что так долго пишу - я школу заканчиваю, экзамены, выпускные, поступление на носу...

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

Arsuit — Wed, 26 Apr 2006 13:28:47 +0000

Arsuit: Хорошо, я уже работаю над этим.

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

volvo877 — Sun, 23 Apr 2006 12:40:08 +0000

volvo877: Будут, когда ты это оформишь как следует. В таком виде ничего присоединяться не будет.

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

Arsuit — Sun, 23 Apr 2006 12:30:29 +0000

Arsuit: ну так это будут приобщать к общей статье?

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

Arsuit — Fri, 21 Apr 2006 14:20:40 +0000

Arsuit: ну хорошо. начнем с вычитания.

Цитата Arsuit @ 20.04.06, 17:40

if a[0]>b[0] then k := a[0] else k := b[0];

в этой строчке мы в переменную k записываем max(a[0],b[0]) - для границы цикла.

Затем мы запускаем цикл от 1 до k.
Переменная p служит для того, чтобы мы знали, занимали ли мы из соседнего разряда, или нет. (Если занимали, то p=1, иначе p=0 (все помнят вычитание столбиком?)).

Цитата Arsuit @ 20.04.06, 17:40

c[i]:=a[i]-b[i]-p;

Текущему разряду ответа присваиваем разность текущих разрядов вычитаемого и ... ну как его... то, что вычитают. Не помнь я как оно называется. Скажите пожалуйста, кто помнит. Ну так вот. Текущему разряду разности присваиваем разности вичитаемого, то, что вычитают и, если мы из этого разряда занимали, то вычитаем еще и единицу. Затем мы проверяем, если разность получилась отрицательной (if c[i]<0) то занимаем из соседнего разряда, а к текущему разряду ответа прибавляем основание (т. к. он стал отрицатльным).

и наконец вот эти

Цитата Arsuit @ 20.04.06, 17:40

for i := k downto 1 do
if c[i]<>0 then break;
c[0]:=i;

строки определяют кол-во цивр в ответе.
Ну вот с вычитанием мы вроде немного разобрались. Теперь деление. (Чтобы понять все, что здесь написано, вы должны помнить, как делятся числа столбиком :) )

Цитата Arsuit @ 20.04.06, 17:40

i := 1;
j := a[0];
while i begin
swap(a[i],a[j]);
inc(i);
dec(j);
end;

начнем с этих строк. Они переворачивают делимое. (если кто помнит, в длинной арифметике все числа записаны задом на перед - так с ними удобнее работать, в данном же случае (в случае деления) с длинным числом как раз таки удобнее работать, если оно записано в нормальном виде).

В переменной ost хранится остаток от деления разряда делимого на делитель. На каждом шаге цикла от 1 до a[0] мы к текущему остатку приписываем цифру из текущего разряда делимого (Longint(ost)*osn+a[i]), и делим все это на делитель (div b) и записываем в разряд частного. А в переменную, хранящую остаток мы записываем остаток от деления (Longint(ost)*osn+a[i]) на делитель.
Все. число поделено.

if c[1]=0 then
begin
c[0]:=a[0]-1;
for i := 1 to c[0] do c[i]:=c[i+1];
c[c[0]+1]:=0;
end
else c[0]:=a[0];
если a[1] В конце алгоритма мы переворачиваем число обратно.

Заметим, что этот алгоритм деления можно несколько усовершенствовать. Можно не переворачивать число, и начать деление с конца. Но выигрыш во времени от этого будет не значительный, а запутаться можно. Так что решайте сами, что вам важнее.

Добавлено 21.04.06, 14:21
ну вот. заценивайте статейку.

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

Romtek — Fri, 21 Apr 2006 10:14:26 +0000
Romtek: А обьяснить принцип? Как ты пришёл к этим процедурам? Это всё желательно показать, т.к. готовых процедур и модулей в интернете полно, а вот нормального описания мало.

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

Arsuit — Thu, 20 Apr 2006 17:40:53 +0000
Arsuit: Недавно решал задачи про длинную арифметику. Написал еще 2 процедуры - это длинное вычитание и деление длинного на короткое. Вот:

procedure longsub(a,b:tlong; var c:tlong);
var k,i,p:longint;
begin
  fillchar(c,sizeof(c),0);
  if a[0]>b[0] then k := a[0] else k := b[0];
  p := 0;
  for i := 1 to k do
   begin
   c[i]:=a[i]-b[i]-p;
   if c[i]<0 then
   begin
   p := 1;
   inc(c[i],osn);
   end
   else p:=0;
   end;
  for i := k downto 1 do
   if c[i]<>0 then break;
  c[0]:=i;
end;

procedure longdiv(a:tlong; b:longint; var c:tlong);
var
  p:longint;
  i,j,ost:integer;
begin
  fillchar(c,sizeof(c),0);p:=0;
  i := 1;
  j := a[0];
  while i<j do
   begin
   swap(a[i],a[j]);
   inc(i);
   dec(j);
   end;
  ost:=0;
  for i := 1 to a[0] do
   begin
   c[i]:=(Longint(ost)*osn+a[i])div b;
   ost :=(Longint(ost)*osn+a[i])mod b;
   end;
  if c[1]=0 then
   begin
   c[0]:=a[0]-1;
   for i := 1 to c[0] do c[i]:=c[i+1];
   c[c[0]+1]:=0;
   end
  else c[0]:=a[0];
  i := 1;
  j := c[0];
  while i<j do
   begin
   swap(c[i],c[j]);
   inc(i);
   dec(j);
   end;
end;

Прошу приобщить все это к основной статье.