Escrever o seu próprio função de raiz quadrada
https://stackoverflow.com/questions/1623375
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como você escrever sua própria função para encontrar a raiz quadrada mais precisa de um inteiro?
Depois de googling, eu encontrei este (arquivado a partir de sua link original ), mas em primeiro lugar, eu não obtê-lo completamente, e em segundo lugar, é de aproximadamente também.
Suponha raiz quadrada como número inteiro mais próximo (à raiz real) ou um float.
Solução
A seguir calcula andar (sqrt (N)) para N> 0:
x = 2^ceil(numbits(N)/2)
loop:
y = floor((x + floor(N/x))/2)
if y >= x
return x
x = y
Esta é uma versão do método de Newton dada em Crandall & Pomerance, "Números Primos: Uma Perspectiva Computacional". A razão que você deve usar esta versão é que as pessoas que sabem o que estão fazendo provaram que converge exatamente no chão da raiz quadrada, e é simples de modo a probabilidade de fazer um erro de implementação é pequena. Também é rápido (embora seja possível construir um algoritmo ainda mais rápido - mas fazer isso corretamente é muito mais complexo). A busca binária devidamente implementado pode ser mais rápido para muito pequeno N, mas você pode também usar uma tabela de pesquisa.
Para volta para o mais próximo inteiro, apenas compute t = andar (sqrt (4 N)) usando o algoritmo acima. Se o bit menos significativo de t é definido, então escolher x = (T + 1) / 2; caso contrário escolher t / 2. Note que este rodadas até em um laço; você também pode rodada para baixo (ou rodada até mesmo), observando se o resto é diferente de zero (ou seja, se t ^ 2 == 4 N).
Note que você não precisa usar aritmética de ponto flutuante. Na verdade, você não deve. Este algoritmo deve ser implementado inteiramente usando números inteiros (em particular, o andar () funciona apenas indicam que a divisão inteira regular deve ser usado).
Outras dicas
Dependendo de suas necessidades, a estratégia de dividir e conquistar simples pode ser usado. Não vai convergir como rápido como alguns outros métodos, mas pode ser muito mais fácil para um novato para entender. Além disso, uma vez que é um O (log n) algoritmo (reduzir para metade o espaço de busca cada iteração), o pior caso para um float de 32 bits será de 32 iterações.
Vamos dizer que você quer a raiz quadrada de 62,104. Você escolhe um valor a meio caminho entre 0 e que e Praça lo. Se o quadrado é maior do que o seu número, você precisa se concentrar em números menor que o ponto médio. Se for muito baixa, concentrado sobre aqueles superior.
Com matemática real, você poderia manter dividindo o espaço de busca em dois para sempre (se ele não tem uma raiz quadrada racional). Na realidade, os computadores acabarão por ficar sem precisão e você terá a sua aproximação. O seguinte programa C ilustra o ponto:
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
float val, low, high, mid, oldmid, midsqr;
int step = 0;
// Get argument, force to non-negative.
if (argc < 2) {
printf ("Usage: sqrt <number>\n");
return 1;
}
val = fabs (atof (argv[1]));
// Set initial bounds and print heading.
low = 0;
high = mid = val;
oldmid = -1;
printf ("%4s %10s %10s %10s %10s %10s %s\n",
"Step", "Number", "Low", "High", "Mid", "Square", "Result");
// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) {
oldmid = mid;
// Get midpoint and see if we need lower or higher.
mid = (high + low) / 2;
midsqr = mid * mid;
printf ("%4d %10.4f %10.4f %10.4f %10.4f %10.4f ",
++step, val, low, high, mid, midsqr);
if (mid * mid > val) {
high = mid;
printf ("- too high\n");
} else {
low = mid;
printf ("- too low\n");
}
}
// Desired accuracy reached, print it.
printf ("sqrt(%.4f) = %.4f\n", val, mid);
return 0;
}
Aqui está um par de pistas para que esperamos obter uma idéia de como ele funciona. 77:
pax> sqrt 77
Step Number Low High Mid Square Result
1 77.0000 0.0000 77.0000 38.5000 1482.2500 - too high
2 77.0000 0.0000 38.5000 19.2500 370.5625 - too high
3 77.0000 0.0000 19.2500 9.6250 92.6406 - too high
4 77.0000 0.0000 9.6250 4.8125 23.1602 - too low
5 77.0000 4.8125 9.6250 7.2188 52.1104 - too low
6 77.0000 7.2188 9.6250 8.4219 70.9280 - too low
7 77.0000 8.4219 9.6250 9.0234 81.4224 - too high
8 77.0000 8.4219 9.0234 8.7227 76.0847 - too low
9 77.0000 8.7227 9.0234 8.8730 78.7310 - too high
10 77.0000 8.7227 8.8730 8.7979 77.4022 - too high
11 77.0000 8.7227 8.7979 8.7603 76.7421 - too low
12 77.0000 8.7603 8.7979 8.7791 77.0718 - too high
13 77.0000 8.7603 8.7791 8.7697 76.9068 - too low
14 77.0000 8.7697 8.7791 8.7744 76.9893 - too low
15 77.0000 8.7744 8.7791 8.7767 77.0305 - too high
16 77.0000 8.7744 8.7767 8.7755 77.0099 - too high
17 77.0000 8.7744 8.7755 8.7749 76.9996 - too low
18 77.0000 8.7749 8.7755 8.7752 77.0047 - too high
19 77.0000 8.7749 8.7752 8.7751 77.0022 - too high
20 77.0000 8.7749 8.7751 8.7750 77.0009 - too high
21 77.0000 8.7749 8.7750 8.7750 77.0002 - too high
22 77.0000 8.7749 8.7750 8.7750 76.9999 - too low
23 77.0000 8.7750 8.7750 8.7750 77.0000 - too low
sqrt(77.0000) = 8.7750
Para 62,104:
pax> sqrt 62.104
Step Number Low High Mid Square Result
1 62.1040 0.0000 62.1040 31.0520 964.2267 - too high
2 62.1040 0.0000 31.0520 15.5260 241.0567 - too high
3 62.1040 0.0000 15.5260 7.7630 60.2642 - too low
4 62.1040 7.7630 15.5260 11.6445 135.5944 - too high
5 62.1040 7.7630 11.6445 9.7037 94.1628 - too high
6 62.1040 7.7630 9.7037 8.7334 76.2718 - too high
7 62.1040 7.7630 8.7334 8.2482 68.0326 - too high
8 62.1040 7.7630 8.2482 8.0056 64.0895 - too high
9 62.1040 7.7630 8.0056 7.8843 62.1621 - too high
10 62.1040 7.7630 7.8843 7.8236 61.2095 - too low
11 62.1040 7.8236 7.8843 7.8540 61.6849 - too low
12 62.1040 7.8540 7.8843 7.8691 61.9233 - too low
13 62.1040 7.8691 7.8843 7.8767 62.0426 - too low
14 62.1040 7.8767 7.8843 7.8805 62.1024 - too low
15 62.1040 7.8805 7.8843 7.8824 62.1323 - too high
16 62.1040 7.8805 7.8824 7.8815 62.1173 - too high
17 62.1040 7.8805 7.8815 7.8810 62.1098 - too high
18 62.1040 7.8805 7.8810 7.8807 62.1061 - too high
19 62.1040 7.8805 7.8807 7.8806 62.1042 - too high
20 62.1040 7.8805 7.8806 7.8806 62.1033 - too low
21 62.1040 7.8806 7.8806 7.8806 62.1038 - too low
22 62.1040 7.8806 7.8806 7.8806 62.1040 - too high
23 62.1040 7.8806 7.8806 7.8806 62.1039 - too high
sqrt(62.1040) = 7.8806
Para 49:
pax> sqrt 49
Step Number Low High Mid Square Result
1 49.0000 0.0000 49.0000 24.5000 600.2500 - too high
2 49.0000 0.0000 24.5000 12.2500 150.0625 - too high
3 49.0000 0.0000 12.2500 6.1250 37.5156 - too low
4 49.0000 6.1250 12.2500 9.1875 84.4102 - too high
5 49.0000 6.1250 9.1875 7.6562 58.6182 - too high
6 49.0000 6.1250 7.6562 6.8906 47.4807 - too low
7 49.0000 6.8906 7.6562 7.2734 52.9029 - too high
8 49.0000 6.8906 7.2734 7.0820 50.1552 - too high
9 49.0000 6.8906 7.0820 6.9863 48.8088 - too low
10 49.0000 6.9863 7.0820 7.0342 49.4797 - too high
11 49.0000 6.9863 7.0342 7.0103 49.1437 - too high
12 49.0000 6.9863 7.0103 6.9983 48.9761 - too low
13 49.0000 6.9983 7.0103 7.0043 49.0598 - too high
14 49.0000 6.9983 7.0043 7.0013 49.0179 - too high
15 49.0000 6.9983 7.0013 6.9998 48.9970 - too low
16 49.0000 6.9998 7.0013 7.0005 49.0075 - too high
17 49.0000 6.9998 7.0005 7.0002 49.0022 - too high
18 49.0000 6.9998 7.0002 7.0000 48.9996 - too low
19 49.0000 7.0000 7.0002 7.0001 49.0009 - too high
20 49.0000 7.0000 7.0001 7.0000 49.0003 - too high
21 49.0000 7.0000 7.0000 7.0000 49.0000 - too low
22 49.0000 7.0000 7.0000 7.0000 49.0001 - too high
23 49.0000 7.0000 7.0000 7.0000 49.0000 - too high
sqrt(49.0000) = 7.0000
Um simples (mas não muito rápido) método para calcular a raiz quadrada de X:
squareroot(x)
if x<0 then Error
a = 1
b = x
while (abs(a-b)>ErrorMargin)
a = (a+b)/2
b = x/a
endwhile
return a;
Exemplo: squareroot (70,000)
a b
1 70000
35001 2
17502 4
8753 8
4381 16
2199 32
1116 63
590 119
355 197
276 254
265 264
Como você pode ver ele define um limite superior e um limite inferior para a raiz quadrada e estreita a fronteira até seu tamanho é aceitável.
Existem métodos mais eficientes mas este ilustra o processo e é fácil de entender.
Apenas tome cuidado para definir o Errormargin a 1 se estiver usando números inteiros mais você tem um loop infinito.
Deixe-me apontar um método extremamente interessante de calcular uma raiz quadrada de 1 / sqrt inversa (x), que é uma lenda no mundo do design de jogo, porque é mind-boggingly rápido. Ou espera, leia o seguinte post:
http://betterexplained.com/articles/understanding-quakes -fast-inverso do quadrado da raiz /
PS: Eu sei que você só quer a raiz quadrada, mas a elegância do tremor superou toda a resistência de minha parte:)
A propósito, o artigo acima mencionado também fala sobre o chato Newton-Raphson aproximação em algum lugar.
É claro que é aproximada; que é como a matemática com números de ponto flutuante de trabalho.
De qualquer forma, o caminho padrão é com de Newton método. Isto é sobre o mesmo que usar a série de Taylor, o outro caminho que vem à mente imediatamente.
Calcular a raiz quadrada com precisão arbitrária em Python
#!/usr/bin/env python
import decimal
def sqrt(n):
assert n > 0
with decimal.localcontext() as ctx:
ctx.prec += 2 # increase precision to minimize round off error
x, prior = decimal.Decimal(n), None
while x != prior:
prior = x
x = (x + n/x) / 2 # quadratic convergence
return +x # round in a global context
decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()
Output:
111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
É uma pergunta da entrevista comum feita pelo Facebook etc. Eu não acho que é uma boa idéia usar o método de Newton em uma entrevista. E se o entrevistador perguntar-lhe o mecanismo do método de Newton quando você realmente não entendo isso?
I forneceu uma solução baseada busca binária em Java que eu acredito que todos possam entender.
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0 || x == 1) return x;
int lowerbound = 1;
int upperbound = x;
int root = lowerbound + (upperbound - lowerbound)/2;
while(root > x/root || root+1 <= x/(root+1)){
if(root > x/root){
upperbound = root;
} else {
lowerbound = root;
}
root = lowerbound + (upperbound - lowerbound)/2;
}
return root;
}
Você pode testar o meu código aqui: leetcode: sqrt (x)
A um ótimo artigo sobre Integer Praça raízes .
Esta é uma versão ligeiramente melhorada que apresenta lá:
unsigned long sqrt(unsigned long a){
int i;
unsigned long rem = 0;
unsigned long root = 0;
for (i = 0; i < 16; i++){
root <<= 1;
rem = (rem << 2) | (a >> 30);
a <<= 2;
if(root < rem){
root++;
rem -= root;
root++;
}
}
return root >> 1;
}
Aqui está uma forma de obter uma raiz quadrada usando trigonometria. Não é o algoritmo mais rápido por um longo caminho, mas é preciso. Código está em javascript:
var n = 5; //number to get the square root of
var icr = ((n+1)/2); //intersecting circle radius
var sqrt = Math.cos(Math.asin((icr-1)/icr))*icr; //square root of n
alert(sqrt);
Existe um algoritmo que eu estudei na escola que você pode usar para calcular raízes exata quadrados (ou de arbitrariamente grande precisão se a raiz é um número irracional). É definitivamente mais lento do que algoritmos de Newton, mas é exato. Vamos dizer que você quer calcular a raiz quadrada de 531.3025
A primeira coisa é que você dividir o seu número a partir do ponto decimal em grupos de 2 dígitos:
{5} {31}. {30} {25}
Então:
1) Encontre a raiz quadrada mais próximo para o primeiro grupo que é menor ou igual à raiz quadrada real do primeiro grupo: sqrt ({5})> = 2. Esta raiz quadrada é o primeiro dígito da sua resposta final. Vamos denotar os dígitos já encontramos da nossa raiz quadrada final como B. Então, no momento B = 2.
2) Em seguida calcular a diferença entre {5} e B ^ 2: 5-4 = 1.
3) Para todos os grupos subsequentes de 2 dígitos faça o seguinte:
Multiplicar o restante por 100, em seguida, adicioná-lo ao segundo grupo: 100 + 31 = 131.
Achado X - próximo dígito de sua raiz, de modo que 131> = ((B * 20) + X) * X. X = 3. 43 * 3 = 129 <131. Agora B = 23. Também porque você não tem mais grupos de 2 dígitos à esquerda do ponto decimal, de ter encontrado todos os dígitos inteiros de sua raiz final.
4) Repetir o mesmo para {30} e {25}. Então você tem:
{30}: 131-129 2. = 2 * 100 + 30 = 230> = (23 * 2 * 10 + X) * X -> X = 0 -> B = 23,0
{25}: 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025> = (230 * 2 * 10 + X) * X -> X = 5 -> B = 23,05
resultado final = 23,05.
Os olhares algoritmo complicado desta forma, mas é muito mais simples se você fizer isso no papel usando a mesma notação que você usa para "divisão longa" você estudou na escola, exceto que você não fazer a divisão, mas sim calcular a raiz quadrada.
A primeira coisa que me vem à mente é: este é um bom lugar para usar a pesquisa binária (inspirado por esta grande tutoriais .)
Para encontrar a raiz quadrada de vaule, estamos buscando a number em (1..value) onde o preditor
É verdade pela primeira vez. O preditor estamos escolhendo é number * number - value > 0.00001.
double square_root_of(double value)
{
assert(value >= 1);
double lo = 1.0;
double hi = value;
while( hi - lo > 0.00001)
{
double mid = lo + (hi - lo) / 2 ;
std::cout << lo << "," << hi << "," << mid << std::endl;
if( mid * mid - value > 0.00001) //this is the predictors we are using
{
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt (isqrt4)
// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)
private static uint sqrt(uint x)
{
uint y, z;
if (x < 1u << 16)
{
if (x < 1u << 08)
{
if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
else
{
if (x < 1u << 06)
{ y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
else
{ y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
}
}
else // slower (on my pc): .... y = 3u << 04; } goto L1; }
{
if (x < 1u << 12)
{
if (x < 1u << 10)
{ y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
else
{ y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
}
else
{
if (x < 1u << 14)
{ y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
else
{ y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
}
}
}
else
{
if (x < 1u << 24)
{
if (x < 1u << 20)
{
if (x < 1u << 18)
{ y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
else
{ y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
}
else
{
if (x < 1u << 22)
{ y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
else
{ y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
}
}
else
{
if (x < 1u << 28)
{
if (x < 1u << 26)
{ y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
else
{ y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
}
else
{
if (x < 1u << 30)
{ y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
else
{ y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
}
}
}
z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}
usar busca binária
public class FindSqrt {
public static void main(String[] strings) {
int num = 10000;
System.out.println(sqrt(num, 0, num));
}
private static int sqrt(int num, int min, int max) {
int middle = (min + max) / 2;
int x = middle * middle;
if (x == num) {
return middle;
} else if (x < num) {
return sqrt(num, middle, max);
} else {
return sqrt(num, min, middle);
}
}
}
Em geral, a raiz quadrada de um número inteiro (como 2, por exemplo) podem somente ser aproximado (não por causa de problemas com aritmética de ponto flutuante, mas porque eles são números irracionais que não pode ser calculado exatamente).
É claro, algumas aproximações são melhores que outros. Quero dizer, é claro, que o valor 1.732 é uma melhor aproximação da raiz quadrada de 3, de 1,7
O método utilizado pelo código nesse link que você deu obras, tendo uma primeira aproximação e usá-lo para calcular um melhor aproximação.
Este é chamado o método de Newton, e você pode repetir o cálculo com cada nova aproximação até é o suficiente precisas para você.
Na verdade, existem deve haver alguma maneira de decidir quando parar a repetição ou ele vai correr para sempre.
Normalmente, você iria parar quando a diferença entre aproximações é menos de um valor de decidir.
EDIT:. Eu não acho que pode ser uma implementação mais simples do que os dois que você já encontrou
O inverso, como o nome diz, mas às vezes "perto o suficiente" é "suficientemente próximo"; um interessante ler de qualquer maneira.
Uma solução simples que pode lidar com a raiz quadrada de bóia e precisão arbitrária utilizando busca binária
codificado em ruby ??
include Math
def sqroot_precision num, precision
upper = num
lower = 0
middle = (upper + lower)/2.0
while true do
diff = middle**2 - num
return middle if diff.abs <= precision
if diff > 0
upper = middle
else diff < 0
lower = middle
end
middle = (upper + lower)/2.0
end
end
puts sqroot_precision 232.3, 0.0000000001
Vamos dizer que estamos tentando encontrar a raiz quadrada de 2, e você tem uma estimativa de 1,5. Vamos dizer a = 2 e x = 1,5. Para calcular uma estimativa melhor, vamos dividir um por x. Isto dá um novo valor y = 1,333333. No entanto, não podemos simplesmente tomar isso como nosso próximo estimativa (por que não?). Precisamos média, com a estimativa anterior. Portanto, a nossa próxima estimativa, xx será (x + y) / 2, ou 1,416666.
Double squareRoot(Double a, Double epsilon) {
Double x = 0d;
Double y = a;
Double xx = 0d;
// Make sure both x and y != 0.
while ((x != 0d || y != 0d) && y - x > epsilon) {
xx = (x + y) / 2;
if (xx * xx >= a) {
y = xx;
} else {
x = xx;
}
}
return xx;
}
Epsilon determina quão preciso à aproximação precisa ser. A função deve retornar a primeira aproximação x obtém que satisfaz abs (x * x - a). square_root(2, 1e-6)
Output: 1.4142141342163086
Bem, existem já algumas respostas, mas aqui vai a minha É a peça mais simples de código (para mim), aqui é o algoritmo para ele.
E código em python 2.7:
from __future__ import division
val = 81
x = 10
def sqr(data,x):
temp = x - ( (x**2 - data)/(2*x))
if temp == x:
print temp
return
else:
x = temp
return sqr(data,x)
#x =temp
#sqr(data,x)
sqr(val,x)
Para calcular a raiz quadrada de um número com a ajuda da função inerente
# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;
float squreroot(float);
float z=squareroot(x);
cout<<z;
float squareroot(int x)
{
float s;
s = pow(x,.5)
return(s);
}
