LINEBURG


<< Пред. стр.

страница 2
(всего 4)

ОГЛАВЛЕНИЕ

След. стр. >>

=1 + + + …, (1)
учный характер. Если, например, рассчитать длину экватора сферы, 4 35 79 11
вмещающей известную нам часть Вселенной (радиус сферы 5 1026 м),
используя при этом найденное Лудольфом значение ?, то погрешность названный в честь открывшего его в 1673 году немецкого матема-
не превысит одной миллионной доли миллиметра! тика Готфрида Вильгельма Лейбница (1646—1716) рядом Лейбница.
Многоточие, поставленное справа от знака «+» в формуле (1), следу-
*) Точного значения ?.
ет понимать так. Чем больше слагаемых взять в правой части этого
**) 805 306 368 = 3 228 .
равенства, тем меньше их алгебраическая сумма будет отличаться
***) 1 073 741 824 = 230 .
10 11
? трических тождеств:
от числа . Это даёт принципиальную возможность вычислять ? со
4
x+y
сколь угодно большой точностью. arctg x + arctg y = arctg (xy 1),
1 xy
Ряд Лейбница является частным случаем более общего ряда, от-
xy
крытого английским математиком Джеймсом Грегори (1638—1675) arctg x arctg y = arctg (xy 1),
1 + xy
в 1670 году:
2x
2 arctg x = arctg (x 1).
x3 x5 x7 x9 x11
arctg x = x + + +… (2) 1 x2
3 5 7 9 11
1 1
(здесь x 1). Раскладывая каждый из арктангенсов arctg , arctg в ряд
5 239
Грегори не заметил, что этот ряд имеет отношение к числу ?. Ряд
Грегори, получим весьма удобное для вычислений выражение
Лейбница (1) получается из ряда Грегори (2) при x = 1.
1 1 1 1
?
Коль скоро появился удобный инструмент, вычислители не пре- =4 + +…
4 5 3
5 55 7 57
35
минули им воспользоваться. Ряд (1) не очень удобен для расчётов:
чтобы получить ? с двумя верными знаками после запятой, надо сло- 1 1 1 1
+ +… .
239 3
5 2395 7 2397
3 239
жить 50 членов ряда, а для трёх десятичных знаков понадобится более
3 Это разложение позволило Джону Мэчину вычислить 100 десятич-
300 действий. Если же в формуле (2) положить x = , то получится
3 ных знаков числа ?. Его результат был опубликован в 1706 году
ряд У. Джонсом в уже упоминавшейся работе «Обозрение достижений
3 1 1 1 1 1 математики», где впервые зарегистрировано использование буквы ?
?
= 1 + + +… (3)
6 3 9 45 189 729 2673 для обозначения отношения длины окружности к диаметру.
Упражнение 3. Приведённые формулы Л. Эйлера и Л. К. Шульца
с гораздо более быстрой сходимостью (обратите внимание, как бы-
позволяют сформулировать следующую гипотезу:
стро здесь увеличиваются знаменатели). Именно этим разложени-
ем (3) воспользовался Авраам Шарп (1651—1742) для вычисления 1 1 1 1 1
arctg 1 = arctg + arctg + arctg + arctg + arctg +…
в 1699 году рекордного количества точных десятичных знаков чи- 2 5 13 34 89
сла ? — 71 знак.
(в знаменателях дробей в правой части стоят числа Фибоначчи с
Следующая «хитрость», которой воспользовались вычислители,
нечётными номерами). Обоснуйте эту закономерность.
состояла в подборе комбинаций арктангенсов, каждый из которых
Успехи Шенкса и Мэчина окрылили других вычислителей, и они
выражается при помощи ряда, сходящегося быстрее, чем ряд Лейб-
с азартом присоединились к удивительному соревнованию, начатому
ница (1):
математиками эпохи вписанных и описанных многоугольников.
Де Ланьи (1660—1734), используя метод Шарпа, в 1719 году
1 1
arctg 1 = 4 arctg arctg (Джон Мэчин),
вычислил 127 точных десятичных знаков числа ?. Вскоре Леонард
5 239
Эйлер другим способом проверил результат Ланьи и обнаружил
1 1
arctg 1 = arctg + arctg (Леонард Эйлер),
ошибку в 113-м знаке. В 1794 году Вега указал значение ? с точно-
2 3
стью до 140 десятичных знаков, из которых точными оказались 136.
1 1 1
arctg 1 = 4 arctg arctg + arctg (Джеймс Стирлинг, В 1841 году Уильям Резерфорд сообщает 208 десятичных знаков. Его
5 70 99
Томас Симпсон, результат перепроверил талантливый гамбургский вычислитель Ио-
Уильям Резерфорд), ганн Мартин Захария Дазе (1824—1861). Он показал, что Резерфорд
1 1 1 ошибся в 153-м знаке. В 1844 году Дазе довёл точность до 205 зна-
arctg 1 = arctg + arctg + arctg (Л. К. Шульц).
2 5 8 ков, из которых 200 были вычислены верно. В 1847 году Томас
Проверить эти формулы можно исходя из известных тригономе- Клаузен продвинулся до 250 знаков, из которых 248 были точны.
12 13
В 1853 году Резерфорд увеличил своё достижение до 440 десятичных кордсменов стали делить между собой машины. У кого тактовая
знаков. Рекорд того времени установил Уильям Шенкс — 530 знаков частота процессора больше, тот и победил.
(из них 527 верных). В последующем Шенкс упорно работал над Но не тут-то было! Оказалось, что человека — виновника всей
вычислениями новых знаков, доведя их количество до 707. этой кутерьмы с вычислениями числа ? — рано списывать со счетов.
Он стал придумывать не просто схемы умножения многозначных чи-
сел, а схемы с в е р х б ы с т р о г о умножения, не просто алгоритмы
НОВАЯ ЭРА
вычисления числа ?, а с в е р х э ф ф е к т и в н ы е алгоритмы…
Впечатляющие результаты Уильяма Шенкса возглавляли табли-
цу рекордов вплоть до середины XX века. Вычисленные Шенксом Схемы «сверхбыстрого» умножения
707 десятичных знаков числа ? появились на страницах научно-по-
Способ умножения «в столбик», которым мы обычно пользуемся,
пулярных изданий. Архитекторы стали украшать ими свои сооруже-
с «точки зрения» современного компьютера довольно расточителен.
ния. Именно эти 707 цифр были размещены в виде гипсового фри-
Чтобы перемножить таким способом два натуральных n-разрядных
за под потолком «цифирной палаты» в Доме занимательной науки
числа, нужно произвести n2 попарных умножений цифр и ещё некото-
на Фонтанке (в Ленинграде), организованном по инициативе Якова
рое количество сложений. Объём этой вычислительной работы можно
Исидоровича Перельмана в 1934 году. Этими же 707 цифрами Уильям
существенно уменьшить, если рационально распорядиться промежу-
Голени в 1937 году украсил купол циклической галереи парижского
точными вычислениями.
Дворца Открытий.
На одно из «рационализаторских» усовершенствований подобно-
Двадцатый век вошёл в историю человеческой цивилизации не
го рода обратил внимание отечественный математик Анатолий Алек-
только своими разрушительными войнами. Он ознаменовался значи-
сандрович Карацуба в 1962 году (см., например, [5]). Предположим,
тельными достижениями человеческого духа, в частности, компью-
что каждый из сомножителей x и y имеет по 2n цифр. Разобьём их на
терной революцией. Уже первые проверки на появившихся в 1945 го-
два блока по n цифр:
ду электронно-вычислительных машинах показали, что Уильям
x = 10n x1 + x0 , y = 10n y1 + y0 .
Шенкс в своих расчётах ошибся, начиная с 528 знака, так что весь
последующий «хвост» из 180 знаков оказался неверным. Это дало по- Здесь x1 , x0 , y1 , y0 — n-значные числа. Воспользовавшись тождеством
вод английскому математику Гарольду Коксетеру (р. 1907) с горечью
(x1 x0 )(y0 y1 ) = x1 y1 x0 y0 + x1 y0 + x0 y1 ,
констатировать: «Нельзя без грусти думать о том, что вычисления, на
которые бедный Шенкс потратил значительную часть своей жизни, произведение xy можно записать так:
современная ЭВМ может воспроизвести (без его роковой ошибки) xy = (10n x1 + x0 )(10n y1 + y0 ) =
всего за несколько секунд просто для „разминки“» ([4], с. 379).
= (102n + 10n )x1 y1 + 10n (x1 y1 ) + (10n + 1)x0 y0 .
x0 )(y0
С появлением компьютеров темпы погони за точными десятич-
ными знаками числа ? резко ускорились. Таким образом, задача умножения 2n-разрядных чисел свелась к
В июне 1949 года Джон фон Нейман (1903—1957) и его сотруд- трём операциям для n-разрядных чисел x1 y1 , (x1 x0 )(y0 y1 ), x0 y0 и
ещё к операциям сложения и сдвига. Вместо 4n2 операций поразряд-
ники вычислили 2037 знаков на одной из первых вычислительных
ного умножения обычным способом здесь требуется всего 3n2 опера-
машин ENIAC. Рубеж в 10 000 знаков был достигнут в 1958 году
Ф. Женюи с помощью компьютера IBM 704. Сто тысяч знаков ? вычи- ций. Выигрыш, казалось бы, небольшой, но ведь и возникшие здесь
слили в 1961 году Дэниэл Шенкс (однофамилец Уильяма Шенкса) и n-значные числа также можно перемножать подобным образом, их
Джон Ренч с помощью компьютера IBM 7090. В 1973 году Жан Гийу составные части — тоже, и т. д. По мере увеличения n экономия вы-
и М. Буйе преодолели отметку в 1 000 000 знаков, что заняло меньше числений может оказаться существенной.
одного дня работы компьютера CDC-7600. Современные алгоритмы «сверхбыстрого» умножения использу-
Казалось бы, эра компьютеров окончательно и безвозвратно ют ещё более изощрённую технику вычислений. Например, алгоритм
устранила человека с арены соревнований. Лавры победителей-ре- Шёнхаге—Штрассена (1971) умножения целых чисел использует
14 15
интерполяцию полиномов и так называемое «быстрое преобразование a2 , …, вычисляя их по формуле
Фурье». Объём вычислений по этому алгоритму двух целых n-разряд-
22n+3 yn+1 (1 + yn+1 + y2 ),
an+1 = (1 + yn+1 )4 an n = 0, 1, 2, …
ных чисел по сравнению с методом умножения «в столбик» умень- n+1

n 1
шается в раз. Например, поиск произведения двух Оказывается, по мере увеличения номера шага n величина очень
log2 n log2 log2 n an
быстро приближается к ?, а именно, имеет место оценка
216 -разрядных сомножителей ускоряется более чем в тысячу (210 ) раз
по сравнению с обычным способом умножения. Довольно существен-
1 22n+1 ? .
22n+5 e
0 an
ная экономия для электронных вычислителей точных знаков числа ?! ?

1
Так, уже a4 даёт 694 верных знаков числа .
«Сверхэффективный» алгоритм ?
Джонатана и Питера Борвейнов У истоков открытия этого алгоритма лежали исследования в
области так называемых эллиптических интегралов и тета-функ-
Канадские математики Джонатан и Питер Борвейны в 1987 году ций — высших разделов современной математики [7]. Авторы этого
нашли удивительный ряд: поразительного алгоритма также утверждают, что им помогли
некоторые идеи гениального индийского математика Сринивазы
( 1)n (6n)!
1
= 12 Рамануджана (1887—1920).
3
? 3n+
n=0 2
(n!)3 (3n)! (5280(236674 + 30303 61))
Продолжение «марафона»
(212 175 710 912 61 + 1 657 145 277 365 +
Удивительный «марафон», начатый с вычисления Архимедом
+ n(13 773 980 892 672 61 + 107 578 229 802 750)) ,
трёх точных знаков числа ?, сегодня так же далёк от завершения,
как и две тысячи лет назад.
По алгоритму Джонатана и Питера Борвейнов в январе 1986 го-
где n! = 1 2 3 … n, а 0! = 1.
да Дэвид Х. Бейли получил 29 360 000 десятичных знаков ? на су-
Последовательность стоящих под знаком суммы слагаемых при
перкомпьютере Cray-2, а в 1987 году Я. Канада и его сотрудники —
n = 0, 1, 2, … добавляет около 25 точных цифр числа ? с каждым
134 217 000 знаков на суперкомпьютере NEC SX-2. Результат Дэвида
новым членом. Первый член (соответствующий n = 0) даёт число, со-
и Грегори Чудновски из Колумбийского университета в Нью-Йорке,
впадающее с ? в 24 десятичных знаках [6].
вычисливших в 1989 году 1 011 196 691 знак числа ?, попал даже
Джонатан и Питер Борвейны предложили также алгоритм рас-
в книгу рекордов Гиннесса. Для своих расчётов они использовали
чёта десятичных знаков числа ?, имеющий фантастическую эффек-
суперкомпьютер Cray-2 и сеть компьютеров IBM-3090. К октябрю
тивность: каждый новый шаг выполнения этого алгоритма уточняет
1995 года сотрудниками Токийского университета Ясумасой Кана-
количество верных цифр в разложении числа ? более чем вчетверо!
дой и Дайсуке Такахаши было вычислено свыше 6 миллиардов цифр.
[6, 7]. Вот этот удивительный алгоритм.
Они же в 1999 году на компьютере HITACHI SR 8000 вычислили
Вначале положим y0 = 2 1, a0 = 6 4 2, а затем каждое новое
206 158 430 000 цифр числа ? [8].
значение yn+1 будем находить, отправляясь от предыдущего значения
В конце прошлого столетия посетители сайта [9] встречали объ-
по формуле
явление, приглашающее их принять участие в глобальном проекте
4
y4
1 1 «Pi-Hex». Любой житель Земли, подключив свой компьютер к сети
n
yn+1 = , n = 0, 1, 2, …
Интернет, мог стать участником коллективных вычислений отдель-
4
1 + y4
1+ n
ных цифр двоичной записи числа ?. Координатором этого глобально-
Похожим образом будем находить члены последовательности a0 , a1 , го проекта выступил студент университета Симона Фрезера (США)
16 17
Колин Персивал. В проекте приняло участие около 2000 доброволь- опишет некоторую непрерывную линию, начинающуюся внутри S,
цев. Вычисления на каждом отдельном компьютере в глобальной се- а заканчивающуюся снаружи S в такой точке O1 , что A1 O1 = AO. Сле-
ти проводились в так называемом «фоновом» режиме, когда участ- довательно, найдётся такое положение BC этого вектора, при кото-
вующий в совместных работах компьютер не занимался решением ром и его начало B и его конец C будут принадлежать окружности S.
каких-то своих собственных задач. Объединённая общим проектом Так как четырёхугольники OABC и OA1 CB — параллелограммы, то
команда нашей планеты в 1998 и 1999 годах вычислила цифры, стоя- ?(A, B) = ?(O, C) = 1, ?(B, C) = ?(A, O) = 1, ?(A1 , C) = ?(O, B) = 1.
щие на 5000000000000 и на 40000000000000 местах двоичной дроби
Отсюда вытекает, что периметр центрально симметричного выпукло-
числа ?. Ими оказались нули [9].
го шестиугольника ABCA1 B1 C1 , вписанного в единичную окруж-
Остановится ли когда-либо удивительная погоня за исчезающи-
ность S, в геометрии Минковского—Банаха равен 6, поэтому пери-
ми в бесконечности знаками числа ?? По-видимому, этот вопрос мож-
метр 2? окружности S не меньше 6 и, значит, ? 3.
но переформулировать так: прекратит ли когда-либо своё существо-
вание человеческая цивилизация?
C Q
B
M1

ВСЕГДА ЛИ ? = 3,14…? N R
U
Условимся считать, что вдоль любой прямой евклидовой плоско- а) б)
U1
A O A1 O1 O
сти расстояния измеряются как обычно с той лишь разницей, что еди- P N1
S
ница длины различна для прямых разных направлений, но одинакова S
M
в)
для параллельных прямых. Это соглашение лежит в основе причуд- B1
C1 T
ливой геометрии, придуманной Германом Минковским (1864—1909) Рис. 5 Рис. 6 Рис. 7
и Стефаном Банахом (1892—1945).
Выберем фиксированную точку O плоскости и отложим от неё А теперь покажем, что ? 4.
во всех направлениях отрезки единичной длины. Мы получим не- Рассмотрим всевозможные вписанные в S параллелограммы с
которую замкнутую кривую — единичную окружность. Можно по- центром O и выберем среди них параллелограмм MNM1 N1 наиболь-
казать (см., например, [10], с. 465—469), что если точка O лежит шей возможной (евклидовой) площади. Опишем вокруг MNM1 N1
внутри единичной окружности, причём ограниченный этой окруж- параллелограмм PQRT, стороны которого параллельны диагоналям
ностью единичный круг является выпуклой фигурой, симметричной MM1 и NN1 . Если бы кривая S содержала некоторую точку U, рас-
относительно точки O, то все аксиомы расстояния ?(A, B) как функ- положенную дальше от прямой MM1 , чем прямая PQ (рис. 6), то па-
ции двух точек A и B в данной геометрии выполняются: раллелограмм MUM1 U1 имел бы большую площадь, чем MNM1 N1 ,
1) ?(A, B) = ?(B, A); что невозможно. Итак, кривая S целиком заключена внутри парал-
2) ?(A, B) 0, причём ?(A, B) = 0 лишь в том случае, если точка A лелограмма PQRT. С другой стороны, ?(P, Q) = ?(M, M1 ) = 2, ?(Q, R) =
совпадает с точкой B; = ?(M, M1 ) = 2, поэтому периметр параллелограмма PQRT в геоме-
3) ?(A, B) + ?(B, C) ?(A, C) для любых точек A, B, C. трии Минковского—Банаха равен 8, и, значит, 2? 8, т. е. ? 4.
В дальнейшем выполнение этих условий мы будем предполагать. Нетрудно убедиться, что число ? может принимать любые значе-
Обозначим длину единичной окружности 2?. Следуя [10], дока- ния в промежутке от 3 до 4. Для этого нужно взять в качестве единич-
жем, что в геометрии Минковского—Банаха 3 ? 4, причём число ной окружности S произвольную выпуклую центрально симметрич-
? может принимать любые значения в указанном промежутке. ную фигуру периметра 2?. Равенство ? = 3 выполняется, если S пред-
Пусть A — произвольная точка единичной окружности S с цен- ставляет собой, например, правильный шестиугольник (рис. 7, а),
тром O, A1 — диаметрально противоположная ей точка окружнос- ? = 4, если S представляет собой квадрат (рис. 7, б). А если S со-
ти S (рис. 5). При непрерывном обносе вектора AO вдоль кривой S, впадает с обыкновенной (евклидовой) окружностью (рис. 7, в), то
при котором начало A этого вектора описывает дугу AA1 , его конец O ? = 3,14159…
18 19
НЕРЕШЁННЫЕ ПРОБЛЕМЫ Тогда можно рассматривать новые цифры ? в этой новой системе и
исследовать выполнимость равенства
Сначала немного о том, что известно достоверно. К настояще-
му времени доказано, что число ? иррационально и трансцендентно. N(?, n) 1
lim =, (6)
n g
Свойство иррациональности числа ?, т. е. непредставимость его в ви- n
де отношения двух целых чисел, доказали Иоганн Ламберт (1728— аналогичного равенству (5) (здесь 0 ? g). Если бы вдруг оказалось,
1777) и Адриен Лежандр (1752—1833) в конце XVIII века. Свойство что для любой системы счисления (для любого g 2) и для любой циф-
трансцендентности означает, что число ? не является корнем никако- ры ? в этой системе последовательность цифр дробной части числа ?
го многочлена с целыми коэффициентами. Это свойство было доказа- удовлетворяла равенству (6), то в этом случае дробная часть числа ?
но немецким математиком Фердинандом Линдеманом (1852—1939) представляла бы собой слабо нормальное число.
в 1882 году. В настоящее время ведутся исследования по уточнению Наконец, чтобы ввести понятие нормального числа, рассмотрим
«тонкой структуры» числа ?. не одиночные цифры, а произвольные кортежи из цифр. Предста-
вим, что в k-местные сани для бобслея (k — любое натуральное число)
Нормально ли число ??
друг за другом садятся произвольные k цифр (?1 , ?2 , …, ?k ) системы
С точки зрения здравого смысла число ? вполне нормально, ничем счисления с основанием g, а затем эти сани проносятся вдоль после-
не хуже других чисел. Здесь мы познакомимся с определением нор- довательности
мальности числа, которое дал французский математик Эмиль Борель ?1 , ?2 , ?3 , …, ?n , …, (7)
в 1909 году. Грубо говоря, положительное число, меньшее единицы,
получающейся при разложении действительного числа ?, 0 1в
?
называется нормальным, если в его десятичной записи любая ком-
?3 ?n
?1 ?2
бинация цифр встречается одинаково часто. Это определение можно бесконечную дробь ? = + + +…+ + … в системе счисления с
gn
g 2 3
g g
распространить и на другие, недесятичные системы счисления. Вот
основанием g. Пусть N(?, n) — число совпадений набора (?1 , ?2 , …, ?k )
более точное определение.
с наборами вида (?i ,?i+1 ,…,?i+k 1 ), где i принимает значения от 1 до n.
Рассмотрим последовательность десятичных цифр дробной части
Тогда, если
числа ?:
N(?, n) 1
1, 4, 1, 5, 9, 2, 6, 5, … (4) lim = k,
n g
n
Зададимся какой-нибудь одной цифрой, например 9, и подсчитаем
то число ? называется нормальным.
количество появлений этой цифры среди первых n членов после-
В настоящее время неизвестно даже, является ли дробная часть
довательности (4). Обозначим это количество через N(9, n). Имеем:
числа ? слабо нормальной к основанию 10 или к какому-либо дру-
N(9, 1) = 0, N(9, 2) = 0, N(9, 3) = 0, N(9, 4) = 0, N(9, 5) = 1, N(9, 6) = 1
гому основанию. Иными словами, неизвестно, одинаково ли часто
и т. д. Если в среднем среди 10 цифр последовательности (4) оказыва-
встречаются все цифры в записи ?. Имеющиеся в настоящее время
ется одна девятка, то при больших значениях n естественно ожидать
данные вычислительного эксперимента свидетельствуют о том, что
N(9, n) 1
появления приближённого равенства , или, более точно, среди первых 200 000 000 000 десятичных знаков числа ? (не считая
10 10
целой части) все цифры встречаются примерно одинаково часто:
N(9, n) 1
lim = . (5)
n 10
n

