Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
fullcircle:24:программа_на_си_ч4 [2010/05/02 16:41] |
— (текущий) | ||
|---|---|---|---|
| Строка 1: | Строка 1: | ||
| - | ======Програмирование на Си -- Часть 8 ====== | ||
| - | <style right> | ||
| - | //Автор – Ели Де Брауен (Elie De Brauwer)// | ||
| - | </style> | ||
| - | Для тех, кто заинтересовался, версия сценария на языке PythonКомпьютеры и математика всегда были лучшими друзьями. Возможно, поэтому существует так много ошибок. В этой статье речь будет идти о распространённой проблеме с переполнением. В нашем примере мы будем работать с так называемой последовательностью Фибоначчи, которая начинается с нуля и единицы, и каждое следующее значение последовательности равно сумме двух предыдущих чисел. Итак, последовательность будет выглядеть таким образом: 0, 1, 1, 2, 3, 5, 8, 13, 21..., и сразу становится ясно, что генерация такой последовательности – идеальная работа для компьютера. Но есть загвоздка: эти числа очень быстро возрастают. У последовательности Фибоначчи много интересных свойств, и существуют разнообразные, более эффективные алгоритмы генерации определённого числа. | ||
| - | |||
| - | Определяем границы | ||
| - | Листинг 1: Fibonacci.c | ||
| - | <code> | ||
| - | 01. #include <stdio.h> | ||
| - | 02. | ||
| - | 03. typedef unsigned long long fibo_type; | ||
| - | 04. #define FIBO_FORMAT "%10llu" | ||
| - | 05. | ||
| - | 06. void printFibo(fibo_type num) | ||
| - | 07. { | ||
| - | 08. printf(FIBO_FORMAT,num); | ||
| - | 09. } | ||
| - | 10. | ||
| - | 11. int main() | ||
| - | 12. { | ||
| - | 13. int num=0; | ||
| - | 14. fibo_type a=0,b=1,c | ||
| - | 15. | ||
| - | 16. printf("%4d: ",++num); printFibo(a); printf("\n"); | ||
| - | 17. | ||
| - | 18. printf("%4d: ",++num); printFibo(b); printf("\n"); | ||
| - | 19. | ||
| - | 20. c=a+b; | ||
| - | 21. while(c>=b) | ||
| - | 22. { | ||
| - | 23. printf("%4d: ",++num); printFibo(c); printf("\n"); | ||
| - | 24. a=b; b=c; c=a+b; | ||
| - | 25. } | ||
| - | 26. printf("Остановка после %d знаков\n",num); | ||
| - | 27. printFibo(c); printf("\n"); | ||
| - | 28. return 0; | ||
| - | 29. } | ||
| - | </code> | ||
| - | |||
| - | |||
| - | На Листинге 1 представлено простое приложение, в основном цикле которого (строки 11 – 29 ) определены три переменные: a, b и c, которые будут содержать предыдущий, текущий и следующий член последовательности Фибоначчи. В каждой итерации числа смещаются, и рассчитывается следующее значение. Правда, есть одна странная вещь: условие в цикле while на строке 21. Оно звучит как c>=b, но c равно b+a, и с точки зрения математики это выражение бессмысленно, так как всегда будет выполняться. | ||
| - | Однако, это приложение работает не в математической утопии, а на компьютере. Это значит, в случае с 32-битными целыми числами без знака (unsigned integer), если прибавить к 0xffffffff единицу, в результате получится 0x0. Это говорит о том, что произошло переполнение разрядной сетки, и новое значение выходит за пределы 32 бит (0x100000000), поэтому результат вычисляется только по 32-м младшим битам (0x100000000&0xffffffff=0x0). Другими словами, произошёл циклический возврат (wrap). То же самое происходит при работе с числами со знаком, но в этом случае переполнение сначала произойдёт в знаковом бите, и в итоге вы получите большое отрицательное значение. | ||
| - | |||
| - | В строках 3 и 4 определены fibo_type и FIBO_FORMAT. Они используются для того, чтобы легко адаптировать приложение к другим типам данных. Таким образом можно наблюдать, где проходит граница при использовании величины со знаком (signed), или типа short. В случае unsigned long long, приложение может вычислить 94 числа Фибоначчи. | ||
| - | |||
| - | |||
| - | Можно также поэкспериментировать с числами с плавающей точкой, у которых диапазон значений шире. Но учтите, что при этом теряется точность. Это, возможно, даже более опасно, так как число выглядит корректным, но на самом деле это не так (если сомневаетесь – спросите тех, кто писал программы для ракеты Ariane 5). | ||
| - | |||
| - | Вывод такой: это хорошо, что множество целых чисел бесконечно. Но было бы ещё лучше, если бы мы могли действительно использовать их все. | ||
| - | |||
| - | Рушим границы | ||
| - | |||
| - | Ну, в действительности мы можем использовать все, но придётся за это заплатить производительностью. Сложение двух 32-битных величин – чертовски быстрая процедура, фактически, это делается простой командой ассемблера, но опять же, мы натыкаемся на 32-битный предел (предел может различаться в зависимости от типа процессора, но присутствует в любом случае). Но есть обходной путь. Вместо целых чисел мы могли бы использовать массив и реализовать операцию сложения самостоятельно, просто сделав так, как нас учили в начальной школе: добавлять по одной цифре, считать результат и т.д. Для сложения и вычитания это делается легко, но при умножении, делении и вычислении квадратных корней всё усложняется, и кажется маловероятным, что можно реализовать эти операции эффективно. Сложение двух цифр занимает столько же времени, как сложение двух целых чисел, поэтому сложение двух четырёхзначных чисел вручную займёт в четыре раза больше времени, чем в варианте с типом integer. | ||
| - | |||
| - | К счастью, мы живём в открытом мире (по крайней мере частично), и нет необходимости заново изобретать велосипед. Существует библиотека GMP (GNU Multiple Precision Arithmetic Library, http://gmplib.org), в которой есть эта и множество других возможностей. Всё, что нам нужно сделать – ввести в консоли sudo apt-get install libgmp3-dev. У этой библиотеки обширный функционал, но в этой статье мы лишь пройдёмся по поверхности. Я настоятельно рекомендую читателю взглянуть на документацию по API на http://gmplib.org/manual/, чтобы ознакомиться с возможностями этой библиотеки. | ||
| - | |||
| - | На Листинге 2. | ||
| - | |||
| - | <code> | ||
| - | 01. #include <stdio.h> | ||
| - | 02. #include <stdlib.h> | ||
| - | 03. #include <string.h> | ||
| - | 04. #include <gmp.h> | ||
| - | 05. | ||
| - | 06. int main() | ||
| - | 07. { | ||
| - | 08. int num=0; | ||
| - | 09. mpz_t f_1; | ||
| - | 10. mpz_t f_2; | ||
| - | 11. | ||
| - | 12. mpz_init(f_1); | ||
| - | 13. mpz_init(f_2); | ||
| - | 14. mpz_set_ui(f_1,0); | ||
| - | 15. mpz_set_ui(f_1,1); | ||
| - | 16. printf("%10d: 0\n",++num); | ||
| - | 17. | ||
| - | 18. while(1) | ||
| - | 19. { | ||
| - | 20. mpz_add(f_1,f_2,f_1); | ||
| - | 21. mpz_swap(f_1,f_2); | ||
| - | 22. char * res = mpz_get_str(NULL,10,f_2); | ||
| - | 23. printf("%10d: %s\n",++num, res); | ||
| - | 24. free(res); | ||
| - | 25. } | ||
| - | 26. | ||
| - | 27. mpz_clear(f_1); | ||
| - | 28. mpz_clear(f_2); | ||
| - | 29. return 0; | ||
| - | 30. } | ||
| - | |||
| - | Листинг 2: Fibonacci2.c | ||
| - | </code> | ||
| - | |||
| - | Его можно скомпилировать командой: | ||
| - | |||
| - | <code>gcc -Wall -lgmp Fibonacci2.c -o Fibonacci2</code> | ||
| - | |||
| - | представлена реализация того же алгоритма, но с использованием GMP. В строках 12-15 происходит инициализация переменных и установка их начальных значений. GMP незаметно для нас выделяет память и производит необходимый учёт ресурсов. Строки с 18 по 25 представляют собой главный цикл (бесконечный), где функция mpz_add выполняет сложение двух целых чисел и помещает результат в mpz_t. Это заменяет операцию c=a+b. А mpz_swap используется для упорядочивания значений. Здесь используются только две переменные и один обмен значениями, в отличие от трёх переменных и двойного обмена значениями в Листинге 1. Во второй части цикла while, в строках 22-24 создаётся строковое десятичное представление mpz_t, производится его вывод на экран и освобождение памяти (внимание: здесь есть что улучшить, смотрите упражнения). Строки 26-30 никогда не исполняются, но они показывают, как будет очищаться внутренняя структура. Этот пример ярко показывает, какая мощная эта библиотека. С точки зрения программиста всё, что нам нужно сделать – заменить инициализацию наших переменных на вызов библиотеки. Библиотека без нашего ведома позаботится обо всём остальном. Но не забывайте, что все эти «простые» сложения на самом деле представляют собой трудоёмкие вычисления, и использовать тип, отличный от integer, для переменной num – это не очень хорошая идея. | ||
| - | |||
| - | Итак, это приложение (круче которого теперь только Матрица) даёт нам действительно безграничное (ну, на самом деле num переполнится после 2^31 цифр Фибоначчи) количество чисел Фибоначчи. | ||
| - | |||
| - | Упражнения | ||
| - | |||
| - | • Попробуйте запустить приложение для различных типов в Fibonacci.c: char со знаком (signed) и без (unsigned), short, long и long long, и попробуйте определить их границы. | ||
| - | |||
| - | • Попробуйте то же с типами чисел с плавающей точкой в Fibonacci.c. Больше ли чисел получается? Они корректны? В какой момент появляется ошибка? | ||
| - | |||
| - | • Пройдитесь по документации к GMP и ознакомьтесь с возможностями библиотеки. | ||
| - | |||
| - | • Прочитайте руководство по GMP и найдите раздел о mpz_get_str. Теперь перепишите Fibonacci2 так, чтобы память не выделялась и освобождалась каждый раз, а чтобы она перераспределялась, когда возникает необходимость в дополнительных разрядах. | ||
