Написание собственной функции квадратного корня
Как вы пишете свою собственную функцию для нахождения наиболее точного квадратного корня целого числа?
погуглив его, я нашел этой (архивировано из своего ссылка на источник), но во-первых, я не получил его полностью, а во-вторых, это тоже приблизительно.
предположим, что квадратный корень является ближайшим целым числом (к фактическому корню) или поплавком.
20 ответов:
следующее вычисляет пол (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; в противном случае выберите t/2. Обратите внимание, что это округляет на галстуке; вы также можете округлить вниз( или округлить до четного), глядя на то, является ли остаток не равен нулю (т. е. является ли t^2 == 4N).
обратите внимание, что вам не нужно использовать вычисления с плавающей точкой. Этот алгоритм должен быть реализован полностью с использованием целых чисел (в частности, функции floor () просто указывают, что должно использоваться регулярное целочисленное деление).
в зависимости от ваших потребностей, можно использовать простую стратегию "разделяй и властвуй". Он не будет сходиться как быстро как некоторые другие методы, но это может быть намного проще для новичка, чтобы понять. Кроме того, поскольку это алгоритм O(log n) (сокращение вдвое пространства поиска на каждой итерации), худшим случаем для 32-битного float будет 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
простой (но не очень быстрый) метод вычисления квадратного корня из 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;пример: squareroot (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, если с помощью целых чисел еще у вас есть бесконечный цикл.
позвольте мне указать на чрезвычайно интересный метод вычисления обратного квадратного корня 1 / sqrt(x), который является легендой в мире игрового дизайна, потому что это умопомрачительно быстро. Или подождите, прочитайте следующий пост:
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
PS: Я знаю, что вы просто хотите квадратный корень, но элегантность quake преодолела все сопротивление с моей стороны :)
кстати, выше упомянутая статья также говорит о скучном приближении Ньютона-Рафсона где-то.
конечно, это приблизительно;вот как работает математика с числами с плавающей запятой.
в любом случае, стандартный способ-с метод Ньютона. Это примерно то же самое, что использовать серию Тейлора, другой способ, который сразу приходит на ум.
вычислить квадратный корень с произвольной точностью в 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
это общий вопрос интервью, заданный 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)
нашел отличную статью о Целочисленные Квадратные Корни.
это немного улучшенная версия, которую он представляет там:
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; }
вот способ получения квадратного корня с помощью тригонометрии. Это не самый быстрый алгоритм на дальний выстрел, но он точен. Код на 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);
есть алгоритм, который я изучал в школе, который вы можете использовать для вычисления точных квадратных корней (или сколь угодно большой точности, если корень является иррациональным числом). Это определенно медленнее, чем алгоритмы Ньютона, но это точно. Допустим, вы хотите вычислить квадратный корень из 531.3025
во-первых, вы делите свое число, начиная с десятичной точки, на группы из 2 цифр:
{5}{31}.{30}{25}
Затем:
1) Найти ближайший квадратный корень для первая группа, которая меньше или равна фактическому квадратному корню первой группы: sqrt ({5}) >= 2. Этот квадратный корень является первой цифрой вашего окончательного ответа. Давайте обозначим цифры, которые мы уже нашли из нашего конечного квадратного корня, как B. Так что на данный момент B = 2.
2) Далее вычисляют разницу между {5} и B^2: 5 - 4 = 1.
3) для всех последующих 2-значных групп выполните следующие действия:
Умножьте остаток на 100, затем добавьте его ко второй группе: 100 + 31 = 131.
Найти X-next цифра вашего корня, такая что 131 >=((B*20) + X)*X. X = 3. 43 * 3 = 129 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.
Алгоритм выглядит сложным таким образом, но он намного проще, если вы делаете это на бумаге, используя ту же нотацию, которую вы используете для "длинного деления", которое вы изучали в школе, за исключением того, что вы не делаете деление, а вместо этого вычисляете квадратный корень.
первое, что приходит мне на ум: это хорошее место, чтобы использовать двоичный поиск (вдохновленный этим великим уроки.)
чтобы найти квадратный корень из
vaule,мы ищем тегnumberна(1..value)где предиктора правда в первый раз. Предиктор, который мы выбираем,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; }
использовать двоичный поиск
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); } } }
В общем случае квадратный корень целого числа (например, 2) может только быть аппроксимированы (не из-за проблем с арифметикой с плавающей запятой, а потому, что они иррациональные числа, которые не могут быть вычислены точно).
конечно, некоторые приближения лучше, чем другие. Я имею в виду, конечно, что значение 1.732 является лучшее приближение к квадратному корню из 3, чем 1,7
метод, используемый кодом по этой ссылке, которую вы дали, работает принимая первое приближение и используя его для вычисления лучше приближение.
Это называется методом Ньютона, и вы можете повторить расчет с каждым новым приближением до это достаточно точно для вас.
на самом деле есть должны быть какой-то способ решить, когда остановить повторение или он будет работать вечно.
обычно вы бы остановились, когда разница между приближениями меньше, чем значение, которое вы решаете.
EDIT: я не думаю, что может быть более простая реализация, чем те два, которые вы уже нашли.
обратное, как говорится в названии, но иногда "достаточно близко" - это "достаточно близко"; интересное чтение в любом случае.
// A Java program to find floor(sqrt(x) public class Test { public static int floorSqrt(int x) { // Base Cases if (x == 0 || x == 1) return x; // Do Binary Search for floor(sqrt(x)) int start = 1, end = x, ans=0; while (start <= end) { int mid = (start + end) / 2; // If x is a perfect square if (mid*mid == x) return mid; // Since we need floor, we update answer when mid*mid is // smaller than x, and move closer to sqrt(x) if (mid*mid < x) { start = mid + 1; ans = mid; } else // If mid*mid is greater than x end = mid - 1; } return ans; } // Driver Method public static void main(String args[]) { int x = 11; System.out.println(floorSqrt(x)); } }выход : 3 (пол)
Let 's' be the answer. We know that 0 <= s <= x. Consider any random number r. If r*r <= x, s >= r If r*r > x, s < r.:
начать с "пуск" = 0, конец = 'х', у После время "старта" меньше или равно "конец".
a) вычислить ' mid ' как (начало + конец)/2
b) сравните mid*mid с x.
- C) если x равен средний*средний, вернуться в середине.
- d) Если x больше, сделайте двоичный поиск между серединой+1 и концом. В этом случае мы также обновляем ans (обратите внимание, что нам нужен пол).
- e) Если x меньше, выполните двоичный поиск между start и mid-1
временная сложность вышеуказанного решения равна O (√n).
простое решение, которое может иметь дело с плавающим квадратным корнем и произвольной точностью с помощью двоичного поиска
закодировано в 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
допустим, мы пытаемся найти квадратный корень из 2, а у вас оценка 1,5. Скажем, a = 2 и x = 1.5. Чтобы вычислить более точную оценку, мы будем делить на X. Это дает новое значение y = 1.333333. Однако мы не можем просто взять это в качестве нашей следующей оценки (почему бы и нет?). Нам нужно усреднить его с предыдущей оценкой. Таким образом, наша следующая оценка, xx будет (x + y) / 2, или 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; }Эпсилон определяет, насколько точным должно быть приближение. Функция должно возвращать первое приближение x, которое удовлетворяет abs(x*x - a)
square_root(2, 1e-6) Output: 1.4142141342163086
Ну там уже довольно много ответов, но вот идет мой это самый простой кусок кода ( для меня ), вот это алгоритм для него.
и код в 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)
вычислить квадратный корень из числа с помощью встроенной функции
# 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); }
Comments