fullcircle:24:программа_на_си_ч4 | Русскоязычная документация по Ubuntu

Эта страница только для чтения. Вы можете посмотреть исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
======Програмирование на Си -- Часть 8 ======
<style right>
//Автор – Ели Де Брауен (Elie De Brauwer)//
</style>

Для тех, кто заинтересовался, версия сценария на языке PythonКомпьютеры и математика всегда были лучшими друзьями. Возможно, поэтому существует так много ошибок. В этой статье речь будет идти о распространённой проблеме с переполнением. В нашем примере мы будем работать с так называемой последовательностью Фибоначчи, которая начинается с нуля и единицы, и каждое следующее значение последовательности равно сумме двух предыдущих чисел. Итак, последовательность будет выглядеть таким образом: 0, 1, 1, 2, 3, 5, 8, 13, 21..., и сразу становится ясно, что генерация такой последовательности – идеальная работа для компьютера. Но есть загвоздка: эти числа очень быстро возрастают. У последовательности Фибоначчи много интересных свойств, и существуют разнообразные, более эффективные алгоритмы генерации определённого числа.

Определяем границы

<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. }

Листинг 1: Fibonacci.c 
</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 так, чтобы память не выделялась и освобождалась каждый раз, а чтобы она перераспределялась, когда возникает необходимость в дополнительных разрядах.
fullcircle:24:программа_на_си_ч4 Правка
