Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления
- Название:Том 15. От абака к цифровой революции. Алгоритмы и вычисления
- Автор:
- Жанр:
- Издательство:«Де Агостини»
- Год:2014
- ISBN:978-5-9774-0710-6
- Рейтинг:
- Избранное:Добавить в избранное
-
Отзывы:
-
Ваша оценка:
Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления краткое содержание
Алгоритмы управляют работой окружающих нас электронных устройств, благодаря которым становится возможным существование нашего удивительного цифрового мира.
По сути, компьютерная программа — не более чем алгоритм, составленный на языке, понятном компьютеру. Однако царствование алгоритмов в вычислительной технике — лишь краткий эпизод долгой и интересной истории, которая началась вместе с зарождением вычислений. В этой книге рассказывается история алгоритмов, а также описываются важнейшие особенности вычислений и вычислительной техники, начиная от первых счетных палочек и заканчивая компьютерами, без которых невозможно представить современный мир.
Том 15. От абака к цифровой революции. Алгоритмы и вычисления - читать онлайн бесплатно полную версию (весь текст целиком)
Интервал:
Закладка:
До появления компьютеров наилучших результатов добился англичанин Д. Фергюсон, который исключительно с помощью калькулятора вычислил свыше тысячи знаков: 620 знаков в 1946 году, 808 — в 1947-м, 1120 — в 1949-м (совместно с Джоном Ренчем).
Джон Ренч в том же году впервые в истории вычислил приближенное значение τ с помощью компьютера. По инициативе Джона фон Неймана расчеты производились на компьютере ENIAC. Спустя 70 часов вычислений было получено 2037 знаков Я. Пять лет спустя, в 1954 году, Николсон и Джинель превзошли этот результат, вычислив 3092 знака Я всего за 13 минут с помощью IBM NORC — самого мощного компьютера того времени. В 1959 году, опять же спустя пять лет, на IBM 704, первом массовом компьютере, где была реализована арифметика с плавающей запятой, за 4,3 часа было вычислено 16167 знаков. Расчеты произвел Франсуа Женюи в Париже. Вскоре пал рубеж в 100000 знаков: его преодолели Дэниел Шенке и Джон Ренч в 1961 году с помощью нового компьютера IBM 7090, в котором вместо электронных ламп использовались транзисторы, что позволило в шесть раз увеличить скорость расчетов по сравнению с его предшественниками. 100265 знаков были вычислены за 8,7 часа.
Джин Гийу в 1966 году установил новый рекорд, вычислив 250 000 знаков за 41 час 55 минут. Он же в 1967 году получил 500 000 знаков за 28 часов 10 минут.
Впечатляющий показатель в миллион знаков был достигнут усилиями Джина Гийу и Мартина Буйе в 1973 году. Они использовали компьютер CDC 7600 компании Control Data Corporation — конкурента IBM на рынке компьютеров второго поколения (в них использовались транзисторы), которые выпускались в 1960-е. За 23 часа 18 минут было вычислено 1001250 знаков 71.
В 1980-е главную роль играли японцы Ясумаса Канада и Казунори Миёши: в 1981 году им удалось преодолеть отметку в 2 миллиона знаков за 137 часов, в 1982-м — 8 миллионов за 6 часов 52 минуты, в 1983-м — 16 миллионов менее чем за 30 часов, в 1987-м на японском компьютере NEC SX-2 им удалось вычислить 100 миллионов знаков за 35 часов 15 минут. В 1989 году Григорий Чудновский, который считается одним из лучших среди ныне живущих математиков, и его брат Давид вычислили свыше миллиарда знаков 71 на компьютере IBM 3090.
Отметку в триллион знаков преодолел Ясумаса Канада и возглавляемая им группа, которая использовала компьютер HITACHI SR8000/MPP. Этот рекорд был установлен в Токио в декабре 2002 года. Для вычисления 1241100000000 знаков потребовалось 600 часов, то есть 25 суток вычислений, что соответствует скорости 574583 знака в секунду. В апреле 2009 года японец Дайсуке Такахаши из университета Цукуба вычислил более 2 триллионов знаков за 29,09 часа. Нынешний рекорд, который составляет почти 2,7 триллиона знаков [2] Данные на 31.12.2009 года. 19 октября 2011 года Александр Йи и Сигэру Кондо вычислили 10 триллионов знаков после запятой.
, удерживает французский программист Фабрис Беллар, который использовал обычный персональный компьютер под управлением операционной системы Linux. На выполнение расчетов ему потребовался 131 день.
Большинство этих результатов были получены благодаря открытиям удивительного и загадочного индийского математика Сринивасы Рамануджана(1887–1920). Один из полученных им рядов, опубликованный в 1914 году, дает 8 новых знаков π на каждый член ряда. Этот ряд записывается так:

