Repair for Distributed Storage Systems with Erasure Channels. (arXiv:1301.7054v1 [cs.IT])

from cs.IT updates on arXiv.org http://arxiv.org/abs/1301.7054

We study the repair problem of distributed storage systems in erasure
networks where the packets transmitted from surviving nodes to the new node
might be lost. The fundamental storage-bandwidth tradeoff is calculated by
multicasting analysis in erasure networks. The optimal tradeoff bound can be
asymptotically achieved when the number of transmission (packets) goes to
infinity. For a limited number of transmission, we study the probability of
successful regenerating. Then, we investigate two approaches of increasing the
probability of successful regenerating, namely, by connecting more surviving
nodes or by increasing the storage space of nodes. Using more nodes may pose
larger delay and in certain situation it might not be possible to connect to
more nodes too. We show that in addition to reducing repair bandwidth,
increasing storage space can also increase reliability for repair.

matplotlib核心剖析

from 博客园_首页 http://www.cnblogs.com/vamei/archive/2013/01/30/2879700.html

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

 

matplotlib是基于Python语言的开源项目,旨在为Python提供一个数据绘图包。我将在这篇文章中介绍matplotlib API的核心对象,并介绍如何使用这些对象来实现绘图。实际上,matplotlib的对象体系严谨而有趣,为使用者提供了巨大的发挥空间。用户在熟悉了核心对象之后,可以轻易的定制图像。matplotlib的对象体系也是计算机图形学的一个优秀范例。即使你不是Python程序员,你也可以从文中了解一些通用的图形绘制原则。

matplotlib使用numpy进行数组运算,并调用一系列其他的Python库来实现硬件交互。matplotlib的核心是一套由对象构成的绘图API。

 

matplotlib项目是由John D. Hunter发起的。John D. Hunter由于癌症于去年过世,但他发为社区作出的无比贡献将永远留存。

John D. Hunter

 

你需要安装Python, numpy和matplotlib。(可以到python.org下载Python编译器。相关Python包的安装,请参看我的Python小技巧)

matplotlib的官网是: http://matplotlib.org/  官网有丰富的图例和文档说明。

matplotlib在github的地址为:https://github.com/matplotlib 欢迎有兴趣的开发者fork。

 

 

函数式绘图

matplotlib是受MATLAB的启发构建的。MATLAB是数据绘图领域广泛使用的语言和工具。MATLAB语言是面向过程的。利用函数的调用,MATLAB中可以轻松的利用一行命令来绘制直线,然后再用一系列的函数调整结果。

matplotlib有一套完全仿照MATLAB的函数形式的绘图接口,在matplotlib.pyplot模块中。这套函数接口方便MATLAB用户过度到matplotlib包。下面,我们调用该模块绘制一条直线。

# a strait line: use pyplot functions

from matplotlib.pyplot import *

plot([0, 1], [0, 1]) # plot a line from (0, 0) to (1, 1)
title(
a strait line)
xlabel(
x value)
ylabel(
y value)
savefig(
demo.jpg)

上面的每一条命令都很简单,你可以从函数名读出该函数所要实现的功能。比如plot为画线,title为增加标题。最终保存的demo.jpg如下:

上面的函数式调用很方便。在Python特殊方法与多范式中,我们已经谈到,Python中的函数式编程是通过封装对象实现的。matplotlib中的函数式调用其实也是如此。matplotlib本质上还是构建对象来构建图像。函数式编程将构建对象的过程封装在函数中,从而让我们觉得很方便。

matplotlib.pyplot中,你还可以找到下面的绘图函数。如果你经常使用数据绘图程序,应该会很熟悉这些图形:

 

 

上面图片的绘图程序如下:

import matplotlib.pyplot as plt

# 1D data
x = [1,2,3,4,5]
y
= [2.3,3.4,1.2,6.6,7.0]

plt.figure(figsize=(12,6))

plt.subplot(231)
plt.plot(x,y)
plt.title(
plot)

plt.subplot(232)
plt.scatter(x, y)
plt.title(
scatter)

plt.subplot(233)
plt.pie(y)
plt.title(
pie)

plt.subplot(234)
plt.bar(x, y)
plt.title(
bar)

# 2D data
import numpy as np
delta
= 0.025
x
= y = np.arange(-3.0, 3.0, delta)
X, Y
= np.meshgrid(x, y)
Z
= Y**2 + X**2

plt.subplot(235)
plt.contour(X,Y,Z)
plt.colorbar()
plt.title(
contour)

# read image
import matplotlib.image as mpimg
img
=mpimg.imread(marvin.jpg)

plt.subplot(236)
plt.imshow(img)
plt.title(
imshow)

plt.savefig(matplot_sample.jpg)

上面用到的marvin.jpg是下图,请保存到当地电脑:

 

函数式编程创造了一个仿真MATLAB的工作环境,并有许多成形的绘图函数。如果只是作为Matplotlib的一般用户(非开发者),pyplot可以满足大部分的需求。

(当然,matplotlib是免费而开源的,MATLAB昂贵而封闭。这是不“仿真”的地方)

 

面向对象编程

尽管函数式绘图很便利,但利用函数式编程会有以下缺点:

1) 增加了一层“函数”调用,降低了效率。

2) 隶属关系被函数掩盖。整个matplotlib包是由一系列有组织有隶属关系的对象构成的。函数掩盖了原有的隶属关系,将事情变得复杂。

3) 细节被函数掩盖。pyplot并不能完全复制对象体系的所有功能,图像的许多细节调中最终还要回到对象。

4) 每件事情都可以有至少两种方式完成,用户很容易混淆。

而对于开发者来说,了解对象是参与到Matplotlib项目的第一步。

 

我们将上面的直线绘图更改为面向对象式(OO, object-oriented)的,为此,我们引入两个类: FigureFigureCanvas。(函数式编程也调用了这些类,只是调用的过程被函数调用所遮掩。)

# object-oriented plot

from matplotlib.figure import Figure
from matplotlib.backends.backend_agg import FigureCanvasAgg as FigureCanvas

fig = Figure()
canvas
= FigureCanvas(fig)
ax
= fig.add_axes([0.1, 0.1, 0.8, 0.8])

line, = ax.plot([0,1], [0,1])
ax.set_title(
a straight line (OO))
ax.set_xlabel(
x value)
ax.set_ylabel(
y value)

canvas.print_figure(demo.jpg)

新的demo.jpg如下:

 

理解对象

上面的例子中,我们至少构建了四个对象: fig, canvas, ax, line。它们分别属于Figure类,FigureCanvas类,Axes类和Line2D类。(使用obj.__class__.__name__来查询对象所属的类)

在深入各个对象之前,我们先来做一个比喻。看下面一个图片:

这个图片是用KTurtle绘制。参看把你的孩子打造成为码农

可以看到,图中有一个房子,房子上有窗户和门,窗户上有条纹,门上有把手,此外图像外还有一只小乌龟。我们所提到的房子,窗户,门,条纹,把手,都可以称其为对象。不同的对象之间有依附关系,比如窗户和门属于房子,而把手属于门。乌龟和房子则是并行的两个对象。此外,整个图像外有一个方框,用来表明可绘图的范围,所有上面提到的元素都依附于该方框。

