月份: 2016-03

3 逗还是 4 逗?

为方便位数较长的数字,我们经常会加上一些逗号或者故意在若干位数之间加大间隙以方便阅读。比如:

8326cffc1e178a82fd70f340f303738da877e886

100万亿元津巴布韦币

这里的 100 万亿尽管没有直接加逗号『,』,但在每三位数字之间加大了间隙,所以如果学过英语,就可以比较方便地数出  Thousand, Million, Billion, Trillion 四级单位,所以这张钱是 One hundred trillion dollars。

但这是使用英语度量衡的国家,他们的语言以千为一级,所以以 3 位一级标比较方便,而中文是以 4 位一级的,这意味着在数数量级单位时,我们的思维变成了『千,百万,十亿,万亿』,于是得到『一百万亿』这个表达。

在汉语语系下,这个划分并不方便。直观的显然应该是 4 位一级,也就是『万,亿,万亿,兆,…… 』下去。比如:

三位一级:100,000,000,000,000

四位一级:100,0000,0000,0000

看起来显然是 4 位一级更直观。

接下来又到了是民族还是世界的争论,我认为在这种鸡毛蒜皮的『3 逗还是 4 逗』问题上,以下的见解是可以达成一致的:

  1. 这个标记本来就是辅助阅读用的小改进。除了它应当承担的用途外, 不承担别的用途。
  2. 无论 3 逗还是 4 逗,即使不熟悉的人,阅读起来也并不会造成障碍。本来这就是个辅助阅读的事情,辅助不了就当它不存在。
  3. 对于相应语言体系下的人,只有熟悉的分法才有较好的辅助作用。

所以我的结论是,如果作者和可以预知到的读者群体,都更熟悉 4 逗的话,那么相应的文字应该以 4 逗优先。反之 3 逗优先。假如某种文化是 5 位一个数量级的话,他们的出版物显然应该以 5 逗优先。如果作者与读者群的习惯不一致并且可以预期这种不一致的话,我觉得应该以读者优先。如果不可预知,那就是看作者个人习惯了。

于是,在我的博客和我可能的译作(英译中)的相关文字里,我都会尽量以 4 位为大数划分数量级。而若写的是英文博客的话,则会以 3 位划分。

说白了这就是个习惯问题,中文环境中并不需要强求以 3 位划分为准,4 位更习惯就用 4 位吧。

据我所知日语也是 4 位一级单位的,那么想必中国周边受中华文化影响的应该都是 4 位,大概。

 

Excel 计算缺陷与大数计算

Excel 很多时候可以当作一个简易的数学计算程序,代替 Mathematica 或者 Matlab 之类的专业软件进行一些不算太复杂的数值运算。但 Excel 的数据处理存在很多弱项,在遇到时需要相应作一些处理。

问题一:有效位数大约只有 15-16 位,更多的位数只会用 0 填充了。

1

精确计算的 2n 的尾数不会是 0,始终是 2→4→8→6→2…… 的循环,但从截图上可以看到,Excel 在计算 250 时,就遇到了有效位数问题,使得末尾出现了数字0。

关于问题一的应对:

从例子中可以看到,Excel 提供了 15 位的精度,这意味在在『千万亿』这个级别上 Excel 依然可以进行精确的计算。相当于以小数点后 4 位精度,即 0.0001 元 = 0.01 分 的精度下,处理九千亿人民币以下的财务数据。处理全国 GDP 的数据也可以精确到分,以米为精度可以让光跑一个月,以毫秒为精度覆盖三万多年。

但是如果你真觉得不够,就需要自己用公式实现进位,使用多个单元格作为『数字段』,来确保每个单元格内的数字长度不超过 15 位。

以 2为例,其计算由两部分组成:

最右一列公式为:

其中,Right 函数保证每个单元格只取结果的最右 12 位,让精度始终符合 15 位上限的要求。而 Text() 函数则保证当截取 12 位数字时,不会将原来在中间位置的 0 因为截取而成为首位 0 消失掉。例如,263 =  461,1686,0092,1369,3952,当截取 12 位时,会获得0092,1369,3952,如果不通过 Text() 函数保存首位的 0,则最后合并回去时就会产生错误。

左边每一列的公式均为:

这个公式同时适用于左边任意多列,使得只要电脑性能过关,尽可用尽 Excel  的所有列(一共 16384 列)。

公式略复杂,以 Y2 为例:

最外层 Text() 依然是为了保留首位 0。Value(Left()) 用于提取右边列的进位数字,即当前列的右侧列如果出现超过 12 位的数字时,则截取头部进到本列。Iferror() 用于检测是否进位。将进位数字和本列上一行数据乘二的结果相加后,再检测是否本列也多于 12 位,如果多则截取。公式引用关系如下:

I9N46D5M6%U}E@8IXWXS8CU

