主页 / 问题 / 891685
Accepted
Crux Commissa
Asked:2020-10-11 17:02:08 +0000 UTC2020-10-11 17:02:08 +0000 UTC

什么可以比数学 sqrt 更快？

  • 772

我有一个任务：我需要尽快找到几万亿个整数的整数平方根个数，不超过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++;

但事实证明，这种方法比通常的平方根计算要慢很多倍。告诉我，是否有可能使用语言工具以某种方式加速一次迭代的执行，或者用更快的方法替换根下的计算？我会很高兴任何提示！

c++

5 个回答

  1. Best Answer

    有一种非常有效的方法可以加快计算速度——丢弃明显的“非正方形”。如果你回想一下学校数学，你可以猜到一个数字平方的最后 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%。这是非常好的。也就是说，在五分之四的情况下，您甚至不需要计算任何东西。继续前行。使用最后三位数字，您已经可以过滤掉 84.1%，4 位数字 89.56 - 这非常非常好 - 您可以将随机数据增加十倍。

    数据本身可以存储在一个小数组中，并在启动时计算。可以通过 检索最后 3 位数字% 1000。

    • 24

  2. 我会尝试在位掩码上设置我自己的实现。我们在一块中分配约 1.2 Gb 的内存，并在其中设置 100,000 个必要的位。

    由于 set 将非常稀疏，我们首先检查整个字节是否不为 0，如果是，我们检查所需的位。

    也许一次处理 4 或 8 个字节会比 1 个字节快。

    • 6

  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;
    • 6

  4. 使用 std::set 的想法很好，但您需要使用由脚本生成的排序正方形数组而不是 std::set，您应该得到如下内容：

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

    此外，使用二分搜索，std::lower_bound(n2, n2+size, testValue)您将很快找到所需的值（或找不到）。这样的阵列只需要 800kb 并且很容易放入处理器缓存中

    • 3

  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;}
    • 0

相关问题