这就是用面向对象的方式来理解一个图像。事实上,对象是描述图像的最自然的方式,面向对象编程最成功的领域就是在计算机图形方面。

 

我们先来看什么是Figure和Axes对象。在matplotlib中,整个图像为一个Figure对象。在Figure对象中可以包含一个,或者多个Axes对象。每个Axes对象都是一个拥有自己坐标系统的绘图区域。其逻辑关系如下:

转过头来看直线图。整个图像是fig对象。我们的绘图中只有一个坐标系区域,也就是ax。此外还有以下对象。(括号中表示对象的基本类型)

Title为标题。Axis为坐标轴,Label为坐标轴标注。Tick为刻度线,Tick Label为刻度注释。各个对象之间有下面的对象隶属关系:

(yaxis同样有tick, label和tick label,没有画出)

尽管data是数据绘图的关键部分,也就是数据本身的图形化显示,但是必须和xaxis, yaxis, title一起,才能真正构成一个绘图区域axes。一个单纯的,无法读出刻度的线是没有意义的。xaxis, yaxis, title合起来构成了数据的辅助部分(data guide)。

上面元素又包含有多种图形元素。比如说,我们的data对象是一条线(Line2D)。title, tick label和label都是文本(Text),而tick是由短线(Line 2D)和tick label构成,xaxis由坐标轴的线和tick以及label构成,ax由xaxis, yaxis, title, data构成,ax自身又构成了fig的一部分。上面的每个对象,无论是Line2D, Text还是fig,它们都来自于一个叫做Artist的基类。

OO绘图的原程序还有一个canvas对象。它代表了真正进行绘图的后端(backend)。Artist只是在程序逻辑上的绘图,它必须连接后端绘图程序才能真正在屏幕上绘制出来(或者保存为文件)。我们可以将canvas理解为绘图的物理(或者说硬件)实现。

在OO绘图程序中,我们并没有真正看到title, tick, tick label, xaxis, yaxis对象,而是使用ax.set_*的方法间接设置了这些对象。但这些对象是真实存在的,你可以从上层对象中找到其“真身”。比如,fig.axes[0].xaxis就是我们上面途中的xaxis对象。我们可以通过fig -> axes[0] (也就是ax) -> xaxis的顺序找到它。因此,重复我们刚才已经说过的,一个fig就构成了一个完整的图像。对于每个Artist类的对象,都有findobj()方法,来显示该对象所包含的所有下层对象。

 

坐标

坐标是计算机绘图的基础。计算机屏幕是由一个个像素点构成的。想要在屏幕上显示图像,计算机必须告诉屏幕每个像素点上显示什么。所以,最贴近硬件的坐标体系是以像素为单位的坐标体系。我们可以通过具体说明像素位置来标明显示器上的某一点。这叫做显示坐标(display coordinate),以像素为单位。

然而,像素坐标不容易被纳入绘图逻辑。相同的程序,在不同的显示器上就要调整像素值,以保证图像不变形。所以一般情况下,还会有图像坐标数据坐标

图像坐标将一张图的左下角视为原点,将图像的x方向和y方向总长度都看做1。x方向的0.2就是指20%的图像在x方向的总长,y方向0.8的长度指80%的y方向总长。(0.5, 0.5)是图像的中点,(1, 1)指图像的右上角。比如下面的程序,我们在使用add_axes时,传递的参数中,前两个元素为axes的左下角在fig的图像坐标上的位置,后两个元素指axes在fig的图像坐标上x方向和y方向的长度。fig的图像坐标称为Figure坐标,储存在为fig.transFigure

(类似的,每个axes,比如ax1,有属于自己的图像坐标。它以ax1绘图区域总长作为1,称为Axes坐标。也就是ax1.transAxes。(0.5, 0.5)就表示在Axes的中心。Axes坐标和Figure坐标原理相似,只是所用的基准区域不同。)

# object-oriented plot
from matplotlib.figure import Figure
from matplotlib.backends.backend_agg import FigureCanvasAgg as FigureCanvas

fig = Figure()
canvas
= FigureCanvas(fig)

# first axes
ax1 = fig.add_axes([0.1, 0.1, 0.2, 0.2])
line,
= ax1.plot([0,1], [0,1])
ax1.set_title(
ax1)

# second axes
ax2 = fig.add_axes([0.4, 0.3, 0.4, 0.5])
sca
= ax2.scatter([1,3,5],[2,1,2])
ax2.set_title(
ax2)

canvas.print_figure(demo.jpg)

我们在绘图,比如使用plot的时候,绘制了两点间的连线。这两点分别为(0, 0)和(1, 1)。(plot中的第一个表为两个x坐标,第二个表为两个y坐标)。这时使用的坐标系为数据坐标系(ax1.transData)。我们可以通过绘出的坐标轴读出数据坐标的位置。

 

如果绘制的是具体数据,那么数据坐标符合我们的需求。如果绘制的是标题这样的附加信息,那么Axes坐标符合符合我们的需求。如果是整个图像的注解,那么Figure坐标更符合需求。每一个Artist对象都有一个transform属性,用于查询和改变所使用的坐标系统。如果为显示坐标,transform属性为None。

 

深入基础

在上面的例子中,无论是使用plot绘制线,还是scatter绘制散点,它们依然是比较成熟的函数。matplotlib实际上提供了更大的自由度,允许用户以更基础的方式来绘制图形,比如下面,我们绘制一个五边形。

# object-oriented plot

from matplotlib.figure import Figure
from matplotlib.backends.backend_agg import FigureCanvasAgg as FigureCanvas

fig = Figure()
canvas
= FigureCanvas(fig)
ax
= fig.add_axes([0.1, 0.1, 0.8, 0.8])

from matplotlib.path import Path
import matplotlib.patches as patches

verts = [
(0., 0.),
(0.,
1.),
(
0.5, 1.5),
(
1., 1.),
(
1., 0.),
(0., 0.),
]

codes = [Path.MOVETO,
Path.LINETO,
Path.LINETO,
Path.LINETO,
Path.LINETO,
Path.CLOSEPOLY,
]

path = Path(verts, codes)

patch = patches.PathPatch(path, facecolor=coral)
ax.add_patch(patch)
ax.set_xlim(
-0.5,2)
ax.set_ylim(
-0.5,2)

canvas.print_figure(demo.jpg)

在上面的程序中。我们首先确定顶点,然后构建了一个path对象,这个对象实际上就是5个顶点的连线。在codes中,我们先使用MOVETO将画笔移动到起点,然后依次用直线连接(LINETO)(我们也可以用曲线来连线,比如CURVE4,但这里没有用到)。 在path建立了封闭的5边形后,我们在path的基础上构建了patch对象,是一个图形块。patch的背景颜色选为coral。最后,我们将这个patch对象添加到预先准备好的ax上,就完成了整个绘图。

