|
© 2018
Легалов А.И.
Примеры программ (2.7 кб)
Данный пример поясняет суть методических приемов, описанных в заметке: О разработке программного обеспечения. Модельный взгляд
Дополнительные знания о предметной области и модели исполнителя позволяют повысить эффективность процесса программирования. В качестве простого демонстрационного примера можно рассмотреть вычисление факториала от 100 (100!). Для того, чтобы написать программу необходимо выбрать:
- способ (модель) вычисления факториала, на основе которой будет разрабатываться алгоритм;
- язык программирования, на котором будет реализован этот алгоритм в виде программы.
Зачастую этот выбор определяется на основе субъективных знаний, что позволяет быстрее написать требуемый код, применяя при этом наиболее очевидные алгоритмы. Для факториала известны два основных описания: рекурсивный вариант, который часто используется как математическое описание задачи, и итеративный подход, позволяющий наглядно и просто показать, чем является вычисление факториала.
Рекурсивная версия опирается на следующее математическое представление факториала:
Алгоритм 1:
n! = если i=1 то 1
иначе n*(n-1)!
Итеративный алгоритм можно описать следующим образом:
Алгоритм 2
n! = произведению натуральных чисел от 1 до n.
Вполне понятно, что второй вариант более понятен для реализации на традиционных императивных языках и практически сразу позволяет попытаться построить решение. Что касается выбора языка программирования, то во многих случаях основным инструментом является тот, который хорошо изучен. Иногода это первый и единственный на данный момент язык. Пусть это будет язык C++.
Пойдем прямым путем
Исходя из выбранных начальных предпочтений функция вычисления факториала может выглядеть следующим образом:
// Вычисление факториала с использованием беззнаковых целых
unsigned factorial(unsigned n) {
if (n < 2) return 1;
unsigned p = 1;
for (unsigned i = 2; i <= n; ++i) {
p *= i;
}
return p;
}
Для получения результата сформируем главную функцию, осуществляющую вывод требуемого значения:
#include <iostream>
int main() {
std::cout << "100! = " << factorial(100) << std::endl;
return 0;
}
Однако после запуска этой функции получаем результат, который не оправдывает наших ожиданий:
100! = 0
Оказывается, что мы не учли возможность переполнения разрядной сетки, которая при вычислении факториала наступает достаточно быстро, что демонстрирует следующая версия главной функции:
#include <iostream>
int main() {
std::cout << "100! = " << factorial(100) << std::endl;
for(unsigned i = 0; i < 20; ++i) {
std::cout << i <<"! = " << factorial(i) << std::endl;
}
return 0;
}
Уже начиная с 14! результаты начинают вызывать сомнение:
100! = 0
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280
15! = 2004310016
16! = 2004189184
17! = 4006445056
18! = 3396534272
19! = 109641728
Не спасает и использование чисел с плавающей точкой:
// Вычисление факториала с использованием действительных чисел
double factorial(double n) {
if (n < 2.0) return 1;
double p = 1.0;
for (double i = 2.0; i <= n; ++i) {
p *= i;
}
return p;
}
#include <iostream>
int main() {
std::cout << "100! = " << factorial(100.0) << std::endl;
for(double i = 0.0; i < 20.0; ++i) {
std::cout << i <<"! = " << factorial(i) << std::endl;
}
return 0;
}
Правда использование порядка позволяет расширить диапазон вычисляемых значений, заодно показав, что уже 13! имеет другие начальные числа. Однако из-за фиксированного размера мантисы наблюдается потеря точности:
100! = 9.33262e+157
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3.6288e+06
11! = 3.99168e+07
12! = 4.79002e+08
13! = 6.22702e+09
14! = 8.71783e+10
15! = 1.30767e+12
16! = 2.09228e+13
17! = 3.55687e+14
18! = 6.40237e+15
19! = 1.21645e+17
Да и превращение целочисленной задачи в вещественную не является тем результатом к которому мы стремились. Таким образом наше недостаточное знание модели исполнителя не позволило получить требуемый результат.
«Нормальные герои всегда идут в обход»
Одним из путей решения данной задачи является разработка и реализация моделей, обеспечивающих построение алгоритмов и программы на основе моделирования целочисленной арифметики, работы с длинными числами. Для этого требуемые целочисленные величины нужно представить в виде массива машинных слов, а также определить необходимые для решения задачи функции, обеспечивающие работу с этими числами. Смоделируем длинное беззнаковое целое как одномерный массив, состоящий из коротких беззнаковых. Размер выберем исходя из желание переносить программу на C++ между 32-х и 64-х разрядными компьютерами. Типы short и long имеют для них зафиксированный размер (16 и 32 разряда соответственно). Длинные беззнаковые будем использовать для организации вычислений без переполнения над короткими беззнаковыми. Сократим обозначения типов:
typedef unsigned short us;
typedef unsigned long ul;
В данном учебном примере на будет уделять особого внимания надежности и прочим критериям, акцентировавшись на реализации специализированных моделей, описывающих функции, необходимые для решения поставленной задачи. Одной из таких функций является умножение. Перемножаются значение аккумулятора, являющегося беззнаковым длинным числом и беззнаковое, представляющее значение очередного числа. То есть, имеем массив беззнаковых v с текущим числом, занимающим len коротких беззнаковых слов, умножаемым на второй сомножитель y. Умножение осуществляется как в первом классе: столбиком. То есть в цикле с младших элементов массива осуществляется перемножение всех элементов на y. Перемножение осуществляется в длинном беззнаковом, что позволяет избежать переполнения. Перенос фиксируется в отдельной переменной путем сдвига старших разрядов результата вправо. При наличии переноса после перемножения старших разрядов он заносится в массив, длина которого увеличивается на единицу.
// Умножение вектора коротких чисел на целое положительное число.
int mult(us v[], int len, ul y) {
ul acc, per = 0;
for(int i = 0; i < len; i++) {
acc = (ul)v[i] * (ul)y +per;
v[i] = acc;
per = acc >> 16;
}
if(per) v[len++] = per;
return len;
}
Научившись перемножать можно написать функцию вычисления факториала, используя выбранную ранее итерационную модель. Отличие от предшествующих реализаций заключается лишь в использовании своей функии перемножения вместо операции, имеющейся в языке программирования.
#include <cstdlib>
#include <iostream>
using namespace std;
// Функция вычисления факториала заданной величины
int fact(us v[], int max_len, ul y) {
v[0] = 1;
int len = 1;
for(ul i = 2; i <= y; i++) {
len = mult(v, len, i);
if(len >= max_len) {
cout << "Vector overflow!!!" << endl;
exit (1);
}
}
return len;
}
Следует отметить, что перемножение осуществляется в двоичной системе счисления. Однако для вывода полученного значения необходимо его перевести в десятичную систему, реализовав соответствующую функцию вывода беззнакового длинного. Этот перевод тоже можно осуществить по простой классической схеме, применяемой, например, при преобразовании десятичного числа в двоичное,то есть путем деления с получением остатков. Только в данном случае делить нужно на 10. В результате деления получается новое частно в том же массиве и остаток от деления.
// Получение частного и остатка от деления
// вектора коротких целых на 10
int div_mod_10(us v[], int len, int &mod_rez) {
ul acc;
int i_v = len - 1;
mod_rez = 0;
while(i_v >= 0) {
acc = (mod_rez << 16) + v[i_v];
v[i_v] = acc / 10;
mod_rez = acc % 10;
--i_v;
}
if(v[len-1] == 0) --len;
return len;
}
Представленная выше функция используется в функции вывода беззнакового целого, которая реализована с применением левой рекурсии. Это позволяет выводить полученные остатки от деления в обратном порядке, обеспечивая тем самым десятичное представление двоичного числа.
// Вывод в десятичном виде содержимого вектора коротких целых чисел
void vector_out(us v[], int len) {
int xmod;
int new_len;
if(len > 0) {
new_len = div_mod_10(v, len, xmod);
vector_out(v, new_len);
cout << xmod;
}
}
Чтобы не встраивать дополнительные проверки, размер аккумулятора выберем таким образом чтобы при решении этой задачи он не переполнялся. Будем считать, что двухсот беззнаковых нам хватит (предыдыдущая программа, вычисляющая факториал на основе действительных чисел показала размер порядка, равный 157). Для контроля правильности работы написанной прораммы вставим дополнительный тестовый код, осуществляющий вычисление факториала с плавающей точкой. Будем считать, что все ОК, если старшие числа результатов совпадают (грубо, но в данном случае достаточно).
int main() {
us rezult[200];
int len = fact(rezult, 200, 100);
cout << endl << "rezult = ";
vector_out(rezult, len);
cout << endl;
cout << endl;
// Контрольный тест с использованием
// арифметики с плавающей точкой
long double f = 1;
for(int n=2; n<=100; n++) {
f *= n;
}
cout << "f = " << f << endl;
}
В результате получим следующее значение 100!:
rezult = 933262154439441526816992388562667004907159682643 \
816214685929638952175999932299156089414639761565182862536979208 \
27223758251185210916864000000000000000000000000
f = 9.33262e+157
Знания лишними не бывают
Используя хорошо понятный циклический алгоритм и знакомый язык мы, поднапрягшись в формировании вспомогательных моделей (используя методы формализации предметной области) получили решение искомой задачи. Однако через некоторое время выясняется, что существуют языки программирования, в которых данная формализация уже зашита в виде арифметики над длинными целыми числами. В стародавние времена таким языком являлся Lisp. Несмотря на вырвиглазный синтаксис (это метафора, а не наезд) и отсутствие операторов цикла (только рекурсия) он позволяет расправиться с данной предметной областью без каких-либо дополнительных функций и, следовательно, без манипуляциями с дополнительными моделями. То есть, данный язык напрямую реализует задачи рассматриваемой предметной области. Леворекурсивное решение при этом выглядит следующим образом:
;;; Использование левой рекурсии для вычисления факториала
;;; на языке программирования lisp
(defun factorial (n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
(print (factorial 100))
Для тех, кто желает повысить эффективность кода и более глубоко погружен в знание данного языка доступно праворекурсивное решение с хвостовой рекурсией, которое на уровне транслятора может легко быть преобразовано в итерацию:
;;; Использование хвостовой (правой) рекурсии для вычисления факториала
;;; на языке программирования lisp
(defun fact-iter (result counter)
(if (= counter 0)
result
(fact-iter (* counter result)
(- counter 1))))
(defun factorial (n)
(fact-iter 1 n)
)
(print (factorial 100))
Следует отметить, что современные языки сценариев тоже позволяют напрямую обрабатывать длинные целые числа. Поэтому погружаться в синтаксис Лиспа для решения подобных задач совсем не обязательно. Достаточно слегка окунуться в Питон (Python), чтобы, используя итеративный подход получить нужное решение.
# Вычисление факториала на языке программирования python
def factorial(n):
if n < 2:
return 1
f = 1
while n >= 2:
f *= n
n -= 1
return f
print ('100! = ', factorial(100))
Таким образом, наличие в инструментальных средствах прямой поддержки предметной области позволяет обойти формулирование и кодирование многих специализированных моделей. Языки программирования, напрямую поддерживающие предметную область, обеспечивают более быстрое написание соответствующих программ.
Однако не всегда можно найти и использовать соответствующие языки и инструменты. И в этом стоит обернуться назад и посмотреть, все ли мы выжали из известных нам инструментов? Речь идет о библиотеках, которые по сути являются различными проблемно- и предметно-ориентированными расширениями существующих языков программирования. Возможно меньшая наглядность функций и методов по сравнению с конструкциями, непосредственно включенными в специализированные и проблемно-ориентированные языки, затрудняет изучение этих дополнительных надстроек, но по мощности они ничуть не уступают, а зачастую и превосходят специально заточенные языковые средства.
Вернемся к С и C++. Оказывается, что программируя и на этих языках можно использовать длинную целочисленную арифметику. Для этого достаточно подключить свободную библиотеку произвольной точности (The GNU Multiple Precision Arithmetic Library, GMP). GMP - это бесплатная библиотека для арифметики произвольной точности, работающая с целыми знаковыми числами, рациональными числами и числами с плавающей запятой. Нет никаких практических ограничений на точность, кроме тех, которые определяются доступной памятью на компьютере. GMP имеет богатый набор функций, а функции имеют обычный интерфейс.
Основными целевыми приложениями для GMP являются приложения и исследования в области криптографии, приложения для обеспечения безопасности в Интернете, алгебраические, исследование в области вычислительной алгебры и т.д.
GMP тщательно спроектирована, чтобы быть максимально быстрой как для коротких, так и для длинных операндов. Скорость достигается за счет использования полных машинных слов в качестве основного арифметического типа, использования быстрых алгоритмов, оптимизацией на уровне машинного кода для большинства внутренних циклов, реализованных для различных процессоров, а также общего акцента на скорости вычислений.
В частности, используя язык программирования C, вычисление 100! можно осуществить следующим образом:
// Вычисление факториала с использованием библиотеки gmp и языка C
#include <stdlib.h>
#include <gmp.h>
int main(int argc, char* argv[]) {
mpz_t result;
unsigned long int x;
if(argc !=2)
x = 100;
else
x = atoi(argv[1]);
mpz_init_set_ui(result, 1UL);
unsigned long int i;
for(i = 2; i <= x; i++) {
mpz_mul_ui(result, result, i);
}
gmp_printf("%Zd\n", result);
return 0;
}
Тем, кому лениво выстраивать собственные циклы, достаточно напрямую использовать встроенную в библиотеку функцию вычисления факториала:
// Вычисление факториала с непосредственным использованием
// функции mpz_fac_ui, имеющейся в библиотеке gmp
#include <stdlib.h>
#include <gmp.h>
int main(int argc, char* argv[]) {
mpz_t result;
unsigned long int x;
if(argc !=2)
x = 100;
else
x = atoi(argv[1]);
mpz_init(result);
mpz_fac_ui(result, x);
gmp_printf("%Zd\n", result);
return 0;
}
Для любителей C++ реализована соответствующая обертка, включая перегрузку традиционных базовых операций. Поэтому программа смотрится почти также, как и написанная с использованием встроенных операций и типов данных:
// Вычисление факториала с использованием библиотек gmp и gmpxx
#include <cstdlib>
#include <iostream>
#include <gmpxx.h>
using namespace std;
int main(int argc, char* argv[]) {
if(argc !=2) {
cout << "Argumen is absent!!!" << endl;
return -1;
}
mpz_class result(1UL);
unsigned long int x = atoi(argv[1]);
for(unsigned long int i = 2; i <= x; i++) {
result *= i;
}
cout << result << endl;
return 0;
}
В заключении следует отметить, что формализация предметной области и ее последующая инструментальная поддержка позволяют резко повысить эффективность разработки ПО. Побочным эффектом этого является необходимость приобретения дополнительных знаний как о предметной области, так и об используемых инструментах, обеспечивающих формирование программ для выбранного исполнителя. Ведь чем больше мы знаем, тем больше забываем.
Если хотите вернуться к дальнейшему изучению методических приемов, то Вам сюда: О разработке программного обеспечения. Модельный взгляд
|