发现完美的广场和建筑方块

自古以来，数学家就一直面临求完全平方根的问题。计算数论的最新发现使发现平方数的有效算法得以发展。来自德州农工大学加尔维斯顿校区基础科学系(数学)的菲利普·布朗教授开发了一种新的算法，可以检测出一个完全平方数，并使用二进制算法来计算它的根。布朗教授演示了他的算法是如何容易实现的，并可以测试数以百万计的数字。

自古以来，找到完全平方数(一个数自身相乘得到的平方数)以及求其平方根的问题一直是困扰数学家的难题。

实际上没有人知道谁发明了平方根，但据认为是平方根的知识最初来自土地的划分区域分成相等的部分，使得方形侧的长度成为其区域的平方根。巴比伦人和希腊人已被认为发现了苍鹭的方法，牛顿的迭代方法的前身虽然印度数学家被认为已经使用了800公元左右的类似系统。埃及人使用逆比例方法计算方形，回到1650BC。200BC左右的中国数学着作表明，使用过量和缺陷方法近似方形。在1450AC中，RemioMontanus发明了一个方形根的符号，写成精心制作R. Square Root符号√在1525年首次使用。

递归算法，如牛顿法，从平方根的近似值或猜测开始，然后先找到更高阶的数字。这种迭代方法可以在计算机上使用浮点运算来实现，但是对于非常大的数字，它们通常很难实现，并且除法运算会产生计算困难。最近，计算数论——数论的一个领域，关注于发现和实现有效的计算机算法——已经使涉及筛选方法的算法得以发展，以确定一个正整数是否为完美幂。

来自德克萨斯农工大学加尔维斯顿校区基础科学系(数学)的菲利普·布朗教授开发了一种新的算法来发现平方数。该算法将初等数论和算法数论相结合，只使用加、减、乘，不需要可能存在问题的除法运算。该算法易于实现，可以测试数以百万计的数字。此外，这种新算法可以确定地测试一个数字是否为完全平方数，而其他方法只能在很高的概率下测试。

Konnor Chappell(德州农工大学加尔维斯顿分校的一名学生)帮助Brown教授编写了Python代码以实现算法。

揭示完全平方的性质
布朗教授观察到，如果数字以2的幂为基数表示，比如在二进制、八进制和十六进制数字系统中，就会揭示出完全平方的一些性质。这为他的算法如何识别一个完全平方并建立其平方根奠定了基础，从低阶数字开始，一直到高阶数字。

因为该算法从低阶数字开始建立平方根，如果我们从右到左读取或标记这些数字，就更容易理解。

布朗教授演示了算法如何从转换输入数字开始N从底数10到底数2。如果N是偶数，那么它的基础2表达式开始（在右侧），其中一系列二进制数字均等于0，例如，十进制数4和20分别表示为100和10100的基座2。当输入号码时，N，是一个偶数，则该数字的二进制表示的初始零字符串被截断，留下得到的奇数待测试。如果这个奇数是平方，那么N要么是一个正方形，要么是两个正方形。这意味着算法只需要继续N是奇怪的。所以给出了一个奇数整数N在八进制格式中，算法将确定n是完美的正方形，如果需要计算平方根。

与基地8的观察
以8为基数是演示布朗教授算法的一个方便的数字系统，因为它最接近以10为基数。以8为基数乘4，例如1 × 4 = 4,2 × 4 = 10，总是得到一个右边有0或4的数字。因此，所有以8为底数的完全平方都以0或4开始(从右到左)。布朗教授还指出，所有以8为底的奇数完全平方数都以1开头。

Brown教授为该算法开发了理论依据，该算法提供了新的洞察方数的属性。

以2为底^S.
此外，布朗教授表明，对于较高功率的碱，表示为2^S.，如果是第一个基地2^S.数量的数字N不一致（Modulo 2^S.)的平方，然后是奇数N不是一个方形的数字。

时间复杂性
算法的时间复杂度量化了算法运行所需的时间，它是输入长度的函数。布朗教授的算法测试是否为正整数N是平方数，和/或计算的平方根N时间复杂度为O(log²N)/s)，其中s是所选底数的乘数——例如，以8为底数的s = 3，以16为底数的s = 4。这种“大O”表示算法的性能与(log)成正比²N)/s，使得算法非常高效，特别是在处理大量数字时。

时间复杂性与S成反比，虽然它是一个编程决策，但如果用户选择速度，则算法将更有效N．在输入数字的试验中N从1000到512000位，布朗教授观察到似乎存在与数字位数对数成正比的最佳s值N被测试。

发展
Brown教授为该算法开发了一种理论依据，该算法使用二进制，八进制和十六进制算术来提供新的洞察方数的性质。这项工作也可以扩展到具有甚至更大功率的基础的其他数字系统。

该算法可以用二进制算法检测完全平方根并建立其根。

该算法可以用二进制算法检测完全平方根并建立其根。它的使用相对简单，在计算复杂度和存储空间要求方面与其他算法不相上下，其优点是结果具有确定性，不需要对概率进行解释。

在算法中，布朗教授为用户提供了许多选项，让他们根据自己的需求定制算法。例如，程序员可以选择使用预先计算好的选择矩阵或扩展的欧几里得算法来求解乘法逆。他们还可以选择以8为基数或以2为幂的任何其他基数来实现算法，这可能取决于要测试的数字的大小。

正在进行和未来的工作
该算法使用底数为2的幂的数字系统有效地运行。目前还没有直接使用10号基地等其他基地的方法。布朗教授正忙于开发二进制算法的递归实现，该算法在每一级递归中使用较小的s值，开始时s值与log n成比例。该算法的时间复杂度提高了O(log)N日志²日志N)，用台式电脑在不到一小时的时间内就可以测试数十亿个数字。他还在考虑该算法是否可以推广到大于2的完美幂，比如完美立方体。