何となく Blog by Jitta
Microsoft .NET 考

目次

Blog 利用状況
  • 投稿数 - 761
  • 記事 - 18
  • コメント - 18763
  • トラックバック - 222
ニュース
  • IE7以前では、表示がおかしい。div の解釈に問題があるようだ。
    IE8の場合は、「互換」表示を OFF にしてください。
  • 検索エンジンで来られた方へ:
    お望みの情報は見つかりましたか? よろしければ、コメント欄にどのような情報を探していたのか、ご記入ください。
It's ME!
  • はなおか じった
  • 世界遺産の近くに住んでます。
  • Microsoft MVP for Visual Developer ASP/ASP.NET 10, 2004 - 9, 2011
広告

記事カテゴリ

書庫

日記カテゴリ

ギャラリ

その他

わんくま同盟

同郷

 

プチ祭り?「気がつくと」とか、「[C++] 1から10まで足す」とか、「1+2+…+10」とか、「[C] 1から10までの総和をマクロでエレファントに解く。」とか。


「55と出力する」に決まってるじゃないですか。


10 REM This code is written for N80-BASIC
20 PRINT 55

大元のネタは、おそらく、「転職活動する暇があったらブログを書け」について(ベンチャー社長で技術者で)だと思います。私の答えは、一般社会ではそれではダメで、意図がまったく読み取れてないからゼロです。だ、そうです。

うむ、そうですか。私は、意図を、読みません。だって、読み間違えていたら、手戻り作業が大変じゃないですか。だから、意図は尋ね、確認します。・・・いや、ごめんなさい。これからは確認します。今、意図を読み違えて大変なことになっているのよ~~(T^T)

私が上記のようなコードを書いた意図は、わざわざ「written for N80-BASIC」と、今回は remark を振ったところにあります。N80-BASIC は、インタープリター言語です。逐次翻訳です。FOR 文を書いたら、命令をコンパイルしながら実行するので、遅いのです。先に計算できるものはしておく。インタープリター言語を使っていた頃の、ひとつの知識です。

もちろん、C/C++ で、次のように書くのもありです。これもコンパイル時に最適化で計算されてしまいます。


#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    cout << 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 << endl;
    return 0;
}

ところで、ここのコメントに、「10億だったら…」とありますが。

まず、10億だったら、答えは何か。
10だと、55
100だと、5050
1000だと、500500、です。法則が見えましたね。
10億は1000000000、0が9個あるので、5の後に0を8個入れた、500000000500000000…50京5億です。

これがコンピューターに計算できるか?微妙です。なぜなら、コンピューターが扱える数の範囲には、限りがあるからです。

演算に用いる型のビット数が32ビットの場合、約21億(符号無しで約42億)が最大となります。このため、32ビットの整数型では、計算途中にオーバーフローが発生します。64ビットだと、約922京(符号無しだと約1844京)です。SQL Server や Oracle ではもっと大きな数字を扱えます。SQL Server 2005以降と Oracle では38桁扱えます。えっと。。。京、垓、杼(正しくはノ木偏)、穣、溝、澗の、澗(カン)だそうです。

じゃぁ、64ビットだと、いくつまで計算できるでしょうか。10億で50京です。100億だと5千京です。ああ、超えた。。。

反対にしよう。総和が922京になる数字を求めよう。・・・4294967295。これの答えが9223372034707292160。約922京なので、求められるはずです。

ところが、生島さんが期待する「(n + 1) × n ÷ 2」の計算式では、答えが求められないのです。

なぜでしょう?

「(n + 1) × n」で、約1844京となり、桁あふれを起こすからです。922京を2倍して平方根を取ると、42億になります。が、それを先に書くと1844京という値が先に出てしまい、オーバーフローがチョンばれです。その為、上ではいきなり42億という数字を出しています。

検証
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    __int64 max = 4294967295;
    __int64 sum = 0;
    for (__int64 i = 1; i <= max; ++i) {
        sum += i;
    }
    cout << sum << endl;
    cout << (max + 1) * max / 2 << endl;
    return 0;
}

結果
C:\Projects\TestSolution\Debug>totalSum.exe
9223372034707292160
-2147483648

これを防ぐためには、「(n + 1) × (n ÷ 2)」とするのが、ひとつの方法です。しかし、n が奇数の場合、正しい結果が得られません(9223372032559808512になる)。整数と整数の除算は整数になり、0.5が捨てられるからです。n が奇数の場合は、「((n + 1) ÷ 2) × n」とします。


#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    __int64 max = 4294967295;
    __int64 sum = 0;
    for (__int64 i = 1; i <= max; ++i) {
        sum += i;
    }
    cout << sum << endl;
    cout << (max + 1) * max / 2 << endl;
    cout << ((max % 2 == 1) ? ((max + 1) / 2) * max
                                  : (max + 1) * (max / 2))
        << endl;
    return 0;
}

結果
C:\Projects\TestSolution\Debug>totalSum.exe
9223372034707292160
-2147483648
9223372034707292160

今回は固定の数字を求めましたが、ユーザーによる手入力の場合は、上限を超えるような数字ではないことを確認しておく必要があるかもしれません。

投稿日時 : 2009年10月1日 22:41
コメント
  • # re: 1から10まで足す、ですって?
    かずき
    Posted @ 2009/10/02 16:27
    1~10の総和からここまで・・・
    ここまで来ると、お遊びネタって感じでは無くなりますね。
    凄いの一言です!
  • # re: 1から10まで足す、ですって?
    Jitta
    Posted @ 2009/10/02 19:03
    かずきさん、コメントありがとうございます!

    いや、ゼロと言われて悔しかっただけです(笑)
    コンパイラが賢いので、基本的にコンパイラの最適化に任せるのが基本ですが、バグの作り込みや、不用意な"修正"からの自衛手段は、用意しておくべきかと思います。その意味で、先に計算しておくのは(計算ミスがあったらパー!ですが)、他のどの様な要因からも保護されていると思います。
  • # 1から10までの和を、ループを使わずに計算してみる
    いや、まだだから
    Posted @ 2009/10/06 0:23
    1から10までの和を、ループを使わずに計算してみる
タイトル  
名前  
Url
コメント