上面的过程中,我们就好像拿着一个画笔的小孩,一步步画出心目中的图画。这就是深入理解matplotlib的魅力所在——创造你自己的数据绘图函数!

(将上面的程序封装到函数中,保留顶点以及其它参数接口,就构成了一个五边形绘图函数。O(∩_∩)O~ 我们也创造了新的“一键绘图”)

 

可以相像,一个plot函数如何用path对象实现。

 

总结

我们已经了解了matplotlib的最重要的方面,它们是:

1) pyplot函数绘图借口

2) 对象如何组合成为图像

3) 坐标系统

希望我的讲解没有消耗完你对matplotlib的兴趣。事实上,matplotlib是发展相当迅猛的绘图包,而它的开放性也让它成为了解计算机图形学的一个好接口。谢谢John D. Hunter。

 

本文链接

High-Rate Regenerating Codes Through Layering. (arXiv:1301.6157v1 [cs.IT])

from cs.IT updates on arXiv.org http://arxiv.org/abs/1301.6157

In this paper, we provide explicit constructions for a class of exact-repair
regenerating codes that possess a layered structure. These regenerating codes
correspond to interior points on the storage-repair-bandwidth tradeoff where
the cut-set bound of network coding is known to be not achievable although it
is known that one can, under functional repair, asymptotically achieve the
bound. The codes presented in this paper compare well in comparison to schemes
that employ space-sharing between MSR and MBR points, and thus provide the
best-known lower bound on file size obtained through explicit construction. The
codes are high-rate and can repair multiple nodes simultaneously. Also, no
computation at helper nodes is required in order to repair a failed node.

物种命名,与灭绝赛跑?

from 果壳网 guokr.com http://www.guokr.com/article/436623/

有许多人悲观地认为,大多数的物种会在被发现之前就灭绝,发现世界上所有的物种是不可能的。这种担心来自于对即将灭绝物种数量的过高估计、令人惊惧的高物种灭绝率,以及对分类学家不断减少的担忧。最近,来自新西兰奥克兰大学(University of Auckland)的马克·科斯特洛(Mark J. Costello)教授及其合作者对此提出了异议,认为这种担心是不必要的。

灭绝速度几何?

对物种灭绝速率的预测层出不穷,许多流行的观点认为,已知的脊椎动物类群的灭绝速率已经逼近地质年代的大灭绝时间。然而,科斯特洛则认为,“当代的物种灭绝速率远没有那么高”。同时,他还指出,“有效的物种保护行动、物种在人为管理的次生生境中的存活、以及‘灭绝债务’(extinction debt),都能够减缓物种的灭绝”。

预测物种的灭绝速率是非常困难的,因为不同生物类群受到的灭绝威胁和灭绝风险程度不同,未来的生境和环境变化也难以估计,而且物种对环境的适应能力也在不断变化。科斯特洛对果壳网谈到:“不同生物类群的灭绝速率和尚未被发现的物种数量差异很大”,“比如,我们如果把两栖类的灭绝速率用于地球上所有的物种,那么物种灭绝速率就会高许多”。物种灭绝速率的预测不能够以一概全。

根据绝大多数的模型预测,物种的灭绝速率都小于每10年5%;文章认为,根据最新的综述,更实际的灭绝速率可能是在0.01%-1%之间。

该综述文章指出,以现在的物种分类能力,在过去10年间每年约命名和描述1.75万个物种,自2006年起速度增长到每年1.8万种。依照此速度,如果地球上有200万物种,那么全球物种将在2040年以前被命名和描述;如果有500万物种,那么2220年以前就能够完成此任务(图1)。如果物种描述速度能够增长到每年2万种,那么2100年就可以提前完成全球物种的命名和描述。

图1 比较在不同的灭绝速率下(每10年0.1%—绿色实线;1%—蓝色短划线;5%—红色虚线),最终会剩下多少物种在灭绝前没有得到描述(假如每年平均描述1.6万种新物种)。供图:Mark J. Costello

 

虽然新物种的发现将越来越难,但随着在未被研究的地区和生物类群上投入的努力,这种不足将能够随之抵消。此外,随着许多数据库和信息共享的普及,公众更加容易获取分类学资讯,业余爱好者也正在对物种发现和分类做出前所未有的贡献。

物种灭绝的速度如果能够达到每10年5%,那么地球上半数的物种都会在150年间灭绝。但是,物种更可能的灭绝速率为每10年小于1%,那么无论物种总数是200万还是800万,物种命名和描述速度都远远超过其灭绝速率。当然,相对于较稳定的物种发现率,实际的物种灭绝速率可能并非线性。

文章作者建议,应该采取实际行动来提高分类效率、增进对物种分类的了解、更好地保护生物多样性。据估计,如果每年投入5-10亿美元来加大全球物种分类的努力,那么有望在50年内完成对所有物种的命名和描述。

物种的发现为何重要?

    正如元素之于化学,粒子之于物理学,物种乃是生物学的根本,认识物种是探索生物学的第一步。只有在物种描述后,对于种群、遗传和生物化学多样性的研究才有可能开展。一份标准的物种名录,对于生物学和生态系统的研究、以及自然资源管理的质量保障十分关键。此外,发现物种也能够帮助我们了解有多少物种、那些物种将会灭绝。

    作者综合多项研究和数据分析,指出现在全球的物种总数估计约有200万到800万(之前有其他估计认为这一数字可高达3000万至1亿,作者认为不太可能)。考虑到有一些物种命名存在重复的可能,现在实际已命名物种已达到150万种。
 

分类学家在不断减少?

科斯特洛指出,越来越多的数据表明,“来自世界各个地区的分类学文章数量在不断增加”(图2),分类学家的数量也在不断增加。然而,可能由于新物种发现的难度越来越大,所以每个分类学家发表的新种平均数有所下降。人们对分类学家数量减少的误解,可能是由于分类学家往往要到他们临近退休是才得以扬名,因此给人一种传统分类学正在衰退的错觉。在那些曾经引领分类学的翘楚之国的翘楚研究机构,分类学家可能是在减少,但是在除了欧洲和北美之外的其他国家和地区,尤其是南美和亚洲,情况却截然不同。

 

 

 

 

 

 

 

图2 ​(左) 新物种发表论文数量的增长:1981-1990 (空白), 1991-2000 (灰色),2001-2010 (黑色)(样本量 n = 10,819, 12,703, 28,596). (右) 北美发表的文章的比例下降,亚洲和拉丁美洲的文章比例上升。

 

文章最后指出,考虑到生物多样性的丧失,也需要考虑到栖息地、物种和自然资源之间的关系,就好比关注人类健康不能不考虑到食物和水的供应、人们生活的质量等等。所有生物与非生物因素都是密切相关的,构成了一个生命之网。

对物种数量和灭绝率的过高估计会形成一种自我打击,使生物多样性的发现和保育看似无望。我们应该更加乐观和积极地看待这个问题,要看到,现在有更多的分类资源正在加快物种发现和描述的速度,也在加强物种的保护。分类学家并非濒临灭绝,反而人丁更加兴旺了起来。文章作者相信,在分类和保育的不断努力下,大部分的物种会被发现并受到保护。

 

 

