前言:
目前兄弟们对“勒让德多项式的求值算法”大约比较珍视,兄弟们都需要学习一些“勒让德多项式的求值算法”的相关文章。那么小编同时在网摘上搜集了一些对于“勒让德多项式的求值算法””的相关资讯,希望小伙伴们能喜欢,大家快快来学习一下吧!作者 | 蔡天新来源 | 赛先生(ID: mrscience100)
何为真理?不能坐等答案。 ——弗朗西斯·培根
道古新桥
杭州城内,离开西湖北岸的宝石山不远,有一条小路叫西溪路。在西溪路的东段,与杭大路的交叉口西侧(也在浙江大学西溪校区与玉泉校区之间,靠近西溪校区),有一座石桥,叫道古桥。始建于南宋嘉熙年间(1237-1241),初名西溪桥。南宋咸淳初年《临安志》有载:“‘西溪桥’,本府试院东,宋代嘉熙年间道古建造”。这个造桥的道古不是别人,正是南宋大数学家秦九韶,道古是他的字。
道古桥在杭州的位置图(梁津铭绘)
秦九韶(1202-1261)祖籍河南范县,该县位处鲁豫交界处,县城有数百年设在山东莘县境内,故他自称山东鲁郡人。秦九韶出生在四川普州(今成渝之间)安岳,并在那里长大。其父中过进士(据笔者了解,家乡人传秦家三代进士),曾任巴州(今川东北巴中)地方长官。1219年,巴州发生了一起兵变,促使其离开故乡,调任首都临安(杭州),全家住在西溪河畔。原来,1201年,临安发生了一场著名的大火,烧了三天三夜,烧掉太庙、三省、六部、御史台等,受灾居民达三万五千多家,部分朝廷命官及家眷便迁居当时属于郊外的西溪河畔,秦家来临安后也住那里。
九韶自幼聪颖好学,兴趣广泛,他的父亲来临安后一度出任工部郎中,后任秘书少监,掌管图书,其下属机构设有太史局,这使他有机会博览群书,学习天文历法、土木工程和数学、诗词等。1225年,秦父又被任命为潼川(今四川三台)知府,该地靠近吐蕃部落,为边关重地。秦父决定把家眷安置在离开临安不远的湖州,只携带了心仪的小儿子九韶前往赴任。九韶曾出任擢郪县(今三台县郪江乡)县尉,故也有九韶为义兵首的说法,他有领兵打仗的才能。
宋理宗赵昀,曾接见秦九韶,宠爱奸臣贾似道的贵妃姐姐。
1232年,秦九韶也考中进士,先后在四川、湖北、安徽、江苏、江西、广东等地为官。1236年,元兵攻入四川,嘉陵江流域战乱频繁,在故乡为官的九韶不得不时常参与军事活动。在《数书九章》序言中,九韶也对这一段生活有所描述。1238年,秦九韶回临安丁父忧(后移居湖州,继续为父奔丧),见河上无桥,两岸人民往来很不便,便亲自设计,再通过朋友从府库得到银两资助,在西溪河上造了一座桥。
桥建好后,原本没有名字,因桥建在西溪河上,习惯上被叫作“西溪桥”。直到元代初年,另一位大数学家、游历四方的北方人朱世杰(1249-1314)来到杭州,才倡议将“西溪桥” 更名为“道古桥” ,以纪念造桥人、他所敬仰的前辈数学家秦九韶,并亲自将桥名书镌桥头。
网友提供的原道古桥(疑似)
道古桥一直存在到新千年之交(笔者在附近居住了十九年,历史上有无重建不得而知),因为西溪路扩建改造,原先的桥和溪流被夷(填)为平地(曾经有过的道古桥居委会也随之消失),并建起高楼大厦,诸如国际商务中心、浙江省国土资源厅和黄龙世纪雅苑,只留一个公交车站名道古桥(据说还有地图上未显示的道古桥路)。
2005年,道古桥附近天目山路(杭州东西主干道)南侧西溪支流沿山河上修建了一座人行石桥(在杭大路的马登桥和黄龙路的沿山河桥之间,离开道古桥原址约百米左右,比原先的长且宽阔)。我曾数度实地勘察,发现此桥跨河而建,两岸垂柳披挂,风景优美,且闹中取静,关键是尚未命名,故而引导我突发奇想。
道古新桥。作者摄于杭州
数学大略
1244年,秦九韶任建康府(南京)通判期间,因母丧离任,回浙江湖州守孝三年。正是在这次守孝期间,秦九韶专心研究数学,完成了二十多万字的巨著《数书九章》(1247年9月),名声大震加上他在天文历法方面的丰富知识和成就,曾受皇帝(宋理宗赵昀)召见。他在皇帝面前阐述自己的见解,并呈奏稿和“数术大略”或“数学大略”(即《数书九章》)。可以说,秦九韶是第一个受皇帝接见的中国数学家。几年以后,河北的数学家李冶也曾三度被忽必烈召见。
《数书九章》线装版封面(吴文俊作序)
《数书九章》分九类十八卷,每类九个问题,应该说全面超越了古典名著《九章算术》。其中,最重要的成果无疑要数第一卷大衍类的“大衍总数术”和第九卷“市易类”的“正负开方术”。“开方正负术”或“秦九韶算法”给出了一般n次代数方程正根的解法,系数可正可负。此类方程求解需要迭代运算,那样需要反复求取该多项式的值,而每次求值原本需经n(n+1)/2次乘法和n次加法。秦九韶将其转化为n个一次式的求解,只需n次乘法和n次加法,他并给出了最高10次21个方程的例子。直到19世纪初,这一算法才被英国数学家霍纳发现,称霍纳算法,即便在计算机时代的今天,秦九韶(霍纳)算法仍有重要的意义。
“大衍总数术”给出了孙子定理的一般表述。大约在公元四、五世纪成书的《孙子算经》里有所谓的“物不知数”问题。即“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”“答曰二十三”。换句话说,孙子只是给出了一个特殊例子。而在江苏淮安的民间传说里,这个故事可溯源到公元前二、三世纪西汉名将韩信点兵的故事。
话说秦朝末年,楚汉相争。一次,韩信率兵与楚军交战。苦战一场,汉军死伤数百,遂整顿兵马返回大本营。当行至一处山坡,忽报楚军骑兵追来。只见远方尘土飞扬,杀声震天。此时汉军已十分疲惫,韩信令士兵3人一排,结果多出2名;接着令5人一排,结果多出3名;再令士兵7人一排,又多出2名。韩信当即宣布:我军1073名勇士,敌人不足五百。果然士气大振,一举击败了楚军。
用现代数学语言来描述“大衍总数术”就是:设有k个两两互素的大于1的正整数,其乘积为M,则对任意k个整数,存在唯一不超过M的正整数x,x被各个相除所得余数依次为。秦九韶并给出了求解的过程,为此他发明了“辗转相除法”(欧几里得算法)和“求一术”。后者是指,设a和m是互素的正整数,m大于1,可以求得唯一不超过m的正整数x,使得a和x的乘积被m除后余数为1。
遗憾的是,由于古代中国没有素数的概念(要到清朝康熙年间才有,叫数根),且当时的用途并非在理论上,而主要用于解决历法、工程、赋役和军旅等实际问题,秦九韶对他发现的定理没有给出严格的证明。但对求解型的定理来说,这个并不十分重要。实际上,他还允许模不两两互素,并给出了可靠的计算程序将其化为两两互素的情形。值得一提的是,大衍求一术和欧拉定理是20世纪密码学中赫赫有名的“RSA公钥体系”中的两个关键因素。
此外,秦九韶还给出了“三斜求积术”,此乃著名的海伦公式(已知三角形的三条边长求面积)的等价形式。在第二章天时类,秦九韶给出了历法推算和雨雪量的计算。在南京北极阁气象博物馆里,有古代著名气象学家的雕像,其中也有秦九韶,雕像的石碑上写着:他用“平地得雨之数”(即单位面积内得雨)量度雨水,在世界上最早为雨量和雪量测定奠定了科学理论依据。
享誉欧洲1801年,数学王子高斯的名著《算术研究》(第2篇第7节)里,也给出了上述“大衍求一术”,此前瑞士数学家欧拉已作了深入研究,但他们都不知道中国的数学家早已经有这个结果。直到1852年,秦九韶的结果和方法被英国传教士伟烈亚力(与清代数学家李善兰合作译完欧几里得《几何原本》)译介到欧洲,他的论文《中国科学史札记》在欧洲学术界受到广泛关注,并被迅速从英文转译成德文和法文,此文同时也介绍了秦九韶算法。至于何时何人命名了中国剩余定理,仍是个未解之谜,但应不晚于1929年。
《数书九章》插图,相传画的是湖州飞英塔。
严格来讲,孙子定理应称为秦九韶定理,我在拙作 《数之书》(以及近作《经典数论的现代导引》)中、英文版里也的确这么做了。之所以被命名为孙子定理,应与下文要讲的秦九韶的道德疑难有关。而据笔者的先师潘承洞教授分析,西方人之所以称其为中国剩余定理,是因为古代中国数学家注重计算,缺乏理论建树,因而是一种轻视。无论如何,她都可以说是中国人发现的最具世界性影响的定理,是中外任何一本基础数论教科书不可或缺的,同时也被拓广到另一数学分支——抽象代数里面。此外,还被广泛应用到密码学,数值分析里的多项式插值计算,哥德尔不完全性定理的证明,丢番图方程可解性的判断(希尔伯特第十问题之否定),以及快速傅里叶变换理论等诸多领域。
德国著名数学史家莫里茨·康托尔赞扬秦九韶是“最幸运的天才”,这是因为当时西方尚未为这个命题命名。此前法国大数学家拉格朗日也是这样称赞牛顿的。拉格朗日认为,发现万有引力定律只有一次机会。有着“科学史之父”美誉的美国科学史家乔治·萨顿认为,秦九韶是“他那个民族,他那个时代,并且确实也是所有时代最伟大的数学家之一。”2005年,牛津大学出版社出版了《数学史,从美索不达米亚到现代》,该书重点介绍的12位数学家中,秦九韶是唯一的中国人。
剑桥的数学桥,相传为牛顿设计。作者摄
秦九韶造桥的故事,堪与英国数学家牛顿造桥的故事媲美。现今剑桥大学的皇后学院内,流经的剑河上有一座桥叫数学桥,只因传说原桥设计师是17世纪的数学家牛顿。据称牛顿造桥时没用到一根钉子,后来有好事者悄悄把桥拆下来,发现真是这样,却再也无法安装回去,只好在原址重新造了一座桥。时至今日,数学桥早已成为一处名胜,可以说是到访剑桥旅客的必游之地。
相比之下,道古桥的故事不仅更为古老(比牛顿早四个世纪),且与两位古代大数学家有关(可惜当年宣传甚少,甚至杭州多数数学工作者都不知道,道古即秦九韶)。如果得以(重新)命名,酌情在桥头设立一块石碑,必将为杭州这座历史文化名城增添一处不可多得的科学人文景观(此建议后来被杭州市政府采纳,我并请数学家王元先生题写了桥名)。
道德疑难
必须要指出的是,由于秦九韶的学术成就未被同代人认识,加上一些不好的传闻和描述,称其贪赃枉法、生活无度,甚至犯有人命、非复人类,他在暮年和后世成了一个有争议的人物。所有宋史和地方志都未为秦九韶列传,他的名字和桥名时隐时现,后裔也下落不明。不仅中文数论教科书里不出现他的名字,中国校园里也只张贴或雕塑祖冲之的像,甚至英国BBC新近制作播出的四集纪录片《数学的故事》在夸赞他的学术成就之余(秦是唯一被提及的中国数学家,也是七位东方数学家中镜头最多的一位),也渲染其道德污点。
经笔者多方求证和讨教,得知有关秦九韶的传闻主要有两个出处,其内容大有互通。比秦九韶年长十五岁的福建词人刘克庄《后村先生大全集》中的《缴秦九韶知临江军奏状》(1260)在前,比秦九韶小三十岁的湖州文人周密《癸辛杂识·续集》中的《秦九韶》(共两页,癸辛是杭州的街名,宋亡后周密留居此地)在后,后者曾被清代(乾隆年间)的《四库全书》列入“小说家之类”流传。可以说,刘周两人都是南宋文学史上有一定影响和地位的人。
广东梅州,秦九韶的谢世地。作者摄
到了嘉庆年间,文理兼备的扬州学派著名学者焦循,浙江巡抚、经学家、教育家阮元,以及晚清湖州学者、藏书家陆心源等人相继批驳周密,指其造谣诽谤,始有人为秦九韶列传。而刘克庄生前便趋奉贾似道,被认为谀词产语,连章累牍,为人所讥。1842年,《数书九章》由历算名家宋景昌校订后第一次印刷出版,结束了近六百年的传抄史。之前,其抄本先后被收入明代的《永乐大典》和《四库全书》。在传抄过程中,一度被称为《数学九章》,后被明末戏剧家王应遴定名为《数书九章》。从这个意义上,《数书九章》堪与荷马史诗媲美。
必须指出的,吴潜和贾似道是宋理宗时一忠一奸的宰相,秦九韶和刘克庄分别与两人过从甚密。吴潜出身状元,以正直无私、忧国忧民、忠义爱国闻名,还是一代词人、水利专家和抗倭英雄;贾似道恶贯满盈,却是皇帝宠爱的贵妃的同父异母弟弟,人称蟋蟀宰相。1261年,秦九韶去世那年,年近七旬的吴潜被贾似道罗织罪名,再度被罢免宰相,流放循州(今广东龙川),与秦九韶的谢世地梅州(今梅县)相去不远,且次年便暴病身亡(疑被投毒)。
吴潜是安徽宁国人(一说是湖州德清人),那里与湖州毗邻,秦九韶在巴州任职时便与之相识,后一同在湖州丁忧母。或许,秦九韶从吴潜赠送的地基上建起的房子有些奢华,引得当地文人周密的嫉妒。特别是,周密是湖州本地人而秦九韶是异乡人。除了擅长作词以外,周密还爱好史学、画帖、医学,甚至算学。他的《志雅堂杂钞》也是一本杂书,有趣的是,里头居然有韩信点兵的描述,他称之为“鬼谷算”或“隔墙算”。
秦九韶纪念馆,四川安岳。作者摄
另一方面,秦九韶的骈俪诗词也颇有造诣,并曾得著名词人李刘指点,因此也不排除文人相轻的可能性。秦九韶的遭遇无疑是政治斗争的牺牲品,他生命的最后六年是在梅州度过的。事实上,在金人和蒙古大军南下时,吴潜和贾似道分属主战派和主和派。笔者曾专程前往梅州,只见周围群山环抱,城内主要街道栽满了榕树。我想起造纸术的发明人蔡伦,他和秦九韶在科学、技术上的成就在中国古代无人可以匹敌。蔡伦因为发明造纸术被封侯,晚年却在宠爱他的皇太后过世后耻于被政敌侮辱,沐浴后穿戴整齐,喝毒药而死。
有意思的是,后来曾有无名氏作《长相思》:“去年秋,今年秋,湖上人家乐复忧,西湖依旧流。吴循州,贾循州,十五年前一转头,人生放下休。”也就是说,15年以后,贾似道也被贬到当年吴潜遭贬去世的地方,且途中被富有正义感的监押官杀死。到了清代,吴潜的后裔吴鲁又考中状元、光宗耀祖,吴氏家族多居住在福建,其中泉州涂门街的吴氏大宗祠又名东观西台。至于秦九韶的最后岁月、下葬地及其后裔,笔者虽曾在梅州努力探访,仍无从知晓。假如真的如刘周文章所言,他早应被处斩或入狱,如何只是被贬官且仍“治政不辍”?
值得一提的是,《数书九章》里有一幅著名的插图,是用来计算图中的宝塔塔尖高度的,通过观察角度的调整和正切函数的运用,便可以求得。这座宝塔与湖州城内的唐代古寺飞英寺里的飞英塔造型相似,此塔内是石塔外是砖木塔,因为塔中有塔而别具一格,属于全国重点文物保护单位。虽然内塔和外塔分别建于唐代和北宋年间,但在12世纪前后遭到拆毁,现在的塔重建于13世纪30年代,刚好在秦九韶寓居湖州之前。
05
世界本原
最后,我想谈谈秦九韶为《数书九章》这部唯一的著作所作的序诗(每卷一首)和序言。第一卷是大衍类,即最有价值的一次同余式求解理论。他在这卷序诗里写道,“巍巍昆仑,气势磅礴;世界本原,在于数学。”第二卷是关于天文历法,序诗曰,“七大行星,苍穹回旋;世间诸事,变化多端。”第三卷是关于土地面积测量,序诗的开头是,“百姓虽小,当放首位;审时度势,以观世界。”
接下来的几卷先后涉及测量计算、运输税收、粮谷容积、建筑施工、军需供应、交易利息等。在赋役一卷中他写道,“当官的要施仁政,为民着想,设身处地,犹如自己挨饿受灾。如果赋税徭役分配不均,难道能让人心安理得吗?”因此可以说,这部著作不只谈论数学,还涉及自然现象和社会生活,成为后人了解当时社会政治和经济生活的重要参考文献。
秦九韶纪念馆,四川安岳。作者摄在“钱谷”一卷,序诗更是针砭时弊,有理有据。“纳粮上税,要看等级,粮食入库,要看时节。一粒粒粟,一寸寸丝, 都是男女劳动所得。”“达官贵人相互攀缘,欺榨百姓,大小贪官,用尽心机。”“治理财政,理当犹如智者治水。正本清源,有条不乱,治标治本,消除隐患。”“那些昏官视而不见,人民悲惨,用刑不断。离开理智愈来愈远,为官不仁!可叹可叹!”
在序言的开头,秦九韶便提到,周朝数学属于“六艺”(礼、乐、射、御、书、数)之一。学者和官员们历来重视、崇尚数学。人们因为要认识世界的规律,产生了数学。从大的方面说,数学可以认识自然,理解人生;从小的方面说,数学可以经营事务,分类万物。秦九韶坚信,世间万物都与数学相关,这与古希腊的毕达哥拉斯学派不谋而合。
蔡天新在南京北极阁气象博物馆秦九韶塑像旁
这也正是数学吸引秦九韶的地方,他向学者、能人求教,深入探索数学之精微。“我在青少年时代曾随父亲到过都城临安,有机会访问国家天文台的历算家,向他们学习历算。此外,我还从隐君子那里学习数学。”这里的隐君子并非指吸毒(烟)成瘾的人,而是指隐居逃避尘世的人。其时,元军入侵四川,九韶有时却不得不在战乱中长途跋涉,可是他仍不忘钻研数学。
与此同时,秦九韶也感叹,数学家的地位和作用,而今不被人们所认识,这里他主要指的是纯粹数学和暂时无法用到的方法技巧。他认为,数学这门学问遭到鄙视,算学家只被当作工具使用,这就犹如制造乐器的人,仅仅拨弄出乐器的声音。“原本我想要把数学提升到哲理(道)的高度,只是实在太难做到了。”由此我们可以推断,这是一位有思想有品味的人,与传言中的秦九韶实难相符。时光流逝了七个多世纪,秦九韶的道德污点也成为古代中国科学史上最大的疑案。
2012年5月,杭州 “ 作者简介
蔡天新浙江大学数学学院教授、博士生导师、求是特聘学者,近作有《小回忆》增订版、《26城记》、《数学与艺术》、《经典数论的现代导引》(中、英文版)、《完美数与契波那契序列》(即出),主编《地铁之诗》、《高铁之诗》。
蔡天新教授近作
《经典数论的现代导引》作者:蔡天新出版社:科学出版社出版时间:2021.5点击封面图立即购买
内容简介
本书既适合用作高等院校本科生、研究生的基础数论课程教材或参考书,也适合专业的数论工作者和业余的数学爱好者阅读。
目 录
向上滑动阅览
序: 数是我们心灵的产物
第章整除的算法
1.1 自然数的来历
完美数与亲和数
1.2 自然数的奥妙
镶嵌几何与欧拉示性数
1.3 整除的算法
梅森素数与费尔马素数
1.4 最大公因数
格雷厄姆猜想
1.5 算术基本定理
希尔伯特第 8问题
第章同余的概念
2.1 同余的概念
高斯的《算术研究》
2.2 剩余类和剩余系
函数[x]与 3x+1问题
2.3 费尔马-欧拉定理
欧拉数和欧拉素数
2.4 表分数为循环小数
默比乌斯函数
2.5 密码学中的应用
广义欧拉函数
第章同余式理论
3.1 秦九韶定理
斐波那契的兔子
3.2 威尔逊定理
高斯的《算术研究》
3.1 丢番图方程
毕达哥拉斯数组
3.2 卢卡斯同余式
覆盖同余系
3.3 素数的真伪
素数或合数之链
第章平方剩余
4.1 二次同余式
高斯环上的整数
4.2 勒让德符号
表整数为平方和
4.3 二次互反律
n角形数与费尔马
4.4 雅可比符号
阿达马矩阵和猜想
4.5 合数模同余
正十七边形作图法
第5章n次剩余
5.1 指数的定义
埃及分数
5.2 原根的存在性
阿廷猜想
5.3 n次剩余
佩尔方程
5.4 合数模的情形
丢番图数组
5.5 狄利克雷特征
三类特殊指数和
第6章整数幂模同余
6.1 贝努利数和多项式
库默尔同余式
6.2 荷斯泰荷姆定理
椭圆曲线
6.3 拉赫曼同余式
abc猜想
6.4 莫利定理和雅克布斯坦定理
自守形式和模形式
6.5 一类调和和同余式
多项式系数非幂
第7章加乘数论
7.1 新华林问题
7.2 新费尔马定理
7.3 欧拉猜想
7.4 F 完美数问题
7.5 新同余数问题
7.6 abcd方程
参考文献
附录 10000以内素数表
本书特色
带你了解数论的前沿:
主要内容虽说是基础的,但几乎每小节都穿插前沿的问题
延展你对数论的理解:
前五章内容虽属于经典,但多处已用现代的目光将其拓展
丰富你的数论知识:
标签: #勒让德多项式的求值算法