大きな数の最初の10桁を求める

大きな数の最初の10桁を効率的に計算しないといけないような問題に遭遇した。

下n桁を求めるのは剰余で出来るけど、上n桁ってどうやるのだろう。
logを使うとうまく出来そうだ。ということでやってみた。
とりあえず2のべき乗の上10桁を求めてみた。

プログラム

#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-6;

// return the first 10 digits of 2^k
long long calc(int k) {
    double x = k * log(2);
    int d = x / log(10);
    x -= d * log(10);
    x += 9 * log(10);
    return exp(x) + EPS;
}


int main(int argc, char **argv) {
    
    cout << calc(1000) << endl;
    cout << calc(10000) << endl;
    cout << calc(100000) << endl;

    return 0;
}

結果確認

プログラムの実行結果。

1071508607
1995063116
9990020930

Pythonで2^kを実際に計算して検算してみた。正しく計算出来ていた。

$ python -c "print str(2**1000)[:10]"
1071508607
$ python -c "print str(2**10000)[:10]"
1995063116
$ python -c "print str(2**100000)[:10]"
9990020930

Graphvizで二分探索木を描画する

Graphvizという便利なツールがあることを知った。
AT&T研究所が開発したオープンソースのグラフ描画ツールである。とりあえず動かして遊んでみようということで、二分探索木を描画してみた。

インストール

Ubuntuマシンにインストール。

$ sudo apt-get install graphviz

二分木を作るプログラム

まず、20個の乱数を二分探索木に格納する。
その後、Graphvizに読み込ませるDOT言語のスクリプトをdump関数で出力する。

#include <iostream>
#include <cstdlib>

using namespace std;

struct node {
    int x;
    node *lch, *rch;

    node (int x) : x(x), lch(NULL), rch(NULL) {}
};

node *insert(node *v, int x) {
    if (v == NULL)
        return new node(x);
    if (x < v->x) 
        v->lch = insert(v->lch, x);
    if (x > v->x) 
        v->rch = insert(v->rch, x);
    return v;
}

void dump(node *v, node *par = NULL) {
    if (v == NULL)
        return;

    if (par == NULL) {
        cout << "digraph G{" << endl;
        cout << "  graph [ordering=\"out\"];" << endl;
    }
    else {
        cout << "  " << par->x << " -> " << v->x;
        if (v->x > par->x)
            cout << " [style = dotted]";
        cout << ";" << endl;
    }

    dump(v->lch, v);
    dump(v->rch, v);

    if (par == NULL)
        cout << "}" << endl;
}

int main(int argc, char **argv) {

    srand(time(NULL));
    node *root = NULL;

    for (int i = 0; i < 20; i++)
        root = insert(root, rand() % 100);

    dump(root);

    return 0;
}

上のソースはbst.cppという名前で保存しているとする。

以下を実行。

$ g++ bst.cpp -o bst
$ ./bst >sample.dot
$ dot -Tpng sample.dot -o sample.png
$ xdg-open sample.png 

すると、以下の画像が表示される。実戦が左の子への辺、破線が右の子への辺である。

これで木の回転をして遊んだり、平衡二分木を自分で実装したり、などなどするときに動作確認がしやすくなる。

商社は何をやっているのか

　商社は何をやっているのか？どうやって儲けているのか？
半年くらい働いてみて分かったことをまとめておく。
商社の規模や扱っている商品によって違いはあるかもしれないが、基本的な部分はだいたい共通していると思う。

販売額 - 仕入れ額のマージンが儲け

商社の利益は、販売額と仕入れ額の差から生まれる。メーカーから商品を仕入れて、それに値段を上乗せして、消費者や小売業者に販売する。このとき上乗せした値段が利益になる。

　ここまでは前から知っていた。いまいち分かっていなかったのは商社の存在意義。メーカーが直接売ればいいじゃん。なんか商社って楽して儲けてるだけで何の価値も創造していないような・・と思っていた。