Если бы аналогичное (5) равенство выполнялось не только для девят- Цифра Сколько раз появляется Цифра Сколько раз появляется
ки, но и для любой цифры 0, 1, …, 9, то в этом случае дробная часть
0 20 000 030 841 5 19 999 917 053
числа ?, по терминологии Э. Бореля, представляла бы собой веще- 1 19 999 914711 6 19 999 881 515
ственное число, слабо нормальное к основанию 10. Естественно, что 2 20 000 013 697 7 19 999 967 594
3 20 000 069 393 8 20 000 291 044
число ? можно представить в системе счисления с другим основани-
4 19 999 921 691 9 19 999 869 180
ем g, например, в двоичной (g = 2) или в троичной (g = 3) системе.
20 21
? = 3,1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1...




1/? = 0,3 1 8 3 0 9 8 8 6 1 8 3 7 9 0 6 7 1 5 3 7 7 6 7 5 2 6 7 4 5 0 2 8 7 2 4 0 6 8 9 1 9 2 9 1 4 8 0 9...
(данные лаборатории Токийского университета, руководимой Ясу-




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
масой Канадой и Дайсуке Такахаши [8]). Как видно, доля появлений




Начиная с разряда №




Начиная с разряда №
каждой десятичной цифры примерно равна одной десятой (погреш-




89 634 825 550




53 699 510 337
83 358 197 954


<< Пред. стр.

страница 2
(всего 4)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign