Як використовувати алгоритми

Книга американського фахівця із системного програмування — унікальна збірка завдань із програмування з різних галузей: моделювання, точності обчислень, обробки текстів, штучного інтелекту, конструювання компіляторів. Більшість завдань базується на реальних та ігрових ситуаціях.

Для всіх, хто викладає та вивчає програмування.

Етюди для програмістів

Як використати алгоритми?

Для знаходження? треба буде провести обчислення по одній із формул, виписаних раніше в цьому пункті, з використанням ряду для арктангенсу. Фактично для страховки слід використовувати дві формули, а потім порівняти результати біт за бітом. Значенням? буде загальна початкова частина цих двох результатів.

Все ще залишається відкритим питання, як за допомогою алгоритмів, що працюють тільки з цілими числами, отримати очевидно дрібні значення членів ряду. Нехай ми хочемо вирахувати я, скажімо, з точністю 1000 бітів. Обчислимо тоді 2 1000, помноживши всі чисельники на 2 1000. Ця процедура робить також всі ділимо набагато більше дільників (як передбачалося вище) і дозволяє припинити обчислення, коли приватні стануть нульовими.

Виберемо тепер (не обов'язково найкращий) ряд для обчислень, скажімо

? = 16 arctg(1/5)? 4 arctg(1/239).

Ми фактично обчислюватимемо 2 1000?, тому хотілося б обчислити 2 1000 · 16 arctg (1/5). Першим членом відповідного ряду буде 21000 · 16/5; назвемо його a1 (зазначимо, що a1 складається із сумою). Тепер, щоб отримати наступний член ai+1 з ai, поділимо a1 на 5 · 5 · (2i? 1) [34]. Якщо ai додавався до суми, то віднімемо ai+1 із суми, якщо ai віднімається, додамо ai+i. Будемо поділимо a1 на 5 · 5 · (2i? 1). Якщо ai додавався до суми, то обчисленнязакінчуються, коли члени обох рядів стануть нульовими. В результаті отримаємо приблизно тисячу бітів числа?. Результат, звичайно, треба буде перевести до десяткової системи.

Тема.Складіть програми, що реалізують описані вище алгоритми множення та поділу, і всі необхідні їм службові підпрограми. Використовуйте їх для обчислення з високою точністю за допомогою одного з виписаних рядів. Прослідкуйте, щоб ваші програми не виявилися занадто тісно прив'язані до обчислення?; бібліотека програм для обчислень з високою точністю може бути корисною для інших завдань. Повинна бути передбачена можливість збільшення точності рахунку без зміни програм, лише шляхом розширення пам'яті для результатів. Вихідні дані повинні включати статистику щодо використання кожної програми, за кількістю виконання кожного кроку двох центральних алгоритмів та використання пам'яті. Збір такої інформації обійдеться дуже дешево, порівняно з усією роботою.

Вказівки виконавцю.Цей етюд довгий і важкий. Не останню роль тут грає те, що два центральні алгоритми потрібно певною мірою приймати на віру. Однак, як це часто буває у реальних завданнях, головною проблемою є не кодування програми, а вибір структур даних. Як уявляти довгі числа? Позначення [m, u] наводить на думку, що всяке довге число є парою аргументівдовжинаізначення. Частинадовжиналегко реалізується, алезначеннямає, очевидно, змінну довжину, і його важко буде безпосередньо зберігати в пам'яті. Тому ми зробимозначенняпокажчиком дуже довгий вектор бітів; тоді кожна пара матиме фіксований розмір. Однак вектор, який є у нашому розпорядженні, не настільки довгий, щоб ми могли дозволити собі використовувати.кожну його частину лише по одному разу. Таким чином, потрібна програма для збору непотрібної пам'яті. Зараз ми фактично описали традиційну схему розміщення ланцюжків.

Отже, зрештою нам потрібні крім алгоритму множення та поділу такі допоміжні підпрограми:

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

Повернення пам'яті. Вихідними даними для цієї підпрограми є парадовжинаізначення. Пов'язана із нею пам'ять звільняється повторного використання. Цю підпрограму необхідно викликати щоразу, коли довжина будь-якої змінної змінюється.

Зсув. Вихідними даними для підпрограми служать довге число і величина зсуву; результатом має бути довге число, зсунуте праворуч або ліворуч на відповідну величину. Ця операція відповідає множенню чи розподілу на ступінь двійки.

Складання. Вихідними даними підпрограми служать два довгі числа, а результатом повинна бути їх сума у вигляді числа на один біт довше довшого з операндів. Таку форму можна виконувати так само, як вручну, рухаючись праворуч наліво.

Віднімання. Ця підпрограма аналогічна підпрограмі складання і видає різницю двох довгих чисел.

Придушення нулів. Вихідними даними цієї підпрограми служить довге число, а результатом має бути більш коротке довге число, що має те ж значення, але без старших нулів. Якщо виявиться, що вихідне число дорівнює нулю, результатом має бути [1, 0].

Коротке множення. Вихідними даними служать два довгі числа довжиною точно 32 біти; результатом має бути їхній 64-розрядний твір. Цю операцію можна виконувати праворуч, як у ручному методі.

Множення довгого на коротке. Вихідними даними служать довге число і звичайне число, за величиною рівне 64 або менше; результатом має бути їхнє твір у вигляді довгого числа. Цю операцію можна виконувати праворуч, як вручну.

Поділ довгого на короткий. Вихідними даними служать довге число і звичайне число, що не перевищує 64, а результатом має бути довге приватне від поділу довгого числа на коротке. Цю операцію можна виконувати ліворуч, як це робиться вручну.

Переклад. Вихідними даними для цієї підпрограми є довге число, а результатом має бути те ж число, що записане в десятковій системі на деякому пристрої виведення. З появою потреби у складнішому висновку можна розробити детальніші специфікації підпрограми перекладу.

Інструментування.Як мову реалізації відразу ж спадає на думку Паскаль: у цій мові хороші структури даних і керуючі структури. Однак Паскаль не дозволяє легко переводити внутрішню бітову виставу в бітові ланцюжки, доступні програмісту, і назад. Мови нижчого рівня — BLISS і XPL — забезпечують більш прямий доступом до ЕОМ з допомогою певної втрати виразності та надійності. Хороша захищеність мов високого рівня і доступ до машинного уявлення поєднуються в PL/I, але зазвичай це доводиться розплачуватися часом виконання. Для цього етюду важливим є також час, який ви втратите, намагаючись осягнути деякі досить витончені можливості PL/I. Цікавою є реалізація на Траку,оскільки у разі автоматично вирішується завдання розподілу пам'яті для ланцюжків.

Тривалість виконання.Одному виконавцю на 5 тижнів або двом на 3 тижні.

Розвиток теми.Як тільки у нас з'являється арифметика високої точності, відразу виникає багато цікавих завдань. Одна з них – точне обчислення числа e. Ряд для e особливо простий:

де 0! = 1. Будь-який студент, який вивчає математичний аналіз, може придумати дуже багато рядів і констант.

Крім того, має сенс зберігати довгі числа не в двійковій системі числення, а в десятковій (звичайно, не по одній цифрі в елементі масиву, а по стільки цифр, скільки міститься в звичайному числі). При цьому відпадає потреба у програмі перекладу. Тепер арифметичні програми можуть працювати дещо повільніше (але зовсім не обов'язково; далеко не всі компілятори використовують команди зсуву для множення та поділу на ступені двійки), проте в цілому можна отримати виграш у швидкості, оскільки час роботи алгоритму перекладу довгих чисел із двійкової системи в десяткову (описаного у Кнута) пропорційно n?, тобто того ж порядку, що й час решти всіх обчислень.

За допомогою лише цих програм складання та поділу можна обчислити багато математичних константів: ?, e, ?2, ?2, ln 2 і т. д. Реалізація такого усіченого варіанту потребує, ймовірно, не більше одного людино-тижня. Складні динамічні структури даних не знадобляться; у нас буде всього два-три довгі числа відомого розміру, для представлення яких цілком підійдуть масиви Фортрана.