信息来源:EurekAlert!

参考论文:“Can We Name Earth’s Species Before They Go Extinct,” by M.J. Costello at University of Auckland in Warkworth, New Zealand; R.M. May at University of Oxford in Oxford, UK; N.E. Stork at Griffith University in Brisbane, QLD, Australia.

 

跨越千年的RSA算法

from Matrix67: My Blog http://www.matrix67.com/blog/archives/5100

    数论,数学中的皇冠,最纯粹的数学。早在古希腊时代,人们就开始痴迷地研究数字,沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后,几千年来的数论研究成果突然有了实际的应用,这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》,但受篇幅限制,只有一万字左右的内容。其实,从数论到 RSA 算法,里面的数学之美哪里是一万字能扯完的?在写作的过程中,我查了很多资料,找到了很多漂亮的例子,也积累了很多个人的思考,但最终都因为篇幅原因没有加进《程序员》的文章中。今天,我想重新梳理一下线索,把所有值得分享的内容一次性地呈现在这篇长文中,希望大家会有所收获。需要注意的是,本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释,一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述,可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后,希望大家能够积极指出文章中的缺陷,我会不断地做出修改。

======= 更新记录 =======

2012 年 12 月 15 日:发布全文。
2012 年 12 月 18 日:修改了几处表达。

======== 目录 ========

(一)可公度线段
(二)中国剩余定理
(三)扩展的辗转相除
(四)Fermat 小定理
(五)公钥加密的可能性
(六)RSA 算法


 
 
