天空为什么是蓝色的

在现代社会中,光和颜色已经深深融入了我们日常生活的方方面面。它们的存在是如此自然,以至于我们很少停下来思考它们的普遍性和重要性。光与颜色无处不在,从清晨的第一缕阳光,到入睡前的最后一瞥屏幕,它们贯穿了我们一整天的生活。

 

每天早晨,当我们睁开眼睛,阳光透过窗帘照射进房间,为我们揭开新的一天。自然光充斥着我们的生活空间,照亮我们起居的每一个角落。无论是在家中、办公室、街道,还是在商场、咖啡馆,自然光和人工光源交织在一起,为我们的生活环境增添亮度和温暖。

在家中,光不仅仅是为了照明。厨房的灯光帮助我们烹饪,餐厅的吊灯营造用餐氛围,卧室的床头灯提供阅读的舒适光线,浴室的镜前灯则确保我们能清晰地看见自己。每个房间的灯光设计都考虑到了使用的便利性和视觉效果,光成为了家居设计的重要组成部分。

颜色同样无处不在。家里的墙壁、家具、床上用品、装饰品,每一样物品都有其特定的颜色,这些颜色组合在一起,定义了我们生活空间的整体风格和氛围。墙壁的颜色可能是柔和的米色或温暖的橙色,家具可能是深沉的木色或现代的黑白对比,这些色彩元素每天都在潜移默化地影响着我们的感知。

离开家门,我们走进的每一个公共空间,无论是街道、商店、办公室还是公园,光与颜色依然无处不在。街道上的交通信号灯通过颜色指挥着车辆和行人,广告牌和店铺招牌用鲜艳的颜色吸引着过路人的注意。商场的橱窗设计、展品的灯光布置,甚至超市货架上的商品摆放,都是利用光与颜色来引导我们的视线和选择。

在工作场所,光和颜色的存在同样不可或缺。办公室的照明不仅仅是为了看清文件和电脑屏幕,还关系到员工的舒适度和工作效率。办公桌上的台灯、会议室中的吊灯、走廊里的壁灯,这些灯光设计都经过精心考虑,以确保在不同的场景下提供最合适的光线。墙壁的颜色、地毯的图案、办公家具的色调,这些元素构成了办公室的整体视觉效果,影响着我们每天的工作环境。

 

随着科技的发展,光和颜色在数字世界中扮演了更加重要的角色。每天,我们花费大量时间盯着各种电子设备的屏幕,无论是电脑、手机、平板还是电视,这些屏幕都是通过光和颜色来呈现信息的。屏幕显示的每一个图像、每一个文字,都是通过光的发射和颜色的组合实现的。

在数字媒体中,光和颜色的运用已经成为一种艺术和科学的结合。网页设计师、应用程序开发者、游戏设计师都在使用不同的颜色方案和光影效果,来打造引人注目的界面和场景。一个简单的按钮可能需要经过多次调整颜色和亮度,才能在屏幕上既清晰可见,又符合整体设计风格。

视频内容的制作也是如此。无论是电影、电视节目还是在线视频,画面中的每一个场景都依赖于光的布置和颜色的调整。导演和摄影师通过灯光的明暗、色调的变化,来传达不同的情感和氛围。即使是社交媒体上的短视频创作者,也会利用光和颜色来增加视频的吸引力,使其在众多内容中脱颖而出。

艺术与设计中的光与颜色

在艺术和设计领域,光与颜色更是不可或缺的元素。无论是绘画、摄影、雕塑还是建筑设计,艺术家和设计师都利用光和颜色来表达他们的创意和思想。

绘画是最直接的使用颜色的艺术形式。画家通过颜料的混合和运用,创造出各种各样的色彩效果,从而表现出自然景象、人物形象或抽象情感。不同的颜色组合可以传达出截然不同的情感,如温暖、冷酷、平静或激动。光在绘画中同样重要,通过明暗对比,画家能够赋予作品立体感和深度。

在摄影中,光线的控制决定了照片的质量和效果。摄影师通过调整光源的方向、强度和颜色,来捕捉最佳的瞬间。无论是自然光还是人工光,光线的变化可以改变照片的氛围,甚至可以完全改变观众对照片主题的感知。

