Вычисление квадратного корня из целого числа
Представленный алгоритм был создан в те бородатые времена, когда производительность x87 оставляла желать лучшего. Но и сейчас, скорость работы этого алгоритма соизмерима со скоростью вычисления с плавающей точкой на PII или MMX. На мой взгляд, материал может быть интересен, как начинающим программистам — пусть учатся писать программы, а не ломать их, и не вирусы, так и опытным — как игра ума., скомпилированный MSVC 5.0, на PII-233×2 дает следующие результаты (Листинг 1):
testing with range[0..1000] Done. testing range1=[0..1000]. fpu1. cpu1. cpu2. testing range2=[1000..10000]. fpu1. cpu1. cpu2. testing range3=[10000..100000]. fpu1. cpu1. cpu2. Done. range fpu1 cpu1 cpu2 1000 1.000 3.000 3.000 10000 1.000 3.000 4.000 100000 1.000 3.000 5.000
Задача вычисления квадратного корня при построении программ достаточна тривиальная. Функция для ее решения — sqrt — присутствует практически в любом из современных языков программирования. Однако практика использования функции sqrt показала, что данная функция ведет себя совершенно различным способом для целочисленных и действительных аргументов.
Пример 1 #include #include void main( ) < int i = 169, j = 168; printf( , i, (int)sqrt(i), j, (int)sqrt(j) ); >
Результат выполнения кода приведенного в примере 1 выглядит так:
В действительности, значение квадратного корня для числа 168 соответствует числу 12.96, что по общепринятым правилам округления ближе к целому числу 13. В данном примере мы видим классический машинный случай округления с отбрасыванием дробной части.
Известно, многие сталкивались с подобной проблемой при построении целочисленных расчетных задач. Как правило, эта проблема решается написанием собственной функции, возвращающей правильный результат, т.е. результат, округленный до ближайшего целого, вместо отбрасывания дробной части. Один из вариантов собственной функции приведен в примере 2.
Пример 2 unsigned sqrt_fpu_true(long l)
Функция, приведенная в примере 2, дает абсолютно правильные значения для всех целых чисел согласно принятым правилам округления. Однако возникает вопрос: возможно ли получение правильных результатов при использовании целочисленных алгоритмов?
Самый известный целочисленный алгоритм для вычисления квадратного корня из числа поражает своей простотой и приведен в примере 3.
Пример 3 unsigned sqrt_cpu_int(long l) < unsigned div = 1, rslt = 0; while (l >0) < l -= div, div += 2; rslt += l < 0 ? 0 : 1; >return rslt; >
Результат работы алгоритма из примера 3 идентичен результату из примера 1 — отбрасывание дробной части. Кроме того, невооруженным глазом виден еще один недостаток данного алгоритма — количество итераций в цикле соответствует значению вычисленного квадратного корня от аргумента L:
iteration count ~= sqrt(L) (1).
Рассматривая задачу вычисления квадратного корня с точки зрения уменьшения величины вычислительных затрат, более привлекателен целочисленный алгоритм, реализующий формулу Ньютона — пример 4.
Пример 4 unsigned sqrt_cpu_newton(long l) < unsigned rslt = (unsigned)l; long div = l; if (l div) rslt = (unsigned)div; else return rslt; > >
Количество итераций в цикле для алгоритма из примера 4 приблизительно будет равняться натуральному логарифму от аргумента L:
iteration count ~= ln(L) (2).
Легко заключить, что разница в значениях формул (1) и (2) достаточно велика особенно для больших чисел, что и иллюстрирует ниже приведенная таблица.
Число L sqrt_cpu_int sqrt_cpu_newton 70000 264 11 300000 574 13 700000 836 13 990000 994 14
Однако результат работы алгоритма из примера 4 опять тот же — округление до целого числа отбрасыванием дробной части. Анализ кода алгоритма показывает, что наибольшая ошибка при вычислениях накапливается в главной формуле алгоритма и возникает при целочисленном делении на 2 без учета остатка от деления. В примере 5 приведен модифицированный алгоритм вычисления квадратного корня, с учетом вышеупомянутого замечания.
Пример 5 unsigned sqrt_cpu_newton(long l) < long temp, div = l; unsigned rslt = (unsigned)l; if (l > 1; div += temp & 1; if (rslt > div) rslt = (unsigned)div; else return rslt; > >
В модифицированный алгоритм добавлена одна переменная и две новые строки, реализующие целочисленное деление на 2 с учетом остатка. Модифицированный алгоритм вычисляет правильные значения — корень от аргумента с округлением до ближайшего целого практически для всех значений аргумента за исключением определенного ряда чисел. Для чисел этого ряда корень вычисляется, как число на единицу большее, чем истинное целочисленное его значение, определенное по общепринятым правилам округления (см. таблицу).
Число 2 6 12 20 30 42 56 72 90 110 132 Действит.корень 1,4 2,4 3,4 4,4 5,4 6,4 7,4 8,4 9,4 10,4 11,4 Целый корень 1 2 3 4 5 6 7 8 9 10 11 Вычисл.корень 2 3 4 5 6 7 8 9 10 11 12
Для всех аргументов алгоритма из приведенного ряда характерно, что вычисленное алгоритмом значение — есть целочисленный множитель, произведение которого с истинным целочисленным значением квадратного корня от аргумента дает сам аргумент. Знание выявленной закономерности позволяет сделать последнюю модификацию алгоритма, позволяющую окончательно устранить ошибки в вычислениях. Модификация заключается в проверке условия для выполнения коррекции результата вычисления при завершении работы алгоритма — пример 6.
Пример 6 unsigned sqrt_cpu_newton(long l) < long temp, div = l; unsigned rslt = (unsigned)l; if (l > 1; div += temp & 1; if (rslt > div) rslt = (unsigned)div; else < if (l / rslt == rslt - 1 && l % rslt == 0) rslt-; return rslt; >> >
Итак, вопрос о существовании целочисленного алгоритма для вычисления квадратного корня из целого числа с округлением результата до ближайшего целого по общепринятым правилам округления имеет утвердительный ответ.
В заключении следует отметить о существовании еще одной модификации алгоритма. На этот раз модификация преследует только задачу повышения производительности алгоритма. Повысить производительность итерационных алгоритмов возможно только одним способом — уменьшить количество итераций. Для приведенного в примере 6 алгоритма количество итераций можно значительно снизить, более точно подобрав начальные значения для переменной div — пример 7.
Пример 7 unsigned sqrt_newton(long l) < long temp , div; unsigned rslt = (unsigned)l; if (l 4) ? 0x7 : l; while (1) < temp = l / div + div; div = temp >> 1; div += temp & 1; if (rslt > div) rslt = (unsigned)div; else < if (l / rslt == rslt - 1 && l % rslt == 0) rslt-; return rslt; >> >
Последняя модификация алгоритма (пример 7) вычисляет квадратный корень из числа без ошибок округления на диапазоне [0..10000] в среднем за 3 итерационных цикла. В таблице ниже представлена сводная таблица по вычислительным затратам алгоритма на исследуемом диапазоне. На других диапазонах аргумента количество итераций не бывает больше 6, а в среднем равняется 3. Сравнивая с первоначально достигнутыми результатами, см. таблицу в начале, можно сказать, что достигнуто увеличение производительности как минимум в 2 — 4 раза.
Кол-во итераций 1 2 3 4 5 6 7 случаев из 10000 2 1965 6173 1779 80 0 0 % от всего 0,02% 19,65% 61,73% 17,19% 0,8% 0 0
Вероятно, что предел производительности алгоритма еще не достигнут, однако данная тема не является главной для настоящей статьи.
Листинг 1 // sqrt.cpp #include #include #include #include unsigned sqrt_fpu1(long l) < if (l == 0) return 0; double f_rslt = sqrt(l); unsigned rslt = (int)f_rslt; if (!(f_rslt - rslt < .5)) rslt ++; return rslt; >unsigned sqrt_cpu1(long l) < long temp; unsigned div, rslt = l; if (l 4) ? 0x7 : l; while (1) < temp = l / div + div; div = temp >> 1; div += temp & 1; if (rslt > div) rslt = div; else < if (l / rslt == rslt - 1 && l % rslt == 0) rslt--; break; >> return (unsigned)rslt; > unsigned sqrt_cpu2(long l) < if (l div) rslt = div; else break; > return (unsigned)rslt; > unsigned sqrt_cpu3(long l) < unsigned div = 1; unsigned rslt = 0; while (l >0) < l-= div, div += 2; rslt += l < 0 ? 0 : 1; >return rslt; > unsigned sqrt_cpu4(long l) < unsigned div = 1, rslt = 0; while (l >0) < l-= div, div += 2; rslt += l < 0 ? 0 : 1; >if (l != 0) rslt++; return rslt; > #define steps 1000 #define range1 1000L #define range2 10000L #define range3 100000L #define count 2000 double times[3][3]; void CalcTime() < long l; int i; time_t first, second; printf("testing range1=[%lu..%lu]. \n", 0L, range1); printf("fpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = 0l; l < range1; l += range1 / steps) sqrt_fpu1(l); second = time(NULL); times[0][0] = difftime(second, first); printf("cpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = 0l; l < range1; l += range1 / steps) sqrt_cpu1(l); second = time(NULL); times[0][1] = difftime(second, first); printf("cpu2. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = 0l; l < range1; l += range1 / steps) sqrt_cpu2(l); second = time(NULL); times[0][2] = difftime(second, first); printf("testing range2=[%lu..%lu]. \n", range1, range2); printf("fpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range1; l < range2; l += (range2 - range1) / steps) sqrt_fpu1(l); second = time(NULL); times[1][0] = difftime(second, first); printf("cpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range1; l < range2; l += (range2 - range1) / steps) sqrt_cpu1(l); second = time(NULL); times[1][1] = difftime(second, first); printf("cpu2. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range1; l < range2; l += (range2 - range1) / steps) sqrt_cpu2(l); second = time(NULL); times[1][2] = difftime(second, first); printf("testing range3=[%lu..%lu]. \n", range2, range3); printf("fpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range2; l < range3; l += (range3 - range2) / steps) sqrt_fpu1(l); second = time(NULL); times[2][0] = difftime(second, first); printf("cpu1. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range2; l < range3; l += (range3 - range2) / steps) sqrt_cpu1(l); second = time(NULL); times[2][1] = difftime(second, first); printf("cpu2. \n"); first = time(NULL); for (i = 0; i < count; i++) for (l = range2; l < range3; l += (range3 - range2) / steps) sqrt_cpu2(l); second = time(NULL); times[2][2] = difftime(second, first); printf("Done.\n"); printf("range\t\t fpu1\t cpu1\t cpu2\n"); printf( "%lu\t\t%5.3f\t%5.3f\t%5.3f\n", range1, times[0][0], times[0][1], times[0][2] ); printf( "%lu\t\t%5.3f\t%5.3f\t%5.3f\n", range2, times[1][0], times[1][1], times[1][2] ); printf( "%lu\t\t%5.3f\t%5.3f\t%5.3f\n", range3, times[2][0], times[2][1], times[2][2] ); >typedef unsigned (*sqrt_func)(long L); void ViewDifferents(long rang1, long rang2, unsigned step, sqrt_func fpsqrt) < unsigned long l; unsigned rf, ri; printf("testing with range[%lu..%lu]\n", rang1, rang2); for (l = rang1; l < rang2; l += (rang2 - rang1) / step) < rf = sqrt_fpu1(l); ri = (*fpsqrt)(l); if (rf != ri) printf("sqrt(%lu) %u %u %6.2f\n", l, rf, ri, sqrt(l)); >printf(«Done.\n»); > void main()
Как вычислить корень из числа в c
Разделы
Быстрое вычисление квадратного корня на Си
18/01/2013 — 01:11 Pavel Bobkov
При программировании микроконтроллеров разработчики иногда сталкиваются с проблемой вычисления квадратного корня. Например, данная операция требуется при выполнении быстрого преобразования Фурье или вычислении среднеквадратического значения сигнала.
В стандартной библиотеке Си – math.h, есть функция для вычисления квадратного корня sqrt(), которой при желании можно воспользоваться. Она работает с числами типа float, обеспечивает высокую точность результата, но требует для своей работы длительного времени. Для микроконтроллера AVR это порядка 3000 циклов тактовой частоты (проверено в компиляторе IAR на разных уровнях оптимизации).
Если к точности вычисления корня не предъявляются высокие требования, можно воспользоваться упрощенным алгоритмом, занимающим меньше места в памяти и выполняющим вычисления в несколько раз быстрее.
Алгоритм выглядит так.
unsigned int root(unsigned int x)
unsigned int a,b;
b = x;
a = x = 0x3f;
x = b/x;
a = x = (x+a)>>1;
x = b/x;
a = x = (x+a)>>1;
x = b/x;
x = (x+a)>>1;
return(x);
>
Как мне подсказали умные люди, алгоритм основан на итерационной формуле Герона.
где А – фиксированное положительное число, а X1 – любое положительное число.
Итерационная формула задаёт убывающую (начиная со 2-го элемента) последовательность, которая при любом выборе X1 быстро сходится к квадратному корню из числа А.
Ради интереса я переписал алгоритм в явном виде. Скомпилированный, он ничуть не потерял ни в быстродействии, ни в объеме. Объем даже на пару байтов уменьшился.
unsigned int root1(unsigned int a)
unsigned int x;
x = (a/0x3f + 0x3f)>>1;
x = (a/x + x)>>1;
x = (a/x + x)>>1;
return(x);
>
Недостатки приведенного кода в том, что он работает только с целыми 16-ти разрядными числами и при больших значениях аргумента вычисления становятся не точными. Правда, точность вычислений можно повысить, добавив еще несколько итераций, но за это естественно придется платить быстродействием.
Код занимает прядка 70 байт и выполняется ~ за 700 циклов. Данные получены в компиляторе IAR AVR при medium оптимизация по скорости.
Точность вычисления данного алгоритма можно оценить по приведенному ниже графику. Синий график построен по значениям, полученным c помощью библиотечной функции sqrt(), красный график по значениям функции root().
В ходе обсуждения моей заметки, те же самые умные люди подсказали еще один алгоритм вычисления квадратного корня.
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0) b = y | m;
y = y >> 1;
if (x >= b) x = x - b;
y = y | m;
>
m = m >> 2;
>
return y;
>
Related items
- Планировщик для микроконтроллера
- Медианный фильтр
- AVR4027: Трюки и советы по оптимизации Си кода для 8-и разрядных AVR микроконтроллеров. Ч.2
- AVR4027: Трюки и советы по оптимизации Си кода для 8-и разрядных AVR микроконтроллеров. Ч.1
- Что размещать в заголовочном файле .h?
Comments
# Nobody 2013-01-18 02:58
К сожалению, не могу раскрыть подробности его работы, потому что они мне неизвестны.
Это итерационная формула Герона, если добавить ещё одну итерацию, то точность увеличится.
# Nobody 2013-01-18 05:30
Хотя, я был не прав. По итерационной формуле Герона нужно 8 делений для получения приближенного ответа. В описанном вами методе можно увеличить точность добавив ещё одну итерацию:
x = b/x;
a = x = (x+a)>>1;
Но для AVR, данный алгоритм не оптимальный, т.к. деление выполняется долго. Посмотрите на метод бинарного поиска целочисленного квадратного корня (только умножение и сложение), описан в книге «Алгебраические трюки для программиста». Там ещё описан алгоритм без умножения, только сдвиги, сложения и битовые операции. Можно попробовать адаптировать для AVR его, тогда выигрыш во времени будет значительный.
# Pashgan 2013-01-18 06:40
Да нет, все правильно. В википедии приведена формула Герона.
Xn+1 = (Xn + A/Xn)*1/2
A — число из которого требуется вычислить корень, X1 — любое положительное число.
# Pashgan 2013-01-18 07:01
Если написать код так
Code:
unsigned int root(unsigned int a)
unsigned int x;
x = (a/0x3f + 0x3f)>>1;
x = (a/x + x)>>1;
x = (a/x + x)>>1;
return(x);
>
получаются точно такие же результаты. Как по ответам, так и по скорости исполнения кода. А по объему даже небольшой выигрыш. Зачем надо было так мудрить?
# spkik 2016-04-07 13:25
Quoting Nobody:
Хотя, я был не прав. По итерационной формуле Герона нужно 8 делений для получения приближенного ответа. В описанном вами методе можно увеличить точность добавив ещё одну итерацию:
x = b/x;
a = x = (x+a)>>1;
Но для AVR, данный алгоритм не оптимальный, т.к. деление выполняется долго. Посмотрите на метод бинарного поиска целочисленного квадратного корня (только умножение и сложение), описан в книге «Алгебраические трюки для программиста». Там ещё описан алгоритм без умножения, только сдвиги, сложения и битовые операции. Можно попробовать адаптировать для AVR его, тогда выигрыш во времени будет значительный.
подскажите пожалуйста как проделать это с переменной типа long?
# Nikolay 2013-01-18 07:43
Добрый день. Уважаемый, Pashgan, вот ви пишете Quote:
— компактность (~80 байтов), — скорость выполнения (~1000 циклов для AVR).
Можете рассказать как вы определяете сколько занимает и сколько циклов выполняется код?
# Neptun 2013-01-18 09:37
Напишу как делаеться в AVR Studio. Пишеться код — компилим,смотри м сколько занял,добавляем функцию — и смотрим новий размер кода. Разница между новым и старым значение есть размер функции.
Для скорости выполнения. ставим брейкпойнт перед вызовом функции и после,запускаем симуляцию — обнуляем cycle counter,запуска ем симуляцию — и новое значение будеть скоростью выполнения (также можно увидеть сколько время исполняеться функция в мкс или мс).
# Pashgan 2013-01-18 11:19
Для IAR`a . Нужно включить опцию создания листинга программы. Project > Options > C/C++ Compiler > List галочка Output list file. Если включить еще и Assembler mnemonics в lst файле будет ассемблерный код, сгенерированный компилятором из твоей программы. Эта информация полезна для оптимизации сишного кода, конечно, если ты знаешь ассемблер.
Затем запускаешь компиляцию проекта и с левой стороны (в окне отображения структуры проекта) ищешь файлы с расширением *.lst Они будут созданы для каждого программного модуля. В конце этого файла есть табличка со списком функций и значениями занимаемой памяти.
Чтобы прикинуть скорость выполнения какого-нибудь куска кода (обычно функции), я прогоняю этот код в программном симуляторе IAR`a. Включаю опцию Project > Options > Linker > Debug Information . Запускаю компиляцию и отладку с помощью кнопки Debug (Ctrl+D). Устанавливаю брейкпоинты, открываю окно с регистрами микроконтроллер а (меню View > Register) и запускаю код на выполнение по шагам (F11) или непрерывно (f5). В окне регистров в разделе CPU Register есть строка CYCLES. Она отображает число прошедших тактов. По показаниям этого числа можно прикинуть сколько тактов занимает выполнение функции.
То же самое можно делать и в AVR Studio. Там это даже лучше получается, потому что студия моделирует прерывания, а IAR нет.
# Nobody 2013-01-18 09:44
У меня нет компилятора для AVR под рукой.
Можете проверить функцию:
Code:
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x — b;
y = y | m;
>
m = m >> 2;
>
return y;
>
Сколько занимает и как долго выполняется?
# Neptun 2013-01-18 11:04
Quoting Nobody:
У меня нет компилятора для AVR под рукой.
Можете проверить функцию:
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x — b;
y = y | m;
>
m = m >> 2;
>
return y;
>
Сколько занимает и как долго выполняется?
F = 8 MHz, ATmega8, optimization O0 (none):
размер 14 байт.
скорость 540 циклов — 67.5uS
F = 8 MHz, ATmega8, optimization Os (none):
размер 14 байт.
скорость 2 циклf — 0.25uS
# Neptun 2013-01-18 11:07
Код которий тестировал:
unsigned int value = 0;
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
int main(void)
asm(«nop»);
value = isqrt(4096);
asm(«nop»);
# Pashgan 2013-01-18 11:33
У меня в IAR` получилось 52 байта, 180 тактов при LOW оптимизации по размеру кода
# spkik 2016-04-07 13:27
Quoting Nobody:
У меня нет компилятора для AVR под рукой.
Можете проверить функцию:
Code:
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x — b;
y = y | m;
>
m = m >> 2;
>
return y;
>
Сколько занимает и как долго выполняется?
подскажите пожалуйста как проделать это с переменной типа long?
# Neptun 2016-04-07 15:49
тоже самое но с типом long
unsigned long isqrt(unsigned long x)
unsigned long m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x — b;
y = y | m;
>
m = m >> 2;
>
return y;
>
# Васьок 2014-10-09 12:34
Пользовался детским алгоритмом, на мой взгляд достаточно быстр и достаточно компактный. Идея в том что от числа последовательно отнимаются все нечётные числа, и сколько вычитаний удалось сделать, таков и корень числа. Пример, число 49;
1) 49 — 1 = 48
2) 48 — 3 = 45
3) 45 — 5 = 40
4) 40 — 7 = 33
5) 33 — 9 = 24
6) 24 — 11 = 13
7) 13 — 13 = 0
7 циклов, корень числа 49 — 7.
И кстати при работе с МК типа AVR-ки лучше избегать делений, т.к. у AVR ядра нет аппаратного деления, а программное занимает дофига тактов. Другое дело ARM Cortex-M3 и выше, у которых деление выполняется за 2. 12 тактов.
# Петгосян 2016-11-20 13:37
У функции корня есть некоторые свойства симметрии, которые позволяют вычислять ее только на некотором отрезке, а потом решение распространить на всю ось. Например,
sqrt(a*2^16)=2^ 8*sqrt(a).
Удобно в качестве такого отрезка взять значения [2^30-2^31), потому что остальные значения можно свести к нему побитовым сдвигом и при этом не будет происходить потеря точности. Сначала вычисляем первый значащий бит (программно половинным делением или процессорной инструкцией, например на ARM это __clz). Потом сдвигаем входное число на это кличество бит и вычисляем корень, полученное значение сдвигаем обратно на в два раза меньшее количество).
Для вычисления корня на отрезке интерполируем его многочленом Лагранжа (параболой). Например, возьмем в качестве точек многочлена 2^30, 1,5 * 2^30, 2^31. Можно воспользоваться сторонним сервисом, и не возиться с вычислением коэффициентов. У меня получилась такая формула:
-x^2/499100218444523 + x/52370 + 14575
Очевидно, напрямую её использовать нельзя, потому что значения не влазят даже в диапазон целых. Но надо учесть, что нам важны только 16 бит результата, поэтому можно немного схитрить и вынести что-то за скобки.
(-x/9530269590 + 1) * x/52370 + 14575
(-x/145420 + 65536) * (x/65536) / 52370 + 14575
Ну и последнее — заменить деление на умножение. Допустим, у нас в резерве 30 бит числа. Мы хотим поделить некое число x, например, на 543. Вычисляем, в числе 543 есть 10 бит, в х 16 бит.
x / 543 * 2^26 / 2^26
x * (2^26 / 543) / 2^26
x * 123589 / 2^26
Теперь эти знания применяем к своему многочлену.
(-x/2^14 * 7384 / 2^16 + 2^16) * (x/2^16) / 2^16 * 20503 / 2^14 + 14575
Не ручаюсь за правильность коэффициентов, надо внимательно проверить.
Когда писал, не учел одну штуку, число бит может быть нечетным, отрезок надо брать больше.
Естественно, алгоритм будет быстро работать при наличии аппаратного умножения.
# Петгосян 2016-11-20 13:38
Если умножение делается за один такт, можно сделать вычисление корня побитовым подбором. На первой итерации выставляем 16 бит в 1, возводим в квадрат, сравниваем с входным числом. Если больше, сбрасываем бит. Потом с 15 битом повторяем то же самое и т.д. Как в АЦП.
# nebelwerfer 2017-01-22 14:19
А что за магическое число:
Code: m = 0x4000; ?
Это половина от максимума int ?
А вот 2й вариант работает отлично, спасибо!
Мне нужно считать корни из больших чисел до 250 000 000, поэтому увеличил количество:
Code: x = (a/x + x)>>1;
до 7 и точность приемлима.
У вас недостаточно прав для комментирования.
Найти корень из числа
Найти цифровой корень натурального числа
нужно найти цифровой корень числа без рекурсии
Не выводит цифровой корень числа
Доброго времени суток Нужно написать програму, что вычисляет цифровой корень рандомно.
Вычислить цифровой корень числа
Доброго времени суток Мне надо разработать функцию, которая вычисляет цифровой корень заданного.
Вычислить обратный корень числа
Исходные данные: Входной поток содержит набор целых чисел Ai (0 ≤ Ai ≤ 1018).
Вычисление квадратного корня без библиотечных методов
Если это реальная проблема, объясните, чем стандартный корень не подходит. Если это учебное задание, думайте сами, иначе вы ничему не научитесь. У нас не принято делать задания за студентов.
15 сен 2016 в 7:46
кстати, есть ещё инстрики. Они как бы не библиотечные функции. Более того, если все правильно сделать, то можно по 4 числа одновременно обрабатывать. Да, современные компиляторы их обычно и используют, когда пишем sqrt() .
15 фев 2017 в 20:26
из-за таких как VladD портится русскоязычное комьюнити, вопрос непростой, человек может понять пытается, что там за функцией написано, а его сразу называют студентом и пафосно *******тся «У нас не принято делать задания для студентов», уже успел разделить людей на «мы (элита русскоязычного комьюнити, которые всегда назовут студентами и отправят читать документацию)» и студентов, которые ищут халявы на стековерфлоу
23 янв 2018 в 18:31
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Вопрос на самом деле имеет множество решений.
Самый банальный — метод половинного деления.
double l = 0; double r = 1e100; //большое число double m; while (r - l > 1e-8) < //точность m = l + (r - l)/2; if (m*m >n) l = m; else r = m; > //ответ в l Есть более оригинальные способы, например симуляция вычисления в столбик (вот пример, код приводить не буду )
Способ больше для C, но думаю можно использовать и в Java. Объяснение
float Q_rsqrt( float number ) < long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1 итерация // y = y * ( threehalfs - ( x2 * y * y ) ); // 2 итерация, можно удалить return 1/y; > Можно использовать логарифмы
return Math.exp( Math.log(n) / 2); Можно использовать численные методы, например метод Ньютона
double x = 1; for (;;) < double nx = (x + n / x) / 2; if (abs (x - nx) < 1e-10) break; //точность x = nx; >Существует и много других способов, всё зависит от конкретных требований.