CFA LogoCFA Logo Computer
Новости Статьи Магазин Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

Один, два, три... много!

Андрей КОВАЛЕНКО uant@ukr.net

Окончание, начало см. МК № 47 (270).

Определяем операции над «большими числами»

Теперь займемся реализацией сложения двух БЧ. Как видно из листинга, описывающего класс TLargeNum, мы вводим два метода Add: для прибавления БЧ и прибавления простого целого. Вот реализация первого:

Что делает этот метод? Он выполняет обычный алгоритм сложения «в столбик». Сначала мы обнуляем «хвост» 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) выглядит не просто просто — очень просто:

Вот оно, повторное использование кода.

Мы умеем складывать, значит, мы умеем умножать! В самом деле, 3210000 значит «прибавить 32 к нулю десять тысяч раз». Но если вы таким образом будете реализовывать метод TLargeNum.Mul, вы рискуете быть сожженным на костре паладинами Ее Величества Оптимальности :-). Конечно же, умножать мы будем тоже в столбик.

Сначала научимся умножать «на цифру», т.е. на число длиной 1:

Надеемся, никаких объяснений не требуется — полная аналогия с TLargeNum.Add. Для умножения «в столбик» на многозначное число (см. Рис. 1) нам понадобится метод, который смещает БЧ влево на n разрядов, дописывая нули в освобождающихся, т.е. умножает БЧ на 10^n:

Рис. 1.

А вот и функция умножения на произвольное число (мы близки к достижению сверхзадачи!):

Умножение на целое теперь нам дается «на шару»:

Может оказаться полезной функция перевода БЧ в обычное целое (разумеется, она будет корректно работать только для небольших Больших Чисел, уж простите за невольный каламбур):

В свою очередь метод TLargeNum.ToString дает представление БЧ в виде строки:

Такой «обходной» путь преобразования БЧ в целое немного напоминает процесс удаления гланд в армии :-), но, госпожа Оптимальность, потерпите еще немного, мы увидим значение 1000!, а потом так оптимизируем программу, что «вам тоже будет приятно» (это из «Мимино»).

Последний штрих перед написанием тривиального метода TLargeNum.Fact — реализация операции сравнения двух БЧ (Num1 = Num2 не годится, т.к. здесь происходит сравнение адресов объектов Num1 и Num2, а не их содержимого)

Метод сравнения БЧ с целым:

И наконец, вычисляем факториал:

Правда, просто? Осталось только создать формы ввода для наших больших чисел и вывода результатов вычислений. Поскольку у нас есть методы преобразования строки в БЧ и обратно, эта задача не сулит никаких затруднений (см. Рис. 2).

Вот что можно узнать, написав и отладив программу:

число 1000! содержит 2568 цифр;

из них 472 нуля;

из этих нулей 249 — завершающие;

удельное число цифр (частота появления) в числе 1000! примерно одинакова (см. диаграмму на Рис. 3).

Рис. 2.   Рис. 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 мышку протирать. Надо давать и твердую пищу своим пытливым умам :-).

Удачи!

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © sector.biz.ua 2006-2015 design by Vadim Popov