Листинг 18.1. Сравнение выполнения программы с использованием справочных таблиц и встроенных функций sin и cos (LOOKNUP.C).

#include <math.h>

#include <stdio.h>

#include <graph.h>

float sin_table[360], cos_table[360];

main()

{

int index, x,y,xo,yo,radius,color,ang;

char far *screen = (char far *)0xA0000000;

// использовать библиотеку Microsoft для перехода

// в режим 320х200х256

_setvideomode(_MRES256COLOR);

// создать таблицы быстрого доступа

for (index=0; index<360; index++)

{

sin_table[index]= sin(index*3.14159/180};

cos_table[index]= cos(index*3.14159/180);

}

// нарисовать 1000 окружностей, используя встроенные

// функции sin и cos

for (index=0; index<1000; index++)

(

// получить случайные числа

radius = rand()%50;

xo = rand()%320;

yo = rand(}%200;

color = rand()%256;

for (ang=0; ang<3 60; ang++)

{

x = xo + cos(ang*3.14159/180) * radius;

У = yo + sin(ang*3.14159/180) * radius;

// нарисовать точку окружности

screen[(y<<6) + (y<<8) + x] = color;

}

}// все, ждать пока пользователь нажмет клавищу

printf("\nHit,a key to see circles drawn twith look up tables.");

getch();

_setvideomode(_MRES256COLOR);

// нарисовать 1000 окружностей, используя таблицы поиска

for (index=0; index<1000; index++)

{

// нарисовать случайную окружность

radius = rand()%50;

хо = randO %320;

уо = rand()%200;

color = rand()%256;

for (ang=0; ang<3 60; ang++)

{

x = хо + cos table[ang] * radius;

у = уо + sin_table[ang] * radius;

// нарисовать точку окружности

screen[(y<<6) + (y<<8) + x] = color;

} }

// подождать, пока пользователь нажмет любую клавишу

printf("\nHit any key to exit."};

getch();

_setvideomode(_DEFAULTMODE);

}

После запуска LOOKNUP.C вы должны согласиться, что справочные таблицы крайне удобны и могут здорово увеличить скорость выполнения программы.

Следующая тема будет касаться математики с фиксированной запятой.

Математика с фиксированной запятой

Математика с фиксированной запятой? Нет, это не новая точка зрения на дробные числа. Просто это немного другой путь рассмотрения компьютерной математики.

Существуют две формы математики, предназначенные для компьютера:

• Математика целых чисел;

• Математика с плавающей запятой.

Первая использует значения типов CHAR, INTEGER, LONG и т. д. Вторая оперирует числами FLOAT, DOUBLE и т. п. Разница между двумя этими видами математики заключается в том, как представлены числа в памяти и какие именно числа - целые или дробные - принимают участие в расчетах. Целые числа представлены в компьютере непосредственно в двоичной форме, без какого-либо кодирования. Как вы знаете, они могут быть как положительными, так и отрицательными, и у них отсутствует дробная часть. С другой стороны, числа с плавающей запятой должны иметь десятичные части.

Но к чему такая забота по поводу чисел? Объясняю: ПК может выполнять математические вычисления весьма быстро, но «весьма быстро» еще не значит «достаточно быстро для видеоигр». Даже с математическим сопроцессором ПК до сих пор оставляет желать лучшего в режиме реального времени при работе с трехмерной графикой. Известно, что вычисления с целыми выполняются гораздо быстрее, чем с дробными числами.

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

Вычисления с плавающей запятой пожирают так много времени из-за способа представления чисел, с которыми они оперируют. Эти числа не являются в полном смысле двоичными, напротив, они хранятся в специальном формате IEEE, в котором характеристика (целая часть) и мантисса (экспонента) представлены в жутко свернутой форме, и прежде чем число использовать в вычислениях, его нужно еще расшифровать. Числа — это только инструмент для представления игровых объектов. Если бы вы захотели, то могли бы разработать свои собственные форматы хранения десятичных чисел. Это та область, где в бой вступает математика с фиксированной запятой. Например, можно представить число содержащим как целую, так и десятичную часть внутри отдельного целого. Как это сделать? Притворимся, что десятичные части существуют где-то внутри целого и что двоичные цифры слева являются целой частью числа, а все, что находится справа, это десятичная часть. Рисунок 18.3 должен помочь вам представить это.

Где именно вы поместите десятичную часть, зависит от вас. Важно, чтобы позиция десятичной точки и выбор базового типа данных удовлетворяли нашим потребностям. Я предлагаю использовать тип данных LONG, который имеет 32 бита точности, а десятичную точку поместить где-нибудь посередине. Скажем, отведем для десятичной части восемь младших битов, тогда целая часть займет 24 старших разряда. Этого более чем достаточно для наших потребностей, поскольку в видеоиграх не нужна очень высокая точность. Пары знаков после запятой будет вполне достаточно. Чтобы использовать математику с фиксированной запятой, нам необходимо только разобраться, как выполнять с ней несколько операций:

§ присваивание;

§ сложение;

§ вычитание;

§ умножение;

§ деление;

§ сравнение.

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

long fix_1,fix_2,fix_3;

Что, обманул вас на секунду, да? Не правда ли, проще не придумаешь? Как я сказал ранее, мы используем тип данных LONG для чисел с фиксированной точкой и только предполагаем наличие десятичной части. И это все, что нам нужно для определения числа с фиксированной запятой.

Присваивание

Теперь поговорим о присваивании. Если мы хотим присвоить целую часть фиксированного числа, мы делаем.следующее:

int а=300;

long fix_1=0;

// в двоичном виде - 0000 0000 0000 0000 0000 0000 0000 0000

fix_1=((long)a << 8);

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

long fix_1 = (long) (23.4*256)

