计算x ^ 2的算法或计算数字的平方根的算法更有效?

盖尔伯

计算x ^ 2和x ^(1/2)的效率更高的算法是什么?两者之间最好的是什么更有效?我要解决的问题是找到第n个“绿色”数字,如果N ^ 2以n结尾,则N是“绿色”数字。例如5 ^ 2 = 25、376 ^ 2 = 141376。这是我尝试的一些代码,但是要花很多时间来计算第十个数字:

我所做的基本上基本上是取x个数字中的i个获得i的最后x个数字,而没有加总功效,如果将总和1与累加器变量重合,则将这个最后x个数字与i进行比较。我正在考虑以另一种方式来解决这个问题,而不是为每个数字计算i ^ 2,而是计算数字的i ^(1/2)并进行相同的比较,可能会改善程序,因为只需要接受即可。计算以0,1,4,9,6,5结尾的数字。但是我知道真正的进步来自用另一种方式思考问题,而我丝毫没有丝毫想法。

def special_multiply(sa):
reverse_num = reversed(sa)
accumulator = 0
for i, digit in enumerate(reverse_num):
    temp_chunk = sa[i:]
    temp_pow = "".join(['1', '0' * i])
    accumulator += int(digit) * int(temp_chunk) * int(temp_pow)
return accumulator % int("".join(['1', '0' * (i + 1)]))

def green(n):
count = 0
i = 0
while count <= n:
    i += 1
    si = str(i)
    if si == str(special_multiply(si)):
        count += 1
return i
大卫·艾森斯塔

换句话说,如果一个k数字x满足,则该数字为绿色

 2           k
x  = x mod 10 .

中国剩余定理意味着,这个方程就相当于两个方程

 2          k
x  = x mod 2

 2          k
x  = x mod 5 .

求解这些方程等效于找到x^2 - x = x (x - 1)2的幂为模的多项式的根5Mod2和mod5有两种解决方案,分别是x = 0x = 1由于多项式的导数对于两个解2x - 1都是非零mod2和mod 5,因此Hensel引理暗示0并且1实际上是唯一的对幂进行幂解的解决方案。

因此,有四个解决方案mod 10^k,它们具有残基01mod2^k5^k例如376 mod 5^3 = 1376 mod 2^3 = 0对于每个k,我们可以使用中国余数定理找到四个解(其中一个为零,因此不合格)。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

  1. 1

    来自Microsoft Office加载项taskpane.js的MySQL驱动程序模块的空引用

  2. 2

    使用AWS Cognito和React的仅限Facebook / Google的登录名(无用户名/密码)

  3. 3

    创建Windows Phone 8应用并将其连接到数据库的最佳方法(最好是SQL Server)

  4. 4

    为什么Java中的System.out.println()打印到控制台?

  5. 5

    卷曲函数无法解析来自bash中变量的代理

  6. 6

    是什么在Android的consumer-rules.pro和proguard-rules.pro之间的区别?

  7. 7

    设置与Apache POI Excel表散点图标记图标的颜色

  8. 8

    将Qt Pyside2与asyncio await语法一起使用?

  9. 9

    崇高的文字+蟒蛇的蟒蛇

  10. 10

    任务':app:minifyReleaseWithR8'.java.lang.NullPointerException的执行失败(无错误消息)

  11. 11

    OpenJDK的和AdoptOpenJDK的区别

  12. 12

    大型数据集缓存到Spark内存中时,“超出了GC开销限制”(通过sparklyr和RStudio)

  13. 13

    “执行测试CMAKE_HAVE_LIBC_PTHREAD”失败实际上是什么意思?

  14. 14

    使用Core 2.2中的Identity,如何在关闭浏览器15分钟后保持会话活动?

  15. 15

    React中的ForwardRefExoticComponent和ForwardRefRenderFunction有什么区别?

  16. 16

    猫鼬查找结果,然后将字段替换为findOne

  17. 17

    如何降级Google Colab的Torch版本

  18. 18

    Keras提前停止回调错误,val_loss指标不可用

  19. 19

    如何避免VSCode中的“导入路径不能以.ts扩展名结尾”错误?

  20. 20

    Nuxt.JS:如何在页面中获取路由URL参数

  21. 21

    是否有为什么会AccessibilityManager.sInstance导致内存泄漏的一个原因?

热门标签

归档