Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
fullcircle:24:программа_на_си_ч8 [2010/05/02 16:49] |
fullcircle:24:программа_на_си_ч8 [2013/09/28 17:02] (текущий) [HOW-TO: Программа на Си. Часть 8] |
||
|---|---|---|---|
| Строка 1: | Строка 1: | ||
| - | ====== HOWO-TO: Програмирование на Си -- Часть 8 ====== | + | ====== HOW-TO: Программа на Си. Часть 8 ====== |
| - [[..:17:программа_на_си_ч1|Программа на Си. Часть 1]] | - [[..:17:программа_на_си_ч1|Программа на Си. Часть 1]] | ||
| Строка 17: | Строка 17: | ||
| ===== ===== | ===== ===== | ||
| - | Для тех, кто заинтересовался, версия сценария на языке PythonКомпьютеры и математика всегда были лучшими друзьями. Возможно, поэтому существует так много ошибок. В этой статье речь будет идти о распространённой проблеме с переполнением. В нашем примере мы будем работать с так называемой последовательностью Фибоначчи, которая начинается с нуля и единицы, и каждое следующее значение последовательности равно сумме двух предыдущих чисел. Итак, последовательность будет выглядеть таким образом: 0, 1, 1, 2, 3, 5, 8, 13, 21..., и сразу становится ясно, что генерация такой последовательности – идеальная работа для компьютера. Но есть загвоздка: эти числа очень быстро возрастают. У последовательности Фибоначчи много интересных свойств, и существуют разнообразные, более эффективные алгоритмы генерации определённого числа. | + | Для тех, кто заинтересовался, версия сценария на языке Python. Компьютеры и математика всегда были лучшими друзьями. Возможно, поэтому существует так много ошибок. В этой статье речь будет идти о распространённой проблеме с переполнением. В нашем примере мы будем работать с так называемой последовательностью Фибоначчи, которая начинается с нуля и единицы, и каждое следующее значение последовательности равно сумме двух предыдущих чисел. Итак, последовательность будет выглядеть таким образом: 0, 1, 1, 2, 3, 5, 8, 13, 21..., и сразу становится ясно, что генерация такой последовательности – идеальная работа для компьютера. Но есть загвоздка: эти числа очень быстро возрастают. У последовательности Фибоначчи много интересных свойств, и существуют разнообразные, более эффективные алгоритмы генерации определённого числа. |
| - | Определяем границы | + | =====Определяем границы===== |
| - | <code> | + | **Листинг 1: Fibonacci.c** |
| + | <code c> | ||
| 01. #include <stdio.h> | 01. #include <stdio.h> | ||
| 02. | 02. | ||
| Строка 51: | Строка 52: | ||
| 28. return 0; | 28. return 0; | ||
| 29. } | 29. } | ||
| - | |||
| - | Листинг 1: Fibonacci.c | ||
| </code> | </code> | ||
| + | На Листинге 1 представлено простое приложение, в основном цикле которого (строки 11 – 29 ) определены три переменные: a, b и c, которые будут содержать предыдущий, текущий и следующий член последовательности Фибоначчи. В каждой итерации числа смещаются, и рассчитывается следующее значение. Правда, есть одна странная вещь: условие в цикле while на строке 21. Оно звучит как c>=b, но c равно b+a, и с точки зрения математики это выражение бессмысленно, так как всегда будет выполняться. | ||
| - | На Листинге 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). То же самое происходит при работе с числами со знаком, но в этом случае переполнение сначала произойдёт в знаковом бите, и в итоге вы получите большое отрицательное значение. | Однако, это приложение работает не в математической утопии, а на компьютере. Это значит, в случае с 32-битными целыми числами без знака (unsigned integer), если прибавить к 0xffffffff единицу, в результате получится 0x0. Это говорит о том, что произошло переполнение разрядной сетки, и новое значение выходит за пределы 32 бит (0x100000000), поэтому результат вычисляется только по 32-м младшим битам (0x100000000&0xffffffff=0x0). Другими словами, произошёл циклический возврат (wrap). То же самое происходит при работе с числами со знаком, но в этом случае переполнение сначала произойдёт в знаковом бите, и в итоге вы получите большое отрицательное значение. | ||
| В строках 3 и 4 определены fibo_type и FIBO_FORMAT. Они используются для того, чтобы легко адаптировать приложение к другим типам данных. Таким образом можно наблюдать, где проходит граница при использовании величины со знаком (signed), или типа short. В случае unsigned long long, приложение может вычислить 94 числа Фибоначчи. | В строках 3 и 4 определены fibo_type и FIBO_FORMAT. Они используются для того, чтобы легко адаптировать приложение к другим типам данных. Таким образом можно наблюдать, где проходит граница при использовании величины со знаком (signed), или типа short. В случае unsigned long long, приложение может вычислить 94 числа Фибоначчи. | ||
| - | |||
| Можно также поэкспериментировать с числами с плавающей точкой, у которых диапазон значений шире. Но учтите, что при этом теряется точность. Это, возможно, даже более опасно, так как число выглядит корректным, но на самом деле это не так (если сомневаетесь – спросите тех, кто писал программы для ракеты Ariane 5). | Можно также поэкспериментировать с числами с плавающей точкой, у которых диапазон значений шире. Но учтите, что при этом теряется точность. Это, возможно, даже более опасно, так как число выглядит корректным, но на самом деле это не так (если сомневаетесь – спросите тех, кто писал программы для ракеты Ariane 5). | ||
| Строка 66: | Строка 64: | ||
| Вывод такой: это хорошо, что множество целых чисел бесконечно. Но было бы ещё лучше, если бы мы могли действительно использовать их все. | Вывод такой: это хорошо, что множество целых чисел бесконечно. Но было бы ещё лучше, если бы мы могли действительно использовать их все. | ||
| - | Рушим границы | + | =====Рушим границы===== |
| Ну, в действительности мы можем использовать все, но придётся за это заплатить производительностью. Сложение двух 32-битных величин – чертовски быстрая процедура, фактически, это делается простой командой ассемблера, но опять же, мы натыкаемся на 32-битный предел (предел может различаться в зависимости от типа процессора, но присутствует в любом случае). Но есть обходной путь. Вместо целых чисел мы могли бы использовать массив и реализовать операцию сложения самостоятельно, просто сделав так, как нас учили в начальной школе: добавлять по одной цифре, считать результат и т.д. Для сложения и вычитания это делается легко, но при умножении, делении и вычислении квадратных корней всё усложняется, и кажется маловероятным, что можно реализовать эти операции эффективно. Сложение двух цифр занимает столько же времени, как сложение двух целых чисел, поэтому сложение двух четырёхзначных чисел вручную займёт в четыре раза больше времени, чем в варианте с типом integer. | Ну, в действительности мы можем использовать все, но придётся за это заплатить производительностью. Сложение двух 32-битных величин – чертовски быстрая процедура, фактически, это делается простой командой ассемблера, но опять же, мы натыкаемся на 32-битный предел (предел может различаться в зависимости от типа процессора, но присутствует в любом случае). Но есть обходной путь. Вместо целых чисел мы могли бы использовать массив и реализовать операцию сложения самостоятельно, просто сделав так, как нас учили в начальной школе: добавлять по одной цифре, считать результат и т.д. Для сложения и вычитания это делается легко, но при умножении, делении и вычислении квадратных корней всё усложняется, и кажется маловероятным, что можно реализовать эти операции эффективно. Сложение двух цифр занимает столько же времени, как сложение двух целых чисел, поэтому сложение двух четырёхзначных чисел вручную займёт в четыре раза больше времени, чем в варианте с типом integer. | ||
| Строка 72: | Строка 70: | ||
| К счастью, мы живём в открытом мире (по крайней мере частично), и нет необходимости заново изобретать велосипед. Существует библиотека GMP (GNU Multiple Precision Arithmetic Library, http://gmplib.org), в которой есть эта и множество других возможностей. Всё, что нам нужно сделать – ввести в консоли sudo apt-get install libgmp3-dev. У этой библиотеки обширный функционал, но в этой статье мы лишь пройдёмся по поверхности. Я настоятельно рекомендую читателю взглянуть на документацию по API на http://gmplib.org/manual/, чтобы ознакомиться с возможностями этой библиотеки. | К счастью, мы живём в открытом мире (по крайней мере частично), и нет необходимости заново изобретать велосипед. Существует библиотека GMP (GNU Multiple Precision Arithmetic Library, http://gmplib.org), в которой есть эта и множество других возможностей. Всё, что нам нужно сделать – ввести в консоли sudo apt-get install libgmp3-dev. У этой библиотеки обширный функционал, но в этой статье мы лишь пройдёмся по поверхности. Я настоятельно рекомендую читателю взглянуть на документацию по API на http://gmplib.org/manual/, чтобы ознакомиться с возможностями этой библиотеки. | ||
| - | На Листинге 2. | + | **Листинг 2: Fibonacci2.c** |
| - | + | <code c> | |
| - | <code> | + | |
| 01. #include <stdio.h> | 01. #include <stdio.h> | ||
| 02. #include <stdlib.h> | 02. #include <stdlib.h> | ||
| Строка 106: | Строка 103: | ||
| 30. } | 30. } | ||
| - | Листинг 2: Fibonacci2.c | + | |
| </code> | </code> | ||
| Строка 117: | Строка 114: | ||
| Итак, это приложение (круче которого теперь только Матрица) даёт нам действительно безграничное (ну, на самом деле num переполнится после 2^31 цифр Фибоначчи) количество чисел Фибоначчи. | Итак, это приложение (круче которого теперь только Матрица) даёт нам действительно безграничное (ну, на самом деле num переполнится после 2^31 цифр Фибоначчи) количество чисел Фибоначчи. | ||
| - | Упражнения | + | =====Упражнения===== |
| - | • Попробуйте запустить приложение для различных типов в Fibonacci.c: char со знаком (signed) и без (unsigned), short, long и long long, и попробуйте определить их границы. | + | * Попробуйте запустить приложение для различных типов в Fibonacci.c: char со знаком (signed) и без (unsigned), short, long и long long, и попробуйте определить их границы. |
| + | * Попробуйте то же с типами чисел с плавающей точкой в Fibonacci.c. Больше ли чисел получается? Они корректны? В какой момент появляется ошибка? | ||
| + | * Пройдитесь по документации к GMP и ознакомьтесь с возможностями библиотеки. | ||
| + | * Прочитайте руководство по GMP и найдите раздел о mpz_get_str. Теперь перепишите Fibonacci2 так, чтобы память не выделялась и освобождалась каждый раз, а чтобы она перераспределялась, когда возникает необходимость в дополнительных разрядах. | ||
| - | • Попробуйте то же с типами чисел с плавающей точкой в Fibonacci.c. Больше ли чисел получается? Они корректны? В какой момент появляется ошибка? | ||
| - | • Пройдитесь по документации к GMP и ознакомьтесь с возможностями библиотеки. | ||
| - | • Прочитайте руководство по GMP и найдите раздел о mpz_get_str. Теперь перепишите Fibonacci2 так, чтобы память не выделялась и освобождалась каждый раз, а чтобы она перераспределялась, когда возникает необходимость в дополнительных разрядах. | + | <note tip> **Eli De Brauwer** - фанатик Linux из Бельгии. Когда он не со своей семьёй, он любит играть с технологиями и проводит дни ожидая, когда Blizzard наконец выпустит Diablo III.</note> |
| + | |||
| + | ---- | ||
| + | <style center> | ||
| + | - [[..:17:программа_на_си_ч1|Программа на Си. Часть 1]] | ||
| + | - [[..:18:программа_на_си_ч2|Программа на Си. Часть 2]] | ||
| + | - [[..:19:программа_на_си_ч3|Программа на Си. Часть 3]] | ||
| + | - [[..:20:программа_на_си_ч4|Программа на Си. Часть 4]] | ||
| + | - [[..:21:программа_на_си_ч5|Программа на Си. Часть 5]] | ||
| + | - [[..:22:программа_на_си_ч6|Программа на Си. Часть 6]] | ||
| + | - [[..:23:программа_на_си_ч7|Программа на Си. Часть 7]] | ||
| + | - [[..:24:программа_на_си_ч8|Программа на Си. Часть 8]] | ||
| + | |||
| + | ---- | ||
| + | |||
| + | //[[..:24|К содержанию номера]]// | ||
| + | |||
| + | //[[:fullcircle|К архиву журналов]]// | ||
| + | </style> | ||
| + | |||
| + | {{tag>howto Си Программирование Full_Circle}} | ||
