问题标签 [square-root]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
6 回答
9409 浏览

algorithm - 用整数算术计算第 N 个根

有几种方法可以仅使用整数算术来找到整数平方根。比如这个。它带来了有趣的阅读和一个非常有趣的理论,特别是对于我这一代,这些技术不再那么有用了。

最主要的是它不能使用浮点运算,因此排除了牛顿法及其推导。我知道找到根的唯一另一种方法是二项式展开,但这也需要浮点运算。

有哪些技术/算法仅使用整数算术计算整数 n 次根?

编辑:感谢到目前为止的所有答案。他们似乎都在进行稍微聪明的试验和改进。没有更好的办法吗?

Edit2:好的,所以如果没有试验/改进以及牛顿法或二进制搜索,似乎没有聪明的方法可以做到这一点。谁能在理论上对两者进行比较?我在两者之间运行了许多基准测试,发现它们非常相似。

0 投票
3 回答
1277 浏览

algorithm - 从整数和余数中找到平方根作为浮点数?

我现在正在研究计算平方根的特定算法,它返回平方根的整数部分和余数。

例如:mysqrt(140) = 11*11 + 19 = integer 11, remainder 19

问题是我可以将平方根计算为浮点数,例如 140 的平方根是 ~ 11.8321 ....?

从评论编辑

我正在研究一个定点平方根的 VHDL 实现,它只使用像左/右移位、加法和减法这样的二进制操作。

...算法就足够了。

编辑 2我实际上在这里阅读这个算法:http: //pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf

似乎可以通过将radicand左移2n来获得更好的精度。我不太确定为什么这有效?谁能解释一下

0 投票
3 回答
1692 浏览

javascript - 使用查找表进行优化:

这家伙:http ://andrew-hoyer.com/experiments/cloth/做了一个 javascript 算法来模拟布料。他指出代码太慢了,所以他不得不使用泰勒级数优化平方根。

  1. 难道不能通过预先计算每个可能的值并使用查找表来优化它吗?

  2. 这个经常用吗?例如,在 3d 游戏中,他们是否真的执行计算,或者他们已经为每个 sin、cos、tg、sqrt 和类似函数提供了一个查找表?

  3. 为什么不将其预编程到处理器中?

0 投票
1 回答
781 浏览

algorithm - 有效地找到一个完美的正方形

如何从函数中找到第一个完美正方形:f(n)=An²+Bn+C?给出了 B 和 C。A,B,C 和 n 总是整数,而 A 总是 1。问题是找到 n。

Example: A=1, B=2182, C=3248

第一个完美正方形的答案是 n=16,因为sqrt(f(16))=196.

我的算法增加 n 并测试平方根是否为整数。

当 B 或 C 很大时,该算法非常慢,因为需要 n 次计算才能找到答案。

有没有更快的方法来做这个计算?有没有一个简单的公式可以得出答案?

0 投票
5 回答
218 浏览

c++ - 计算距离:方法“必须返回一个值”?

我正在尝试调用该dist()方法,但是我不断收到错误消息,说dist()必须返回一个值。

0 投票
3 回答
5717 浏览

c - C/C++中double的快速平方反比

最近我在分析一个程序,其中的热点肯定是这个

之后不使用值 d2,因为我只需要值 c。前段时间我读过关于快速反平方根的卡马克方法,显然不是这种情况,但我想知道类似的算法是否可以帮助我计算 1/x^2。

我需要相当准确的精度,我已经检查过我的程序没有使用 gcc -ffast-math 选项给出正确的结果。(g++-4.5)

0 投票
4 回答
1353 浏览

javascript - Math.sqrt() 返回无穷大?

Math.sqrt();似乎适用于长度小于 310 个字符的任何数字。

但是,任何 310 个字符或以上的数字都将返回无穷大......

如果你想自己测试一下,这里是 jsfiddle http://jsfiddle.net/gqhk9/2

无论如何,我需要得到数字的平方根,包括一些 310 个字符或更长的数字。

我怎么能在js中做到这一点?

0 投票
2 回答
3241 浏览

c++ - 以代数方式简化平方根

我想以代数方式简化整数的平方根,而不是用数值计算它,即√800应该是20√2,而不是28.2842712474619

我找不到通过编程解决这个问题的任何方法:(

0 投票
1 回答
2954 浏览

bezier - 如何计算 4 次多项式的长度(在平方根内)

我正在尝试用这种形式求解积分(其中 a、b、c、d、e、f 和 g 是常数):

我在尝试找到三次贝塞尔曲线的长度时遇到了这个问题(不使用递归细分)。我的目标是有一个符号方程,可以找到任何 t 范围之间的贝塞尔曲线的长度(即上面方程中的 f 和 g)。

我的第一个猜测是完成平方,但维基百科很清楚这仅适用于二次方程。
按部分集成......似乎不适用于此。

下一个问题(虽然,不是本主题的主题),使用它真的比递归细分贝塞尔曲线更快吗?

0 投票
1 回答
5539 浏览

bit-shift - 使用位移求整数平方根的最快方法是什么?

我正在寻找计算数字(整数)平方根(整数)的最快方法。我在维基百科中遇到了这个解决方案,它找到一个数字的平方根(如果它是一个完美的平方)或它最近的下完美平方的平方根(如果给定的数字不是一个完美的平方:

我尝试了很多测试运行来跟踪算法,但我似乎不理解里面的部分while(bit!=0)。有人可以向我解释这部分吗?