Мы умножаем на 256 потому, что это эквивалентно сдвигу на восемь разрядов влево (помните, я уже говорил, что нет смысла сдвигать числа с плавающей запятой).

Сложение и вычитание

Чтобы складывать или вычитать числа с фиксированной запятой, мы можем использовать обычные операторы Си. К примеру, чтобы сложить два числа и записать результат в третье, мы могли бы сделать так:

fix_3=fix_1+fix_2

Вычитание получается точно так же. Кроме того, вы можете использовать и отрицательные значения, поскольку внутреннее представление типа данных LONG учитывает знак, и это вполне применимо также и к числам с фиксированной запятой.

Умножение

Самая сложная из всех операций — это умножение. Здесь мы должны соблюдать осторожность: существует несколько нюансов, которые могут наплодить множество ошибок. Например, когда умножаются два числа с фиксированной запятой, для сохранения результата может потребоваться в два раза больше битов, нежели содержат сомножители. Другими словами, если оба сомножителя были 32-битными, не исключена возможность получить 64-битный результат. То есть мы должны следить за величиной чисел с фиксированной запятой, которые перемножаются. Как и обычно, для этого мы будем использовать оператор умножения. Однако когда умножение выполнено, мы должны сдвинуть результат на 8 позиций назад вправо. Это нужно сделать потому, что когда мы задаем число с фиксированной запятой, то искусственно перемножаем его на 256 (помните, восемь младших разрядов заняты под десятичную часть). Поэтому мы должны сдвинуть окончательный результат назад восемь раз вправо, иначе говоря, результат должен быть разделен на 256. Если этого не сделать, то, умножая 2 на 5, мы получим 2х5х256 вместо правильного ответа равного 10. Здесь приводится способ, каким делать умножение.

fix_1=(fix_2*fix_3)>>8;

Если вы хотите вычислить сумму произведений, то нет надобности после каждого умножения сдвигать результат. Достаточно сделать это только один раз в самом конце расчетов. Рассмотрим пример:

fix_1=(fix_2*fix_3+fix_4*fix_5)>>8;

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

Деление

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

fix_1=(long)(256*1/34);

fix_2=(fix_3*fix_1)>>8;

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

Точность

Поскольку мы договорились, что в нашем формате чисел с фиксированной запятой восемь младших разрядов будут содержать десятичную часть, то самым маленьким числом, которое можно представить, окажется значение 1/256 или примерно 0.004. Следовательно, максимальная ошибка будет получаться при умножении двух чисел. Наибольшее число, которое мы можем получить в произведении, равно 32761. Следовательно, наибольшая ошибка, которая может закрасться в расчеты, это 0.004х32761 или 131.044. Ого! Это слишком много. Однако в действительности у нас никогда не будет ошибок такой величины. Только вы не должны с одним и тем же числом выполнять больше 2-5 умножений, и сомножители не должны превышать 32761. Как правило, в большинстве случаев ошибки не будут превышать 0.01-0.5, что вполне допустимо, поскольку 90 процентов всех расчетов направлены на определение местоположения пикселей на экране и результаты все равно округляются.

Хватит насчет точности. Перейдем к определению максимального числа, которое может быть представлено в нашей системе с фиксированной запятой.

Максимальное цифровое представшие

Поскольку у нас есть 24 бита для целой и 8 бит для десятичной части числа, вы можете подумать, что таким образом можно представить значения вплоть до 2²⁴ или 16777216. Почти, но не совсем. Так как число с фиксированной запятой может быть и положительным и отрицательным, мы располагаем числами в диапазоне от -8388608 до +8388608. Мы можем без всяких проблем складывать и вычитать числа из этого диапазона, но при умножении, должны быть исключительно осторожны, чтобы не переполнить тип LONG.

Когда я изучал математику с фиксированной запятой в первый раз и пытался алгоритмизовать ее, то допустил ошибку. Я использовал схему, похожую на нашу (то есть 24 бита для целой части и 8 бит для десятичной) и думал, что наибольшие числа, пригодные для умножения, могут быть любыми, лишь бы результат укладывался в 24 бита. Это означало бы, что можно перемножить 4096 на 4096 и получить правильный ответ. Ошибочка! Я забыл об остальных 8 битах десятичной части- Следовательно, в действительности я умножил 4096х256х4096х256, что составляет примерно 1.09х1012. Поскольку тип LONG состоит из 32-х битов, то он может представлять числа от -2147483648 до [phone] (которые в 1000 раз меньше полученного результата). Мораль сей басни такова, что числа с фиксированной запятой остаются принадлежащими типу LONG, и если в них записать числа, интерпретируемые как LONG, то при умножении возникнет переполнение.

Наибольший результат умножения, который может быть получен в нашей системе с фиксированной запятой равен 32761 или 181 в степени 2. Число 181 было получено исходя из следующих соображений: это число, которое, будучи умноженным на 256 и возведенным в квадрат, не должно превышать размерности типа LONG ([phone]). Мы используем 256, так как у нас есть восемь двоичных цифр, a 2⁸ равно 256.

Как, ни странно, но наибольшее число, которое может быть получено в результате умножения — это 32761, а величина чисел для сложения может достигать примерно 8000000? Ну что ж... где-то мы нашли, а где-то потеряли.

Чтобы помочь вам в экспериментах с числами с фиксированной запятой и увидеть некоторые их интересные свойства, я создал небольшую библиотеку и программу main() для демонстрации их использования (Листинг 18.2). Я предлагаю вам потратить немного времени, чтобы получить действительно целостное понимание сути чисел с фиксированной запятой, поскольку это очень важно и про это мало кто знает. Никогда не надо забывать, что десятичная запятая является воображаемой!

Дата добавления: 2015-07-12