Автор: Эли Дэ Брувэр (Elie De Brauwer)
Для тех, кто заинтересовался, версия сценария на языке Python. Компьютеры и математика всегда были лучшими друзьями. Возможно, поэтому существует так много ошибок. В этой статье речь будет идти о распространённой проблеме с переполнением. В нашем примере мы будем работать с так называемой последовательностью Фибоначчи, которая начинается с нуля и единицы, и каждое следующее значение последовательности равно сумме двух предыдущих чисел. Итак, последовательность будет выглядеть таким образом: 0, 1, 1, 2, 3, 5, 8, 13, 21…, и сразу становится ясно, что генерация такой последовательности – идеальная работа для компьютера. Но есть загвоздка: эти числа очень быстро возрастают. У последовательности Фибоначчи много интересных свойств, и существуют разнообразные, более эффективные алгоритмы генерации определённого числа.
Определяем границы
Листинг 1: Fibonacci.c
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 представлено простое приложение, в основном цикле которого (строки 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: Fibonacci2.c
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. }
Его можно скомпилировать командой:
gcc -Wall -lgmp Fibonacci2.c -o Fibonacci2
представлена реализация того же алгоритма, но с использованием 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 так, чтобы память не выделялась и освобождалась каждый раз, а чтобы она перераспределялась, когда возникает необходимость в дополнительных разрядах.