(一)可公度线段

    Euclid ,中文译作“欧几里得”,古希腊数学家。他用公理化系统的方法归纳整理了当时的几何理论,并写成了伟大的数学著作《几何原本》,因而被后人称作“几何学之父”。有趣的是,《几何原本》一书里并不全讲的几何。全书共有十三卷,第七卷到第十卷所讨论的实际上是数论问题——只不过是以几何的方式来描述的。在《几何原本》中,数的大小用线段的长度来表示,越长的线段就表示越大的数。很多数字与数字之间的简单关系,在《几何原本》中都有对应的几何语言。例如,若数字 a 是数字 b 的整倍数,在《几何原本》中就表达为,长度为 a 的线段可以用长度为 b 的线段来度量。比方说,黑板的长度是 2.7 米,一支铅笔的长度是 18 厘米,你会发现黑板的长度正好等于 15 个铅笔的长度。我们就说,铅笔的长度可以用来度量黑板的长度。如果一张课桌的长度是 117 厘米,那么 6 个铅笔的长度不够课桌长, 7 个铅笔的长度又超过了课桌长,因而我们就无法用铅笔来度量课桌的长度了。哦,当然,实际上课桌长相当于 6.5 个铅笔长,但是铅笔上又没有刻度,我们用铅笔来度量课桌时,怎么知道最终结果是 6.5 个铅笔长呢?因而,只有 a 恰好是 b 的整数倍时,我们才说 b 可以度量 a 。

    给定两条长度不同的线段 a 和 b ,如果能够找到第三条线段 c ,它既可以度量 a ,又可以度量 b ,我们就说 a 和 b 是可公度的( commensurable ,也叫做可通约的), c 就是 a 和 b 的一个公度单位。举个例子: 1 英寸和 1 厘米是可公度的吗?历史上,英寸和厘米的换算关系不断在变,但现在,英寸已经有了一个明确的定义: 1 英寸精确地等于 2.54 厘米。因此,我们可以把 0.2 毫米当作单位长度,它就可以同时用于度量 1 英寸和 1 厘米: 1 英寸将正好等于 127 个单位长度, 1 厘米将正好等于 50 个单位长度。实际上, 0.1 毫米、 0.04 毫米 、 (0.2 / 3) 毫米也都可以用作 1 英寸和 1 厘米的公度单位,不过 0.2 毫米是最大的公度单位。

    等等,我们怎么知道 0.2 毫米是最大的公度单位?更一般地,任意给定两条线段后,我们怎么求出这两条线段的最大公度单位呢?在《几何原本》第七卷的命题 2 当中, Euclid 给出了一种求最大公度单位的通用算法,这就是后来所说的 Euclid 算法。这种方法其实非常直观。假如我们要求线段 a 和线段 b 的最大公度单位,不妨假设 a 比 b 更长。如果 b 正好能度量 a ,那么考虑到 b 当然也能度量它自身,因而 b 就是 a 和 b 的一个公度单位;如果 b 不能度量 a ,这说明 a 的长度等于 b 的某个整倍数,再加上一个零头。我们不妨把这个零头的长度记作 c 。如果有某条线段能够同时度量 b 和 c ,那么它显然也就能度量 a 。也就是说,为了找到 a 和 b 的公度单位,我们只需要去寻找 b 和 c 的公度单位即可。怎样找呢?我们故技重施,看看 c 是否能正好度量 b 。如果 c 正好能度量 b ,c 就是 b 和 c 的公度单位,从而也就是 a 和 b 的公度单位;如果 c 不能度量 b ,那看一看 b 被 c 度量之后剩余的零头,把它记作 d ,然后继续用 d 度量 c ,并不断这样继续下去,直到某一步没有零头了为止。

      

    我们还是来看一个实际的例子吧。让我们试着找出 690 和 2202 的公度单位。显然, 1 是它们的一个公度单位, 2 也是它们的一个公度单位。我们希望用 Euclid 的算法求出它们的最大公度单位。首先,用 690 去度量 2202 ,结果发现 3 个 690 等于 2070 ,度量 2202 时会有一个大小为 132 的零头。接下来,我们用 132 去度量 690 ,这将会产生一个 690 – 132 × 5 = 30 的零头。用 30 去度量 132 ,仍然会有一个大小为 132 – 30 × 4 = 12 零头。再用 12 去度量 30 ,零头为 30 – 12 × 2 = 6 。最后,我们用 6 去度量 12 ,你会发现这回终于没有零头了。因此, 6 就是 6 和 12 的一个公度单位,从而是 12 和 30 的公度单位,从而是 30 和 132 的公度单位,从而是 132 和 690 的公度单位,从而是 690 和 2202 的公度单位。

      

    我们不妨把 Euclid 算法对 a 和 b 进行这番折腾后得到的结果记作 x 。从上面的描述中我们看出, x 确实是 a 和 b 的公度单位。不过,它为什么一定是最大的公度单位呢?为了说明这一点,下面我们来证明,事实上, a 和 b 的任意一个公度单位一定能够度量 x ,从而不会超过 x 。如果某条长为 y 的线段能同时度量 a 和 b ,那么注意到,它能度量 b 就意味着它能度量 b 的任意整倍数,要想让它也能度量 a 的话,只需而且必需让它能够度量 c 。于是, y 也就能够同时度量 b 和 c ,根据同样的道理,这又可以推出 y 一定能度量 d ……因此,最后你会发现, y 一定能度量 x 。

    用现在的话来讲,求两条线段的最大公度单位,实际上就是求两个数的最大公约数——最大的能同时整除这两个数的数。用现在的话来描述 Euclid 算法也会简明得多:假设刚开始的两个数是 a 和 b ,其中 a > b ,那么把 a 除以 b 的余数记作 c ,把 b 除以 c 的余数记作 d ,c 除以 d 余 e , d 除以 e 余 f ,等等等等,不断拿上一步的除数去除以上一步的余数。直到某一次除法余数为 0 了,那么此时的除数就是最终结果。因此, Euclid 算法又有一个形象的名字,叫做“辗转相除法”。

    辗转相除法的效率非常高,刚才大家已经看到了,计算 690 和 2202 的最大公约数时,我们依次得到的余数是 132, 30, 12, 6 ,做第 5 次除法时就除尽了。实际上,我们可以大致估计出辗转相除法的效率。第一次做除法时,我们是用 a 来除以 b ,把余数记作 c 。如果 b 的值不超过 a 的一半,那么 c 更不会超过 a 的一半(因为余数小于除数);如果 b 的值超过了 a 的一半,那么显然 c 直接就等于 a – b ,同样小于 a 的一半。因此,不管怎样, c 都会小于 a 的一半。下一步轮到 b 除以 c ,根据同样的道理,所得的余数 d 会小于 b 的一半。接下来, e 将小于 c 的一半, f 将小于 d 的一半,等等等等。按照这种速度递减下去的话,即使最开始的数是上百位的大数,不到 1000 次除法就会变成一位数(如果算法没有提前结束的话),交给计算机来执行的话保证秒杀。用专业的说法就是,辗转相除法的运算次数是对数级别的。

    很长一段时间里,古希腊人都认为,任意两条线段都是可以公度的,我们只需要做一遍辗转相除便能把这个公度单位给找出来。事实真的如此吗?辗转相除法有可能失效吗?我们至少能想到一种可能:会不会有两条长度关系非常特殊的线段,让辗转相除永远达不到终止的条件,从而根本不能算出一个“最终结果”?注意,线段的长度不一定(也几乎不可能)恰好是整数或者有限小数,它们往往是一些根本不能用有限的方式精确表示出来的数。考虑到这一点,两条线段不可公度完全是有可能的。

    为了让两条线段辗转相除永远除不尽,我们有一种绝妙的构造思路:让线段 a 和 b 的比值恰好等于线段 b 和 c 的比值。这样,辗转相除一次后,两数的关系又回到了起点。今后每一次辗转相除,余数总会占据除数的某个相同的比例,于是永远不会出现除尽的情况。不妨假设一种最为简单的情况,即 a 最多只能包含一个 b 的长度,此时 c 等于 a – b 。解方程 a / b = b / (a – b) 可以得到 a : b = 1 : (√5 – 1) / 2 ,约等于一个大家非常熟悉的比值 1: 0.618 。于是我们马上得出:成黄金比例的两条线段是不可公度的。

      

    更典型的例子则是,正方形的边长和对角线是不可公度的。让我们画个图来说明这一点。如图,我们试着用辗转相除求出边长 AB 和对角线 AC 的最大公度单位。按照规则,第一步我们应该用 AB 去度量 AC ,假设所得的零头是 EC 。下一步,我们应该用 EC 去度量 AB ,或者说用 EC 去度量 BC (反正正方形各边都相等)。让我们以 EC 为边作一个小正方形 CEFG ,容易看出 F 点将正好落在 BC 上,同时三角形 AEF 和三角形 ABF 将会由于 HL 全等。因此, EC = EF = BF 。注意到 BC 上已经有一段 BF 和 EC 是相等的了,因而我们用 EC 去度量 BC 所剩的零头,也就相当于用 EC 去度量 FC 所剩的零头。结果又回到了最初的局面——寻找正方形的边长和对角线的公度单位。因而,辗转相除永远不会结束。线段 AB 的长度和线段 AC 的长度不能公度,它们处于两个不同的世界中。

      

    如果正方形 ABCD 的边长 1 ,正方形的面积也就是 1 。从上图中可以看到,若以对角线 AC 为边做一个大正方形,它的面积就该是 2 。因而, AC 就应该是一个与自身相乘之后恰好等于 2 的数,我们通常把这个数记作 √2 。《几何原本》的第十卷专门研究不可公度量,其中就有一段 1 和 √2 不可公度的证明,但所用的方法不是我们上面讲的这种,而更接近于课本上的证明:设 √2 = p / q ,其中 p / q 已是最简分数,但推着推着就发现,这将意味着 p 和 q 都是偶数,与最简分数的假设矛盾。

    用今天的话来讲, 1 和 √2 不可公度,实际上相当于是说 √2 是无理数。因此,古希腊人发现了无理数,这确实当属不争的事实。奇怪的是,无理数的发现常常会几乎毫无根据地归功于一个史料记载严重不足的古希腊数学家 Hippasus 。根据各种不靠谱的描述, Hippasus 的发现触犯了 Pythagoras (古希腊哲学家)的教条,最后被溺死在了海里。

    可公度线段和不可公度线段的概念与有理数和无理数的概念非常接近,我们甚至可以说明这两个概念是等价的——它们之间有一种很巧妙的等价关系。注意到,即使 a 和 b 本身都是无理数, a 和 b 还是有可能被公度的,例如 a = √2 并且 b = 2 · √2 的时候。不过,有一件事我们可以肯定: a 和 b 的比值一定是一个有理数。事实上,可以证明,线段 a 和 b 是可公度的,当且仅当 a / b 是一个有理数。线段 a 和 b 是可公度的,说明存在一个 c 以及两个整数 m 和 n ,使得 a = m · c ,并且 b = n · c 。于是 a / b = (m · c) / (n · c) = m / n ,这是一个有理数。反过来,如果 a / b 是一个有理数,说明存在整数 m 和 n 使得 a / b = m / n ,等式变形后可得 a / m = b / n ,令这个商为 c ,那么 c 就可以作为 a 和 b 的公度单位。

    有时候,“是否可以公度”的说法甚至比“是否有理”更好一些,因为这是一个相对的概念,不是一个绝对的概念。当我们遇到生活当中的某个物理量时,我们绝不能指着它就说“这是一个有理的量”或者“这是一个无理的量”,我们只能说,以某某某(比如 1 厘米、 1 英寸、 0.2 毫米或者一支铅笔的长度等等)作为单位来衡量时,这是一个有理的量或者无理的量。考虑到所选用的单位长度本身也是由另一个物理量定义出来的(比如 1 米被定义为光在真空中 1 秒走过的路程的 1 / 299792458 ),因而在讨论一个物理量是否是有理数时,我们讨论的其实是两个物理量是否可以被公度。

 