在建筑设计中,光与颜色的运用更为复杂。建筑师在设计建筑物时,不仅要考虑结构的功能性,还要通过光的自然引入和人工照明的布置,来创造舒适的生活和工作环境。颜色则通过建筑材料的选择和室内装饰的搭配,形成建筑物的视觉形象。

交通和标识中的光与颜色

在我们的日常生活中,光与颜色也在帮助我们导航和指引方向。交通信号灯是最典型的例子,红色、绿色和黄色的灯光通过简单的颜色区分,传达出“停”、“行”和“注意”的信息。这些颜色编码已经成为全球通用的标准,几乎每个人都能立即识别和理解。

在机场、火车站、地铁等公共交通系统中,颜色和灯光被广泛用于引导乘客。不同的线路可能使用不同的颜色标识,地铁站台上的指示灯和地面上的彩色箭头都在帮助人们找到正确的方向。夜间航行时,船只和飞机也依靠不同颜色的导航灯来确保安全。

商品与消费中的光与颜色

走进商场或超市,光与颜色再次展现其无处不在的特性。商品包装、货架陈列、促销海报,这些都离不开颜色的巧妙运用。鲜艳的包装颜色可能会吸引你的目光,而温暖的灯光则可能让你感到舒适,愿意在店内多逛一会儿。商家利用颜色来区分不同的商品类型,或突出特定的促销产品,而这些颜色的选择通常基于消费者心理研究,目的是最大化销售。

在服装店中,光线的布局和颜色的选择尤为关键。柔和的灯光可以让试衣间的环境更加温馨,让顾客感到轻松自在,颜色的搭配则直接影响到顾客对服装的选择。无论是展示商品的橱窗,还是店内的陈列区,光和颜色的搭配都是为了吸引顾客的注意力,并提升购物体验。

日常生活的每个角落

从早晨的第一缕阳光,到夜晚的最后一盏灯光,光与颜色贯穿了我们日常生活的每一个角落。它们在我们的家中、街道、工作场所、公共空间、数字设备和购物环境中无处不在。尽管我们可能习以为常,但光和颜色的确是我们生活中不可或缺的元素。它们不仅使我们的世界更加丰富多彩,也让我们的生活变得更加便利和舒适。

现代人生活在一个被光和颜色包围的世界里,无论是自然环境还是人工构建的空间,光与颜色无时无刻不在影响着我们的生活方式。虽然我们可能不会时常思考光和颜色的存在,但它们早已成为我们日常生活中不可分割的一部分,渗透在生活的每一个细节中,构成了我们感知世界的基本框架。

 

 

尽管光和颜色在今天的生活中如此平常、随处可见,但在历史上,它们曾经长期困扰着人类。光是什么?颜色是如何产生的?这些问题曾是古代哲学家和科学家们不断思索和争论的课题。光和颜色看似简单,但其背后的奥秘却令无数思想家感到困惑。

在古代,光和颜色的本质是哲学和科学中一个充满争议的话题。早在古希腊时期,哲学家们就开始探讨光的本质和颜色的起源。柏拉图认为光是从物体中发出并被眼睛捕捉的,而亚里士多德则提出,颜色是光与物体表面相互作用的结果。这些早期的理论虽然为后世的研究奠定了一定的基础,但对于光和颜色的真正机制,古代思想家们仍然无法给出确切的答案。

随着时间的推移,来自不同文明的学者们继续探索光和颜色的奥秘。伊斯兰黄金时代的学者们在光学研究方面取得了重要进展,尤其是伊本·海赛姆,他的实验和理论显著推动了对光传播和反射的理解。然而,即便在这些学者的努力下,光和颜色的真相依然笼罩在神秘之中。

光和颜色不仅在科学上让人困惑,在日常生活中,它们的表现形式也是多种多样的。例如,为什么彩虹会出现?光线通过玻璃为什么会折射?不同的物体为什么呈现不同的颜色?这些现象无论在古代还是在中世纪,都充满了神秘感。虽然人们可以观察到这些现象并提出一些理论,但对这些现象的真正原因,直到牛顿时代之前,都没有一个统一的解释。

