Вычисление квадратного корня из 1000+ битового слова в C

Question

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

Я предполагаю, что наше большое число - это один массив (старшие разряды в начале?). Квадратный корень - это более или менее половина исходного числа. При попытке использовать алгоритм "Цифра за цифрой" возникает момент, когда длинного длинного usnigned недостаточно для запоминания частичного результата (вычитание с расширенным числом 01). Как это решить? Что с получением одной цифры большого числа? Только по битовой маске?

Пока думал о псевдокоде, застрял на этом вопросе. Есть идеи?

Answer 1

Вычисление квадратных корней очень легко сделать с помощью алгоритма двоичного поиска.

Алгоритм псевдокода:

• Предположить c: значение 1000 бит, деленное на 2 (простое смещение битов).
• Квадрат это:
  • Если квадрат (почти) равен вашему 1000-битному числу, вы получите ответ
  • Если квадрат меньше вашего числа, вы можете быть уверены, что корень находится между c и ваша верхняя граница.
  • Если квадрат больше вашего числа, вы знаете, что корень лежит между вашей нижней границей и c,
• Повторяйте, пока не найдете свой корень, сохраняя при этом верхнюю и нижнюю границы.

Этот вид алгоритма должен работать в log (N) время.

Answer 2

Как бы вы сделали это вручную? Как бы вы поделили 1000-значный номер на 500-значный вручную? (Просто подумайте о методе, очевидно, это будет довольно много времени). Теперь с квадратным корнем, метод очень похож на деление, где вы "угадываете" первую цифру, затем вторую цифру и так далее и вычитаете вещи. Просто для квадратного корня вычитаете немного разные вещи (но не так уж и иначе, вычисление квадратного корня можно сделать способом, очень похожим на деление, за исключением того, что с каждой добавленной цифрой делитель изменяется).

Я не хотел бы говорить вам точно, как это сделать, потому что это портит удовольствие от самостоятельного открытия.

Хитрость в том, что вместо того, чтобы думать о квадратном корне из x, подумайте о том, чтобы найти число y такое, что y*y = x. А когда вы улучшите y, пересчитайте x - y*y с минимальными усилиями.

Answer 3

Вид зависит от того, насколько точно вы этого хотите. Учтите, что квадратный корень из 2^32 == 2^16. Таким образом, вы могли бы сдвинуть 1000-битное число на 500 бит вправо, и у вас есть ответ, который будет в поле зрения.

Насколько хорошо это работает? Посмотрим. Число 36 в двоичном коде равно 100100. Если я сдвину его на 3 бита вправо, то получу 4. Хммм... должно быть 6. Довольно большая ошибка 33%. Квадратный корень из 1 000 000 - это 1000. В двоичном виде 1 000 000 1111 0100 0010 0100 0000, Это 20 бит. Сместил вправо 10 бит, это 1111 0100 00или 976. Ошибка 24/1000, или 2,4%.

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

В зависимости от того, как вы храните числа, сдвиг 1000-битного числа на 500 бит вправо не должен быть ужасно сложным.

Answer 4

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