Как написать собственную функцию извлечения кв. корня из целого числа?
Попробовал написать аналог функции sqrt(), но для целых чисел. Что можно сделать лучше, быстрее? Я просто начинающий, не хотелось бы «говнокодить» с самого начала изучения языка. Знаю, что register средой visual c++ не воспринимается, но судя по литературе, в других компайлерах скорость работы ускорить должно. Заранее спасибо за ответы.
int my_sqr(int number) < register unsigned int temp = 0, x = 1; if (number < 0) number = -number; while (temp != x)< temp = number / x; if (temp == x) return x; x++; >>;- Вопрос задан более трёх лет назад
- 11619 просмотров
Комментировать
Решения вопроса 1
«I’m here to consult you» © Dogbert
Что можно сделать лучше, быстрее?
Поменять алгоритм на метод деления пополам или побитовый поиск, с уменьшением сложности по количеству бит в int с экспоненциальной до линейной.
int my_sqr(int number)< register unsigned int temp, x; if (number < 0) number = -number; for (temp = 0, x = 1u >= 1) < if ((temp | x) * (temp | x) return temp; >Не проверять на равенство if (temp == x), потому что равенства может не быть, например для number = 6.
Убедиться, что функция всегда что-то возвращает. Так, например, при number = 6 ваша функция зацикливается или падает с делением на 0, а при number = 0 завершается с неопределённым значением.
Ответ написан более трёх лет назад
nikitosssguy @nikitosssguy Автор вопроса
Такой вариант будет намного быстрее в случае с большими числами?
Такой вариант гарантированно находит корень за 16 итераций для любого 32-битного инта.
nikitosssguy @nikitosssguy Автор вопроса
@jcmvbkbc, спасибо, надо будет разобраться.
nikitosssguy @nikitosssguy Автор вопроса
Не могли бы вы немного разжевать вашу функцию? Никак не могу вникнуть в происходящее.
@nikitosssguy мы поразрядно подбираем максимальное число, квадрат которого не превосходит заданного. Начинаем с максимального разряда, квадрат которого всё ещё укладывается в unsigned int, и на каждой итерации проверяем, сохраняется ли неравенство temp ^ 2
nikitosssguy @nikitosssguy Автор вопроса
@jcmvbkbc, что-ж, спасибо. Когда изучал битовые операции никак не мог въехать, буду копать, раз уж это настолько полезная особенность c++
Ответы на вопрос 3
ну наверное вспомнить математику и включить голову. логарифм от числа, деленный на логарифм основания дает нам степень:
a^b=c b=ln(c)/ln(a) a=exp(b * ln(c)) для квадратного корня b = 1/2Ответ написан более трёх лет назад
@svd71 а как, вы говорите, это делается в целых числах?
просто подставляем в формулу значения:
@svd71 вы, похоже, не поняли. Как используя только целочисленную математику вычислить части вашего выражения, такие как log и exp для произвольных значений?
нда. Этот момент я точно не понял.
А использовать более оптимальные алгоритмы? Для целого числа очень подойдет разложение в ряд.
1 = 1^2
1 + 3 = 2^2
1 + 3 + 5 = 3^2
1 + 3 + 5 + 7 = 4^2
Замечаете?
Просто вычитаете все нечетные числа начиная с 1. Если остаток меньше следующего нечетного числа, то берете порядковый номер предыдущего нечетного числа. Но это подойдет, если числа не очень большие, хотя ваш алгоритм не лучше в этом отношении.
Ну и как обычно на тостере, поискать видимо лень, поэтому вопросов интересных нет, а вот такая вот фигня.
Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
dmitry2001 @dmitry2001
Существует такой алгоритм как бинпоиск
int sqrt (int v) < int L = 0, R = v; int M = (L + R) /2; while(R - L >1) < if(M * M else < R = M; >M = (L + R)/2; > >Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Ваш ответ на вопрос
Войдите, чтобы написать ответ
- C++
Не могу, понять как компьютер перемещает свой знак?
- 1 подписчик
- 20 часов назад
- 90 просмотров
Math. Sqrt(Double) Метод
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Возвращает квадратный корень из указанного числа.
public: static double Sqrt(double d);public static double Sqrt (double d);static member Sqrt : double -> doublePublic Shared Function Sqrt (d As Double) As DoubleПараметры
Число, квадратный корень которого требуется найти.
Возвращаемое значение
Одно из значений, перечисленных в следующей таблице.
| Параметр d | Возвращаемое значение |
|---|---|
| Нуль или положительное число | Положительный квадратный корень из d . |
| Отрицательное число | NaN |
| Равняется NaN | NaN |
| Равняется PositiveInfinity | PositiveInfinity |
Примеры
Квадратный корень площади квадрата представляет длину любой стороны квадрата. В следующем примере показана площадь некоторых городов в США и создается впечатление размера каждого города, если он был представлен квадратом.
// Create an array containing the area of some squares. Tuple[] areas = < Tuple.Create("Sitka, Alaska", 2870.3), Tuple.Create("New York City", 302.6), Tuple.Create("Los Angeles", 468.7), Tuple.Create("Detroit", 138.8), Tuple.Create("Chicago", 227.1), Tuple.Create("San Diego", 325.2) >; Console.WriteLine(" \n", "City", "Area (mi.)", "Equivalent to a square with:"); foreach (var area in areas) Console.WriteLine(" miles per side", area.Item1, area.Item2, Math.Round(Math.Sqrt(area.Item2), 2)); // The example displays the following output: // City Area (mi.) Equivalent to a square with: // // Sitka, Alaska 2,870.3 53.58 miles per side // New York City 302.6 17.40 miles per side // Los Angeles 468.7 21.65 miles per side // Detroit 138.8 11.78 miles per side // Chicago 227.1 15.07 miles per side // San Diego 325.2 18.03 miles per side open System // Create a list containing the area of some cities. let areas = [ "Sitka, Alaska", 2870.3 "New York City", 302.6 "Los Angeles", 468.7 "Detroit", 138.8 "Chicago", 227.1 "San Diego", 325.2 ] printfn "%-18s %14s> %2s\n" "City" "Area (mi.)" "Equivalent to a square with:" for city, area in areas do printfn $" miles per side" // The example displays the following output: // City Area (mi.) Equivalent to a square with: // // Sitka, Alaska 2,870.3 53.58 miles per side // New York City 302.6 17.40 miles per side // Los Angeles 468.7 21.65 miles per side // Detroit 138.8 11.78 miles per side // Chicago 227.1 15.07 miles per side // San Diego 325.2 18.03 miles per side Module Example Public Sub Main() ' Create an array containing the area of some squares. Dim areas() As Tuple(Of String, Double) = < Tuple.Create("Sitka, Alaska", 2870.3), Tuple.Create("New York City", 302.6), Tuple.Create("Los Angeles", 468.7), Tuple.Create("Detroit", 138.8), Tuple.Create("Chicago", 227.1), Tuple.Create("San Diego", 325.2) >Console.WriteLine(" ", "City", "Area (mi.)", "Equivalent to a square with:") Console.WriteLine() For Each area In areas Console.WriteLine(" miles per side", area.Item1, area.Item2, Math.Round(Math.Sqrt(area.Item2), 2)) Next End Sub End Module ' The example displays the following output: ' City Area (mi.) Equivalent to a square with: ' ' Sitka, Alaska 2,870.3 53.58 miles per side ' New York City 302.6 17.40 miles per side ' Los Angeles 468.7 21.65 miles per side ' Detroit 138.8 11.78 miles per side ' Chicago 227.1 15.07 miles per side ' San Diego 325.2 18.03 miles per side Применяется к
См. также раздел
Вычисление квадратного корня без библиотечных методов
Если это реальная проблема, объясните, чем стандартный корень не подходит. Если это учебное задание, думайте сами, иначе вы ничему не научитесь. У нас не принято делать задания за студентов.
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; >Существует и много других способов, всё зависит от конкретных требований.
Как извлечь корень из числа c
PetarV → Codeforces Round #169 — Unofficial Editorial
MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating
AC_AC → CSES DP SECTION — Book Shop
Hexagons → [OFF TOPIC] Hollow Knight radiant tutorial for bossfight «Markoth»
Gheal → Codeforces Round #833 (Div. 2) Editorial
stefdasca → Easy and Quick Video Tutorials for the CSES Problem Set
vrintle → Invitation to Gym Contest — Alpha IV (by AlgoRave)
maomao90 → Editorial for Hello 2024
maomao90 → I am top 1 contributor. AMA!
YoyOyoYOy000y000 → Centroid Decomposition on a tree(Beginner)
D_coder22 → Uncertainty in Python Time of Execution
bycicle → Click here if you want a fast way to get rid of your alt
SlavicG → Codeforces Round 918 (Div. 4)
mohammed_orkhan → I wnat to be EXPERT!!
thenymphsofdelphi → Codeforces Round #873 (Div. 1 & 2) Editorial
VivaciousAubergine → Wow! You received a rating of -501 in the CodeTON round. Share it!
diskoteka → Codeforces Round #878 (Div.3) Разбор
CheaterExposer → [UPDATE] Codeforces Cheater IOI Medalist
sarthak1357 → CSES shortest routes 1
Pyqe → Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final) Editorial
arham_doshi → cses graph session editorial(incomplete)
SAD_IN_NIGHTMARE → 2024 OIs
parth_1818 → Know Some Sorting Techniques
I_am_Polish_Girl → Dijkstra Algorithgm
atcoder_official → AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement
Блог пользователя alligator
Кубический корень от числа, на С++
Автор alligator, 12 лет назад ,
Добрый день. Может кто-нибудь сказать или показать , как на С++ можно получить кубический корень от числа N? Спасибо.
c++, корень
Комментарии (12)
12 лет назад , # |
Например возведением в степень 1/3: pow(x, 1./3);
12 лет назад , # |
12 лет назад , # |
Бинарный поиск для монотонных функций. Кубическим корнем из числа x называется такое число y, что y^3 = x. Сформулируем задачу так: для данного вещественного числа x (x ≥ 1) найти кубический корень с точностью не менее 5 знаков после точки. Функция при x ≥ 1, ограничена сверху числом x, а снизу единицей. Таким образом, за нижнюю границу мы выбираем 1, за верхнюю само число x. После этого делим текущий отрезок пополам, возводим середину в куб и если куб больше x, то заменяем верхнюю грань, иначе нижнюю. Код будет выглядеть следующим образом: r = x ; l = 1 ; while (fabs(l-r)>eps) < m = ( l+r ) /2 ; if (m*m*m
12 лет назад , # ^ |
← Rev. 4 → 
+21 
Бинпоиск в таких случаях работает долго, уточняя по одной цифре в двоичном разложении за раз. Лучше уж итерационный метод, например Ньютона: Ищем корень кубический из A , в качестве x0 берём что-то приближённое. Итерационный метод возводит точность в квадрат, а не умножает на 2, как бинпоиск.
12 лет назад , # ^ |
Удивляюсь. Я воспринял исходный вопрос как то, что автор не знает pow. Или не слышал о log/exp. Или не подозревает, что извлечь корень кубический, это то же самое, что возвести в степень 1.0/3.
А тут такие серьёзные люди предлагают алгоритмические методы решения задачи.
Вопрос же был не «как получить кубический корень», а «как на С++ можно получить кубический корень».
Может, правда, вопрос был об очень большом целом N, но, тогда действительно только дихотомия и длинное умножение, думаю.
12 лет назад , # ^ |
Разве в длинной арифметике не лучше итерационным с делением?
12 лет назад , # ^ |
← Rev. 2 → 0
А разве он будет сходиться на целых числах? Да и писать длинное деление как-то не клево. А вот в вещественной. Хотя тут уже без BigDecimal печально.
12 лет назад , # ^ |
Будет выдаваться результат с точностью до +-1, а уж три значения можно и проверить.
12 лет назад , # ^ |
← Rev. 3 → 0
Да, согласен. Там же только делить на 2 надо, а это за O(N).
UPD. Не правильно воспринял. Можно же сделать дихотомию без длинного умножения, только с делением на 2, что за O(N). Любое другое длинное деление не на заранее известную константу, действительно напрягает.
12 лет назад , # ^ |
Так возведение в квадрат идёт за O(N 2 ) , как и длинное деление. Где здесь лучше?
12 лет назад , # ^ |
Длинное деление очень просто пишется в варианте N^2 * log2(base). В «кнутовском» варианте за O(n^2) код сложнее, как и сама идея, но для кого-то может быть тоже не сложно пишется.