布朗尼的小屋

Fibonacci 数列的通项公式

发表于 2025-12-04 更新于 2025-12-05

递推公式

Fibonacci 数列的递推公式为：

其中

矩阵表示

上式可以用矩阵表示：

求解方法

令

通过寻找与矩阵相似的对角矩阵，可以利用来得到

通项

特征多项式，令解得特征值

对应的特征向量分别为，得到过渡矩阵及其逆矩阵：

对角矩阵：

由相似变换得到

所以：

所以 Fibonacci 数列的通项公式为：

并行化蒙特卡洛

发表于 2025-12-03 更新于 2025-12-04

测量 CPU 时间

上篇文章写了个简单的蒙特卡洛估计器，用于估计的值，但是那个非常慢，可以通过 System.Diagnostics 提供的 Stopwatch() 方法算一下时间。

var watch = new Stopwatch();

stopwatch.Start();

for (ulong i = 0; i < N; i++)
{
    x = rnd.NextDouble();
    y = rnd.NextDouble();
    if (x * x + y * y <= 1)
    {
        circleCount++;
    }
}
double PI = 4 * (double)circleCount / N;

watch.Stop();

Console.WriteLine("Pi = {0}, time = {1}ms", PI, watch.ElapsedMilliseconds);

设置采样数为 5000000000，得到 Pi = 3.1415527664, time = 37026ms。为了计算这个稳定于 3.1415 以上的结果，花费了 37 秒。

多线程

现代 CPU 具有多个物理核心，可以把它们利用起来。用 ThreadLocal<Random>() 为各个线程单独生成随机数。

using System.Threading;
using System.Threading.Tasks;

void ParallelEst()
{
    // 全局计数器
    long totalCircleCount = 0;

    var watch = new Stopwatch();
    ThreadLocal<Random> threadRnd = new ThreadLocal<Random>(() => new Random(Guid.NewGuid().GetHashCode()));    //各线程通过唯一 GUID 生成哈希值，防止随机样本序列重复

    watch.Start();

    // 循环并行化
    Parallel.For(
        0,
        (long)N,
        () => 0UL,
        (i, loopState, localCount) =>   // i: 当前迭代，localCount: 当前线程的局部计数器
        {
            Random rnd = threadRnd.Value;
            double x = rnd.NextDouble();
            double y = rnd.NextDouble();
    
            if (x * x + y * y <= 1)
            {
                localCount++;
            }
            return localCount; 
        },
        localCount =>  // 累积局部计数器到全局计数器
        {
            Interlocked.Add(ref totalCircleCount, (long)localCount);
        }
    );

    threadRnd.Dispose();

    double PI = 4 * (double)totalCircleCount / N;

    watch.Stop();

    Console.WriteLine("Pi = {0}, time = {1}ms", PI, watch.ElapsedMilliseconds);
}

以下是运行时间：

1 线程	24 线程
36412 ms	6348 ms

多线程的确占用起来了：

踩坑

之前是这么写的，结果并行化反而慢了 10 倍：

void ParallelEst()
{
    ulong circleCount = 0;
    
    var watch = new Stopwatch();
    
    ThreadLocal<Random> threadRnd = new ThreadLocal<Random>(() => new Random(Guid.NewGuid().GetHashCode()));
    
    watch.Start();
    
    Parallel.For(0, (long)N, i =>
    {
        Random rnd = threadRnd.Value;
        double x = rnd.NextDouble();
        double y = rnd.NextDouble();

        if (x * x + y * y <= 1)
        {
            Interlocked.Increment(ref circleCount); // 锁在线程循环里面
        }
    });
    
    threadRnd.Dispose();
    
    double PI = 4 * (double)circleCount / N;
    
    watch.Stop();
    
    Console.WriteLine("Pi = {0}, time = {1}ms", PI, watch.ElapsedMilliseconds);
}

原因是每个线程每次累计一次 circleCount 都要调用一次 Interlocked 方法，导致线程之间产生锁竞争，大幅降低并发性能。

修复方案就是给单个线程分配一个局部的计数器 localCount，等各线程累计结束之后再调用原子操作。

るるちゃんの自殺配信

发表于 2025-12-02

友達ができない帰り道

夕暮れはときどき優しく

飛び交うデータの中で

街のブルートゥースが　あたしを壊した

中央線に飛び込んで　傍迷惑な奴だと言われて

いつだってそこにいたんだ　少女はさっさと死んじゃった

FBIに聞いたって　わかんない彼女のメーセージ

いつだって叫んでたんだって

チャネリングで夜空広げてく

野良猫とワルツを踊った

飛び交うデータの中で

街のブルートゥースがあたしを壊した