(二)中国剩余定理

    如果两个正整数的最大公约数为 1 ,我们就说这两个数是互质的。这是一个非常重要的概念。如果 a 和 b 互质,这就意味着分数 a / b 已经不能再约分了,意味着 a × b 的棋盘的对角线不会经过中间的任何交叉点,意味着循环长度分别为 a 和 b 的两个周期性事件一同上演,则新的循环长度最短为 a · b 。

      

    最后一点可能需要一些解释。让我们来举些例子。假如有 1 路和 2 路两种公交车,其中 1 路车每 6 分钟一班,2 路车每 8 分钟一班。如果你刚刚错过两路公交车同时出发的壮景,那么下一次再遇到这样的事情是多少分钟之后呢?当然, 6 × 8 = 48 分钟,这是一个正确的答案,此时 1 路公交车正好是第 8 班, 2 路公交车正好是第 6 班。不过,实际上,在第 24 分钟就已经出现了两车再次同发的情况了,此时 1 路车正好是第 4 班, 2 路车正好是第 3 班。但是,如果把例子中的 6 分钟和 8 分钟分别改成 4 分钟和 7 分钟,那么要想等到两车再次同发,等到第 4 × 7 = 28 分钟是必需的。类似的,假如某一首歌的长度正好是 6 分钟,另一首歌的长度正好是 8 分钟,让两首歌各自循环播放, 6 × 8 = 48 分钟之后你听到的“合声”将会重复,但实际上第 24 分钟就已经开始重复了。但若两首歌的长度分别是 4 分钟和 7 分钟,则必需到第 4 × 7 = 28 分钟之后才有重复,循环现象不会提前发生。

    究其原因,其实就是,对于任意两个数,两个数的乘积一定是它们的一个公倍数,但若这两个数互质,则它们的乘积一定是它们的最小公倍数。事实上,我们还能证明一个更强的结论: a 和 b 的最大公约数和最小公倍数的乘积,一定等于 a 和 b 的乘积。在第四节中,我们会给出一个证明。

    很多更复杂的数学现象也都跟互质有关。《孙子算经》卷下第二十六问:“今有物,不知其数。三、三数之,剩二;五、五数之,剩三;七、七数之,剩二。问物几何?答曰:二十三。”翻译过来,就是有一堆东西,三个三个数余 2 ,五个五个数余 3 ,七个七个数余 2 ,问这堆东西有多少个?《孙子算经》给出的答案是 23 个。当然,这个问题还有很多其他的解。由于 105 = 3 × 5 × 7 ,因而 105 这个数被 3 除、被 5 除、被 7 除都能除尽。所以,在 23 的基础上额外加上一个 105 ,得到的 128 也是满足要求的解。当然,我们还可以在 23 的基础上加上 2 个 105 ,加上 3 个 105 ,等等,所得的数都满足要求。除了形如 23 + 105n 的数以外,还有别的解吗?没有了。事实上,不管物体总数除以 3 的余数、除以 5 的余数以及除以 7 的余数分别是多少,在 0 到 104 当中总存在唯一解;在这个解的基础上再加上 105 的整倍数后,可以得到其他所有的正整数解。后人将其表述为“中国剩余定理”:给出 m 个两两互质的整数,它们的乘积为 P ;假设有一个未知数 M ,如果我们已知 M 分别除以这 m 个数所得的余数,那么在 0 到 P – 1 的范围内,我们可以唯一地确定这个 M 。这可以看作是 M 的一个特解。其他所有满足要求的 M ,则正好是那些除以 P 之后余数等于这个特解的数。注意,除数互质的条件是必需的,否则结论就不成立了。比如说,在 0 到 7 的范围内,除以 4 余 1 并且除以 2 也余 1 的数有 2 个,除以 4 余 1 并且除以 2 余 0 的数则一个也没有。

    从某种角度来说,中国剩余定理几乎是显然的。让我们以两个除数的情况为例,来说明中国剩余定理背后的直觉吧。假设两个除数分别是 4 和 7 。下表显示的就是各自然数除以 4 和除以 7 的余数情况,其中 x mod y 表示 x 除以 y 的余数,这个记号后面还会用到。

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
i mod 4 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
i mod 7 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5
i 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
i mod 4 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
i mod 7 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4

    i mod 4 的值显然是以 4 为周期在循环, i mod 7 的值显然是以 7 为周期在循环。由于 4 和 7 是互质的,它们的最小公倍数是 4 × 7 = 28 ,因而 (i mod 4, i mod 7) 的循环周期是 28 ,不会更短。因此,当 i 从 0 增加到 27 时, (i mod 4, i mod 7) 的值始终没有出现重复。但是, (i mod 4, i mod 7) 也就只有 4 × 7 = 28 种不同的取值,因而它们正好既无重复又无遗漏地分给了 0 到 27 之间的数。这说明,每个特定的余数组合都在前 28 项中出现过,并且都只出现过一次。在此之后,余数组合将产生长度为 28 的循环,于是每个特定的余数组合都将会以 28 为周期重复出现。这正是中国剩余定理的内容。

    中国剩余定理有很多漂亮的应用,这里我想说一个我最喜欢的。设想这样一个场景:总部打算把一份秘密文件发送给 5 名特工,但直接把文件原封不动地发给每个人,很难保障安全性。万一有特工背叛或者被捕,把秘密泄露给了敌人怎么办?于是就有了电影和小说中经常出现的情节:把绝密文件拆成 5 份, 5 名特工各自只持有文件的 1/5 。不过,原来的问题并没有彻底解决,我们只能祈祷坏人窃取到的并不是最关键的文件片段。因此,更好的做法是对原文件进行加密,每名特工只持有密码的 1/5 ,这 5 名特工需要同时在场才能获取文件全文。但这也有一个隐患:如果真的有特工被抓了,当坏人们发现只拿到其中一份密码没有任何用处的同时,特工们也会因为少一份密码无法解开全文而烦恼。此时,你或许会想,是否有什么办法能够让特工们仍然可以恢复原文,即使一部分特工被抓住了?换句话说,有没有什么密文发布方式,使得只要 5 个人中半数以上的人在场就可以解开绝密文件?这样的话,坏人必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为 (3, 5) 门限方案,意即 5 个人中至少 3 人在场才能解开密文。

    利用中国剩余定理,我们可以得到一种巧妙的方案。回想中国剩余定理的内容:给定 m 个两两互质的整数,它们的乘积为 P ;假设有一个未知数 M ,如果我们已知 M 分别除以这 m 个数所得的余数,那么在 0 到 P – 1 的范围内,我们可以唯一地确定这个 M 。我们可以想办法构造这样一种情况, n 个数之中任意 m 个的乘积都比 M 大,但是任意 m – 1 个数的乘积就比 M 小。这样,任意 m 个除数就能唯一地确定 M ,但 m – 1 个数就不足以求出 M 来。 Mignotte 门限方案就用到了这样一个思路。我们选取 n 个两两互质的数,使得最小的 m 个数的乘积比最大的 m – 1 个数的乘积还大。例如,在 (3, 5) 门限方案中,我们可以取 53 、 59 、 64 、 67 、 71 这 5 个数,前面 3 个数乘起来得 200128 ,而后面两个数相乘才得 4757 。我们把文件的密码设为一个 4757 和 200128 之间的整数,比如 123456 。分别算出 123456 除以上面那 5 个数的余数,得到 19 、 28 、 0 、 42 、 58 。然后,把 (53, 19) 、 (59, 28) 、 (64, 0) 、 (67, 42) 、 (71, 58) 分别告诉 5 名特工,也就是说特工 1 只知道密码除以 53 余 19 ,特工 2 只知道密码除以 59 余 28 ,等等。这样,根据中国剩余定理,任意 3 名特工碰头后就可以唯一地确定出 123456 ,但根据 2 名特工手中的信息只能得到成百上千个不定解。例如,假设我们知道了 x 除以 59 余 28 ,也知道了 x 除以 67 余 42 ,那么我们只能确定在 0 和 59 × 67 – 1 之间有一个解 913 ,在 913 的基础上加上 59 × 67 的整倍数,可以得到其他满足要求的 x ,而真正的 M 则可以是其中的任意一个数。

    不过,为了让 Mignotte 门限方案真正可行,我们还需要一种根据余数信息反推出 M 的方法。换句话说,我们需要有一种通用的方法,能够回答《孙子算经》中提出的那个问题。我们会在下一节中讲到。

 
