主题：快速浮点数转换（Fast conversion from floating-point numbers）

• 内容涉及：
  • Neri 公式（Neri’s equation）
  • Neri-Schneider 算法（Neri-Schneider algorithms）
  • Neri 的技巧（Neri’s hack）

核心算法：Neri 的 hack

提供 C++ 代码：

uint64_t next_dyck_word(uint64_t w) { 
    uint64_t a = w & -w; 
    uint64_t b = w + a; 
    uint64_t c = w ^ b; 
             c = (c / a >> 2) + 1; 
             c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b; 
    return c; 
} 

理解

1. 函数目的：

• next_dyck_word 生成下一个 Dyck word（二进制括号序列的编码）。
• Dyck word 通常用于组合数学，如生成平衡括号、Catalan 数列问题。
• 输入 $w$ 是当前 Dyck word（二进制表示）。

2. 算法步骤解析：

Step 1：计算最右侧 1 位

uint64_t a = w & -w;

• $a$ 是 $w$ 中最右边的 1（Least Significant 1 Bit）。
• 原理：
  • 对于二进制数 $w$，-w 取补码，再 & 运算即可得到最右侧 1。
• 公式形式：
  $$a=w\&(-w)$$

Step 2：生成中间变量 b

uint64_t b = w + a;

• $b$ 用于生成下一个 Dyck word 的基础。
• 将最右侧 1 进位到左边。

Step 3：生成 c 并处理位翻转

uint64_t c = w ^ b;
c = (c / a >> 2) + 1;
c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;

• $c = w ^ b$：异或操作标记变化位。
• c / a >> 2：调整位序（右移 2 位并除以 a）。
• (c * c - 1) & 0xaaaaaaaaaaaaaaaa：通过掩码操作生成下一个合法 Dyck word。
• 最后用 | b 合并前缀，得到完整的下一个 Dyck word。

3. 核心思想：

• 使用 位操作 快速生成序列。
• 完全避免循环或递归。
• 高效生成组合数学序列，非常适合算法竞赛或 SIMD 优化场景。

4. 总结：

• 艺术比喻：
  • Hercules 屠九头蛇 = 解决看似复杂的 C++ 构建和依赖问题。
  • 每一个“头”可以逐步解决（类似前述 10 个问题及解决方案）。
• 算法示例：
  • Dyck word 生成用 Neri hack 展示了“用聪明技巧处理复杂问题”，强调位运算和数学公式的重要性。
• 公式概念：
  $$a=w\&(-w),b=w+a,c=((c/a>>2)+1{)}^2\&0xaaaaaaaaaaaaaaaa|b$$

示例：8 位 Dyck word

假设当前 Dyck word 为：
$$w=0b00111000$$

• 这个 Dyck word 对应的括号序列为 (()()) 的简化二进制表示（1 表示左括号，0 表示右括号）。
• 我们希望通过 next_dyck_word(w) 生成下一个 Dyck word。

Step 1：计算最右侧 1 位

uint64_t a = w & -w;

• $w=0b00111000$
• $-w=0b11001000$（取补码）
• $a=w\&-w=0b00001000$
  解释：最右侧 1 位位于第 4 位（从右数）。

Step 2：计算 b

uint64_t b = w + a;

• $b=0b00111000+0b00001000=0b01000000$
  解释：把最右侧 1 位进位到左边。

Step 3：计算 c

uint64_t c = w ^ b;
c = (c / a >> 2) + 1;
c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;

逐步解析：

1. 异或：
   $$c=w\oplus b=0b00111000\oplus 0b01000000=0b01111000$$
2. 除以 a 并右移 2：
   $$c/a=0b01111000/0b00001000=0b00000111$$
   $$(c/a)>>2=0b00000111>>2=0b00000001$$
3. 加 1：
   $$c=0b00000001+1=0b00000010$$
4. 平方减 1 并掩码：
   $$(c\ast c-1)=0b00000010\ast 0b00000010-1=3=0b00000011$$
   $$(c\ast c-1)\&0xAA=0b00000011\&0b10101010=0b00000010$$
5. 与 b 合并：
   $$next=c|b=0b00000010|0b01000000=0b01000010$$

结果

• 输入：0b00111000
• 输出：0b01000010
  这个就是下一个 Dyck word（二进制括号序列）了。

总结

• Neri hack 利用 位操作和数学公式 高效生成下一个 Dyck word。
• 核心步骤：
  1. 找最右边的 1 位（a）
  2. 生成前缀进位（b）
  3. 用异或、位移和掩码生成后缀（c）
  4. 合并得到最终结果

