一尺之槌,日取其半,1075日而竭

今天的故事源自数月前我在 r/learnpython 上回答的一个问题。以下是对该问题的转述:

将 64 位浮点数 1.0 不断除以 2,多少次后恰好变为 0?

x, i = 1.0, 0
while x:
x /= 2.0
i += 1
print(i) # 1075
fn main() {
let mut x = 1.0f64;
let mut i = 0;
while x != 0. {
x /= 2.0;
i += 1;
}
println!("{}", i); // 1075
}
let x = 1,
i = 0
while (x) {
x /= 2
i++
}
console.log(i) // 1075

古语云:“一尺之槌,日取其半,万世不竭”。但很显然,此话不适用于这个问题。浮点数的精度是有限的,当 x / 2 足够小时,浮点数终无法表示,便会得到结果 0。如以上代码所示,循环将终结在第 1075 次。

1075 次。这表明 64 位浮点能表示的最小数在 $2^{-1075}$ 这个量级,再小的数超出了表示范围,也就归于零了。但 1075 这个数很奇怪,它离 1024 很近,但又多出来一些,有零有整的,这是为什么呢?

阅读更多

老生常谈:使用 Cloudflare 自选 IP 加速站点访问

本站此前是依托 Github Pages 搭建的,即静态文件托管于 Github 上,再将自定义域名 i.hsfzxjy.site CNAME 到 hsfzxjy.github.io。这种方案免费是免费,但国内的访问速度不甚良好,有几个省甚至出现了超时的现象。为了优化访问,本站现将静态文件迁移至 Cloudflare Pages 上,并使用 Cloudflare 的自选 IP 加速访问。

阅读更多

将 Base64 编码的数据快速转换为 Uint8Array

为了方便节省请求数,有时我们会将二进制数据以 Base64 编码的形式嵌入 HTML 或 JavaScript 中,再于运行时解码成 Uint8Array,进行后续运算。然而浏览器没有提供直接的 API 来完成这种解码转换,需要我们自己实现。本文介绍两种快速的解码方法。

阅读更多

阅读更多

阅读更多

新增域名 monad.run

本站将新增一个域名 monad.run,此后旧域名 i.hsfzxjy.site 也将继续保留,与新域名共存,二者皆可用于访问。

新增一个辅助域名,主要考虑到旧域名没有元音不好拼读,不利于读者记忆与传播。此前一位 Reddit 用户 u/Aliics 曾就“hsfzxjy”一名评论道

So many people have problems remembering “xkcd”, but you’ve ramped that up to another level with your username.

就是说,我的用户名如著名的漫画网站“xkcd”一样难记。这当然是戏谑之言,但事实确如此。除了不方便记忆,原域名甚至可能让杀软产生误报。如另一位 Reddit 用户 u/sheepdog69 所说,hsfzxjy.site 被 Bitdefender 列为了钓鱼网站。下面有人追评认为此种行为与域名直接相关,但也只是推测。无论如何,这种潜在的影响也是不利的。

那新域名 monad.run 是怎么选取的呢?我有两方面的考虑。其一当然是经济性。域名说到底只是一个工具,为一个自用的域名花太多钱,有些本末倒置。.run 域名价格普遍在每年100元左右,相对较合理。其二是与站点主题相关。本站发布的多是技术内容,域名多少也要和技术相关。而 Monad 是函数式编程中的一个重要概念,了解 Haskell 的读者应该较为熟悉。run 又有“运行”之意,monad.run 便是一个不错的选择。哪怕是不熟悉 Haskell 或是非技术领域的读者,monad 的拼写也与其预期读音高度一致,从而易于记忆,其也不算过于常见的单词,不致落入俗套。

在部署方面,目前仅是将 monad.run 302 跳转为 i.hsfzxjy.site。本来最理想的情况是将二者皆 CNAME 到 GitHub Pages,奈何 GitHub Pages 不支持多重 CNAME,只好用此折衷方案。未来若有更好的解决方案,将会更新这一架构。


CSS 中为特定字符设置不同字体

为追求更好的阅读体验,本站的中文文章采用了混合字体的排版方式。例如在 Windows 环境中,中文字符以 Microsoft Yahei 渲染,而英文字符则使用 Open Sans 渲染。由于 Microsoft Yahei 中也包含英文字符的字形,其在 font-family 中的优先级需排在 Open Sans 后面,从而保证 Open Sans 能够正确渲染英文字符。大致的代码如下:

[lang="zh"] {
font-family: "Open Sans", "Microsoft Yahei", var(--font-fallback);
}

但这种方式有一个问题,即标点符号的字形比较难看。具体而言是弯引号 U+201C U+201D ,它们的字形无论在 Microsoft Yahei 或是 Open Sans 中都是半角宽度,且头部和尾部粗细区分不明显,难以辨别前后。反观宋体 SimSun 的呈现则更为清晰,更符合中文排版的习惯。

阅读更多

Arbitary Lifetime Transmutation via Rust Unsoundness

Do you believe that one can write a function in safe Rust which can arbitrarily change the lifetime of a reference? For clarity, try to implement the following function without using unsafe:

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 { todo!() }

Such intention seems to violate the fundamental principle of Rust’s lifetime system, which is to prevent dangling references and data. However, it is possible to write such a function in safe Rust, and it is not even that hard:

trait Trait {
type Output;
}

impl<T: ?Sized> Trait for T {
type Output = &'static u64;
}

fn foo<'a, T: ?Sized>(x: <T as Trait>::Output) -> &'a u64 { x }

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
foo::<dyn Trait<Output=&'a u64>>(x)
}
阅读更多

Dijkstra 算法的延伸

我们知道 Dijkstra 算法是一个高效的单源最短路径(SSSP)算法,本文将不再赘述他的细节。但同时,Dijkstra 也是一个动态规划算法。Dijkstra 算法的正确性源自无负边权图的若干性质。如果一个问题本身也满足这些性质,那么即使它不是一个图论最短路径问题,也可以使用 Dijkstra 算法解决。那么,这些性质是什么呢?

阅读更多

Manacher 回文计数算法

以下假设字符串下标从 $0$ 开始,子串记号 $s[i..j]$ 左闭右闭。

给定长度为 $n$ 的字符串 $s$,Manacher 算法可以在 $O(n)$ 的时间复杂度内找到 $s$ 的所有回文子串。

我们先以寻找长度为奇数的子串为例。首先需要明确的是,如果 $s$ 中以第 $i$ 个字符为中心的最长回文子串长度为 $d=2p+1$,则以下皆为 $s$ 的回文子串:

$$s[i-(p-1)..i+(p-1)],\ldots, s[i-1..i+1], s[i..i]$$

因此,我们只需对所有下标 $i$ 求解出以 $s[i]$ 为中心的最长回文子串长度 $2p_i+1$,即可知道 $s$ 的所有回文子串。

阅读更多