正是在这种长期的困惑中,光和颜色的问题成为了科学探索的前沿。虽然它们是我们每天都会接触到的东西,但正是因为它们的普遍性和复杂性,才使得人类对它们的理解如此困难。在牛顿之前,尽管许多学者对光和颜色提出了各自的理论,但这些理论往往是相互矛盾的,缺乏足够的实验验证和科学依据。

直到17世纪,光和颜色的谜题才逐渐揭开面纱。牛顿的出现为光学研究带来了革命性的突破。他不仅在实验中发现了光的本质,还通过一系列巧妙的实验,揭示了光和颜色之间的深层联系。牛顿的研究标志着光学研究从哲学和猜想走向了科学实验和理论验证的新时代,使得人类终于能够解释这些困扰了几千年的自然现象。

光和颜色曾经是如此神秘和不可捉摸,令古代哲学家和科学家们困惑不已。它们的普遍性掩盖了其复杂性,直到牛顿的时代,人类才得以解开这些自然界的奥秘。随着牛顿的光学研究,光和颜色的真正机制逐渐明朗,为后世的科学家们进一步探索和发展奠定了基础。

 

 

 

 

在人类历史上,对光和颜色的理解经历了漫长的发展过程。虽然牛顿的光学革命在西方科学史上占据了重要地位,但在此之前,不同文明的思想家、哲学家和科学家们早已对光与颜色进行了深入的探讨和研究。这些研究不仅限于西方世界,许多来自伊斯兰世界的贡献在中世纪对西方科学产生了深远影响,进而影响了后来的欧洲科学发展。本文将探讨从古希腊时期到17世纪前,东西方文明中的光和颜色研究,重点关注古希腊、伊斯兰世界和西方中世纪及文艺复兴时期的贡献。

古希腊时期的光与颜色理论

古希腊是西方哲学与科学的发源地,许多关于光和颜色的早期理论都诞生于这一时期。其中,最具影响力的思想家之一是柏拉图(Plato)。柏拉图认为,光是从物体中散发出来并被眼睛接收到的。他在《蒂迈欧篇》中描述了光是如何通过空气或其他介质传递到眼睛,并在眼睛内部产生视觉感受。柏拉图的学生亚里士多德(Aristotle)则提出了一种不同的观点。

亚里士多德认为,光并不是从物体中散发出来的,而是来自于光源(如太阳)的某种“发光体”。他认为,颜色是光与物体表面之间相互作用的结果。当光照射到物体上时,物体会吸收一部分光并反射另一部分,这就是我们看到的颜色。亚里士多德还提出了颜色的基本分类,他认为颜色可以分为白色、黑色以及其他由这两种颜色混合而成的颜色。

伊斯兰黄金时代的光学研究

在中世纪时期,伊斯兰世界对光和颜色的研究达到了高度的精确性和系统化,尤其是在伊本·海赛姆(Ibn al-Haytham,约公元965-1040年)的工作中达到了顶峰。伊本·海赛姆的《光学书》被认为是现代光学的奠基之作,他通过实验的方法,否定了古希腊时期流行的“光是从眼睛发射”的观点,提出光是从物体发射出来,并被眼睛接收到的。他的实验表明,光以直线传播,并且当光穿过不同介质时会发生折射和反射。

伊本·海赛姆在颜色方面的研究也非常深入。他提出颜色是光的特性之一,当光通过不同的介质或遇到不同的物体时,会发生变化,从而产生各种颜色。这种对光和颜色的理解为后来西方科学家的研究提供了重要的基础。

除了伊本·海赛姆,阿布·阿里·穆萨·本·沙卡尔(Abu Ali al-Hasan Ibn Musa Ibn Shakir)和他的兄弟们也对光的反射和折射进行了研究。他们通过几何学的原理,试图解释光的传播和反射现象,这些研究对后来的光学发展起到了推动作用。

另一位重要的伊斯兰学者阿尔·法拉比(Al-Farabi)在其哲学著作中也讨论了光的本质。他受亚里士多德的影响,提出光是天体的“发光体”发出的,它能够穿透透明的物质,并与物体表面相互作用,从而产生颜色的感知。伊斯兰学者们不仅保留和扩展了古希腊的光学研究,还结合了他们自己的实验成果,为文艺复兴时期的科学进步奠定了坚实基础。

