Вычисление целочисленного квадратного корня

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

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

Возникла нужда проверить, является ли целое число квадратом, и если да, то вычислить корень. Причем хочется сделать это в целочисленной арифметике. Понятно, что можно реализовать метод Ньютона в целых числах, но он требует деления на каждом шаге. А нельзя ли по другому? Найти квадратный корень по модулю степени двойки, и проверить, а не будет ли он обычным квадратным корнем.

Можно ограничиться нечетными числами: для четного числа, если количество нулевых младших разрядов нечетно, то корня нет, а если четно, то можно сдвинуть число вправо, посчитать корень от нечетного, и сдвинуть обратно влево на половину от первоначального количества нулевых бит.

Для нечетного N и 2k, k > 3, если N ≡ 1 mod 8, то есть 4 разных корня по модулю 2k, а иначе корней нет. Нам нужен наименьший из этих четырех корней x. При этом другие три корня это 2k - x, 2k-1 + x и 2k - 2k-1 - x

Хочется что-то подобное вычислению обратного по модулю 2k — удваивая количество верных бит за итерацию.

Пусть у нас уже есть корень x0 из N по модулю 2k: N - x02 = 2ka
И мы хотим найти x1 = x0 + 2k-1y, такое чтобы в N - x12 было больше младших нулевых бит.
N - (x0 + 2k-1y)2 = 2ka - 2kx0 * y - 22k-2y2
Поделим на 2k: a - x0 * y - 2k-2y2
И приравняем к 0 по модулю 2k-2: y = a * x0-1 mod 2k-2
Получилии x1 = x0 + 2k-1a * (x0-1 mod 2k-2)
И окончательно x1 = x0 + (N - x02)/2 * (x0-1 mod 2k-2)

Из k бит на следующей итерации получится 2(k-1) бит. Параллельно считаем на каждой итерации обратное к корню.

Тестовый код:

uint8_t sqr16(uint16_t n) {
  if (n % 8 != 1) return 0;
  uint16_t sqr = (n + 1) / 2;  //4 bit
  uint16_t inv = 2 - sqr;

  sqr += inv * (n-sqr*sqr)/2;   //6 bit
  inv *= 2 - sqr * inv;

  sqr += inv * (n-sqr*sqr)/2;  //10 bit
  //inv *= 2 - sqr * inv;

  if (sqr & 256)
    sqr = 0u - sqr;
  sqr = (uint8_t)sqr; // lowest root
  if (n == sqr*sqr) return sqr;
  return 0;
}

Добавив пару итераций, получим корень из uint_64
Источник: https://habr.com/ru/post/469561/


Интересные статьи

Интересные статьи

Маркетплейс – это сервис от 1С-Битрикс, который позволяет разработчикам делиться своими решениями с широкой аудиторией, состоящей из клиентов и других разработчиков.
Статья о том, как упорядочить найм1. Информируем о вакансии2. Ведём до найма3. Автоматизируем скучное4. Оформляем и выводим на работу5. Отчитываемся по итогам6. Помогаем с адаптацией...
VUE.JS - это javascript фрэймворк, с версии 18.5 его добавили в ядро битрикса, поэтому можно его использовать из коробки.
Несмотря на то, что “в коробке” с Битриксом уже идут модули как для SOAP (модуль “Веб сервисы” в редакции “Бизнес” и старше), так и для REST (модуль “Rest API” во всех редакциях, начиная с...
Эта статья для тех, кто собирается открыть интернет-магазин, но еще рассматривает варианты и думает по какому пути пойти, заказать разработку магазина в студии, у фрилансера или выбрать облачный серви...