(三)扩展的辗转相除

    中国剩余定理是一个很基本的定理。很多数学现象都可以用中国剩余定理来解释。背九九乘法口诀表时,你或许会发现,写下 3 × 1, 3 × 2, …, 3 × 9 ,它们的个位数正好遍历了 1 到 9 所有的情况。 7 的倍数、 9 的倍数也是如此,但 2 、 4 、 5 、 6 、 8 就不行。 3 、 7 、 9 这三个数究竟有什么特别的地方呢?秘密就在于, 3 、 7 、 9 都是和 10 互质的。比如说 3 ,由于 3 和 10 是互质的,那么根据中国剩余定理,在 0 到 29 之间一定有这样一个数,它除以 3 余 0 ,并且除以 10 余 1 。它将会是 3 的某个整倍数,并且个位为 1 。同样的,在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 2 ;在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 3 ……而在 0 到 29 之间,除掉 0 以外, 3 的整倍数正好有 9 个,于是它们的末位就正好既无重复又无遗漏地取遍了 1 到 9 所有的数字。

    这表明,如果 a 和 n 互质,那么 a · x mod n = 1 、 a · x mod n = 2 等所有方程都是有解的。 18 世纪的法国数学家 Étienne Bézout 曾经证明了一个基本上与此等价的定理,这里我们姑且把它叫做“ Bézout 定理”。事实上,我们不但知道上述方程是有解的,还能求出所有满足要求的解来。

    我们不妨花点时间,把方程 a · x mod n = b 和中国剩余定理的关系再理一下。寻找方程 a · x mod n = b 的解,相当于寻找一个 a 的倍数使得它除以 n 余 b ,或者说是寻找一个数 M 同时满足 M mod a = 0 且 M mod n = b 。如果 a 和 n 是互质的,那么根据中国剩余定理,这样的 M 一定存在,并且找到一个这样的 M 之后,在它的基础上加减 a · n 的整倍数,可以得到所有满足要求的 M 。因此,为了解出方程 a · x mod n = b 的所有解,我们也只需要解出方程的某个特解就行了。假如我们找到了方程 a · x mod n = b 中 x 的一个解,在这个解的基础上加上或减去 n 的倍数(相当于在整个被除数 a · x 的基础上加上或者减去 a · n 的倍数,这里的 a · x 就是前面所说的 M ),就能得到所有的解了。

    更妙的是,我们其实只需要考虑形如 a · x mod n = 1 的方程。因为,如果能解出这样的方程, a · x mod n = 2 、 a · x mod n = 3 也都自动地获解了。假如 a · x mod n = 1 有一个解 x = 100 ,由于 100 个 a 除以 n 余 1 ,自然 200 个 a 除以 n 就余 2 , 300 个 a 除以 n 就余 3 ,等等,等式右边余数不为 1 的方程也都解开了。

    让我们尝试求解 115x mod 367 = 1 。注意,由于 115 和 367 是互质的,因此方程确实有解。我们解方程的基本思路是,不断寻找 115 的某个倍数以及 367 的某个倍数,使得它们之间的差越来越小,直到最终变为 1 。由于 367 除以 115 得 3 ,余 22 ,因而 3 个 115 只比 367 少 22 。于是, 15 个 115 就要比 5 个 367 少 110 ,从而 16 个 115 就会比 5 个 367 多 5 。好了,真正巧妙的就在这里了: 16 个 115 比 5 个 367 多 5 ,但 3 个 115 比 1 个 367 少 22 ,两者结合起来,我们便能找到 115 的某个倍数和 367 的某个倍数,它们只相差 2 : 16 个 115 比 5 个 367 多 5 ,说明 64 个 115 比 20 个 367 多 20 ,又考虑到 3 个 115 比 1 个 367 少 22 ,于是 67 个 115 只比 21 个 367 少 2 。现在,结合“少 2 ”和“多 5 ”两个式子,我们就能把差距缩小到 1 了: 67 个 115 比 21 个 367 少 2 ,说明 134 个 115 比 42 个 367 少 4 ,而 16 个 115 比 5 个 367 多 5 ,于是 150 个 115 比 47 个 367 多 1 。这样,我们就解出了一个满足 115x mod 367 = 1 的 x ,即 x = 150 。大家会发现,在求解过程,我们相当于对 115 和 367 做了一遍辗转相除:我们不断给出 115 的某个倍数和 367 的某个倍数,通过辗转对比最近的两个结果,让它们的差距从“少 22 ”缩小到“多 5 ”,再到“少 2 ”、“多 1 ”,其中 22, 5, 2, 1 这几个数正是用辗转相除法求 115 和 367 的最大公约数时将会经历的数。因而,算法的步骤数仍然是对数级别的,即使面对上百位上千位的大数,计算机也毫无压力。这种求解方程 a · x mod n = b 的算法就叫做“扩展的辗转相除法”。

    注意,整个算法有时也会以“少 1 ”的形式告终。例如,用此方法求解 128x mod 367 = 1 时,最后会得出 43 个 128 比 15 个 367 少 1 。这下怎么办呢?很简单, 43 个 128 比 15 个 367 少 1 ,但是 367 个 128 显然等于 128 个 367 ,对比两个式子可知, 324 个 128 就会比 113 个 367 多 1 了,于是得到 x = 324 。

    最后还有一个问题:我们最终总能到达“多 1 ”或者“少 1 ”,这正是因为一开始的两个数是互质的。如果方程 a · x mod n = b 当中 a 和 n 不互质,它们的最大公约数是 d > 1 ,那么在 a 和 n 之间做辗转相除时,算到 d 就直接终止了。自然,扩展的辗转相除也将在到达“多 1 ”或者“少 1 ”之前提前结束。那怎么办呢?我们有一种巧妙的处理方法:以 d 为单位重新去度量 a 和 n (或者说让 a 和 n 都除以 d ),问题就变成我们熟悉的情况了。让我们来举个例子吧。假如我们要解方程 24 · x mod 42 = 30 ,为了方便后面的解释,我们来给这个方程编造一个背景:说一盒鸡蛋 24 个,那么买多少盒鸡蛋,才能让所有的鸡蛋 42 个 42 个地数最后正好能余 30 个?我们发现 24 和 42 不是互质的,扩展的辗转相除似乎就没有用了。不过没关系。我们找出 24 和 42 的最大公约数,发现它们的最大公约数是 6 。现在,让 24 和 42 都来除以 6 ,分别得到 4 和 7 。由于 6 已经是 24 和 42 的公约数中最大的了,因此把 24 和 42 当中的 6 除掉后,剩下的 4 和 7 就不再有大于 1 的公约数,从而就是互质的了。好了,现在我们把题目改编一下,把每 6 个鸡蛋视为一个新的单位量,比如说“ 1 把”。记住, 1 把鸡蛋就是 6 个鸡蛋。于是,原问题就变成了,每个盒子能装 4 把鸡蛋,那么买多少盒鸡蛋,才能让所有的鸡蛋 7 把 7 把地数,最后正好会余 5 把?于是,方程就变成了 4 · x mod 7 = 5 。由于此时 4 和 7 是互质的了,因而套用扩展的辗转相除法,此方程一定有解。可以解出特解 x = 3 ,在它的基础上加减 7 的整倍数,可以得到其他所有满足要求的 x 。这就是改编之后的问题的解。但是,虽说我们对原题做了“改编”,题目内容本身却完全没变,连数值都没变,只不过换了一种说法。改编后的题目里需要买 3 盒鸡蛋,改编前的题目里当然也是要买 3 盒鸡蛋。 x = 3 ,以及所有形如 3 + 7n 的数,也都是原方程的解。

    大家或许已经看到了,我们成功地找到了 24 · x mod 42 = 30 的解,依赖于一个巧合: 24 和 42 的最大公约数 6 ,正好也是 30 的约数。因此,改用“把”作单位重新叙述问题,正好最后的“余 30 个”变成了“余 5 把”,依旧是一个整数。如果原方程是 24 · x mod 42 = 31 的话,我们就没有那么走运了,问题将变成“买多少盒才能让最后数完余 5 又 1/6 把”。这怎么可能呢?我们是整把整把地买,整把整把地数,当然余数也是整把整把的。因此,方程 24 · x mod 42 = 31 显然无解。

    综上所述,如果关于 x 的方程 a · x mod n = b 当中的 a 和 n 不互质,那么求出 a 和 n 的最大公约数 d 。如果 b 恰好是 d 的整倍数,那么把方程中的 a 、 n 、 b 全都除以 d ,新的 a 和 n 就互质了,新的 b 也恰好为整数,用扩展的辗转相除求解新方程,得到的解也就是原方程的解。但若 b 不是 d 的整倍数,则方程无解。

    扩展的辗转相除法有很多应用,其中一个有趣的应用就是大家小时候肯定见过的“倒水问题”。假如你有一个 3 升的容器和一个 5 升的容器(以及充足的水源),如何精确地取出 4 升的水来?为了叙述简便,我们不妨把 3 升的容器和 5 升的容器分别记作容器 A 和容器 B ã

