行业资讯
23岁学生推翻乘法古老猜想，数学家仍在探寻最快乘法方法！
数学乘法运算的未解之谜小学生计算一位数乘法靠背诵乘法表计算三位数乘法则需用到算法。几千年来数学家认为将数字堆叠相乘是最快的乘法方法然而1960年一位23岁的年轻人打破了这一认知引发了至今未解的谜团。这个谜团对数字世界至关重要因为乘法是计算机的基础运算加密技术、机器人技术、人工智能、音频处理等任务都涉及乘法大规模运算时简单运算也会成为瓶颈效率提升将产生全球性经济影响。小学乘法算法的瓶颈小学算法中运算量与数字位数的平方成正比。计算机科学家用大O符号表示步骤数小学算法需要O( _n_ ²)步数字位数翻倍计算工作量变为四倍位数变为一千倍工作量变为一百万倍。卡拉楚巴算法的突破自古以来数学家怀疑O( _n_ ²)是乘法运算的固有速度极限苏联数学教授安德烈·柯尔莫哥洛夫正式提出此猜想。但仅一周后23岁的学生阿纳托利·卡拉楚巴就证明他错了。有趣的是证明论文由柯尔莫哥洛夫撰写以卡拉楚巴为第一作者发表。卡拉楚巴用加法替代乘法以计算12 × 34为例传统方法需四次乘法他的方法通过巧妙代数技巧只需三次乘法。对于更大数字如1234 × 5678原本需16次一位数乘法用他的方法只需9次。该算法运行时间约为O( _n_ ^1.585)比O( _n_ ²)快得多。卡拉楚巴算法已融入日常软件Python在数字达到约630位十进制数时会采用该算法。寻找乘法终极速度极限卡拉楚巴算法引发了寻找乘法终极速度极限的竞赛2019年数学家大卫·哈维和乔里斯·范德霍芬提出新算法运行时间为O( _n_ × log _n_ )增长速度极慢。不过该算法像卡拉楚巴算法一样只有在数字极其巨大时才领先属于“银河算法”。即便有此限制它仍是里程碑式的成就理论上创造了最快乘法方法记录也可能为实践中以O( _n_ × log _n_ )步运行的算法铺平道路。如今理论计算机科学家怀疑O( _n_ × log _n_ )是最快速度但正式证明仍是该领域的难题历史也提醒我们猜想可能被推翻。那么乘法运算的最快速度究竟是多少呢
郑州网站建设
网页设计
企业官网