中世纪西方的光与颜色理论

随着古希腊罗马文明的衰落,西方进入了一个被称为“黑暗时代”的中世纪时期。在这段时间里,科学的发展相对缓慢,但一些阿拉伯学者的光学研究通过译作传入西方,极大地影响了欧洲的科学发展。

伊本·海赛姆的著作在西方被广泛传播,并在文艺复兴时期成为重要的参考资料。与此同时,欧洲学者开始对光的传播、反射和折射进行研究,并尝试解释这些现象。

在13世纪,罗杰·培根(Roger Bacon)是一位重要的西方学者,他受伊本·海赛姆影响,对光学产生了浓厚的兴趣。培根认为,光是一种通过媒介传播的形式,并提出了光的折射和反射原理。他还强调了实验的重要性,这一思想对后来科学方法的发展产生了深远影响。

文艺复兴时期的光与颜色研究

文艺复兴时期,欧洲的科学和艺术迎来了复兴,对光和颜色的理解也进入了一个新的阶段。达·芬奇(Leonardo da Vinci,1452-1519年)是这一时期最著名的多才多艺的天才之一,他对光和颜色的观察和研究深刻影响了后来的科学家和艺术家。

达·芬奇在他的笔记中详细记录了他对光和阴影的观察,提出了许多关于光线传播和反射的理论。他认为,光线是直线传播的,并且在不同的表面上会产生不同的反射效果。此外,达·芬奇还对颜色的混合进行了实验,他发现通过混合不同的颜色可以创造出新的颜色,这一发现对绘画艺术的发展具有重要意义。

文艺复兴时期的另一位重要人物是约翰内斯·开普勒(Johannes Kepler,1571-1630年)。开普勒是德国的天文学家,他在研究天体运动的同时,也对光学进行了深入的研究。开普勒继承了伊本·海赛姆的理论,并进一步发展了关于光的传播和折射的理解。开普勒的研究为后来牛顿的光学研究奠定了重要基础。

牛顿之前的其他重要贡献者

在牛顿之前,还有许多科学家和哲学家对光和颜色进行了研究,为牛顿的光学革命铺平了道路。其中值得一提的是笛卡尔(René Descartes,1596-1650年)和罗伯特·胡克(Robert Hooke,1635-1703年)。

笛卡尔是法国著名的哲学家和科学家,他提出了关于光的机械理论。他认为光是一种以极高速度传播的“压力波”,类似于声音在空气中的传播。他还进行了关于光的折射和反射的实验,试图用几何学来解释这些现象。虽然笛卡尔的光学理论后来被证明是错误的,但他的方法和思想对科学研究具有深远影响。

罗伯特·胡克则是英国的科学家,他对光和颜色的研究涉及到许多实验和观察。胡克提出了光的波动理论,他认为光是由一种类似于波的运动传播的。他还观察到光通过棱镜时会分解成不同的颜色,这一现象后来成为牛顿研究的重要基础。

其他文化对光的理解

在伊斯兰世界和西方之外,其他文化也对光和颜色进行了探讨。虽然这些研究在系统性和精确性上可能不如伊斯兰世界和西方,但它们在哲学、宗教和艺术中体现了对光的独特理解。

在中国,古代思想家通过阴阳五行学说,将光和颜色与自然界的力量相联系。道家认为光是“气”的表现形式,而五行理论中,颜色则与自然元素、季节和人体脏腑相对应。在印度,光被视为神圣力量的象征,与智慧和启示紧密相连,颜色在宗教仪式中占有重要地位,并与不同的神祇和情感相对应。

虽然这些理解更多地与文化和宗教信仰相连,但它们展示了光在不同文明中的多样性意义,并丰富了人类整体的光学知识。

总结

在人类对光和颜色的理解历程中,来自不同文明的思想家们以各自独特的方式为这个领域做出了贡献。从古希腊到伊斯兰世界,再到中世纪和文艺复兴时期的欧洲,不同文化和思想流派在光与颜色的探索中展现了他们独特的视角和智慧。

在伊斯兰世界,通过精确的实验和几何分析,学者们对光学进行了系统的研究,为西方世界的发展提供了重要基础。西方中世纪的学者在伊斯兰世界研究的基础上进一步发展了这些理论,并在文艺复兴时期将光学研究推向新的高度。牛顿之前的科学家们通过实验与理论推导,为现代光学的诞生奠定了基础。

