Запись собственной функции квадратного корня
Я предположил бы, что пустой массив использует только пространство, должен был выделить сам объектный указатель.
Из памяти в инструкциях по API говорится, что необходимо всегда возвращать пустой массив из метода, который возвращает массив вместо того, чтобы возвратить пустой указатель, таким образом, я оставил бы код путем, это невнимательно. Тем путем вызывающая сторона знает, что он, как гарантируют, получит массив (даже пустой) и не должен проверять на пустой указатель с каждым вызовом.
Редактирование: ссылка о возврате пустых массивов:
http://wesnerm.blogs.com/net_undocumented/2004/02/empty_arrays.html
10 ответов
Следующее вычисляет этаж (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 () просто указывают, что следует использовать обычное целочисленное деление).
В общем, квадратный корень из целого числа (например, 2) может быть приблизительно только (не из-за проблем с арифметикой с плавающей запятой, а потому, что это иррациональные числа, которые могут » t можно рассчитать точно).
Конечно, одни приближения лучше других. Я имею в виду, конечно, что значение 1,732 является лучшим приближением к квадратному корню из 3, чем 1.
Первое, что приходит мне в голову: это хорошее место для использования двоичного поиска (вдохновленное этим замечательным учебным пособием .)
Чтобы найти квадратный корень of vaule , мы ищем число в (1..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;
}
Вычислить квадратный корень с произвольной точностью в 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
Нашел отличную статью о Целочисленных квадратных корнях . 1247] Это немного улучшенная версия, которая представлена здесь:
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;
}
Конечно, приблизительно; так работает математика с числами с плавающей запятой.
Во всяком случае, стандартный способ - с помощью метода Ньютона . Это примерно то же самое, что и использование ряда Тейлора, другой способ сразу приходит на ум.
Позвольте мне указать на чрезвычайно интересный метод вычисления обратного квадратного корня 1 / sqrt (x), который является легендой в мире игрового дизайна, поскольку он невероятно быстр. Или подожди,
В зависимости от ваших потребностей может использоваться простая стратегия «разделяй и властвуй». Он не будет сходиться так же быстро , как некоторые другие методы, но новичку может быть намного легче понять его. Вдобавок, поскольку это алгоритм 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
Простой (но не очень быстрый) метод вычисления квадратного корня из 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, если используются целые числа else у вас бесконечный цикл.
Обратное, как следует из названия, но иногда «достаточно близко» означает «близко» довольно"; в любом случае интересное чтение.