БУМАЖНЫй НОМЕР
![]() |
01.08.2001
Константин Кноп
Мы возобновляем рубрику «Досуги», ранее (в 1997-98 гг.) выходившую в «Компьютерре». В ней будут публиковаться статьи, посвященные разным вопросам на стыке математики и computer science. Как справедливо заметил кто-то из средневековых математиков, предмет этот сам по себе столь серьезен, что не следует упускать случая сделать его хотя бы немного занимательным. К вычислительной науке это относится не в меньшей, а, пожалуй, даже в большей степени. Пишите, о чем бы вы хотели почитать в этой рубрике, присылайте замечания к опубликованным материалам. А особенно мы будем рады открыть для себя и для читателей новых авторов.
Статья посвящена двум любопытнейшим конструкциям - последовательности дробей Фарея и бинарному дереву Штерна-Броко. О первой знают лишь немногие специалисты по теории чисел, а вот вторая в последнее время стала популярной и среди программистов, занимающихся векторной графикой. Тем не менее, конструкции эти очень похожи, а дерево Штерна-Броко имеет еще и самое непосредственное отношение к истории изготовления часовых механизмов. Впрочем, не буду забегать вперед…
Последовательностью Фарея порядка N называется список FN всех несократимых дробей между 0 и 1, знаменатели которых не превосходят N и которые расположены в порядке возрастания. Например, для N=6
Дерево Штерна-Броко - это обыкновенное двоичное (бинарное) дерево, вершины которого дополнительно занумерованы рациональными числами (см. рисунок).
Порядок нумерации такой: в верхнем левом углу помещается дробь 0/1, в верхнем правом углу ставится 1/0, а в каждую вершину дерева записывается медианта двух ближайших к ней сверху вершин (то есть величина (m1 + m2)/(n1 + n2), m1/n1 где - число, записанное у ближайшего предка слева, а m2/n2 - число у ближайшего предка справа).
Такая конструкция позволяет легко построить дерево и подметить много закономерностей, но в то же время порождает немало вопросов. Например, почему все дроби, «родившиеся» на этом дереве, являются несократимыми? Почему никакая дробь не встречается дважды? Наконец, почему каждая дробь вообще встречается? На все эти вопросы у математики есть четкие и простые ответы, которые я предлагаю читателям найти самостоятельно.
Связь между дробями на этом дереве и рядом дробей Фарея довольно проста: дроби Фарея FN получаются обрезанием всей правой половины дерева, а также удалением всех вершин, в которых записаны дроби со знаменателем, большим N. Из этой связи легко сделать вывод, что каждая дробь ряда Фарея равна медианте двух соседних с ней дробей.
Упражнение для крутых математиков
Докажите, что если m/n, m’/n’, m”/n” - три произвольные последовательные дроби Фарея FN, то
(Эти соотношения позволяют вычислить все элементы FN по порядку, начиная с 0/1 и 1/N.)
Но самое интересное не это. Дерево Штерна-Броко позволяет записывать рациональные числа в особой системе счисления, «цифрами» которой являются значки Л и П, обозначающие сдвиги вниз по дереву влево-вправо. Например (см. рис.) 5/8 = ЛПЛП, а 5/7 = ЛППЛ. Каждая положительная дробь (кроме 1/1) получает при этом единственное представление в виде конечной строки символов Л и П. Наконец, дроби 1/1 соответствует пустая строка.
Не углубляясь в вычислительную арифметику, дам ответы на два естественных вопроса:
Ответ на первый вопрос можно выписать в виде алгоритма.
Алгоритм 1
while m <> n do begin
if m<n
then begin writeln (“Л”); n := n-m; end
else begin writeln (“П”); m := m-n; end;
end;
Ответ на второй вопрос я запишу в виде фрагмента алгоритма, предполагая, что S - очередной символ строки, то есть S=Л или S=П. Работа алгоритма заканчивается, когда на входе оказывается «пустой символ».
Алгоритм 2
m:=0; n:=1; m1:=1; n1:=0;
repeat
read(S);
if S=”Л” then begin m1 := m+m1;
n1 : = n+n1; end;
if S=”П” then begin m := m+m1; n := n+n1;
end;
until S<>””;
m:=m+m1; n:=n+n1; writeln(m,n);
И, наконец, еще одно замечание: эта же система счисления способна записывать и иррациональные числа. Как и для обычных систем счисления, иррациональности в ней записываются бесконечными строками. Причем алгоритм получения такой строки для иррационального числа a практически совпадает с алгоритмом 1.
Алгоритм 1'
repeat
if a<1
then begin writeln (“Л”);
a := a/(1-a); end
else begin writeln (“П”); a := a-1; end;
until 0=1;
(Бесконечный цикл в явном виде демонстрирует бесконечность дроби…)
Упражнение для программистов
Придумайте способ сравнения двух чисел, основанный на их записи в системе счисления Штерна-Броко.
Забавно, что в такой системе счиcления многие «известные числа» имеют неожиданно красивые представления. На практике же используют рациональные приближения этих чисел, получающиеся из указанных ЛП-записей в результате применения алгоритма 2 к произвольному начальному куску. Оказывается, они являются наилучшими рациональными приближениями для указанных иррациональностей.
Именно об этом - вторая часть моего рассказа, за которую я должен быть благодарен прежде всего журналу American Scientist и постоянному ведущему его компьютерного раздела Брайену Хейесу (Brian Hayes). В статье Хейеса [1] описана почти детективная история погони за первоисточником - статьей Ахилла Броко [2], опубликованной во французском журнале для часовщиков еще в позапрошлом веке и потому практически неизвестной ни математикам, ни программистам.
Начать следует с того, что только один из трех упомянутых мною людей - профессор Морис Абрахам Штерн - был профессиональным математиком, а двое других персонажей к математике почти не имели отношения. Джон Фарей - английский геолог начала XIX века, один из пионеров геомагнитной разведки. Ахилл Броко - французский изготовитель часовых механизмов, хорошо известный современникам, но совершенно забытый потомками. Что же связывает его с исследованиями по теории чисел? Процитирую Брайана Хейеса:
«Скоро я узнал, почему аспекты теории чисел привлекли интерес изготовителей часов. Вот - пример основной задачи. Предположим, у вас есть вал, который поворачивается один раз в минуту, и вы хотите спроектировать механизм, который замедлит это движение до одного оборота в день. Для этого вам нужно замедлить скорость вращения в 1440 раз. Скорость механизма обратно пропорциональна числу зубьев шестеренки. Таким образом, прямым решением было бы связать шестерню с одним зубом и колесо, состоящее из 1440 зубцов. Но механизм с одним зубом чрезвычайно неуклюж, а механизм с 1440 зубьями - велик. Решение этой проблемы - сочленение нескольких последовательных шестеренок, причем промежуточные шестеренки содержат разное число зубцов, но насажены на один вал и потому вращаются с равными скоростями. Например, если для одной пары шестерен передаточное число равно 6/200, а для другой - 5/216, то в результате получается отношение 30/43200, которое равно требуемому 1/1440. Если колеса в 200 и 216 зубцов все еще слишком велики, тогда можно применить отношения 6/72, 6/60 и 5/60, дающие тот же результат».
Ясно, что сама возможность подбора передаточных чисел непосредственно связана с разложением числа 1440 на простые множители. Для поиска подходящих коэффициентов часовщикам приходилось пользоваться специальными таблицами, содержащими «полезные» числа, то есть те, разложение которых на простые множители не содержит слишком больших чисел.
Однако что делать, если требуемое передаточное число не может быть выражено точным отношением «полезных» чисел? Классический пример такой часовой задачи - связь между одним кругом часов (полусутками) и астрономическим годом. Если принять для простоты, что год - это 365 дней 5 часов 49 минут, то нужно получить отношение, равное 720/525949. Знаменатель этой дроби на небольшие множители не раскладывается. Следовательно, нужно найти другое отношение, как можно более близкое к 720/525949, но имеющее «полезные» числитель и знаменатель. Именно такую задачу и решил Ахилл Броко.
Снова цитирую фрагмент статьи Хейеса:
«В качестве обучающего примера Броко разбирает задачу построения механизма, передающего вращение с одного вала с периодом обращения 23 минуты на другой вал с периодом обращения 191 минута. Поскольку 23 и 191 - простые числа, то единственный вариант - искать приближенное решение задачи. Поиск приближения Броко начинает с замечания, что 191/23 больше 8, но меньше 9, поэтому отношение должно быть в интервале между 8:1 и 9:1. Он записывает это в верхнюю строчку листа бумаги:
8 |
1 |
-7 |
Первые два числа представляют отношение 8:1, а третье - погрешность начального приближения: 8/1 = 184/23, а 184-191 = -7.
В нижней строчке того же листа Броко пишет:
9 |
1 |
+16 |
То есть 9/1 = 207/23, а 297-191 = +16. Далее идет повторяющаяся часть алгоритма. Броко складывает числа в трех колонках и записывает сумму посередине страницы:
17 |
2 |
+9 |
Результат дает новую, уточненную информацию: отношение 17/2, поворачивая более быстрый вал за 23 минуты, заставляет медленный вал делать один оборот за 195,5 минуты, то есть дает погрешность в 4,5 минуты. Ошибка +9 в третьем столбце соответствует числителю дроби 9/2 = 4,5. Далее Броко выбирает, с какой из двух строк (верхней или нижней) нужно сложить текущую строку, чтобы уменьшить ошибку. Очевидно, что предпочтительнее складывать среднюю строку с верхней. Результат Броко записывает между ними:
25 |
3 |
+2 |
Продолжая таким же образом, в конце концов Броко получает на листе табличку:
8 |
1 |
-7 |
33 |
4 |
-5 |
58 |
7 |
-3 |
83 |
10 |
-1 |
191 |
23 |
0 |
108 |
13 |
+1 |
25 |
3 |
+2 |
17 |
2 |
+9 |
9 |
1 |
+16 |
Алгоритм Броко рекомендует в качестве приближений к 191/23 выбирать либо отношение 83/10 (дающее погрешность в 1/10 минуты), либо 108/13 (ошибка в 1/13 минуты)».
D описании легко углядеть метод построения дерева, названного именами Штерна и Броко. Однако и для подбора более точных приближений Броко применяет свой алгоритм! Он помещает одно из приближений в верхней строке, а точное значение - в нижней. Последовательные сложения строк дают отношения, погрешность которых еще меньше:
83 |
10 |
-1 |
274 |
33 |
-1 |
465 |
56 |
-1 |
656 |
79 |
-1 |
. . . |
. . . |
. . . |
. . . |
. . . |
. . . |
191 |
23 |
0 |
Теперь выбор подходящего отношения делается по таблицам «полезных чисел». Так, если взять за основу третью строку последней таблички, то легко построить цепочку из двух колес с передаточным числом 56/465: 56/465 = 7/31 • 8/15. Такой механизм дает ошибку всего в 1/56 минуты за оборот - согласитесь, неплохо…
Меня восхитила концовка статьи Хейеса, где он пишет, что благодаря техническому прогрессу те трудности и проблемы, с которыми сталкивались часовых дел мастера, перестали быть таковыми. Имея компьютер, говорит Хейес, можно попросту перебрать все возможности в поисках подходящего приближения для нужного числа. Этот перебор, оцениваемый им в 100 млн. вариантов, займет всего несколько минут. Может быть, Хейес и прав, однако я почему-то предпочитаю элегантность решений, найденных великими мастерами прошлого.
[1] Brian Hayes. «On the Teeth of Wheels». // American Scientist, Volume 88,
Number 4, July-August, 2000, pp. 296-300.
[2] Achille Brocot. «Calcul des rouages parapproximation, nouvelle methode» //
Revue chronometrique. 3:186-194 (1861).
[3] Р. Грэхем, Д. Кнут, О. Паташник «Конкретная математика». - М.: Мир, 1998,
глава 4.