Dyck Word 的定义

Dyck word 是组合数学中的一个概念，用于表示平衡括号序列或者合法的括号嵌套。

• 它是一个二进制字符串，由 1 和 0 构成。
  • 1 表示左括号 (
  • 0 表示右括号 )
• 条件：
  1. 字符串中 1 的数量 = 0 的数量（括号成对）。
  2. 对任意前缀子串，左括号数量 ≥ 右括号数量（不允许右括号先于左括号出现）。

示例

例 1：4 位 Dyck word

长度为 4（2 对括号）合法的 Dyck words：

Dyck word	括号表示
1100	(())
1010	()()
不合法的：

---

非 Dyck word	原因
1001	第 2 位右括号先于左括号，不合法
1110	左括号多余未闭合，不合法

例 2：6 位 Dyck word（3 对括号）

合法的 Dyck words：

二进制	括号表示
111000	((()))
110100	(()())
110010	(())()
101100	()(())
101010	()()()

Dyck word 的数量由 Catalan 数列 决定
第 n 对括号的合法 Dyck words 数量：
$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$
例如：

• n = 3（3 对括号）：
  $$C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=5$$
  对应上表 5 个合法序列。

应用

Dyck word 不只是括号问题，它在算法和计算机科学中有很多应用：

1. 编译器解析：平衡括号检查
2. 组合生成：Catalan 数列问题
3. 位操作算法：如 Neri hack，用位运算快速生成下一个 Dyck word
4. 数据结构：树的遍历编码、表达式树序列化

1. Neri-Schneider 算法与 Neri’s hack

• 这是用于组合数学/位运算优化的算法，例如生成 Dyck word（平衡括号序列）。
• 核心思想：用位操作快速生成下一个合法序列，无需循环或递归。
• 示例：

uint64_t next_dyck_word(uint64_t w);

• 已在前面的示例中解析。

2. 浮点数快速转换为字符串（π 示例）

目标：把浮点数（如 $\pi \approx 3.141592653589793$）转换为字符串，精度不同方式不同。

方法对比

---

方法	结果	注释
stringstream{} << pi	"3.14159"	默认精度 6 位小数
to_string(pi)	"3.141593"	默认精度 6 位小数（四舍五入）
to_chars(...)	"3.141592653589793"	精确到 double 的最大精度
format("{}", pi)	"3.141592653589793"	C++20 std::format 精确输出

可以看出：不同函数对浮点数字符串化的精度和行为不同，选择方法取决于需求。
参考链接：Godbolt 示例

3. 整数到字符串的转换

• 原理：对整数每位取模和整除。
• 示例代码：

string convert(unsigned int n) { 
    size_t size = number_of_digits(n); 
    string str(size, '\0'); 
    char* p = &str.back(); 
    do { 
        *p = n % 10 + '0'; 
        n /= 10; 
        --p; 
    } while(n); 
    return str; 
}

步骤说明：

1. n % 10 → 得到个位数字
2. n / 10 → 去掉个位
3. 从字符串末尾向前填充
4. 直到数字用完

4. 浮点数最小值 FLT_MIN

• 单精度浮点数最小值：
  $$\text{FLT\_MIN}=2^{-126}\approx 1.1754944\times 10^{-38}$$
• 十进制表示：
  $$0.000\dots 011754943508222875\dots$$
• 位表示：
  • 指数（exponent）：有偏置
  • 尾数（mantissa）：二进制表示有效数字

5. 浮点数表示方法

1. 十进制固定点（Decimal fixed-point）
   • 例如：23.4
   • 拆分为整数部分和小数部分
2. 十进制浮点（Decimal floating-point）
   • 科学计数法表示
   • 有偏指数 + 尾数
   • 示例：
     $$1.234\times 10^3$$
3. 二进制浮点（Binary floating-point）
   • IEEE-754 标准表示
   • Binary16 / Binary32 / Binary64 / Binary128
   • 组成：
     $$(-1{)}^{sign}\times 1.mantissa\times 2^{exponent-bias}$$

6. 总结

• 整数与浮点数转换：
  • 不同方法精度和效率不同
  • 对于浮点数，to_chars 或 format 提供精确表示
• 浮点数表示：
  • 分为指数和尾数（mantissa），并使用有偏指数
• Neri-Schneider 算法：
  • 用位运算高效生成序列
  • 避免循环和递归

1. Binary32 格式概述

IEEE-754 Binary32（单精度浮点数）由 32 位组成：

