Окончание, начало см. МК № 47 (270).
Определяем операции над «большими числами»
Теперь займемся реализацией сложения двух БЧ. Как видно из листинга, описывающего класс TLargeNum, мы вводим два метода Add: для прибавления БЧ и прибавления простого целого. Вот реализация первого:
function TLargeNum.Add(n: TLargeNum): TLargeNum; var Tail: byte; // хвост ("довесок") i: integer; a1, a2: byte; asum: byte; MaxLen: integer; TempArr: TLargeArr; // массив байтов begin Tail := 0; MaxLen := max(Self.Len, n.Len); FillChar(TempArr , _maxlen, 0); // обнуляем for i := 1 to MaxLen do begin a1 := Self .GetDigit(i); a2 := n .GetDigit(i); asum := (a1 + a2 + Tail) mod 10; Tail := (a1 + a2 + Tail) div 10; TempArr[i] := asum; end; TempArr[MaxLen + 1] := Tail; if (Tail > 0) then inc(MaxLen); Self.Value := TempArr; Self.Len := MaxLen; Result := Self; end;
Что делает этот метод? Он выполняет обычный алгоритм сложения «в столбик». Сначала мы обнуляем «хвост» Tail, находим длину MaxLen большего из двух слагаемых БЧ Self и n, после чего заполняем массив TempArr нулями. В цикле по i мы берем i-ю цифру из числа Self и складываем ее с i-й цифрой числа n. Если сумма будет больше 9, то в Tail запишется единица, а в asum — сумма цифр по модулю 10 (т.е. остаток от деления на 10). При очередном проходе цикла значение Tail прибавляется к сумме цифр следующего (старшего) разряда, и так для всех цифр слагаемых. Это и есть сложение в столбик. Наконец, если в результате последнего сложения Tail будет равна 1, необходимо увеличить длину результата на 1. Придирчивому читателю, разумеется, резанет глаз неоптимальность нашей реализации Add (например, для сложения 2783+6 будет выполнено 4 прохода цикла, хотя достаточно одного), но мы отложим пока оптимизацию, которая является отдельной интересной подзадачей, в сторону, отдав предпочтение «прозрачности» алгоритма. Главное, что теперь мы можем складывать числа длиной 2999 цифр! Если, конечно, нас не обломает их вводить :-).
Метод TLargeNumber.Add(n: integer) выглядит не просто просто — очень просто:
function TLargeNum.Add(n: integer):TLargeNum; var tmp: TLargeNum; begin tmp := TLargeNum.Create(n); //преобразуем n в БЧ tmp Result := Self.Add(tmp); tmp.Free(); end;
Вот оно, повторное использование кода.
Мы умеем складывать, значит, мы умеем умножать! В самом деле, 3210000 значит «прибавить 32 к нулю десять тысяч раз». Но если вы таким образом будете реализовывать метод TLargeNum.Mul, вы рискуете быть сожженным на костре паладинами Ее Величества Оптимальности :-). Конечно же, умножать мы будем тоже в столбик.
Сначала научимся умножать «на цифру», т.е. на число длиной 1:
function TLargeNum.MulByDigit(n: byte): TLargeNum; var Tail: byte; i: integer; a: byte; amul: byte; TempArr: TLargeArr; begin if (n=0) then begin Self.AssignNumber(0); Result := Self; exit; end; Tail := 0; FillChar(TempArr , _maxlen, 0); for i := 1 to Len do begin a := Self .GetDigit(i); amul := (a * n + Tail) mod 10; Tail := (a * n + Tail) div 10; TempArr[i] := amul; end; TempArr[Len + 1] := Tail; if (Tail > 0) then inc(Len); Self.Value := TempArr; Result := Self; end;
Надеемся, никаких объяснений не требуется — полная аналогия с TLargeNum.Add. Для умножения «в столбик» на многозначное число (см. Рис. 1) нам понадобится метод, который смещает БЧ влево на n разрядов, дописывая нули в освобождающихся, т.е. умножает БЧ на 10^n:
function TLargeNum.ShiftLeft(cnt: integer): TLargeNum; begin if (((Len = 1) and (Value[1] = 0)) or (cnt<1)) then begin Result := Self; exit; end; Move(Value[1], Value[cnt+1], Len); FillChar(Value[1], cnt, 0); Value[1] := 0; inc(Len, cnt); Result := Self; end;
А вот и функция умножения на произвольное число (мы близки к достижению сверхзадачи!):
function TLargeNum.Mul(n: TLargeNum):TLargeNum; var i: integer; Total: TLargeNum; dig: byte; ACopy: TLargeNum; begin Total := TLargeNum.Create(0); ACopy := TLargeNum.Create(Self); for i := 1 to n.Len do begin dig := n.GetDigit(i); ACopy.AssignNumber(Self); ACopy.MulByDigit(dig); ACopy.ShiftLeft(i-1); Total.Add(ACopy); end; Self.AssignNumber(Total); Total.Free(); ACopy.Free(); Result := Self; end;
Умножение на целое теперь нам дается «на шару»:
function TLargeNum.Mul(n: integer):TLargeNum; var tmp: TLargeNum; begin tmp := TLargeNum.Create(n); // переводим целое в БЧ Result := Self.Mul(tmp); // используем умножение на БЧ tmp.Free; // освободить память — она не резиновая! end;
Может оказаться полезной функция перевода БЧ в обычное целое (разумеется, она будет корректно работать только для небольших Больших Чисел, уж простите за невольный каламбур):
function TLargeNum.ToInteger: integer; begin Result := StrToInt(Self.ToString); //сначала в строку, а потом в целое end;
В свою очередь метод TLargeNum.ToString дает представление БЧ в виде строки:
function TLargeNum.ToString(): WideString; var st: string; i: integer; begin SetLength(st, Len); for i := 1 to len do st[i] := ByteToChar(Value[Len + 1 — i]); Result := st; end;
Такой «обходной» путь преобразования БЧ в целое немного напоминает процесс удаления гланд в армии :-), но, госпожа Оптимальность, потерпите еще немного, мы увидим значение 1000!, а потом так оптимизируем программу, что «вам тоже будет приятно» (это из «Мимино»).
Последний штрих перед написанием тривиального метода TLargeNum.Fact — реализация операции сравнения двух БЧ (Num1 = Num2 не годится, т.к. здесь происходит сравнение адресов объектов Num1 и Num2, а не их содержимого)
function TLargeNum.Equ(Num2: TLargeNum): boolean; var i: integer; begin Result := false; if (Self.Len <> Num2.Len) then exit; for i := 1 to Len do if Self.Value[i] <> Num2.Value[i] then exit; Result := true; end;
Метод сравнения БЧ с целым:
function TLargeNum.Equ(Num2: integer): boolean; var tmp: TLargeNum; begin tmp := TLargeNum.Create(Num2); Result := Self.Equ(tmp); tmp.Free; end;
И наконец, вычисляем факториал:
function TLargeNum.Fact: TLargeNum; var tmp: TLargeNum; i: integer; begin tmp := TLargeNum.Create(1); // tmp — БЧ со значением <1>[формула??????] if (Self.Equ(0)) then begin Result := tmp; exit; // если <0>, то результат будет <1> end; for i := 1 to Self.ToInteger do tmp.Mul(i); Result := tmp; end;
Правда, просто? Осталось только создать формы ввода для наших больших чисел и вывода результатов вычислений. Поскольку у нас есть методы преобразования строки в БЧ и обратно, эта задача не сулит никаких затруднений (см. Рис. 2).
Вот что можно узнать, написав и отладив программу:
число 1000! содержит 2568 цифр;
из них 472 нуля;
из этих нулей 249 — завершающие;
удельное число цифр (частота появления) в числе 1000! примерно одинакова (см. диаграмму на Рис. 3).
Немного об оптимизации и о том, зачем это нужно
Наша программа — пример работающего, но, увы, далекого от совершенства кода. Что можно сделать, чтобы повысить ее производительность и удобство использования?
переписать программу на C++, используя классы и переопределения арифметических операторов;
использовать для хранения БЧ не десятичную, а двоичную систему счисления, поскольку, во-первых, она ближе к аппаратным средствам компьютера, а во-вторых, экономит память;
оптимизировать операции сложения, чтобы цикл сложения цифр повторялся не максимальное число раз, а ровно столько, сколько нужно;
использовать динамические массивы переменной длины, что повысит гибкость программы;
переписать код для операций над БЧ на «чистом» ассемблере, что повысит производительность программы;
добавить реализацию вычитания и поддержку отрицательных чисел;
добавить реализацию деления и работы с дробной частью (эта задача посложнее!);
добавить работу с функциями.
Таким образом вы получите настольный калькулятор, не очень производительный, но очень точный и многоразрядный.
И опять же может возникнуть вопрос: а кому это все надо, зачем тратить столько усилий на бесполезные цифры? Ответим замечательными словами Стивена Вайнберга, автора «Первых трех минут»: The effort to understand the universe is one of the very few things that lifts human life a little above the level of farce and gives it some of the grace of tragedy, то есть «стремление понять мир — одна из очень немногих вещей, которая приподнимает человеческую жизнь над уровнем фарса и придает ей красоту трагедии».
Другими словами, не все же время скины для Винампа вам скачивать да в Counter-Strike мышку протирать. Надо давать и твердую пищу своим пытливым умам :-).
Удачи!