UFOに飛び乗って　反抗期じゃないよママ聞いて

いつだって1人でいたんだ　少女はさっさと死んじゃった

FBIに聞いたって　わかんない彼女のメーセージ

いつだって叫んでたんだって

受験勉強が終わったら

ネコと話す魔女さ

自殺配信してお墓でも立てよ

この最低な気持ちなくなる前に

中央線に飛び込んで　傍迷惑な奴だと言われて

いつだってそこにいたんだ　少女はさっさと死んじゃった

屋根の上で猫たちと　頭が悪い人間見下して

いつだって叫んでたんだって

受験勉強が終わったら

ネコと話す魔女さ

自殺配信してお墓でも立てよ

この最低な気持ちなくなる前に

中央線に飛び込んで　傍迷惑な奴だと言われて

いつだってそこにいたんだ　少女はさっさと死んじゃった

FBIに聞いたって　わかんない彼女のメーセージ

いつだって叫んでたんだって

蒙特卡洛方法

发表于 2025-11-30 更新于 2025-12-01

何为蒙特卡洛

其实就是随机采样。蒙特卡洛方法主要用于复杂数值估计，例如核物理方程的数值解（该方法刚被发明出来的时候就是为了解决这个）。现实里还有很多很难找到或者根本找不到解析解的方程（例如计算机图形学的渲染方程），这时候作为数值方法的蒙特卡洛就是求得近似数值解的一种路径。

核心

根据问题域的概率分布反复生成随机数。

例子：估计

是一个无穷级数，我们只能近似估计它。我们可以在此使用蒙特卡洛方法进行估计。

构造一个单位圆。我们只考虑的部分，也就是一个边长为 1 的正方形内部的一个四分之一圆。

设一个点，如果它在圆的内部，则满足

而四分之一圆的面积：，正方形的面积：

所以存在以下关系：

落 在 圆 内 的 点 落 在 正 方 形 内 的 点

所以 $落在圆内的点落在正方形内的点$

C# 实现

正好最近在学 C#，用它来实现一下可以自定义采样数的蒙特卡洛估计器。使用 .NET 自带 Random 类。

class Program
{
    static void Main(string[] args)
    {
        Random rnd = new Random();

        double x, y;

        ulong circleCount = 0;
        
        Console.WriteLine();
        ulong N = Convert.ToUInt64(Console.ReadLine());

        for (ulong i = 0; i < N; i++)
        {
            // 生成随机样本 (x_i, y_i)
            x = rnd.NextDouble();
            y = rnd.NextDouble();

            // 圆内的采样点
            if (x * x + y * y <= 1)
            {
                circleCount++;
            }
        }

        double PI = 4 * (double)circleCount / N;
        
        Console.WriteLine(PI);

    }
}

采样数与收敛

我们可以发现，的精度随采样数的提高而提高。

这在数学上是有解释的，就是样本均值收敛于数学期望，也即概率论学科中大名鼎鼎的大数定律(Law of large numbers)：

名字的由来

蒙特卡洛是摩洛哥的一个著名赌城。

高数

发表于 2025-11-30

高等数学是本科阶段所有工科专业的通识课程。

进入大学后，我遇到了很多高中数学挺好，但高等数学一点都学不明白的人。我感觉有两点原因。

教材设计不太贴合工科需求

如果你阅读过类似普林斯顿微积分读本的数学书，其实可以发现它的讲法非常易懂，只要上过高一上期的数学课都能无痛自学。但是国内的高等数学不一样，它似乎并不是针对工科专业解决问题的刚需设计的，而更像一本弱化版的数学分析教材。例如在讲述极限的部分，它有大量的篇幅在叙述语言的数学证明，而没有一开始就引导学生关注它的直观概念。

我有一位电子工程专业的朋友接受的是 Maynooth University 的工程数学教育，他们的微积分教材就和国内高数完全不是一个画风。例如，直接在上取变化量和，直接引出微商。要是换成国内的高数教材，还要先给你用分析的语言叙述一下微分的严格定义，再证明这个证明那个的。

这里肯定就有人要批判：“你这种学的根本不叫数学！” 拜托！如果你要“严格性”的话，怎么能直接使用那么多不加定义的长度大小的概念呢？对集合的大小的界定可是发展成了一个叫测度论的数学分支！

高中数学的训练不重视体系化基础

高中数学给人的印象就是用奇技淫巧做一些题。当然高中数学学的东西本身也少，作为对比，日本高中是要学完国内高数上册的大部分知识的。

然而就算是这样，许多人并没有从高中数学得到体系化的思维锻炼，只是得到了一些稀碎的、孤立的知识碎片，以至于网上流传着很多诸如“高中阶段是知识巅峰”这种离谱的论调，因为上了大学就全都忘了。