位段	长度	含义
符号位 (sign)	1 位	0 表示正数，1 表示负数
指数位 (exponent)	8 位	有偏置（bias = 127）
尾数位 (mantissa / fraction)	23 位	小数部分，不包括隐含的 1
浮点数的表示公式为：
$$
(-1)^{sign} \times 1.mantissa \times 2^{exponent - bias}
$$

对于非规格化数（subnormal），隐含的 1 被省略，公式变为：
$$(-1{)}^{sign}\times 0.mantissa\times 2^{1-bias}$$

2. Binary32 各位解析示意

以你提供的示例为基础（这里简化表示）：

符号位: ±   -> 0 表示正数
指数位: 8 位 -> biased exponent (有偏指数)
尾数位: 23 位 -> mantissa (二进制小数)

示意图：

[符号位][指数位(8)][尾数位(23)]
 0     10000010   10110001000000000000000

解析：

1. 符号位：0 → 正数
2. 指数位：10000010 = 130 → 真正指数 = 130 - 127 = 3
3. 尾数位：10110001000000000000000 → 对应二进制小数部分
4. 实际值：
   $$(+1)\times (1+\mathrm{0.101100010...})\times 2^3$$

3. 转换步骤

1. 二进制尾数转十进制小数：
   • 尾数位 = $b_1{b}_2{b}_3...b_{23}$
   • 小数值 = $b_1\cdot 2^{-1}+b_2\cdot 2^{-2}+...+b_{23}\cdot 2^{-23}$
2. 指数解偏置：
   • 有偏指数 = e
   • 真指数 = e - 127
3. 计算浮点值：
   $$value=(-1{)}^{sign}\times (1+mantissa)\times 2^{exponent-127}$$

4. Binary32 示例计算

假设：

• sign = 0
• exponent = 130 → 130 - 127 = 3
• mantissa = 0.10110001 (二进制小数，简化)
  则：

1. 尾数值：
   $$1+0.10110001_2=1+0.6953125=1.6953125$$
2. 乘以 $2^3$：
   $$1.6953125\times 8=13.5625$$

所以这个 Binary32 表示的十进制值 ≈ 13.5625

5. 总结

• Binary32 = 32 位
  • 1 位符号
  • 8 位有偏指数
  • 23 位尾数
• 计算浮点值：
  1. 解析符号
  2. 尾数加上隐含 1
  3. 指数去偏置
  4. 合并得到十进制数

1. 题目回顾

double x = 1.0 / 3.0;
std::print("{}", x);

选项：
(a) 0.3
(b) 0.3333333333333333
© 0.3333333333333334
(d) One third
(e) None of the above
同样还有 float 版本：

float x = 1.f / 3.f;
std::print("{}", x);

选项：
(a) 0.3
(b) 0.33333333
© 0.33333334
(d) One third
(e) None of the above

2. 核心原理

1. 二进制浮点数无法精确表示 1/3

• Binary32 (float, 32 位) 和 Binary64 (double, 64 位) 都是基于 IEEE-754 的二进制浮点表示。
• 1/3 = 0.333… 无限循环小数。
• 二进制浮点数只能截断或四舍五入到有限位数：
  • float (32 位)：尾数 23 位 → 精度约 7 位十进制
  • double (64 位)：尾数 52 位 → 精度约 16 位十进制

2. double 1/3 的近似值

• 二进制存储时，double 的值 ≈
  $$0.333333333333333314829616256247390992939472198486328125$$
• 输出时通常 round 到 16 位十进制 → 0.3333333333333333

3. float 1/3 的近似值

• float 的值 ≈
  $$0.3333333432674407958984375$$
• 输出通常 round 到 8 位十进制 → 0.33333334

3. C++ 输出行为

• std::print("{}", x) 类似 Python format 或 std::format，会根据类型自动选择默认精度：
  • double → 16 位十进制有效数字
  • float → 7-8 位十进制有效数字

4. 正确选项

---

类型	近似值输出	正确选项
double	0.3333333333333333	(b)
float	0.33333334	©

注意：

• 0.3333333333333334 并不是 double 的默认输出值，它是四舍五入后的下一位，但默认精度不会显示这个。
• 0.3 或 “One third” 都不正确。

5. 数学解释

1. double 的二进制形式（IEEE-754）：

• sign = 0
• exponent = 01111111101 (1021) → 真指数 = 1021 - 1023 = -2
• mantissa = 无限二进制 0.0101010101…，截断到 52 位
  公式：
  $$1/3\approx (1+mantissa)\times 2^{-2}\approx 0.3333333333333333$$

2. float 的二进制形式（IEEE-754）：

