Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

• Название: Том 15. От абака к цифровой революции. Алгоритмы и вычисления
• Автор: Бизенц Торра
• Издательство: «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0710-6

Алгоритмы управляют работой окружающих нас электронных устройств, благодаря которым становится возможным существование нашего удивительного цифрового мира.

По сути, компьютерная программа — не более чем алгоритм, составленный на языке, понятном компьютеру. Однако царствование алгоритмов в вычислительной технике — лишь краткий эпизод долгой и интересной истории, которая началась вместе с зарождением вычислений. В этой книге рассказывается история алгоритмов, а также описываются важнейшие особенности вычислений и вычислительной техники, начиная от первых счетных палочек и заканчивая компьютерами, без которых невозможно представить современный мир.

---

С целью решить проблемы ENIAC были начаты работы над новым компьютером — EDVAC. Эккерт, Мокли и фон Нейман очень подробно проанализировали, как должно производиться программирование компьютера, и пришли к выводу, что оптимальным вариантом будет хранение программы в памяти подобно тому, как в ней сохранялись числа. Трудно поверить, что в прошлом компьютерные программы и аппаратное обеспечение не были разделены. Результатом этой идеи стало рождение языков программирования и программирования как отдельной дисциплины.

Создание EDVAC стало значимым событием в истории информатики.

Работы над EDVAC были закончены в 1949 году в Институте Мура Пенсильванского университета. К тому времени Эккерт и Мокли уже не участвовали в проекте, так как покинули его в 1946 году. В EDVAC использовалось 6000 ламп и 12 000 диодов, он весил 7850 килограммов и занимал площадь в 45,5 квадратных метров. Для работы ему требовалось 56 кВт электроэнергии. Он был намного легче ENIAC, учитывая масштаб этих цифр. Он также был быстрее своего предшественника: сложение выполнялось за 864 микросекунды, умножение — за 2900 микросекунд.

В это же время на «Первый черновик» фон Неймана обратили внимание в Великобритании. Морис Уилкс из Кембриджского университета в том же 1949 году сконструировал EDSAC (Electronic Delay Storage Automatic Calculator — автоматический вычислитель на электронных линиях задержки). Это была первая электронная вычислительная машина с набором внутренних команд. Однако первым компьютером с набором внутренних программ стал SSEM. Его память состояла из 512 ячеек по 17 бит каждая. Первая компьютерная игра в мире — крестики-нолики под названием ОХО — была создана на EDSAC. На основе этой вычислительной машины был создан первый компьютер, применявшийся в коммерческих целях — LEO I.

Вырезка из британской газеты, в которой рассказывается о создании EDSAC.

Оставив Пенсильванский университет, Эккерт и Мокли основали компанию Eckert-Mauchly Computer Corporation для постройки UNIVAC — акроним от Universal Automatic Computer, универсальный автоматический компьютер, где слово «универсальный» означало, что компьютер будет способен решать научные, технические, экономические и другие задачи.

Первой организацией, которая приобрела UNIVAC Эккерта и Мокли, стало Бюро переписи населения США. По завершении работ над компьютером в 1951 году компания Эккерта и Мокли была поглощена более крупной компанией Remington Rand. Второй компьютер был куплен Пентагоном в 1952 году. Эти вычислительные машины считаются первыми коммерческими компьютерами в мире.

В большинстве случаев они использовались для обработки данных, а не для физических или математических расчетов. Бюро переписи населения США использовало UNIVAC для обработки результатов переписи и формирования классификаций.

Пульт управления UNIVAC I, хранящийся в Музее науки Бостона.

Основным преимуществом UNIVAC для многих пользователей была не только скорость вычислений, но и использование лент вместо перфокарт для чтения и записи информации. Перфокарты требовали вмешательства оператора, и их замена на ленту означала увеличение степени автоматизации расчетов. Отбор данных производился самой машиной. UNIVAC производил сложение двух чисел за 0,5 микросекунды.

До выхода UNIVAC на рынок компания IBM уделяла основное внимание выпуску калькуляторов, работавших на перфокартах. Однако увидев интерес к новому компьютеру, IBM начала развивать проекты в этом направлении. Первой вычислительной машиной подобного типа стал IBM 701, который был схож с UNIVAC и назывался «электронной машиной для обработки данных». Фон Нейман, который в то время работал над созданием своего компьютера в Принстоне, участвовал в этом проекте в качестве консультанта. Работы над IBM 701 были завершены в 1952 году, а в начале 1953-го он был отправлен в лабораторию Лос-Аламоса, где велась разработка ядерного оружия.

Число π в XX веке

Развитие аппаратного обеспечения в течение XX века позволило вычислить τ с более высокой точностью. В настоящее время известно более триллиона знаков этого числа. Последний результат содержит почти 2,7 триллиона знаков после запятой, то есть 2,7·1012 знаков[1].

До появления компьютеров наилучших результатов добился англичанин Д. Фергюсон, который исключительно с помощью калькулятора вычислил свыше тысячи знаков: 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], удерживает французский программист Фабрис Беллар, который использовал обычный персональный компьютер под управлением операционной системы Linux. На выполнение расчетов ему потребовался 131 день.

Большинство этих результатов были получены благодаря открытиям удивительного и загадочного индийского математика Сринивасы Рамануджана (1887–1920). Один из полученных им рядов, опубликованный в 1914 году, дает 8 новых знаков π на каждый член ряда. Этот ряд записывается так:

На основе результатов, полученных Рамануджаном, были найдены ряды, которые сходятся еще быстрее и позволяют получить несколько верных знаков числа π для каждого члена ряда. Братья Джонатан и Питер Борвейн, канадцы шотландского происхождения, открыли ряд, каждый член которого дает 31 новый знак π.

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

В этой формуле MAG (а, Ь) — это среднее арифметико-геометрическое чисел а и Ь.

Равенства, недавно полученные Дэвидом Бэйли, Питером Борвейном и Саймоном Плуффом, представляют собой наиболее интересные выражения, связанные с числом π. В 1997 году эти исследователи опубликовали ряд формул, которые позволяют вычислить любой знак двоичной записи π без необходимости вычислять предшествующие ему знаки. Эти же формулы, очевидно, можно использовать для расчета знаков π в любой системе счисления по основанию, кратному двум, в частности в шестнадцатеричной системе счисления. Авторы подтвердили корректность своего метода, вычислив миллионный, 10-миллионный, 100-миллионный, миллиардный и 10-миллиардный знаки шестнадцатеричной записи π. В результате были получены следующие шестнадцатеричные числа.