Michael Greb: Alfred 2 Workflow for Audio Device Selection

from Planet Linode http://michael.thegrebs.com/2013/01/18/alfred2-audio-device/

Alfred V2 has a great new feature called workflows. I’ve been playing with a few others wrote and had ported my old custom commands to workflows but was looking for something to really make use of their power.

Changing OSX Audio device from menubar
Changing the selected audio output device was just the thing to implement as a workflow. OS X has a nice shortcut for doing this without heading to system preferences. Option clicking the speaker in the menu bar well let you change the input or output device, but I wanted to do it easily from the keyboard.

The ‘Script Filter’ option under the input menu is the magic for this workflow. It allows a script to output a list of items for display and selection in the Alfred GUI. You get Alfred’s great predictive auto complete which makes selecting a device a breeze.

Selecting output audio device in Alfred

Output via Growl or Notification Center provides feedback of the completed action.

Growl confirmation

The workflow is pretty simple in Alfred’s workflow editor, it ends up looking like this:

Alfred work flow

Alfred makes sharing workflows insanely easy by throwing all the necessary files for each workflow in a dedicated directory. Right clicking a workflow in Alfred gives an export workflow option which creates a zip file of this directory with the ‘.alfredworkflow’ extension.

Grab SwitchAudio.alfredworkflow

The heavy lifting is done by switchaudio-osx by deweller on GitHub with a simple perl glue script to pass data back and forth between Alfred and switchaudio-osx.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#!/usr/bin/env perl

use strict;
use warnings;

use FindBin;

my $action = shift || 'list';
my $direction = shift || 'output';

if ($action eq 'list') {
    my $devices = get_possibilities($direction);
    print qq{<?xml version="1.0"?>\n<items>\n};
    print output_device($_) for @$devices;
    print "</items>\n";
}

if ( $action eq 'set' ) {
    my $device = shift;
    print set_device($direction, $device) . "\n";
}

sub get_possibilities {
    my $direction = shift;
    my @devices;
    open( my $fh, '-|', $FindBin::Bin . '/SwitchAudioSource',
        '-at', $direction );
    while ( my $line = <$fh> ) {
        chomp $line;
        $line =~ s/ \(\Q$direction\E\)$//;
        push @devices, $line;
    }
    close $fh;
    return \@devices;
}

sub set_device {
    my ( $direction, $device ) = @_;
    open( my $fh, '-|', $FindBin::Bin . '/SwitchAudioSource',
        '-t', $direction, '-s', $device );
    my $output = join "\n", <$fh>;
    close $fh;
    return $output;
}

sub output_device {
    my $device = shift;
    ( my $device_no_space = $device ) =~ tr/ /_/;
    return qq{<item arg="$device" uid="$device_no_space"><title>$device</title><subtitle/><icon>icon.png</icon></item>\n};
}

Update-Efficient Regenerating Codes with Minimum Per-Node Storage. (arXiv:1301.2497v1 [cs.IT])

from cs.IT updates on arXiv.org http://arxiv.org/abs/1301.2497

Regenerating codes provide an efficient way to recover data at failed nodes
in distributed storage systems. It has been shown that regenerating codes can
be designed to minimize the per-node storage (called MSR) or minimize the
communication overhead for regeneration (called MBR). In this work, we propose
a new encoding scheme for [n,d] error- correcting MSR codes that generalizes
our earlier work on error-correcting regenerating codes. We show that by
choosing a suitable diagonal matrix, any generator matrix of the [n,{\alpha}]
Reed-Solomon (RS) code can be integrated into the encoding matrix. Hence, MSR
codes with the least update complexity can be found. An efficient decoding
scheme is also proposed that utilizes the [n,{\alpha}] RS code to perform data
reconstruction. The proposed decoding scheme has better error correction
capability and incurs the least number of node accesses when errors are
present.