总之,光和颜色的研究不仅是科学的一部分,也反映了不同文明对自然界的理解与探索。尽管牛顿的光学革命在西方科学史上具有重要意义,但在他之前,人类在不同文明中的积累和探索同样值得铭记与尊重。这些多样化的研究不仅丰富了我们的科学知识,也展示了科学作为全人类智慧结晶的多样性与复杂性。

 

待续……

Remote for Raspberry Pi + OSMC Media Center

It is not so difficult to turn your Raspberry into a media center. Installing OSMC is rather straight forward on Raspberry Pi. You just download the  image from OSMC website, write it to an SD card, boot your Raspberry from the SD card and that’s it. However, getting a remote working for your OSMC media center working proved to be rather challenging. This post is to record what I’ve learned from the internet in order to get a working remote.

What you need:

  • Raspberry Pi running OSMC;
  • IR Receiver (I’m using VS1838B, shown below);

  • Any IR remote with enough buttons;
  • A computer to access OSMC remotely;

Now, 3 steps to put all the things to together and have them work correctly.

继续阅读Remote for Raspberry Pi + OSMC Media Center

Hardware hack and supply chain security

Bloomberg just made big news.

In its recent issue, it featured a cover story: “The Big Hack: How China Used a Tiny Chip to Infiltrate U.S. Companies“, detailed how Chinese military planted malicious chips into motherboards manufactured by Taiwanese supplier, supplying motherboards to a major server provider whose servers were used by almost 30 US companies, including Amazon and Apple. And by  doing this, Chinese military gains potential access to these companies and even US military.

Here’s the malicious chip on the motherboard:

Here’s a illustration of that process directly from their website: 继续阅读Hardware hack and supply chain security

Call for smartasses

Some of you may have seen this video, since it has been around for several years:

(For those you feel so compelled to up-vote this video, sorry I don’t have such a button on my blog, but you are welcome to go to YouTube and search for “Short Comedy Sketch” and express your sympathy there. :)) 继续阅读Call for smartasses

我读《乌合之众》

《乌合之众》是在大学之后接触到的,前后见过好几个译本,但都是随便翻翻,没有深入看进去。有意思的是这本书最近越来越火,尤其在高层推荐《旧制度与大革命》之后,《乌合之众》也沾光再次被各路媒体推荐,新的译本涌现出来不少。

最近得到一本浙江文艺出版社出版的董强翻译的译本,译笔令人意外的流畅,我对照了英文版,似乎也非常忠于原著,认真读了一边,顺便做了简单的笔记。

继续阅读我读《乌合之众》

从防火墙内下载的pycharm有问题!

昨天重装电脑,需要重新安装很多软件。到pycharm网站一看,已经2017.2.1了,于是点击下载准备安装。点击链接,转向下载页面。。。

一切都非常熟悉,非常正常。下载速度有点慢,等着也是等着,我就点开了SHA-256 checksum的链接,把内容拷贝到Downthemall里面,等待下载完了验证。

我知道下载可能会有问题,我知道怎么用checksum,但是的确不是每次都用,谁都有懒得时候……

下载完毕,Downthemall开始验证,然后提示我,verification failed!

继续阅读从防火墙内下载的pycharm有问题!

The sum of all natural numbers…

The notion of 1+2+3+4+…=-1/12 has become so wide spread that quite a few of my friends actually feel convinced that it’s actually a true statement in general, even though it is very counter intuitive.

The point is, in order to evaluate an expression, that expression has to be well-defined.

Expressions like a+b is well defined in the sense that we know it is a binary operation, we know what are we supposed to do to get the result.

Expressions like a+b+c+… is not well defined, because there are multiple operators involved, and the order of evaluation is not clearly specified.

Take the sum of the alternating series as an example:

继续阅读The sum of all natural numbers…

聊记一笔

头天下午看到朋友圈里分享的文章,原以为是朋友分享错了,结果是原文就写错了。

因为FT中文网我也经常看,于是晚上写邮件给责任编辑,指出错误,第二天上午再看就纠正过来了。有意思的是,几天过去了一直没有收到责任编辑的回复。。

