一般旋转矩阵

仿射坐标系中的点P(v,Q)绕向量u旋转θ角，转换后的点为T(P)，有：

T(P)=Q+T(v)

根据罗德里格斯公式(Rodiguez's formula), 向量v绕向量u旋转所得向量为：

T(v)=(cosθ)v+(1-cosθ)(v•u)u+(sinθ)(u×v)

其中, (v•u)u=[v1,v2,v3]Tensor(u,u)；u×v=[v1,v2,v3]U

Tensor称为张量积，定义Tensor(u,v)=Translate(u)*v，其中，Translate表示转置，*表示矩阵乘法。其结果为3×3矩阵：

u1v1, u1v2, u1v3
u2v1, u2v2, u2v3
u3v1, u3v2, u3v3

而U为叉积的乘法矩阵：

0, u3, -u2
-u3, 0, u1
u2, -u1, 0

将v提取出来，得到：

T(v) = vR = v( (cosθ)I + (1-cosθ)Tensor(u,u) + (sinθ)U )，I为3×3单位矩阵

所以，若Q为原点，则旋转矩阵为：Matrix2×2{ R, 0, 0, 1 }
若Q不是原点，则要先将点P转换到以Q为原点的坐标系中(平移)，旋转后再逆转换回来：
M=Matrix2×2{ 1, 0, -Q, 1 }
N=Matrix2×2{ 1, 0, Q, 1 }
T = MRN = Matrix2×2{ R, 0, Q-QR, 1}

Boyer-Moore算法

另一种字符串匹配算法。设字符模板P的长度为 n，目标文本S的长度为 l ，其预处理时间为O( n)，查找的时间在最坏情况下是O( l )，平均时间为O( l / n)。

和KPM算法相比，尽管具有同样的时间复杂性（甚至更优），但实际上，由于其需要事先构造2个表：一个是GC表，构造时间为O( size of charset)；第二个是GS表（Boyer他们称之为RPR表），构造时间至少也要O( n)。所以无论从空间上还是时间上，都比KPM耗费更多。但如果字符模板和目标文本都比较长的话，BM算法却具有更优秀的实际运行效率。

具体算法见Boyer和Moore的论文：A Fast String Searching Algorithm

GS表的构造比较复杂，在论文中并没有给出实现的算法，于是我自己设计了一个算法，接近于O( n)。

Knuth-Pratt-Morris算法

简称KPM算法（或KMP或MKP或...），是一种快速的字符串匹配算法，据说大部分的子串搜索函数都是用该算法实现的。算法如下：

第一步，根据模板字符串P，构建匹配表T，其中P的字符数为 n，T的size也为 n：

1. Set T[ 0] = 0, and let P have n characters.
2. Set i = 1, j = 0.
3. If i >= n then we are done; terminate the algorithm. Otherwise, compare P[i] with P[j].
   • If they are equal, set T[i] = j + 1, j = j + 1, and i = i + 1.
   • If not, and if j > 0, set j = T[j − 1].
   • Otherwise, set T[i] = 0, i = i + 1.
4. Return to step 3.

第二步，使用构造好的表，执行算法，在字符串S搜索P，其中S的字符数为 l ，P的字符数为 n：

1. Let i = m = 0; say P has n characters, and S, l characters.
2. If m + i = l, then we exit; there is no match. Otherwise, compare P[i] versus S[m + i].
   • If they are equal, set i = i + 1. If i = n then we have found a full match; terminate the algorithm and return m as the start of the match.
   • If they are unequal, let e = T[i − 1]. Set m = m + i − e and if i > 0, set i = e.
3. Return to step 2.

构造匹配表的时间是O( n)，查找的时间是O( l )，速度相当快。

快速平方根算法

使用Mageic Number快速计算平方根和平方根的倒数，下面是JC的实现：

// 计算32位浮点数的平方根
float CarmSqrt(float x)
{
   union{
       int intPart;
       float floatPart;
   } convertor;
   union{
       int intPart;
       float floatPart;
   } convertor2;
   convertor.floatPart = x;
   convertor2.floatPart = x;
   convertor.intPart = 0x1FBCF800
       + (convertor.intPart >> 1);
   convertor2.intPart = 0x5f3759df
       - (convertor2.intPart >> 1);
   return 0.5f*(convertor.floatPart
       + (x * convertor2.floatPart));
}
// 计算32位浮点数的平方根的倒数
float InvSqrt (float x)
{
   float xhalf = 0.5f*x;
   int i = *(int*)&x;
   i = 0x5f3759df - (i >> 1);
   x = *(float*)&i;
   x = x*(1.5f - xhalf*x*x);
   return x;
}

Chris Lomot的演算和实验得出，用于该算法最佳的Magic Number是0x5f37a86（32位）和0x5fe6ec85e7de30da（64位）。

具体请参阅：友善之臂旅店

浮点数到整数的快速转换

使用Magic Number的快速转换算法如下：

//
// 将64位浮点数转换为32位整数
// 小数部分将四舍五入到偶数
//
inline void RoundToInt64 (int &val, double dval)
{
   static double magic = 6755399441055744.0;
   dval += magic;
   val = *(int*)&dval;
}

如果要取整的话，需要使用修正值：

// 修正值
static double magic_delta=0.499999999999;

// 截取到整数
inline void Floor64 (int &val, double dval)
{
   RoundToInt64(val,dval-delta);
}
// 进位到整数
inline void Ceil64 (int &val, double dval)
{
   RoundToInt64(val,dval+delta);
}

详细请参阅：友善之臂旅店