没有数学库的Donut.c

在几个YouTube视频（例如LexFridman和JomaTech）中亮相之后，我的小甜甜圈c就一直在反复进行。如果我知道这些年来这些代码会引起多大的关注，那么我会花更多的时间进行编写。

一直很不幸的一件事是大量使用sin和cos –既因为它需要链接数学库（-lm），又因为它使CPU占用的资源比实际需要的多得多。这尤其是如果您尝试将其移植到较旧的CPU或嵌入式设备，则很明显。

因此，这是一个修订版，其中没有使用sin，cos，也不需要链接数学库（尽管此版本仍使用浮点类型）。

i，j，k，x，y，o，N; main（）{float z [1760]，＃define R（t，x，y）f = x; x- = t * y \; y + = t * f; f =（3-x * xy * y） / 2; x * = f; y * = f; = 0，e = 1，c = 1，d = 0，f，g，h，G，H，A，t，D; char b [1760]; for（;;）{memset（b，32,1760 ）; g = 0，h = 1; memset（z，0,7040）; for（j = 0; j＆lt; 90; j ++）{G = 0，H = 1; for（i = 0; i＆lt; 314; i ++）{A = h + 2，D = 1 /（G * A * a + g * e + 5）; t = G * A * eg * a; x = 40 + 30 * D *（H * A * dt * c）; y = 12 + 15 * D *（H * A * c + t * d）; o = x + 80 * y; N = 8 *（（g * aG * h * e）* dG * h * ag * eH * h * c）; if（22 y＆amp; y＆gt; 0 amp＆amp; x＆gt; 0＆amp; 80 80 x＆amp; D＆gt; z [o]）{z [o] = D; b [o] =（N> 0？N：0）[＆＃34;。，-〜：; =！*＃$ @＆＃34;];} R（.02，H，G）; } R（.07，h，g）;} for（k = 0; 1761＆gt; k; k ++）putchar（k％80？b [k]：10）; R（.04，e，a）; R（ .02，d，c）; usleep（15000）; printf（＆＃39; \ n＆＃39; +（＆＃34; donut.c！\ x1b [23A＆＃34;））;}} / *无数学运算lib需要。@ a1k0n 2021。* /

它有些变形，但在底部仍然有评论。我将其输出的第一帧用作模板，并且代码比filledpixels略少-哦，很好。输出与以前几乎相同：

那么，如何在不使用正弦和余弦的情况下得到正弦和余弦呢？嗯，代码本身并不需要真正的正弦和余弦。它实际上所做的是在两个嵌套循环中绕原点旋转一个点，并且还仅为动画旋转了两个角度。如果您还记得另一篇文章，那么内部循环就是在一个圆上绘制点，该圆围绕另一个更大的圆。在每个循环中，正弦/余弦项仅以一个小的固定角度移动。

因此，我们根本不需要跟踪角度，只需要从cos = 1，sin = 0开始，然后绕原点旋转一个圆，即可生成所需的所有正弦和余弦。我们只需要重复应用固定的旋转矩阵：

\ [\ begin {bmatrix} c＆＃39; \\ s＆＃39; end {bmatrix} = \ begin {bmatrix} \ cos \ theta＆amp; -\ sin \ theta \\\ sin \ theta＆amp; \ cos \ theta \ end {bmatrix} \ begin {bmatrix} c \\ s \ end {bmatrix} \]因此，例如，如果我们在内部循环中使用.02弧度的角度，则看起来像：

浮点c = 1，s = 0; // c表示cos，s表示sin（int i = 0; i＆lt; 314; i ++）{// 314 * .02〜=2π//（在代码中使用c，s）float newc = 0。 9998 * c-0。 01 9998666 * s; s = 0。 01 9998666 * c + 0。 9998 * s; c = newc; }

那行得通，但是存在一个问题：无论我们定义常量的精度如何，在重复执行此过程之后，\（\ left（c，s \ right）\）向量的大小都会随着时间呈指数增长或缩小。如果只需要在循环中绕过一遍，也许我们可以避免这种情况，但是如果我们必须绕过一遍（对于旋转动画，则需要这样做），则需要修复该问题。

最简单的方法是将\（c \）和\（s \）乘以\（1 / \ sqrt {c ^ 2 + s ^ 2} \），但是我们回到使用数学再次图书馆。取而代之的是，我们可以利用这样一个事实，即我们的幅度开始时非常接近1，并且我们要迭代此过程：我们可以在每次旋转之后执行一个牛顿步，这足以使幅度“足够接近”到1随着时间的流逝。

我们的目标是找到\（a = c ^ 2 + s ^ 2 \），我们的\（\ left（c，s \ right）\）向量幅值的倒数平方根（soundfamiliar？）。假设我们定义了一个函数\（f（x）= \ frac {1} {x ^ 2}-a \）。当\（x = \ frac {1} {\ sqrt {a}} \）时，该函数为0。我们可以从x的初始猜测为1开始，执行牛顿迭代以获得x'，它将“更接近” \（\ frac {1} {\ sqrt {a}} \），即要缩放的正确值c和s乘以使其幅度\（c ^ 2 + s ^ 2 \）再次“接近” 1。

牛顿步骤定义为\（x＆＃39; = x-\ frac {f（x）} {f＆＃39;（x）} \）。我使用SymPy进行导数和简化，并得出\（x＆＃39; = \ frac {x \ left（3-a x ^ 2 \ right）} {2} \）。由于只执行了一步，因此我们可以为\（x \）插入初始猜测值1，为\（a \）插入后替换\（c ^ 2 + s ^ 2 \）最终得到调整： \（x＆＃39; =（3-c ^ 2-s ^ 2）/ 2 \）。

但是，既然我们不必太担心结果的大小（在限定范围内），我们可以采取另一个捷径（我有了研究旧的CORDIC算法的想法）。如果我们从原始旋转矩阵中除掉余弦，我们得到

\ [\ begin {bmatrix} c＆＃39; \\ s＆＃39; \ end {bmatrix} = \ frac {1} {\ cos \ theta} \ begin {bmatrix} 1＆amp; -\ tan \ theta \\\ tan \ theta＆amp; 1 \ end {bmatrix} \ begin {bmatrix} c \\ s \ end {bmatrix} \]使用触发身份\（\ tan \ theta = \ frac {\ sin \ theta} {\ cos \ theta} \）。由于我们仅处理小角度，因此前导\（\ frac {1} {\ cos \ theta} \）足够接近1，因此我们可以忽略它并让我们的Newtonstep来处理。

现在，我们终于可以理解代码中的旋转方式了。在＃甜甜圈代码的最上方，是我重新定义的#define：

＃定义R（t，x，y）\ f = x; \ x-= t * y; \ y + = t * f; \ f =（3-x * x-y * y）/ 2; \ x * = f; \ y * = f;

这将对单位矢量x，y进行就地旋转，其中t是\（\ tan \ theta \）。 f是一个临时变量；前三行在x，y上执行“矩阵乘法”。然后重新使用f进行幅度调整，最后将x和y乘以f，将它们移回到单位圆上。

进行完该操作后，我只用它们的正弦和余弦替换了所有角度，然后运行旋转运算符R（）而不是调用sin / cos，否则代码是相同的。

我们可以对整数定点算法使用完全相同的想法，而不使用任何浮点数学。我已经以10位精度重做了所有数学运算，并产生了以下C代码，这些代码在嵌入式设备上可以很好地运行，这些设备可以进行32位乘法并具有约4k的可用RAM：

#include＆lt; stdio.h＆gt; #include＆lt; string.h＆gt; #include＆lt; unistd.h＆gt; ＃定义R（mul，shift，x，y）\ _ = x; \ x-= mul * y＆gt;＆gt; shift; \ y + = mul * _＆gt;＆gt; shift; \ _ = 3145728-x * x-y * y＆gt;＆gt; 11; \ x = x * _＆gt;＆gt; 10; \ y = y * _＆gt;＆gt;＆gt;＆gt;＆gt;＆gt;＆gt; 10;字符b [1760]，z [1760]； void main（）{int sA = 1024，cA = 0，sB = 1024，cB = 0，_; for（;;）{memset（b，32，1760）; //文本缓冲区memset（z，127，1760）; // z buffer int sj = 0，cj = 1024;对于（int j = 0; j 10）+ x2）-ci *（cj * sB＆gt; 10）＆gt; 10）-x5＆gt; 7； int o = x + 80 * y; char zz =（x6-K2）＆gt; 15； if（22＆gt; y＆amp; y＆gt; 0＆amp; x＆gt; 0＆amp;＆amp; 80＆gt; x＆amp; zz＆lt; z＆lt; z [o]）{z [o] = zz; b [o] =＆＃34;。，-〜：; =！*＃$ @＆＃34; [N＆gt; 0？ N：0]； } R（5，8，ci，si）//旋转i} R（9，7，cj，sj）//旋转j} for（int k = 0; 1761> k; k ++）putchar（k ％80？b [k]：10）; R（5，7，cA，sA）; R（5，8，cB，sB）;睡着了（15000）; printf（＆＃34; \ x1b [23A＆＃34;）; }}