Хотите вы этого или нет, но рано или поздно вам придется применять математику в своих программах. Возможно, вы пишете игру и должны смоделировать перемещение игрока в мире. Возможно, вам придется конвертировать различные валюты в финансовом приложении, делать выборку больших наборов данных или просто заставить HTML-элементы отображаться там, где вы хотите, на вашем сайте.
Хотя вы наверняка изучали математику и физику в школе, их легко забыть, и при изучении программирования не всегда очевидно, как компьютер работает с числами.
Лично я никогда не был хорош в математике или физике, скорее всего, потому, что в детстве мне это не нравилось. Я думаю, это было потому, что я не понимал их смысла. Мне не к чему было применить полученные знания, поэтому мне было неинтересно. Однако, узнав больше о компьютерных науках и программировании, я начал находить области, где математика может быть применена, и, как и в программировании, я обнаружил, что за математикой стоит система, и она может быть не только полезной, но и увлекательной, если вложить в нее немного времени.
Эта серия статей будет служить дневником, в котором я буду рассказывать о том, как лучше изучать математику и физику в качестве программиста. Я собираюсь начать с основ, а также применять полученные знания в процессе программирования.
Итак, давайте начнем.
Числа
Что такое числа в глазах компьютера и что они могут сделать для нас?
Давайте начнем с того, что существуют различные типы чисел. Эти типы делятся на несколько подмножеств, где множество — это набор элементов, каждый из которых должен быть уникальным.
Первое множество, которое изучает большинство людей, — это множество натуральных чисел, которое обозначается символом
N
. Числа в этом множестве — это положительные числа, начиная с единицы (1, 2, 3, 4, 5 …). Некоторые математики включают в это множество 0.
Добавление множества отрицательных чисел дает нам множество целых чисел, которое мы, программисты, знаем как int в большинстве языков программирования. Символ для этого множества обозначается как
Z
.
Отрицательные числа очень интересны, я научился думать об отрицательных числах в терминах транзакций или сделок. Например, если у вас есть 5 яблок, и вы хотите отдать 2 из них Джонни, это то же самое, что Джонни отдает вам -2 яблока. Эту идею двух подходов можно распространить и на умножение. Если Джонни дает вам -2 яблока -2 раза, то это противоположно тому, что он делает это 2 раза, так что это противоположно тому, что -4 дает вам 4.
Может потребоваться некоторое время, чтобы это усвоить. Если вы не поймете это сразу, то не стоит отчаиваться, потому что людям потребовались столетия, чтобы принять это.
Помимо множества целых чисел, существует также множество рациональных чисел, обозначаемое $${displaystyle mathbb {Q} }$$, которое включает в себя предыдущие множества, о которых мы говорили, а также множество дробей.
Далее у нас также есть иррациональные числа, которые не могут быть выражены через коэффициент двух целых чисел, хорошим примером является квадратный корень из 2. Рациональные и иррациональные числа образуют множество действительных чисел, используя символ
R
. Это те множества, на которых мы сейчас сосредоточимся.
Символы для различных множеств можно забыть, потому что, скорее всего, мы не будем использовать их дальше. Однако, если вы планируете какие-то математические вычисления на бумаге или обсуждаете их с математиком, может быть полезно говорить с ним на одном языке.
Представление чисел
Например, когда мы говорим о числе 4, есть разные способы представления этого числа. Вы можете представить его геометрической фигурой в виде прямоугольника, а можете просто нарисовать на бумаге 4 точки или просто использовать символ «4». У разных представлений есть свои преимущества и недостатки, иногда проблему легче решить, если вы можете увидеть ее визуально.
Различные представления числа 4.
Не существует универсального символа для каждого числа, вместо этого мы используем ограниченный набор символов, которые можно комбинировать для представления любого числа. Для этого используется система оснований. В нашей повседневной жизни числа записываются по основанию 10, но ничто не мешает нам использовать любое другое основание.
К любому числу N в любом основании B можно применить алгоритм, подобный следующему:
function NumberToBase(N, B)
{
ConvertedNumber = [];
Index = 0;
while (N != 0)
{
ConvertedNumber[index] = N % B;
N = N / B;
++Index;
}
// Use the ConvertedNumber array to build a number or string
}
Реальный пример реализации на языке Си может выглядеть следующим образом:
char *NumberTable[] =
{
"0", // 0
"1", // 1
"2", // 2
"3", // 3
"4", // 4
"5", // 5
"6", // 6
"7", // 7
"8", // 8
"9", // 9
"A", // 10
"B", // 11
"C", // 12
"D", // 13
"E", // 14
"F", // 15
};
char *
NumberToBase(int Number, int Base)
{
char *Result = calloc(1, 1024);
int At = 0;
while (Number != 0)
{
int ConvertedNumber = Number % Base;
Number = Number / Base;
PrependString(Result, NumberTable[ConvertedNumber]);
}
return Result;
}
Принцип работы этого алгоритма довольно прост: если ввести числа 462 для аргумента Number и 10 для Base, то при делении Number и Base остаток будет равен 2. Затем, разделив число на 10, мы получим число 62, которое используется для повторения процесса, в результате чего мы получим число 462.
Эту же операцию можно проделать и в обратном порядке:
int
BaseStringToValue2(char *Digits, int Base)
{
int StringLength = strlen(Digits);
if (StringLength == 0)
{
return 0;
}
int Result = 0;
int Power = 0;
while (StringLength != 0)
{
char C = Digits[StringLength - 1];
int Number = ToNumber(C);
Result += pow(Base, Power) * Number;
StringLength--;
Power++;
}
return Result;
}
Если вы передадите строку «3572» и основание 10, то этот алгоритм будет перебирать числа, начиная с 2, и выдаст результат
2∗1+7∗10+5∗100+3∗1000
.
Нет ничего особенного в использовании 10 в качестве основания для чисел, кроме того факта, что у нас есть 10 пальцев для счета. Различные основания имеют свои преимущества и могут использоваться в различных областях, например, в компьютерах используется основание 2, поскольку оно хорошо отображается на транзисторах в аппаратуре. Основание 12 используется, когда речь идет о футах и дюймах, часы часто используют основание 60, а когда речь идет о градусах, мы используем основание 360.
Как компьютеры представляют числа
Как мы уже упоминали, компьютеры представляют числа в двоичном виде. Это идеальный вариант, поскольку компьютер построен на концепции «переключателей», которые могут быть либо включены, либо выключены, что представляется как 1 или 0 соответственно. Каждый переключатель представляет собой один бит информации, слово «бит» здесь является сокращением от «двоичный разряд». С помощью 8 бит вы можете представить любое число от 0 до 255, с помощью 32 бит вы можете представить любое число до 4294967295, а с помощью 64 бит вы можете представить число до 18446744073709551615. Числа 32 и 64-бит — это то, что вы можете узнать: несколько лет назад процессоры поддерживали 32-битную версию, и у вас была установлена 32-битная версия Windows, в то время как сегодня у вас, скорее всего, 64-битный процессор, что означает, что он изначально работает с 64-битными целыми числами, а не с 32-битными.
Это не означает, что используется каждый бит, обычно один бит отводится для обозначения положительности или отрицательности числа. Это означает, что 32-битный компьютер будет работать только с числами от -2147483647 до 2147483647, а не только с положительным диапазоном до 4294967295.
Двоичное сложение выполняется простым сложением всех цифр в одном столбце, и если обе цифры равны 1, то используется перенос цифр, которые переносятся, например, при выполнении сложения типа
1+1=10
.
Вычитание работает почти так же, но вы заимствуете из следующего столбца, если столбец содержит 0, а не перенос, как при сложении, например:
10-1=1
и
101-10=11
.
Арифметические операции над двоичными числами довольно тривиальны и обычно реализуются с помощью логических операторов AND, OR и NOT. В приведенных ниже таблицах показаны различные комбинации битов для различных операций.
AND
Оператор AND дает 1, только если оба операнда равны 1.
| A | B | Результат |
|---|---|---|
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 0 | 0 |
OR
Оператор OR дает единицу, если один или другой операнд равен 1.
| A | B | Результат |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 0 | 0 | 0 |
НЕ
Операция NOT выдает 1, если бит установлен в 0 и наоборот.
| Бит | Результат |
|---|---|
| 0 | 1 |
| 1 | 0 |
Плавающая точка
В какой-то момент чтения этой статьи вы, возможно, задались вопросом, как числа с плавающей запятой вписываются во все то, о чем мы говорили. Если компьютеры знают только двоичные числа 0 и 1, как мы можем представить значение, которое меньше 1, но не 0? Для этого, как и в реальной жизни, мы используем маркер, известный как десятичная точка (также известная как точка радикса).
В системе счисления 10 числа после запятой обозначают десятые, сотые, тысячные и так далее. В двоичном исчислении они обозначают половины, четверти и так далее. Зная это, число
183
в двоичном виде представляется как
1.011(1+41+81)
. Хотя это кажется разумным, существует фатальная проблема, которая заключается в том, что не все дроби могут быть представлены таким образом. Например, в десятичной системе счисления трудно представить
31
потому что это будет состоять из бесконечной серии
103+1003+10003+…
следовательно, мы можем просто написать
0.333…
В двоичном исчислении ситуация еще хуже, потому что вы не можете представить любую дробь, знаменатель которой делится на число, отличное от 2. Примером может служить
51
что в десятичной системе равно
0.2
но в двоичном исчислении это получается бесконечно повторяющееся число:
0.001100110011…
Поскольку эти типы чисел не имеют четкого определения, когда их следует остановить, у компьютеров возникают проблемы с ними.
Есть способы обойти это, которые были опробованы в прошлом. Один из способов — забыть о точке радикса и просто представлять числа в виде дробей, некоторые языки программирования экспериментировали с этим. Хотя каждое число можно представить точно, возникают некоторые проблемы при сложении несовместимых дробей, что приводит к увеличению сложности дроби с каждым шагом вычислений, легко достигая максимального размера для целых чисел, и даже если вы не достигли максимального размера, вычисления будут медленными из-за размера дробей.
Другая проблема возникает, когда вы работаете с иррациональными числами, которые нельзя выразить точно в виде дроби, вместо этого приходится приближать число. Компьютеры используют систему оснований для представления нецелых чисел и округляют их до ближайшего разряда.
С этим тоже могут быть проблемы, но могут возникнуть и другие проблемы, если, например, вместо этого используются представления с фиксированной точкой. Это означает, что после точки радикса используется только фиксированное количество цифр.
Поскольку у вас есть только ограниченное количество битов для каждого числа, каждый бит, добавленный справа от радиксной точки, означает на один бит меньше для использования слева. В результате вы ограничиваете возможности больших и малых чисел. Вместо этого большинство языков программирования позволяют перемещать точку радикса.
Научная нотация
Аналогично перемещению точки радикса существует научная нотация — представление, в котором используется первая значащая (ненулевая) цифра, за которой следует столько цифр, сколько вам нужно, после чего вы указываете позицию радикса. Например, число
305.57
может быть представлено как
30557;3
. Используя научную нотацию, это обычно представляется как
3.0557e2
. Если следовать соглашению, то радикс начинается после первой цифры и далее по порядку,
e2
в данном случае является экспонентой числа.
Стандарт IEEE
IEEE, что означает Институт инженеров электротехники и электроники, — это организация, создавшая множество стандартов, которые обычно используются производителями компьютеров и разработчиками программного обеспечения. Эти стандарты важны для создания общей основы между различным оборудованием, языками программирования и системами.
Был создан стандарт IEEE для использования чисел с плавающей запятой, который определяет, что при работе с 32 битами необходимо использовать 1 бит для знака (положительного или отрицательного) и 8 бит для позиции точки радикса (от -127 до +127), что в сумме дает 255. Значение фактического числа может быть как выше, так и ниже
2128
оставшиеся биты (23) представляют собой мантиссу, то есть фактические цифры числа. Это просто работает, потому что первая значащая цифра двоичного числа всегда равна 1, нет необходимости включать эту цифру в представление числа компьютером, она просто всегда неявно присутствует.
Отличную визуализацию этого можно увидеть следующим образом:
Источник: https://en.wikipedia.org/wiki/IEEE_754
Вы можете думать, что экспонента указывает на размер числа, в то время как мантисса или дробь на картинке выше определяет точность числа.
Забавный маленький трюк, который можно проделать в C++, чтобы увидеть это в действии, можно выполнить с помощью этого фрагмента кода:
#include <stdio.h>
struct FloatBits
{
unsigned int fraction:23; /**< Value is binary 1.fraction ("mantissa") */
unsigned int exp:8; /**< Value is 2^(exp-127) */
unsigned int sign:1; /**< 0 for positive, 1 for negative */
};
/* A union is a struct where all the fields *overlap* each other */
union FloatUnion
{
float f;
FloatBits b;
};
int main()
{
FloatUnion s;
s.f=8.0;
printf("%f = sign %d exp %d fract %dn", s.f, s.b.sign, s.b.exp, s.b.fraction);
return 0;
}
Как работает этот фрагмент, мы просто определяем структуру для битов, как мы указали в изображении и описании выше, это можно сделать с помощью битовых полей C++. Порядок полей обратный тому, что вы могли себе представить, это потому, что машина, на которой мы работаем, является little-endian.
Затем мы определяем объединение для примитива float и нашей структуры FloatBits, это позволяет нам создать примитив float и увидеть то же самое представление в нашем типе данных.
Вычисление числа выглядит следующим образом: $$value = (-1) * sign * 2 (exponent-127) * 1.fraction$$.
Например, значение $$8.0$$, указанное в примере выше, будет храниться со знаком 0, экспонентой 130 $$(3+127)$$, а мантисса будет просто нулями, так как ведущая 1 неявная.
И снова возникают проблемы, потому что независимо от того, насколько точными мы сделаем эти числа с плавающей запятой, они редко будут точными. Это означает, что могут возникнуть ошибки в вычислениях, хотя это уже не так часто встречается, но все еще может произойти. В основном это происходит из-за ошибок округления, когда число не может быть представлено точно и округляется до ближайшего числа. Выполнение тяжелых математических и научных расчетов может стать серьезной проблемой. Иногда помогает перемещение элементов в уравнениях, но проблема все равно остается. Однако в настоящее время компиляторы обычно заботятся об этом за нас, поэтому ошибки округления встречаются реже.
Другая проблема заключается в том, что вычисления с плавающей запятой используют более дорогие инструкции, чем целые числа, что может привести к худшей производительности, чем просто использование целых чисел. Однако современные процессоры справляются с этой задачей все лучше и лучше, но об этом следует помнить.
Если вы действительно хотите погрузиться в тему плавающей точки и ее взлетов и падений, я могу настоятельно порекомендовать вам эту статью: Что каждый компьютерщик должен знать об арифметике с плавающей запятой