いいモノを作れば売れるというわけではない

商社の存在意義を考えるうえでポイントとなるのが、「いいモノを作れば必ず売れる」というのは間違いということ。いいモノを作っても宣伝しなければ売れない。当たり前だ。

　そこで登場するのが商社。商社は持ち前の営業力でモノを上手に宣伝し、顧客に売り込む。もちろん現代においては、ITを駆使した顧客分析、商品分析なども行う。今はこういう商品が人気だから、今度はこういう商品を開発しましょう！というように商品企画に関与することもある。

　つまり商社はメーカーが作ったいいモノを世の中により広く流通させるために営業力の面からサポートを行う仲介業者みたいなイメージ。これが分かったとき、商社は楽して儲けているだけというイメージは完全に無くなった。

モノは買い手にすぐ届くわけではない

モノを買いたい人が見つかったらそれで終わりというわけではない。
モノを顧客の元に届けなければならない。そのためには配送ルートが必要だ。それからモノを格納しておく倉庫も必要だ。何をいつどれだけ作ればいいかを考える生産計画も必要だ。

　こういう物流まわりも商社がやっている。メーカーが作ったモノを営業して売り込み、顧客のもとに届けるまで面倒をみる。これが商社。商品の総合プロデューサーという感じだろうか。

Optimal Strategy for Grundy's Game

 I learned about "Grundy's Game." This game is played by two players as follows:

1. The game starts with a single heap of objects.
2. The first player chooses a heap and splits the heap into two heaps of different sizes.
3. The second player does the same thing as 2.
4. Repeat 2. and 3. The player who cannot make a proper move loses.

For example, let's say the size of an initial heap is 9.

The first player splits a heap into (4, 5).
The second player splits the second heap into (2, 3), making the heap sizes (4, 2, 3).
The first player splits the first heap into (2, 2), making the heap sizes (2, 2, 2, 3).
The second player splits the last heap into (1, 2), which is the only allowed move here, making the heap sizes  (2, 2, 2, 1, 2).

Now there are no proper moves available.
You cannot split a heap of the size 1.
And You cannot split a heap of the size 2 into two heaps of different sizes.
Therefore the second players wins in the example.

Umm, sounds like a good way to kill time. You can play with some coins.

I wrote a program that returns the optimal strategy for this game. As you can guess from the name of this game, I used Grundy numbers. Just run the program, input the heap sizes, like, 10 or 5 10 20 or whatever. That's it.

#include <iostream>
#include <vector>
#include <set>
#include <sstream>

using namespace std;

const int MAX_V = 1000;
int g[MAX_V + 1];

void init() {
    for (int i = 2; i <= MAX_V; i++) {
        set<int> s;
        for (int j = 1; 2 * j < i; j++) {
            s.insert(g[j] ^ g[i-j]);
        }
        while (s.count(g[i]))
            ++g[i];
    }
}

void solve(vector<int> &a) {

    int sum = 0;
    for (int i = 0; i < a.size(); i++)
        sum ^= g[a[i]];

    for (int i = 0; i < a.size(); i++) {
        sum ^= g[a[i]];
        
        for (int j = 1; 2 * j < a[i]; j++) {
            if (!(sum ^ g[j] ^ g[a[i] - j])) {

                for (int k = 0; k < a.size(); k++) {
                    if (k == i)
                        cout << j << " " << (a[i] - j) << " ";
                    else
                        cout << a[k] << " ";
                }
                cout << endl;

                return;
            }
        }
        
        sum ^= g[a[i]];
    }
    
    cout << "Uncle." << endl;
}

int main(int argc, char **argv) {

    init();
    
    for (string line; getline(cin, line), line != "bye"; ) {

        istringstream iss(line);
        vector<int> a;

        int n;
        while (iss >> n)
            a.push_back(n);

        solve(a);

    }

    return 0;
}