На основе результатов, полученных Рамануджаном, были найдены ряды, которые сходятся еще быстрее и позволяют получить несколько верных знаков числа π для каждого члена ряда. Братья Джонатан и Питер Борвейн, канадцы шотландского происхождения, открыли ряд, каждый член которого дает 31 новый знак π .
Остальные результаты, среди которых выделяются достижения Ясумасы Канады, получены с помощью формулы Карла Фридриха Гаусса(1777–1855) , в которой устанавливается связь между числом π и средним арифметико-геометрическим. Формула Гаусса записывается следующим образом:

В этой формуле MAG( а, Ь ) — это среднее арифметико-геометрическое чисел а и Ь .
Равенства, недавно полученные Дэвидом Бэйли, Питером Борвейном и Саймоном Плуффом, представляют собой наиболее интересные выражения, связанные с числом π . В 1997 году эти исследователи опубликовали ряд формул, которые позволяют вычислить любой знак двоичной записи π без необходимости вычислять предшествующие ему знаки. Эти же формулы, очевидно, можно использовать для расчета знаков π в любой системе счисления по основанию, кратному двум, в частности в шестнадцатеричной системе счисления. Авторы подтвердили корректность своего метода, вычислив миллионный, 10-миллионный, 100-миллионный, миллиардный и 10-миллиардный знаки шестнадцатеричной записи π . В результате были получены следующие шестнадцатеричные числа.
* * *
СРЕДНЕЕ АРИФМЕТИКО-ГЕОМЕТРИЧЕСКОЕ
Среднее арифметико-геометрическое определяется на основе двух сходящихся рядов: один из них образован средними арифметическими, другой — средними геометрическими. Напомним выражения для вычисления обеих средних величин:
МА( а, Ь ) = ( a + b )/2
MG( a, b ) = √( a·b) .
Первые члены рядов mаи mg определяются так: ma 1 = МА( a, b ), mg 1 = MG( а, b ). Члены ряда в общем виде определяются так:
ma n+1 = МА( ma n, mg n),
mg n+1 = МG( ma n, mg n)
Эти два ряда сходятся к одному и тому же значению — среднему арифметико-геометрическому MAG( а, Ь ).
* * *

Одна из формул, предложенных Бэйли, Борвейном и Плуффом записывается так:

* * *
СИСТЕМЫ СЧИСЛЕНИЯ
В десятичной системе счисления, как следует из ее названия, используется десять различных цифр. Они записываются в привычном нам виде: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9.
В двоичной системе счисления используются всего две цифры — 0 и 1. В шестнадцатеричной системе используется 16 цифр. Чаще всего они записываются так: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F. Символ А соответствует значению 10 в десятичной системе счисления, В — 11, С — 12, D — 13, Е — 14, F — 15.
Двоичная и шестнадцатеричная система тесно связаны между собой, так как 16 кратно 2 и перейти от одной из этих систем к другой очень просто.
Чтобы перевести число из двоичной системы в шестнадцатеричную, нужно сгруппировать биты по 4, и каждой группе будет соответствовать одна шестнадцатеричная цифра. Чтобы перевести число из шестнадцатеричной системы в двоичную, нужно заменить каждую из шестнадцатеричных цифр на четыре двоичных цифры по следующим правилам:
Читать дальшеИнтервал:
Закладка: