Mgccl 发表于 2009-3-6 08:10:43

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

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

kon3155 发表于 2009-3-6 11:34:18

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

gxqcn 发表于 2009-3-6 12:32:34

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

northwolves 发表于 2009-3-8 12:53:31

假设$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 发表于 2009-3-8 14:16:07

原帖由 northwolves 于 2009-3-8 12:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
假设$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 发表于 2009-3-17 09:36:32

原帖由 gxqcn 于 2009-3-6 12:32 发表 http://bbs.emath.ac.cn/images/common/back.gif
$sqrt(x^2+y^2)=sqrt(((x+y)^2+(x-y)^2)/2)~=(|x|+|y|)/sqrt(2)$
仅适用于 $x, y$ 差异很小的情形。
这方法好，四平八稳的
页: [1]
查看完整版本: 两个整数的平方的整数平方根