但是，体系化的，尤其是像数学这么逻辑清晰的知识是最难遗忘的。加上国内高中如此变态的高强度训练，我们可以看出那些训练其实并没有对建立数学体系的认知起到多大帮助。

C# 垃圾回收

发表于 2025-11-30

C 使用 malloc() 进行动态内存空间分配，当那一部分空间不被需要时就得 free() 手动释放。如果没有进行释放，那么就要等程序结束，在此期间就造成了内存泄漏。为了避免这些情况，现代语言有一些自动回收的特性（Garbage Collection）。为了便于以后 s&box 的进一步开发，最近正在学习一点 C#。它当然有一套 GC 机制。

GC 的条件

内存不足。
手动调用了 GC.Collect 方法：

for (int i = 0; i < 10000; i++)
{
    var temp = new object();
}
// 强制触发 GC
GC.Collect();

GC 的机制

GC 先默认堆中的所有对象都是可以回收的，然后再标记哪些对象被引用（它们是可达/活动的），然后清除掉不可达的对象。

GC.Collect() 里面可以有参数，比如 0 就对应 Gen 0。这是因为 Generational GC 的关系。

Gen 0	Gen 1	Gen 2
新创建的(小)	Gen 0 回收后存活的	长期存活的(大)

当 Gen 0 堆中的内存达到某个阈值，则触发 Gen 0 GC，剩下的存活对象进入 Gen 1；如果 Gen 1 的也达到阈值，则触发 Gen 1 GC，并且同时 Gen 0 中的也再次回收一遍，存活的对象全部放入 Gen 2 的堆内存空间；Gen 2 GC 则同时回收 0, 1, 2 三代的。

问题

GC 需要时间

假设在一个大型开放世界游戏内，玩家突然从一个点跑到距离很远的另一个点，那么旧的点周围的资产必须被卸载掉，否则会爆内存。

如果在这期间进行 GC，游戏将面临十分严重的卡顿。解决方法就是黑屏加载，但是这相当影响观感，所以非传统的流式资产传输（Streaming Assets）应运而生，比如在《荒野大镖客：救赎 2》这样的游戏里，使用外挂进行超速飞行，很难感觉到卡顿。

GC 不能释放所有资源

GC 并不能释放非托管的资源，因为回收机制的一个前提就是它要回收的内存被分配在托管堆上。

在 Apple Silicon 上原生运行《雷神之锤 3》

发表于 2025-11-29 更新于 2025-11-30

前置工作

一份在 Windows 平台下载的原版 Quake III Arena 的游戏文件。
在 ioquake3.org/get-it/ 下载一份基于 Universal 2 Build 的 macOS build 文件。
在 ioquake3.org/extras/patch-data 下载一个 zip 文件（将自动解压为 quake3-latest-pk3s 文件夹）。

这两个部分准备好了，就可以正式安装了。

安装

在“应用程序”文件夹中创建一个名为 ioquake3 的文件夹。
将下载的文件（ioquake3.app）移动到刚刚创建的 ioquake3 文件夹内。
把下载的 quake3-latest-pk3s 文件夹内的两个文件夹解压至 ioquake3 文件夹内。
把 Windows 上的 pak0.pk3 资产文件复制下来，并且转移到 mac 上。

进一步配置

运行 ioquake3 进入游戏，它会提示输入 CD-KEY，可以直接回车键跳过。

此时，屏幕分辨率是个问题，并且有人可能还不在全屏模式，需要在控制台调整。id tech 引擎呼出控制台为 ~ 键。

我的 MacBook Air 的分辨率是 2560*1664，所以逐个输入以下指令：

/r_mode -1

/r_customheight 1664

/r_customwidth 2560

应用分辨率，输入：

/vid_restart

并且还需要进入全屏模式，所以需要输入：

/r_fullscreen 1

至此，游戏配置就差不多了。我们还可以在自带的 SYSTEM 设置里设置画质，例如纹理过滤模式、光照模式、几何细节等等。

针对 macOS 26 没有声音的问题

在 macOS 26 上运行具有 OpenAL 音频库的程序存在兼容性问题，于是游戏无法正常播放声音。解决方法也很简单，只需输入以下指令禁用 OpenAL 库并应用：

/s_useOpenAL 0

/snd_restart

蛋疼

发表于 2025-11-29 更新于 2025-11-30

一事无成

我自从进入大学以来，已经过了大半学期。但自己什么都不会。

自卑

我经常会感到沮丧。总是会感觉自己在任何地方都做得很烂，即使别人做的比我还烂，但我也总会觉得别人的烂比我的烂更有含金量。