Edited at

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

More than 1 year has passed since last update.

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秒というのは、あまりに遅すぎるでしょう。

けれど、こんな無茶苦茶な力技でも、たまに動かす処理や、夜の間に終わればいい処理に使うなら、それなりに現実的な時間で動きました。

とはいえ、ループの中が重くなると、一気に重くなることは目に見えているので、利用できる場面は果たして存在するのか、というくらい少ない気はしますが。