花时间搜索了一下,meta narration的用法,实际上只有百度百科有。在百度百科上,也只有概述部分用了这个错误的meta narration,其它部分都是meta narrative,偏偏这个概述部分会出现在百度搜索的预览中,所以流毒甚广。

推测起来,作者对于这个词汇可能并不熟悉,行文时顺便在百度上搜索了一下进行确认,搜索之后也并未打开页面认真检查,就上了百度的当。

如邮件中所说,这个错误并不影响刘远举先生文章本身的价值,只是从责任编辑和刘先生的反应来看,想来也觉得这个错误犯的有些低级,所以不好回应。记在这里为自己和后来者戒。

Chapter 02 The First Algorithm

摩西快速学习了算术和几何……
这些知识他是从埃及人那里学到的。埃及人研习数学和其它学问。

《形而上学》亚里士多德

算法 是用以完成某项计算任务的有限步骤。算法跟计算机编程有紧密的联系,以至于大多数知道这个词的人以为算法的使用是从计算机科学开始。但实际上,人们使用算法已经有几千年的历史。数学中充满了算法,有一些我们到今天还在使用。学生们学习的长加法就是一种算法。

尽管使用算法的历史很长,算法这个概念并不是一开始就存在,它是后来发明出来的。尽管我们不知道是谁首先发明了这个概念,却明确知道有些算法至迟在4000多年前的古埃及就存在了。

 

古埃及文明的核心是尼罗河,因为其农业有赖于尼罗河泛滥带来的肥沃泥土。问题是,尼罗河一发水,用来划分权属的界标也都被冲掉了。埃及人惯用绳子测量长度,因此发展出一套方法,可以根据书面记录重建界标。一群制定的祭司专司此事,他们学过这些数学技术,因此成为“拉绳子的人(rope-strecher)”。希腊人后来会把他们叫做几何学家(geometers),意思是“土地丈量者”。

很不幸我们并没有多少古埃及数学知识的文字记录,当时的数学文件仅有两篇留存至今。我们关心的一个,叫做Rhind Mathematical Papyrus,名字来自于19世纪在埃及买到它的苏格兰收藏者。这篇文献成于约公元前1650年,抄写者名叫Ahmes。文献中有一系列算术和几何问题,还有一些辅助计算的表格。其中包含一个快速乘法技术和一个快速除法技术,是最早的有记录的算法。我们首先来看一看这个快速乘法算法,(我们很快会看到)它至今仍然是重要的计算技术。

2.1 埃及乘法

跟其它古文明一样,埃及人使用的数字系统中没有数位概念,也没有零。因此,乘法非常复杂,只有少数专家能够掌握。(想象一下只使用罗马数字进行两位数乘法)

首先,什么是乘法?粗略地说,乘法就是“把一个数跟它自身反复相加”。严格一些,我们可以首先把乘法分为两种情况:乘以1,或者乘以一个大于1的数。

乘数为1的乘法的定义是:

$$1a=a$$                                   (2.1)

然后,我们考虑如何计算比我们已经计算出来的再多一倍的情形。有些读者可以意识到这是一个递推,我们会在后面正式使用这个技术。

$$(n+1)a=na+a$$                 (2.2)

计算na的厂家做法是把n个a加起来。但是,在n很大的时候,这可能非常繁琐,因为需要进行n-1次加法。使用C++,这个算法是这样的:

int multiply0(int n, int a){
    if (n==1) return a;
    return multiply0(n-1, a)+a;
}

这样两行代码对应于(2.1)和(2.2)。a和n都必须是正数,古埃及当时的约定也是如此。

Ahmes所描述的算法,这个算法在古希腊被称为“埃及乘法”,而很多现代作者则称之为“俄罗斯农民算法”,建立在如下洞察上:

$$ 4a=((a+a)+a)+a=(a+a)+(a+a) $$

这个优化利用了加法的结合律:

$$a+(b+c)=(a+b)+c $$

这样,我们只需要计算一次a+a,减少了计算次数。

核心思想在于,不断地把n取半,同时把a加倍,使用数的2的次方倍相加来计算乘法结果。在当时,人们不会使用变量a和n来描述算法,而是由作者给出示例,然后说“其它数字同理”。Ahmes也是这么做的,他使用下面的表格来演示这种算法,n=41,a=59:

1        ♦         59
2                  118
4                  236
8        ♦        472
16                944
32      ♦      1888

每个条目的最左边是2的幂,右边是前一条目的数字的倍数(数字加倍相对容易计算)。有标记的值对应41的二进制表示中数值为1的位。这个表格的意思是说:

$$41*59=(1*59)+(8*59)+(32*59)$$

其中右边的每一个乘积可以由对59加倍响应的次数而得到。

这个算法需要检查n是奇数还是偶数,所以我们可以推断古埃及人知道它们的区别,尽管我们没有直接的证据,但是古希腊人,他们自称从古埃及人那里学到数学,显然知道奇偶的区别。下面是他们的定义方法用现代数学标记表达出来:

$$n=n/2+n/2$$    说明n是偶数
$$n=(n-1)/2+(n-1)/2+1$$  说明n是奇数

我们也将使用这个特点:

odd(n) 意味着 half(n)=half(n-1)

下面是埃及乘法的C++实现:

int multiply1(int n, int a){
    if (n==1) return a;
    int result=multiply1(half(n), a+a);
    if (odd(n)) result=result +a;
    return result;
}

odd(x)很容易实现,测试x的最低位就可以了,half(x)则可以通过对x进行一次右移实现:

bool odd(int n) { return n&0x1;}
int half(int n) { return n>>1; }

multiply1需要进行多少次加法运算?每次调用这个函数,我们需要在a+a的地方进行一次加法,因为我们是不断对n取半,我们需要调用这个函数logn次。在某些时候,我们还需要在result+a的地方进行加法运算,因此加法运算的总次数为:

$$\#(n)=logn + v(n)-1$$

其中v(n)是n的二进制表达中1的个数(population count或者pop count)。由此我们把一个O(n)算法优化成了O(logn)算法。

这个算法已经最优了吗?不见得。比如,如果我们要乘以15,使用之前的公式,我们需要

$$\#(15)=3+4-1=6$$

进行6次加法。但是我们使用下面的办法,就只需要5次加法运算:

int multiply_by_15(int a){
    int b=(a+a)+a;    //b == 3*a
    int c+b+b;        //c == 6*a
    return (c+c)+b;   //12*a + 3*a
}

这样一系列加法运算又称为加法链。这里我们发现了15的最优加法链,尽管如此,Ahmes的算法在多数情况下已经足够好了。

练习2.1

为n<100的数找到最优加法链

有读者可能已经注意到其中有些乘法运算可以更快,只要我们在第一个参数大于第二个参数的情况下交换一下参数顺序就可以了(比如,3*15会比15*3更容易计算)。的确如此,而且古埃及人也知道这一点。但是我们不会在这里进行这样的优化,因为到第七章我们会发现,我们最终要把算法推广到不同的数据类型。在这种情况下,参数的顺序是不能交换的。

2.2 改进算法

函数multiply1的加法运算次数还可以,但是它还要进行logn次递归调用。鉴于函数调用的开销很高,我们希望能够优化程序以避免这个开销。

我们将要利用的一个原则是:It is often easier to do more work rather than less. 特别地,我们准备计算

r+na

其中r是加法计算的中间结果,也就是说,我们要实现一个乘法累计函数,而不仅仅是乘法函数。这种思维方式不仅仅适用于程序编写,也适用于硬件设计和数学——比如在数学中,时常有一般性判断比特定判断更容易证明的情形。

这里是我们的乘法累计函数:

int mult_acc0{int r, int n, int a) {
    if (n==1) return r+a;
    if (odd(n)){
        return mult_acc0(r+a, half(n), a+a);
    }else{
        return mult_acc0(r, half(n), a+a);
    }
}

这里有一个不变形式:r+na=r0+n0a0,其中r0、n0和a0是r、n和a这些变量的初始值。

我们可以通过简化递归获得进一步优化。注意在上面的两行递归调用代码只有第一个参数不同,这样对于奇数情况和偶数情况分别进行递归,不如我们在进行递归前根据情况修改第一个参数的值:

