Пример развития математики в приложении к компьютерам.

[hitech]

Выбери из двух зол одно и получи второе в подарок!

Маркетинговая акция.

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

Поэтому люди, разрабатывавшие этот код до меня, пришли к гениальному решению: lookup tables! Память, в отличие от операций процессора, дешёвая. Мы просто заранее рассчитаем значения синусов, косинусов и арктангенсов для множества углов, составим табличку и загоним её в память. При таком решении, если нам повезёт с углом, и он окажется одним из заранее вычисленных, вытащить нужное значение можно будет за одну относительно дешёвую операцию доступа к памяти. А что делать, если запрошенный угол попадает между двумя рассчитанными? Не страшно, выполним интерполяцию, это два доступа к памяти и вычисление пропорции. Более того, вместо вычисления настоящей пропорции (умножение и деление дробных чисел — дорогие операции) можно искать среднее арифметическое (сложение и деление на два — дешёвые операции, даже несмотря на дробные числа), а для достижения нужной точности можно просто повторять вычисление среднего арифметического достаточное количество раз, приближаясь к значению, соответствующему нужному углу, методом «деления пополам».

Пример с числами (можно без опаски пропустить):

Допустим, нам надо вычислить синус 41°, а у нас есть вычисленные заранее значения синусов 30° и 45°, при этом нас устраивает точность в полградуса. Первым действием мы выполняем [sin(30°)+sin(45°)]/2 и получаем sin(37.5°). 41°>37.5°, поэтому выполняем [sin(37.5°)+sin(45°)]/2 и получаем sin(41.25°). Это достаточно близко к нужному углу, чтобы закончить вычисления. Значение синуса, вычисленное таким путём, будет 0.65533, тогда как истинное значение sin(41°)=0.65606, разница в 0,00073, — обычно это достаточно мизерная разница, чтобы она ни на что не влияла. При этом время, которое мы затратим на все эти операции, будет меньше, чем время, которое мы бы затратили на умножение с делением. Учитывая, что в таблице вычислены значения синуса с шагом меньше, чем в пятнадцать градусов, точность получается вполне достойная.

Вот как это выглядит в коде:

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

Ну чо, надо — значит, сделаем. Я набросал программулину, которая выполняет overдофига вычислений синусов и косинусов, замерил время работы и очень удивился. Но просто удивлением сыт не будешь, надо ещё понять, почему программа работает именно так, а не иначе. Воодушевлённый предварительными результатами, я взял код библиотеки, которую предполагалось использовать без сопроцессора, и внимательно его рассмотрел.

И что же я там увидел?

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

Всей разницы — шаг меньше, да код написан на ассемблере. А принцип остался неизменным с 1994 года. И это сейчас, в наши-то дни, когда могучие группировки космических кораблей бороздят просторы Тихого океана!.. …В общем, завтра на совещании расскажу начальству, что они предвосхитили развитие прикладной тригонометрии на четверть века вперёд.