欧拉计划的一些题目需要检测完全平方数,最简单的方法是使用以下 C 语言程序:

int isSquare(long n) { long x = (long)sqrt(n); return x * x == n; }

但是,也有更快的方法,即以下的 C 语言程序(exactSquareRoot.c):

#include <math.h>

char bad255[512] =
{0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0};

// return: < 0 if x is not a square, r if r*r == x and r >= 0
int exactSquareRoot(long x)
{
  // Quickfail
  if (x < 0 || (x & 2) || (x & 7) == 5 || (x & 11) == 8) return -1;
  if (x == 0) return 0;
  // Check mod 255 = 3 * 5 * 17, for fun
  long y = x;
  y = (y & 4294967295L) + (y >> 32);
  y = (y & 65535) + (y >> 16);
  y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
  if (bad255[y]) return -1;
  // Divide out powers of 4 using binary search
  y = x;
  if ((y & 4294967295L) == 0) y >>= 32;
  if ((y & 65535) == 0) y >>= 16;
  if ((y & 255) == 0) y >>= 8;
  if ((y & 15) == 0) y >>= 4;
  if ((y & 3) == 0) y >>= 2;
  if ((y & 7) != 1) return -1;
  int r = (int)sqrt(x);
  return (r * (long)r == x) ? r : -1;
}

我们来比较一下两者的速度(a.c):

#include <stdio.h>
#include <math.h>

extern int exactSquareRoot(long x);

int isSquare1(long n) { long x = (long)sqrt(n); return x * x == n; }
int isSquare2(long n) { return exactSquareRoot(n) >= 0; }

int count(long a, long n, int (*f)(long))
{
  int z = 0;
  for (long i = 0; i < n; i++) if (f(a + i)) z++;
  return z;
}

int main()
{
  long a = 123456789; long n = 4987654321;
  printf("%ld: %ld\n", a, n); fflush(stdout);
  printf("%d\n", count(a, n, isSquare1)); fflush(stdout);
  printf("%d\n", count(a, n, isSquare2)); fflush(stdout);
}

运行结果:

$ clang -O3 a.c exactSquareRoot.c -lm
$ ./a.out | gnomon -i

  40.4646s | 123456789: 4987654321
  24.9703s | 60381
   0.0069s | 60381
           |
     Total | 65.4442s

这个比较程序统计从 123456789 开始的 4987654321 个整数,计算其中的完全平方数的个数,得到的结果是有 60381 个。前者用时 40.46 秒,后者用时 24.97 秒。

注:

参考资料

  1. Wikipedia: Square number
  2. Stack Overflow: Fastest way to determine if an integer's square root is an integer
  3. 图灵社区:测量程序的运行时间