int mult_acc1(int r, int n, int a) {
    if (n==1) return r+a;
    if (odd(n)) r=r+a;
    return mult_acc1(r, half(n), a+a);
}

现在我们的函数是尾递归函数——递归仅仅发生在返回值里面——我们马上会利用这一特点。

我们注意到两点:

  • n=1的情况很少发生;
  • 如果n是偶数,则完全没有必要判断它还是不是1.

因此,我们可以首先判断n的奇偶性,这样把n与1进行比较的次数降低一半:

int mult_acc2(int r, int n, int a) {
    if (odd(n)) {
        r=r+a;
        if (n==1) return r;
    }
    return mult_acc2(r, half(n), a+a);
}

有些程序员认为编译器可以为我们做这样的优化,其实不太可能。编译器不能把一种算法优化成另外一种算法。

到目前为止都很好,不过我们的目标是避免递归以节省函数调用的开销。要达到目的,如果我们的函数是完全尾递归就好了。

定义2.1 一个完全尾递归函数是一个所有递归调用的形式参数都跟函数本身一致的函数。

同样地,我们可以通过在递归调用之前给变量重新赋值来达到这个要求:

int mult_acc3 (int r, int n, int a) {
    if (odd(n)) {
        r=r+a;
        if (n==1) return r;
    }
    n=half(n);
    a=a+a;
    return mult_acc3(r,n,a);
}

到了这里,把它转化成一个循环就很简单了,只需要使用一个while(true)结构替换掉尾递归就可以了:

int mult_acc4(int r, int n, int a) {
    while (true) {
        if (odd(n)) {
            r=r+a;
            if (n==1) return r;
        }
        n=half(n);
        a=a+a;
    }
}

使用这个全新的乘法累加函数,我们可以写一个新版的乘法函数:

int multiply2(int n, int a) {
    if (n==1) return a;
    return mult_acc4(a, n-1, a);
}

注意我们在调用mul_acc4的时候预先把累加结果置为a,这样就减少了一次循环。

效果很不错,除了在n是2的幂的时候。由于我们第一次调用就把n减去1,这样mult_acc4函数被调用的时候第二个参数是一个二进制表达是全1的数,这对于我们的算法是最坏情况。因此,我们要在n是偶数的情况下做一些预处理,以避免这种情形。我们把n取半(同时把n加倍),直到n变成奇数。

int multiply3(int n, int a) {
    while (!odd(n)) {
        a=a+a;
        n=half(n);
    }
    if (n==1) return a;
    return mult_acc4(a, n-1, a);
}

但这样的话,mul_acc4就没有必要再检查n=1的情况了,因为n是奇数,n-1是偶数。因此,我们可以在调用的时候直接把n-1取半,把a再加倍,这样就是我们的最终版:

int multiply4(int n, int a) {
    while (!odd(n)) {
        a=a+a;
        n=half(n);
    }
    if (n==1) return n;
    return mult_acc4(a, half(n-1), a+a);
}

重写代码

在不断变换我们的乘法算法的过程中,可以看到重写代码是很重要的。没有谁一上来就能写出很好的代码,很多时候需要反复尝试才能找到最高效或者最通用的方法。程序员不应该有一遍就过的想法。

在重写过程中你可能会想,一条指令的多少不见得能造成多大的区别。但是也可能你的代码在后来很长时间内被重用很多次(实际上,临时处理措施经常变成代码里面存活时间最长的部分),而且,本来可以省掉的操作现在不起眼,留下来也可能会被修改成非常开销非常高的代码。

努力追求效率的另外一个好处是,在此过程中你不得不逼迫自己深入理解问题本身。与此同时,理解深入必然带来更有效率的实现,这是一个良性循环。

2.3 本章的思考

初等代数的学生都会学习如何通过变换表达式的形式来简化它们。在我们实现埃及乘法的不同实现中,我们也经历了类似的变换过程,重新安排代码语句,使之更清晰更高效。每个程序员都应该养成尝试对代码进行变换的习惯,直到得到最佳形式。

本章我们看到了数学在古埃及是怎样出现的,如何留下了第一个有记录的算法。我们要到靠后面的内容才会回到这个算法并对其进行推广。接下来,我们要向后跳跃1000年,领略一些古希腊人的数学发现。