两个整数的平方的整数平方根

Mgccl

$x$,$y$为整数. $x^2+y^2<2^32$ $z = \sqrt{x^2+y^2}$, 有没有比算出$x^2+y^2$然后再求整数平方根还要快速的方法呢? 特别是$x$和$y$相差非常大是不是有更快的方式呢?

kon3155

比较奇怪的问题，思维都定势了，没有其他想法了

gxqcn

$sqrt(x^2+y^2)=sqrt(((x+y)^2+(x-y)^2)/2)~=(|x|+|y|)/sqrt(2)$ 仅适用于 $x, y$ 差异很小的情形。

northwolves

假设$z=x+k$ $x+k=sqrt(x^2+y^2)$ $k=sqrt(x^2+y^2)-x=y^2/(sqrt(x^2+y^2)+x)~=y^2/(2x)$ 即： $z=x+|__y^2/(2x)__|$ 几个例子： x y z z-x y^2/2x 1012 45 1013 1 1.0004941 1023 64 1025 2 2.0019550 1056 92 1060 4 4.0075758 1088 66 1090 2 2.0018382 1092 81 1095 3 3.0041209 1104 47 1105 1 1.0004529 1150 96 1154 4 4.0069565 1155 68 1157 2 2.0017316 1200 49 1201 1 1.0004167 1224 70 1226 2 2.0016340 1260 87 1263 3 3.0035714 1295 72 1297 2 2.0015444 1300 51 1301 1 1.0003846 1368 74 1370 2 2.0014620 1404 53 1405 1 1.0003561 1440 93 1443 3 3.0031250 1443 76 1445 2 2.0013860 1512 55 1513 1 1.0003307 1520 78 1522 2 2.0013158 1599 80 1601 2 2.0012508 1624 57 1625 1 1.0003079 1632 99 1635 3 3.0027574 1680 82 1682 2 2.0011905 1740 59 1741 1 1.0002874 1763 84 1765 2 2.0011344 1848 86 1850 2 2.0010823 1860 61 1861 1 1.0002688 1935 88 1937 2 2.0010336 1984 63 1985 1 1.0002520 2024 90 2026 2 2.0009881 2112 65 2113 1 1.0002367 2115 92 2117 2 2.0009456 2208 94 2210 2 2.0009058 2244 67 2245 1 1.0002228 2303 96 2305 2 2.0008684 2380 69 2381 1 1.0002101 2400 98 2402 2 2.0008333 2520 71 2521 1 1.0001984 2664 73 2665 1 1.0001877 2812 75 2813 1 1.0001778 2964 77 2965 1 1.0001687 3120 79 3121 1 1.0001603 3280 81 3281 1 1.0001524 3444 83 3445 1 1.0001452 3612 85 3613 1 1.0001384 3784 87 3785 1 1.0001321 3960 89 3961 1 1.0001263 4140 91 4141 1 1.0001208 4324 93 4325 1 1.0001156 4512 95 4513 1 1.0001108 4704 97 4705 1 1.0001063 4900 99 4901 1 1.0001020

winxos

原帖由 northwolves 于 2009-3-8 12:53 发表 假设$z=x+k$ $x+k=sqrt(x^2+y^2)$ $k=sqrt(x^2+y^2)-x=y^2/(sqrt(x^2+y^2)+x)~=y^2/(2x)$ 即： $z=x+|__y^2/(2x)__|$ 几个例子： x y z z-x y^2/2x 1012 45 1013 1 1.0004941 1023 64 1025 2 2 ...

这个只适用于k相对X比较小的情况吧， 如果x与y差不多的时候，误差比较大， >>(1001^2+1002^2)^.5 ans = 1.4163e+003 >> 1002*1002/(2*1001) ans = 501.5005 我觉得应该按照xy关系分类处理，采用不同算法，再给出一个误差限。

wayne

原帖由 gxqcn 于 2009-3-6 12:32 发表 $sqrt(x^2+y^2)=sqrt(((x+y)^2+(x-y)^2)/2)~=(|x|+|y|)/sqrt(2)$ 仅适用于 $x, y$ 差异很小的情形。

这方法好，四平八稳的