• sign = 0
• exponent = 01111101 (125) → 真指数 = 125 - 127 = -2
• mantissa = 01010101010101010101010… 截断到 23 位
  公式：
  $$1/3\approx (1+mantissa)\times 2^{-2}\approx 0.33333334$$

6. 总结

• double 输出 → 0.3333333333333333 → 选 (b)
• float 输出 → 0.33333334 → 选 ©
• 二进制浮点数无法精确表示 1/3，所有显示都是近似值。
• C++ 默认输出 使用 IEEE-754 精度截断，且 std::print 遵循 double / float 默认精度。

1. Dragon’s den 背景

这里列出的是 浮点数转十进制的里程碑式算法：

年份	算法/工具	作者
1990	Dragon	Guy L. Steele, Jon L. White
1996	—	Robert G. Burger, R. Kent Dybvig
2010	Grisù	Florian Loitsch
2013	—	Aubrey Jaffer
2016	Errol	Marc Andrysco, Ranjit Jhala, Sorin Lerner
2018	Ryū	Ulf Adams
2020	Schubfach	Raffaello Giulietti
2020	Grisù-Exact	Junekey Jeon
2022	Dragonbox	Junekey Jeon

这些算法都是 高效、无信息丢失地将浮点数转换为十进制字符串 的实现，每一代都在速度、最短表示和精度上有所改进。

2. Dragon 的三步流程

浮点数 → 十进制字符串的通用方法：

1. decode representation
   • 将浮点数拆解成 尾数（mantissa）和指数（exponent）。
   • Binary32: $x=(-1{)}^s\cdot 1.m\cdot 2^{e-127}$
   • Binary64: $x=(-1{)}^s\cdot 1.m\cdot 2^{e-1023}$
2. convert binary to decimal
   • 将二进制指数与尾数转换成十进制近似：
     $$m\cdot 2^E\approx n\cdot 10^F$$
3. convert exponent and mantissa to string
   • 使用规则选择“最短、无信息丢失”的十进制表示：
     • No information loss：输出的字符串解析回浮点数应得到原值
     • As short as possible：尽量短
     • As close as possible：尽量接近真实数值
     • Tiebreak rules：遇到多个表示时选择规则

3. Dragon 的核心思想

• 浮点数 $f=m\cdot 2^E$ 转换成十进制形式 $n\cdot 10^F$
  • 找到最接近原数的整数 $n$ 和指数 $F$
  • 保证解析回去仍是原浮点数
  • 优先：
    1. 不丢失信息
    2. 尽量短
    3. 接近原数
• 示例：
  • $11,184,811\cdot 2^{-25}\approx \mathrm{0.3333333333...}$
    • 可以转换成 $33,333,334\cdot 10^{-8}$
    • 或 $0.33333334$
    • Dragon 算法会选择 最短且不丢失信息 的表示

4. “As short as possible” 举例

• $10,066,330\cdot 2^{-25}$
  • 可转换成多种十进制：
    1. $30,000,002\cdot 10^{-8}$ → 精度过高
    2. $30,000,001\cdot 10^{-8}$ → 精度过高
    3. $30,000,000\cdot 10^{-8}$ → 足够精确
    4. $3\cdot 10^{-1}$ → 最短表示
  • Dragon 算法优先选择最短且精确 → $3\cdot 10^{-1}$

这里体现了 Dragonbox/Ryū/Schubfach 的设计理念：既保证精度，也保证输出最短。

5. 重点总结

1. 解码浮点数 → 得到尾数 + 指数
2. 二进制转十进制近似 → 找到 $n\cdot 10^F$
3. 最短字符串选择 → 满足：
   • 不丢信息
   • 尽量短
   • 尽量接近原数
4. 输出规则示意：
   • 如果尾数是 10 的倍数 → 可进一步缩短表示
   • 优先选择科学计数法或简短小数
   • 避免不必要的多余零

1. 瓜拉尼神话的创世故事

1. 创世神与最初的人类
   • 神 Tupã 与女神 Arasy 创造了最初的人类：
     • Rupave（父）
     • Sypave（母）
2. 善恶之灵
   • Tupã创造了善与恶的灵：
     • Angatupyry：善的精神
     • Taú：恶的精神
3. 第一代后裔
   • Marangatú：Rupave 与 Sypave 的第二个儿子
   • Keraná：Marangatú 的美丽女儿

2. Taú 与 Keraná的故事

1. Taú的爱慕与欺骗
   • Taú爱上了Keraná
   • 化身为英俊青年
   • 打败善灵 Angatupyry
   • 俘获 Keraná
