Написание вашей собственной функции квадратного корня

Question

Как написать собственную функцию для нахождения наиболее точного квадратного корня из целого числа?

После поиска в Google я нашел этот (заархивированный по его исходной ссылке ), но сначала я не получил его полностью, а во-вторых, он также приблизительный. 1007 *

Предполагается, что квадратный корень является ближайшим целым числом (к фактическому корню) или числом с плавающей запятой.

Answer 1

Следующие вычисления пола (sqrt (N)) для N> 0:

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

Это версия метода Ньютона, приведенная в Crandall & Pomerance, «Простые числа: вычислительная перспектива». Причина, по которой вам следует использовать эту версию, состоит в том, что люди, которые знают, что они делают, доказали, что она сходится точно к полу квадратного корня, и это просто, поэтому вероятность ошибки реализации мала. Это также быстро (хотя возможно построить еще более быстрый алгоритм - но сделать это правильно намного сложнее). Правильно реализованный бинарный поиск может быть быстрее для очень маленьких N, но там вы также можете использовать справочную таблицу.

Чтобы округлить до ближайшего целого числа, просто вычислите t = floor (sqrt (4N)), используя алгоритм выше. Если задан младший значащий бит t, выберите x = (t + 1) / 2; в противном случае выберите т / 2. Обратите внимание, что это округляется на галстуке; Вы также можете округлить (или округлить до четного), посмотрев, является ли остаток ненулевым (т. е. t ^ 2 == 4N).

Обратите внимание, что вам не нужно использовать арифметику с плавающей точкой. На самом деле, вы не должны. Этот алгоритм должен быть полностью реализован с использованием целых чисел (в частности, функции floor () просто указывают, что следует использовать регулярное целочисленное деление).

Answer 2

В зависимости от ваших потребностей можно использовать простую стратегию «разделяй и властвуй». Он не будет сходиться с fast , как некоторые другие методы, но новичку может быть намного легче понять. Кроме того, поскольку это алгоритм O (log n) (делящий пополам пространство поиска на каждую итерацию), наихудший случай для 32-разрядного числа с плавающей запятой - 32 итерации.

Допустим, вы хотите получить квадратный корень из 62.104. Вы выбираете значение на полпути между 0 и этим, и возводите его в квадрат. Если квадрат больше вашего числа, вам нужно сконцентрироваться на числах, меньших средней. Если оно слишком низкое, сконцентрируйтесь на них выше.

С реальной математикой вы могли бы продолжать делить пространство поиска навсегда на два (если оно не имеет рационального квадратного корня). На самом деле, компьютеры со временем станут точнее, и вы получите свое приближение. Следующая программа на C иллюстрирует эту точку:

#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;
}

Вот пара пробежек, поэтому, надеюсь, вы поймете, как это работает. Для 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

Для 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

Для 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

Answer 3

Простой (но не очень быстрый) метод для вычисления квадратного корня из 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;

Пример: квадратный корень (70000)

    a       b
    1   70000
35001       2
17502       4
 8753       8
 4381      16
 2199      32
 1116      63
  590     119
  355     197
  276     254
  265     264

Как видите, он определяет верхнюю и нижнюю границу для квадратного корня и сужает границу до тех пор, пока ее размер не станет приемлемым.

Существуют более эффективные методы, но этот иллюстрирует процесс и его легко понять.

Просто будьте осторожны, чтобы установить Errormargin равным 1, если вы используете целые числа, иначе у вас есть бесконечный цикл.

Answer 4

Позвольте мне указать на чрезвычайно интересный метод вычисления обратного квадратного корня 1 / sqrt (x), который является легендой в мире игрового дизайна, потому что он невероятно быстр. Или подождите, прочитайте следующий пост:

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

PS: я знаю, что вы просто хотите получить квадратный корень, но элегантность землетрясения преодолела все сопротивление с моей стороны:)

Кстати, в вышеупомянутой статье также говорится о скучном приближении Ньютона-Рафсона где-то.

Answer 5

Рассчитать квадратный корень с произвольной точностью в 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()

Выход:

111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True

Answer 6

Конечно, это приблизительно; так работает математика с числами с плавающей точкой.

В любом случае, стандартный способ - метод Ньютона . Это примерно то же самое, что использовать серию Тейлора, другой способ, который сразу приходит на ум.

Answer 7

Это обычный вопрос для интервью, задаваемый Facebook и т. Д. Я не думаю, что это хорошая идея - использовать метод Ньютона в интервью. Что если интервьюер спросит вас о механизме метода Ньютона, когда вы на самом деле его не понимаете?

Я предоставил решение на основе бинарного поиска в Java, которое, как мне кажется, может понять каждый.

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;
}

Вы можете проверить мой код здесь: leetcode: sqrt (x)

Answer 8

Нашел отличную статью о Целочисленных квадратных корнях .

Это немного улучшенная версия, которую она там представляет:

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;
}

Answer 9

Вот способ получения квадратного корня с использованием тригонометрии. Это не самый быстрый алгоритм по большому счету, но он точный. Код в 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);

Answer 10

Существует алгоритм, который я изучал в школе, который вы можете использовать для вычисления точных квадратных корней (или произвольно большой точности, если корень является иррациональным числом). Это определенно медленнее, чем алгоритмы Ньютона, но это точно. Допустим, вы хотите вычислить квадратный корень из 531.3025

Прежде всего, вы делите свой номер, начиная с десятичной точки, на группы из 2 цифр:
{5} {31}. {30} {25}
Тогда:
1) Найдите ближайший квадратный корень для первой группы, который меньше или равен фактическому квадратному корню первой группы: sqrt ({5})> = 2. Этот квадратный корень является первой цифрой вашего окончательного ответа. Обозначим цифры, которые мы уже нашли в нашем конечном квадратном корне, как B. Итак, на данный момент B = 2.
2) Затем вычислите разницу между {5} и B ^ 2: 5 - 4 = 1.
3) Для всех последующих двухзначных групп выполните следующие действия:
Умножьте остаток на 100, затем добавьте его ко второй группе: 100 + 31 = 131.
Найдите X - следующую цифру вашего корня, такую, что 131> = ((B * 20) + X) * X. X = 3. 43 * 3 = 129 <131. Теперь B = 23. Кроме того, поскольку у вас больше нет двухзначных групп слева от десятичных знаков, вы нашли все целые цифры вашего последнего корня. <Br /> 4) Повторите то же самое для {30} и {25}. Итак, у вас есть:
{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
Окончательный результат = 23.05.
Алгоритм выглядит сложным таким образом, но он намного проще, если вы делаете это на бумаге, используя те же обозначения, которые вы используете для «длинного деления», которое вы изучали в школе, за исключением того, что вы не делите, а вместо этого вычисляете квадратный корень.