Государственное образовательное учреждение

высшего профессионального образования

«Московский государственный технический университет имени н.Э. Баумана» (мгту им. Н.Э.Баумана)

________________________________________________________________________

Факультет

«ФУНДАМЕНТАЛЬНЫЕ НАУКИ»

Кафедра

«ПРИКЛАДНАЯ МАТЕМАТИКА»

Домашнее задание по дисциплине

« ПРИКЛАДНОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧАХ

МАТЕМАТИЧЕСКОЙ ФИЗИКИ »

Домашнее задание №1

5 Вариант

ИСПОЛНИТЕЛЬ

студент гр. ФН2-101 ________________ / Голубева Ю.Ю. /

ПРЕПОДАВАТЕЛЬ ________________ / Фисун В. А. /

кандидат ф.-м. наук,

старший научный сотрудник

ИПМ им. М.В.Келдыша РАН.

Москва 2019

Задание 1.

1.5. Использование математических таблиц для автоматизации арифметических операций.

Умножение, деление, возведение в степень и извлечение корня – действия, гораздо более трудоемкие, чем сложение и вычитание, особенно тогда, когда нужно работать с многозначными числами. Настоятельная потребность в таких действиях впервые возникла в XVI веке в связи с развитием дальнего мореплавания, вызвавшим усовершенствование астрономических наблюдений и вычислений. На почве астрономических расчетов и возникли на рубеже XVI и XVII веков логарифмические вычисления, а в настоящее время они применяются повсюду, где приходится иметь дело с многозначными числами. Они выгодны уже при действиях с четырехзначными числами и совершенно необходимы в тех случаях, когда точность должна доходить до пятого знака.

Ценность логарифмического метода состоит в том, что он сводит умножение и деление чисел к сложению и вычитанию – действиям менее трудоемким. Возведение в степень, извлечение корня, а также и ряд других вычислений (например тригонометрических) также значительно упрощаются.

 Открытие логарифмов и логарифмических таблиц Дж. Непером в начале 17 в., позволивших заменять умножение и деление соответственно сложением и вычитанием, явилось крупным шагом в развитии вычислительных систем ручного этапа. Фактически таблицы Непера открыли путь к автоматизации всех арифметических вычислений.

В работе "Описание удивительной таблицы логарифмов" (1614) изложил свойства логарифмов, дал описание таблиц, правила пользования ими и примеры применений. Основанием таблицы логарифмов Непера является иррациональное число, к которому неограниченно приближаются числа вида при безграничном возрастании . Это число называют неперовым числом и обозначают буквой е:

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

Наряду с палочками Непер предложил счетную доску для выполнения операций умножения, деления, возведения в квадрат и извлечения квадратного корня в двоичной системе счисления, предвосхитив тем самым преимущества такой системы счисления для автоматизации вычислений.

Введенные Дж. Непером логарифмы оказали революционизирующее влияние на все последующее развитие счета, чему в значительной степени способствовало появление целого ряда логарифмических таблиц, вычисленных как самим Непером, так и рядом других известных в то время вычислителей (Х. Бриггс, И. Кепплер, Э. Вингэйт, А. Влах). Сама идея логарифмов в алгебраической интерпретации базируется на сопоставлении двух типов последовательностей: арифметической и геометрической.

Логарифмы послужили основой создания замечательного вычислительного инструмента - логарифмической линейки. Прообразом современной логарифмической линейки считается логарифмическая шкала Э. Гюнтера, использованная У. Отредом и Р. Деламейном при создании первых логарифмических линеек. Усилиями целого ряда исследователей логарифмическая линейка постоянно совершенствовалась и видом, наиболее близким к современному, она обязана 19-летнему французскому офицеру А. Манхейму

В наши дни при решении ряда задач в информатике, необходимо снизить требуемый объем памяти за счет более медленного выполнения программы или, наоборот, снизить время вычислений за счет увеличения объема используемой памяти. Подход, описывающий это, называется  "time-memory trade-off" («выбор оптимального соотношения "время-память"»).

Одним из примеров применения такого подхода являются таблицы поиска.

Таблица поиска (англ. lookup table) – это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнение трудоёмких вычислений.

Идея такова: вместо того, чтобы, не используя дополнительную память, перебирать все допустимые решения, или один раз вычислить их все заранее и хранить их в памяти (часто нет ни первой, ни второй возможности), можно заранее вычислить часть допустимых значений, и, организовав их в специальную структуру данных — таблицу поиска, — осуществлять с ее помощью дальнейший перебор уже непосредственно при решении задачи.

Классический пример использования таблиц поиска — вычисление значений тригонометрических функций, например, синуса. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью рядов).

Таблицы поиска также используются в математических сопроцессорах; ошибка в таблице поиска в процессорах Pentium фирмы Intel привела к печально известной ошибке, уменьшавшей точность операции деления.

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

Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — интерполяцией. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.

Таблицы поиска широко используются также в компьютерной обработке изображений (в этой области соответствующие таблицы обычно называют «палитрами»).

Важно отметить, что использование таблиц поиска в тех задачах, в которых они не эффективны, приводит к ухудшению скорости работы. Это происходит не только потому, что извлечение из памяти данных оказывается медленнее, чем их вычисление, но и потому, что таблица поиска может занять всю память и переполнить кэш. Если таблица велика, каждое обращение к ней, скорее всего, будет приводить к промаху кэша. В некоторых языках программирования (например, в Java) обращение к таблице поиска может быть даже более «дорогим» из-за обязательной проверки границ, включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.

Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна умещаться в имеющийся объём, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время, необходимое для создания таблицы поиска при первом запуске — хотя обычно эта операция нужна только один раз, она может отнимать слишком много времени, что делает использование таблиц поиска неподходящим решением.

Пример. Вычисление синуса.

Большинство компьютеров поддерживает только основные арифметические операции и не могут вычислить значение синуса напрямую. Вместо этого для вычисления значения синуса с высокой степенью точности они используют метод CORDIC или ряд Тейлора:

Однако такое вычисление может занять много времени, особенно на медленном процессоре, и существует множество приложений, например, компьютерная графика, которым необходимо вычислять значение тысяч синусов каждую секунду. Распространённое решение — заранее вычислить таблицу значений синуса, и затем нахождение синуса числа сведётся к выбору ближайшего к этому числу аргумента из таблицы (соответствующее значение функции будет близко к правильному значению, потому что синус — непрерывная и ограниченная функция). Например:

real array sine_table[-1000..1000]

for x from -1000 to 1000

sine_table[x] := sine(pi * x / 1000)

function lookup_sine(x)

return sine_table[round(1000 * x / pi)]

Задание 2.