[小ネタ]最近のコンピュータではINT32_MAX回のループでも意外と回ると気づいた話

32ビット整数の最大値って、とてつもなく大きい印象があったのですが。
そして、そんなすごい回数のループなんて、全然終わらない、という印象があったのですが。

家にある、数年前のCore i5のパソコンで、なんとなくやってみました。
最適化などのオプションは何もつけてません。

#include <stdio.h>
int main() {
    int i;
    long long s = 0;
    for(i=0;i<0x7FFFFFFF;i++) s += i;
    printf("%lld\n", s);
}

$ time ./a.out 
2305843005992468481

real    0m5.063s
user    0m5.062s
sys     0m0.000s

もちろん、ループの中が重くなれば、どうなるかは想像に難くないですが。
例えば、以下のように、少し重くするだけで、

#include <stdio.h>
int main() {
    int i;
    long long s = 0;
    for(i=0;i<0x7FFFFFFF;i++) if(i%2) s /= i;
    printf("%lld\n", s);
}

$ time ./a.out 
0

real    0m14.842s
user    0m14.780s
sys     0m0.007s

と、時間も増えてしまいました。

さて。0〜INT32_MAX-1の間で、平方根が整数になるものを力技で求めてみましょう。
(普通は、こんな効率悪い計算せずに、整数を2乗することで求めるかと思いますが)

#include <stdio.h>
#include <math.h>
#include <float.h>
int main() {
    int i;
    for(i=0;i<0x7FFFFFFF;i++) {
        double d = sqrt(i);
        if(fabs(d - (int)d) < DBL_EPSILON) printf("%d\n", i);
    }
}

$ time ./a.out
(略)

real    0m30.276s
user    0m30.049s
sys     0m0.070s

意外と、できるものですなぁ。

例えばこれを、競技プログラミングなどで使うには、ただの足し算で5秒というのは、あまりに遅すぎるでしょう。
けれど、こんな無茶苦茶な力技でも、たまに動かす処理や、夜の間に終わればいい処理に使うなら、それなりに現実的な時間で動きました。
とはいえ、ループの中が重くなると、一気に重くなることは目に見えているので、利用できる場面は果たして存在するのか、というくらい少ない気はしますが。