Что может быть быстрее, чем math sqrt?

216

12 февраля 2019, 16:00

Передо мной стоит задача: Мне необходимо максимально быстро найти количество целых квадратных корней из нескольких триллионов целых чисел, не превышающих 100 000^2 Проще говоря:

100 = 10^2 - подходит

3 = не подходит

28 = не подходит

49 = 7^2 - подходит

...

и т.д.

В рамках поставленной задачи я использую директиву openMP, для равномерного распределения потоков между ядрами процессора, однако даже в таком случае скорость выполнения программы меня не очень устраивает. В данный момент используемая мною конструкция выглядит так:

int y = sqrt(x);
if (y==int(y))
  i++;

Я пытался воспользоваться поиском во множестве SET, зная, что мое число никогда не будет превышать 100 000^2

set<int> mySet;
for (int j = 1; j <= 100001; j++) 
    mySet.insert(j*j);
if (mySet.find(x) != mySet.end()) 
  i++;

Но этот способ оказался во много раз медленнее, чем обычное вычисление из под квадратного корня. Подскажите, возможно ли с помощью средств языка еще как-то ускорить выполнение одной итерации или заменить вычисление из под корня чем-то более быстрым? Буду рад любым наводкам!

Answer 1

Есть очень эффективный способ ускорить вычисления - отбрасывания заведомо "не квадратов". Если вспомнить школьную математику, то можно догадаться, что последние n цифр квадрата числа зависят только от последний n цифр самого числа. Отсюда вывод - если число заканчивается на 0 1 4 5 6 9, то это может быть квадрат какого то числа. Если же 2 3 7 8 - то это точно не квадрат.

Но по последней цифре дает 40% отсеивания. Этого маловато. По последним двум цифрам (00 01 04 09 16 21 24 25 29 36 41 44 49 56 61 64 69 76 81 84 89 96 ) процент отсеивания уже 78%. А это очень хорошо. То есть, в 4 с 5 случаев даже вычислять ничего не нужно. Идем дальше. При последних трех цифрах уже можно отсеять 84.1%, 4 цифры 89.56 - а это очень и очень хорошо - на рандомных данных можно получить десятикратный прирост.

Сами данные можно хранить в небольшом массиве и вычислять при старте. Последние 3 цифры можно получать через % 1000.

Answer 2

Я бы попробовал собственную реализацию с set на битовых масках. Выделяем ~1.2 Gb памяти одним куском и устанавливаем в нем 100000 нужных бит.

Так как set будет сильно разряженным, то сначала проверяем что весь байт не 0, если это так - проверяем нужный бит.

Возможно обработка по 4 или 8 байт сразу будет быстрее чем по 1 байту.

Answer 3

Чтобы не тратить много памяти, создайте фильтр Блума

Это структура данных, позволяющая определить принадлежность элемента к множеству (в данном случае - множеству квадратов 1,4,9...10^10).

У неё есть особенность - алгоритм может сообщить, что элемент присутствует в множестве, хотя на самом деле его нет - ложноположительное срабатывание.

В этом случае придётся проверить руками, извлекая корень. Однако для большинства чисел (доля ложных срабатываний зависит от выделенной памяти) такая проверка не нужна, т.к. ложноотрицательных срабатываний не бывает.

Пример на Delphi

var
  b: TSynBloomFilter;
  i, cnt: Integer;
  ii: Int64;
begin
  //выбираем 5xразмер словаря, больший размер уже не особо влияет на количество коллизий
  b := TSynBloomFilter.Create(500000);
  try
    //загоняем квадраты до 10^10
    for i := 1 to 100000 do begin
      ii := int64(i) * i;
      b.Insert(@ii, sizeof(ii));
    end;
    //считаем, сколько обнаружений выпало на диапазоне 10^8
    //истинных совпадений 10000
    cnt := 0;
    for i := 1 to 100000000 do begin
      ii := i;
      if b.MayExist(@ii, sizeof(ii)) then
          Inc(cnt);
    end;
     //через две секунды видим - 
    //получается, что потребовалось проверить 11359 чисел
    Memo1.Lines.Add(cnt.ToString);
  finally
    b.Free;
  end;

Answer 4

Идея с std::set хорошая, только вместо std::set надо использовать отсортированный массив квадратов, который сгенирировать скритпом, должно получится что-то типа:

const int64_t n2[] = { 1, 4, 9, 16, 25, ... 100000^2 };

Далее используя бинарый поиск std::lower_bound(n2, n2+size, testValue) будешь быстро находить нужное значение (или не находить). Такой массив занимает всего 800kb легко влазит в кеш процессора

Answer 5

Попробуйте целочисленный корень. Может быть будет быстрее, но я не верю.

# include <stdbool.h>
# include <stdio.h>
long isqrt(long ) ;
long isqrt(long num) {
    long res = 0;
    long bit = 1L << (sizeof(long)*8-2); // 2^62
    while (bit > num)        bit >>= 2;
    while (bit) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;        }
        else            res >>= 1;
        bit >>= 2;    }
    return res; }
bool isSquare(long x) ;
bool isSquare(long x){
  long y = isqrt(x);
  //fprintf(stdout,"y = %ld\n",y);
  return y*y == x;}
int main(){
  long x;
  fprintf(stdout,"print number ?");
  fscanf(stdin,"%ld",&x);
  bool res = isSquare(x);
  fprintf(stdout,"result = %s\n",(res?"true":"false"));
  return 0;}