使用类似思想,可以精确进行一次数值变化不超过 1014 的大部分大数计算。需要注意的是,假如一次数值变化较大,则每单元格所能保留的位数就相应变小,不一定是 12 位了。

应对问题一的要点有二, 一是自行实行截取与进位,二是利用 Text() 公式特性,保留截断后的首位 0 不丢失。我通常把这种处理办法称为『大数多列化处理』。

 

 

问题二:数值上限大约在 21024-1,由于有效位数限制,实际上限更小一点,大约在 21023+21022+……+2971 ≈ 1.7977e308 左右。

2

这与问题一不同点在于,这个问题不关注精确展开,而更关注公式计算过程中的上限值。当然,使用问题一中的办法也能解决本问题中的部分情况,但对于更大的数字,例如用尽 Excel 所有列(16384列)也写不下的数字,大约 1016384*14 = 10229376,问题一中精确展开的解法就无能为力了。况且在实际展开中,在装满 Excel 前就早早会遇到内存和 CPU 瓶颈了。问题二的解法注重于在有限的计算资源下计算尽可能大的数字。

我们以计算 361 的阶乘为例,如果使用 Excel 公式直接输入 =Fact(361) 则只会得到一个 #NUM! 的结果。意即该计算的值或者计算过程中已经出现了超过 Excel 单元格所能容纳的最大值。

关于问题二的应对:

我们在 Excel 中准备三列数字,A 列为从 1-361 的展开。C1 公式为 =FLOOR.MATH(LOG10(A1)),B1 公式为 =A1/10^C1。

从 C2 起公式为:

从 B2 起公式为:

于是形成如下形式:

1~P8Q1T0%@[@S4J1CS4Y`U9

即 B C 两列形成了类似科学计数法的 b × 10 c 的数列。但不同之处在于,C 列的所有值全部相加,才是整个计算过程的最终解,如图:

EXWL~KE6X(5_2I4BLEN}%E5

即:361! = B361 × 10 SUM(C1:C361) = 1.43792325888489 × 10768,和上一篇博客对照一下,结果还是很精确的。

仔细观察 B、C 两列数值,其实原理就是每当一个新的 A 乘进来,都对结果作一次科学计数法处理,形成 b × 10 c 结构,确保每一次都有 1<b<10,然后把乘方 c 扔在一边最后再相加。

这一解法的关键在于在计算的每一步都即时处理,避免单元格数字过大而『爆掉』。通过这种方法,Excel 的可计算数域范围从大约 10308 变大到了大约 101,0000,0000,0000,0000,更大的数字则会产生 10 ~1000 倍甚至更大的误差。但如果对 C 列的数字再作问题一解法中的多列化处理,则可计算数上限大约会变成 1010229348 ,这里被迫用了幂的幂。这个数字相当大,并且实际不可能用到。早在这个极限之前,你的电脑内存估计就会挂掉。

 

 

当然,因为有 VBA,Excel 理论上也可以做复杂大数字计算,但考虑到学习成本和应用场景,不如学习 Mathematica 来得方便了。一般使用 Excel 做计算,都仅限于操作单元格和自带公式可以解决的问题。

……数零与进位

最近 AlphaGo 与李世石的人机围棋大赛很火,也蹦出一大波跳梁小丑。你会发现什么热点事件都少不了这种人,总是挡在路上,想不看都不行,比如那个输入法王。我记得上次 SoloLens 它也跳出来大谈 Matrix 来着。

牢骚完毕,这次深夜短篇不是写围棋也不是写计算机的,只说数数,更严格的说,只是数『0』。比如:

围棋棋盘共有 19×19 个点,每个点有『无子』、『黑子』、『白子』三种可能性。不考虑无气提子等特殊情况,则一共有 3^361 种盘面。如果考虑到下子进程,则有 361! 种棋谱。

因为有围棋规则在,实际数字会小一些,但这不是本文重点。这两个数字分别是一个 173 位数和一个 769 位数:

我故意设置了不换行,这样大概能直观地体会这个数字有多大了。(左上角的控制键切换换行与展开)

呼应本文标题的问题来了——这两个数字末尾各有多少个『0』?

你当然可以靠眼力劲儿去数,前者容易看出末尾没有 0,后者大概费些功夫能数出有 88 个 0。当然你也可以使用查找替换,数起来方便些。

但是如果没有事先把总数算出来,又如何数出一个数的末尾有多少个 0 呢?毕竟连乘 300 多次算个 700 多位的数字恐怕是更累的一件事情。能少算就少算点吧。

 

办法是有的,数质因素 5 就可以了。

要注意到,无论多少个数连乘,只有 2×5 才会在末尾添加一个 0。有人说 8×5 也会出 0,4×25 会出两个 0。但 8×5=40=22x2x5,有两个 2 其实浪费掉了。而 4×25 = (2×5)2,本质上正好是两对 2×5 相乘,完全符合之前的设定。又因为在阶乘中,2 作为质因数的出现次数远远超过质因数 5 出的次数。每个偶数都能至少贡献一个质因素 2,而每个 5 个数字才能贡献一或若干个质因数 5。因此可得结论:

只要数清连乘中一共有多少个质因数 5,就知道最终数字末尾有多少个 0 了。

对于 3^361,显然一个质因数 5 都没有。所以末尾没有 0。

对于 361!,

  • 每隔 5 个数字,可以提供一个 5。即 5, 10, 15, 20, 25, 30, ……, 360。一共 361 / 5 向下取整,有 72 个。
  • 每隔 25 个数字,可以一次提供两个 5。即 25, 50, 75, ……。一共 361 / 25 向下取整,有 14 个。由于上一条已经重复计算一次,因此这里的 14 不必再翻倍了。
  • 每隔 125 个数字,可以一次提供三个 5。即 125, 250。一共 361 / 125 向下取整,有 2 个。由于上一条已经重复计算一次,因此这里的 2 不必再翻倍了。

再上去是 625,直接超了。于是数 5 活动就此停止。

一共有 72+14+2=88,而 2 的数量肯定是足够的,于是会产生 88 组 2×5,即末尾有 88 个『0』。

这个方法可以广泛用于各类无聊的数 0 活动中,例如:

任取一个足够大的数字 N,比如 10100 即 1 googol,把小于 N 的所有素数乘起来,那么多素数的乘积的末尾有几个 0?

——答案是只有一个 0,算对了么?

 

那么第二个问题来了,为什么数 5 知 0?

答案是,这个和 10 进制有关。

仔细思考,『进制』的本义就是每满多少就 归 0 进位。换句话说,如果 要让末尾为 0,就必须不多不少,最末尾那些余量恰恰等于当前进制。这个 『余量』不是严谨的用词,意会即可。在 10 进制里,你总要正好凑出 10 个或者 10 的倍数个,才能让末尾是 0。在 8 进制里就要凑 8 的倍数个让末尾是 0。16 进制凑 16,N 进制凑 N。

所以归根结底,要让若干个数连乘得到末尾零,就是看能凑出几份当前进制。10 进制就是要凑 2×5,8 进制要凑 2x2x2,每三份质因数 2 会多一位尾 0,只看 2,别的都没用。

既然 10 进制下,10 的唯一质因数分解就是 2×5,而 2 又远多于 5,所以数 5 知 0 就变成了最简单的办法。

理解了这些,下面这些问题也不难回答了:

3361在 3 进制下,末尾有几个 0?

答案是 361 个 0。这个问题等效于 10 进制下 10361末尾有几个 0,等效于 N 进制下 N361末尾有几个 0。——都是361个。

21024在 16 进制下,末尾有几个 0?

答案是 256 个。因为 16 = 24,1024 / 4 = 256。

最后一个问题:

31024在 2 进制下,末尾有几个 0?

 

HTML5 <audio> 粗考

HTML 5 提供的 <audio> 给了前端相当多的方便,不再需要 js 库和 swf 作为播放器。但是新带来的坑也是坑得我要死要活的。

这是 W3School 提供的一张简表:

Browser MP3 Wav Ogg
Internet Explorer YES NO NO
Chrome YES YES YES
Firefox YES YES YES
Safari YES YES NO
Opera YES YES YES

信了你就掉坑了。

HTML5 的 <audio> 有着比看起来的大得多的坑。主要在于各浏览器的实现上有区别,自带的音频解码器各有不同,导致实际支持的格式各有不一。

并且,在宣称支持的格式里,各浏览器也只支持其中一部分编码格式。例如:

Firefox、Chrome 可以正常播放 Microsoft PCM, 16 bit, mono 8000 Hz 的wav,但是无法播放 GSM 6.10, mono 8000 Hz 的wav

以及来自于 这篇文章 的:

Playing MP3 files in Firefox is actually OS/hardware dependent. That’s right, instead of using a built in, true native support, we have to rely on outside variables that we have no control over. Kind of defeats the purpose of that whole no extensions, native support thing that HTML5 is good for. Yes, this is to avoid patent issues (and so Mozilla doesn’t have to pay licensing fees). If you are serving to a lucky person below, here’s the real MP3 support for Firefox:

  • Windows 7+ (Firefox 21.0)
  • Windows Vista (Firefox 22.0)
  • Android (Firefox 20.0)
  • Firefox OS (Firefox 15.0)
  • OS X 10.7 (Firefox 22.0)

大意是 Firefox  的 MP3 播放支持其实是依赖于系统和硬件的,这样可以免去专利费。相应的,支持列表就变得有点复杂了。

这里有几个测试页, 可以大致用来测试主流浏览器的音频文件支持情况,但是也不完全。就如上文所述,Chrome 对 wav 文件只能说部分支持。

测试页一:http://hpr.dogphilosophy.net/test/

测试页二:https://html5test.com/

所以在实际测试中,某浏览器播放不了指定音频有两种可能性:

  • 音频格式不支持
  • 音频编码格式不支持

对于相关的编码格式,大致查了一下,列表如下:

OGG

同样后缀名为 .ogg 的音频文件,可能有以下几种编码格式: Vorbis, speex, OggPCM, FLAC,其中,Vorbis 是被建议的。

WAV

.wav 文件通常被理解为原始采样,未经压缩。但其实并不一定如此。最广泛标准的 .wav 文件是指微软 PCM 编码的音频文件(其实也已经编码过了,毕竟从模拟信号转数字信号无论如何都会有一个采样过程。)PCM 细分又可分为定长(16bit、32bit 等)和浮点两类。另外.wav 还可能是 GSM 编码格式,这种格式广泛使用于通讯网络,但在互联网上并不常用,最有可能的来源是电话录音导入电脑。

MP3

MP3 规范并没有详细规定如何编码,但却有细致的解码定义。也就是说『符合这一类规范的才叫 MP3』。因此,MP3 的格式反而才是最一致的,除了采样率、变长/定长和声道数量外,不存在其它变化。

Opus

Opus 是设计为同时包含音频和视频的编码格式。* 可以取代复杂的编码后封装方案。但实际上普及率很低,支持也不好。

AAC

AAC (Advanced Audio Coding)主要是得到了苹果的支持。但除此以外,在互联网的使用并不广泛。

Mozilla 提供了另一张更为详细的表格:(注意这个表还是只能作为参考)

Feature Chrome Firefox (Gecko) Internet Explorer Opera Safari
Basic support 3.0 3.5 (1.9.1) 9.0 10.50 3.1
<audio>: PCM in WAVE (Yes) 3.5 (1.9.1) Not supported 10.50 3.1
<audio>: Vorbis in WebM (Yes) 4.0 (2.0) Not supported 10.60 3.1
<audio>: Streaming Vorbis in WebM via MSE ? 36.0 (36.0) ? ? ?
<audio>: Vorbis in Ogg (Yes) 3.5 (1.9.1) Not supported 10.50 Not supported
<audio>: MP3 (Yes) (Yes) 9.0 (Yes) 3.1
<audio>: MP3 in MP4 ? ? ? ? (Yes)
<audio>: AAC in MP4 (Yes) (Yes) 9.0 (Yes) 3.1
<audio>: Opus in Ogg 27.0 15.0 (15.0) ? ? ?
<video>: VP8 and Vorbis in WebM 6.0 4.0 (2.0) 9.0 10.60 3.1
<video>: VP9 and Opus in WebM 29.0 28.0 (28.0) ? (Yes) ?
<video>: Streaming VP9 and Opus/VP8 and Opus in WebM via MSE ? 36.0 (36.0) ? ? ?
<video>: Theora and Vorbis in Ogg (Yes) 3.5 (1.9.1) Not supported 10.50 Not supported
<video>: H.264 and MP3 in MP4 (Yes) (Yes) 9.0 (Yes) (Yes)
<video>: H.264 and AAC in MP4 (Yes) (Yes) 9.0 (Yes) 3.1
any other format Not supported Not supported Not supported Not supported 3.1

 

所以解决方案大概就是先通过测试确定一两种被绝大部分浏览器支持的音频编码格式,然后服务器后端将音频文件转码为这一到两种适用的音频格式再传递给前端。

看起来最通用的是 MP3?简单地说,是的。但要注意的是不是任意一种 mp3 编码格式都支持,最优化编码的 VBR 支持性就存疑。同时,由于 Firefox 的 MP3 支持是基于系统的,所以假如 Ubuntu 没有安装 ubuntu-restricted-extra 包也可能出现支持性问题。

 

* 附:

更复杂的是 <video> 标签,由于视频通常是包含声音和图像两部分的,因此实际上视频文件数据是由已经编码的视频数据和已经编码的音频数据,再次进行数据交错编制而成的。因此除 编码格式 外,又衍伸出 封装格式 的概念。深受大家喜爱的 .avi 格式,即 Audio Video Interleave 的简写,就是一种封装格式。当你使用 avi 封装器折开文件后,就会见到一个无声的视频文件和一个无图像的音频文件。至于各自的编码格式又五花八门了。因此对于 <video> 标签的支持更加混乱,几乎必然需要通过服务器转码才能确保在尽可能多的浏览器上前端一致,这也是各视频网站为什么会有大量集群转码处理用户上传的视频的原因。