2. 诅咒
   • 女神 Arasy 对 Taú 的七个儿子施加诅咒
   • 他们被生为 可怕的怪物

3. 传说中的七大怪物

1. Tejú Jaguá
   • Taú的第一个被诅咒的儿子
   • 是瓜拉尼神话中的传奇怪物
   • 其象征意义通常与 力量、威胁 相关

这里暗示了 恶的后代变为怪物 的象征性故事。

4. 整体理解

• 神话呈现了 创世 → 善恶分化 → 人类后代 → 惩罚与变异 的连续故事线。
• 善灵 vs 恶灵 的冲突是核心主题。
• Taú的七子 变成怪物体现了：
  1. 恶的延续性
  2. 自然/神灵对人类与超自然行为的惩罚
• 与科学或数学公式结合的部分（如 $n\times 10\approx m\times 2^E$）可能是比喻或后续算法/故事解码的类比，如 Dragonbox 中的浮点数处理方法。

Tejú Jaguá - Ⅰ

Tejú Jaguá 问题本质上是在讨论如何将二进制浮点数 $m\times 2^E$ 精确、紧凑地表示为十进制形式 $n\times 10^F$。

1. 近似关系
   我们希望有：
   $$n\times 10^F\approx m\times 2^E$$
   而在实际操作中，还要考虑：
   $$(m-1)\times 2^E,m\times 2^E,(m+1)\times 2^E$$
   以及在计算过程中要允许一个微小的误差区间。
2. 可允许区间
   设 $u,v$ 为可允许区间的上下界。为了保证一定能找到合适的 $n\times 10^F$，必须满足：
   $$v-u>10^F/2^E$$
   这样就不会出现“跳过”的情况，即没有满足条件的十进制表示。
3. 指数和幂次选择
   为了最短的表示形式，通常选择 $F$ 为最大的整数，使得：
   $$10^F\le 2^E⟹F=\lfloor E{\log }_{10}2\rfloor$$
   这个公式是 Dragonbox 中“关键的龙”的核心公式。

Tejú Jaguá - Ⅱ

这一部分讨论了 n×10^F 的候选点，并介绍了如何用二进制分段定位这些候选：

1. 候选点定义
   对每个 $m\times 2^E$，我们考虑：
   $$(2m-1)\times 2^{E-1},2m\times 2^{E-1},(2m+1)\times 2^{E-1}$$
   这些点用于在十进制范围内寻找可能的 $n\times 10^F$。
2. 下界和上界计算
   定义 $a,b,c$ 为候选的十进制整数倍：
   $$a=\lfloor \frac{(2m-1)\times 2^{E-1}}{10^F}\rfloor ,b=\lfloor \frac{(2m+1)\times 2^{E-1}}{10^F}\rfloor ,c=\lfloor \frac{2m\times 2^{E-1}}{10^F}\rfloor$$
   这样可以在候选范围内快速定位最接近的十进制表示。

Tejú Jaguá - Ⅲ & Ⅴ

这里讲了如何选择最终的最短十进制表示 $s\times 10^F$：

1. 选择规则

• 如果 $s$ 是 10 的倍数，则通常更短、更漂亮。
• 在 $[a,b]$ 区间内选择最接近 $m\times 2^E$ 的 $s\times 10^F$。
• 如果存在平局（tie），使用 minverse 算法检查 $5^F$ 的可整除性决定最终选择。

2. 返回最终结果
   最终可能的候选有：
   $$s\times 10^F,c\times 10^F,(c+1)\times 10^F,b\times 10^F$$
   根据离 $m\times 2^E$ 最近或者最短长度的优先级返回。

Dragon 的细节

核心公式：
$$F=\lfloor E{\log }_{10}2\rfloor \approx \lfloor E\times \mathrm{0.30103...}\rfloor$$

• 对每个指数 $E\in [-112,815,112,815]$ 都可以计算 $F$。
• 计算 $a=\lfloor \frac{m\times N(E)}{10^F}\rfloor$，其中 $N(E)\approx 2\cdot 2^K/2^{E-1}/10^F$，这是预计算表，优化了浮点到十进制的转换。
• 检测平局（ties）可以通过除以 $5^F$ 来快速判断，进一步提高性能。

优化与实现思路

1. 整数优化
   • 所有运算尽量使用整数运算，减少浮点误差。
2. 查表优化
   • 对 $N(E)$ 进行预计算并存储查表。
3. 平局检测
   • 使用 minverse 算法快速判断能否被 $5^F$ 整除。
4. 生成最短字符串
   • 删除尾随零，调整指数，返回最终最短表示。