EGGXを用いたマンデルブロ集合の色付き描画

前回の記事のプログラムを少々変更してマンデルブロ集合の図を色付けした。

数列の発散、収束を計算していた関数と、それに関連する部分を少しだけ変えたプログラムを次に示す。発散する点においては、発散するまでに計算した回数を利用して色付けした。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0

int calc(complex<double> c)
{
    int n;
    complex<double> z;
    for (n = 0; n < MAX_ITER; n++) {
        z = z*z + c;
        if (abs(z) >= INF)
            return n%15+1;
    }
    return EGGX_BLACK;
}

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            int color = calc(complex<double>(re, im));
            newpen(win, color);
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
} 

EGGXを用いたマンデルブロ集合の描画

EGGXを使ってマンデルブロ集合を描く。

結論から示す。マンデルブロ集合を描いたとき、次のような図となる。

以下、どのようにこの図を描いていくのかを説明する。

まず、複素数列{Zn}を次のように定義する。
Zn+1 = (Zn)ˆ2 + C
Z0 = 0
ただし、Z0は初項であり、Zn+1におけるCは複素平面上の一点を意味する。

このときマンデルブロ集合は、「数列{Zn}においてn->∞としたとき、その数列が発散しないような複素数C全体の集合」と定義される。

では、マンデルブロ集合を図として描くときの手順を示す。
(1) 実部の区間を[-2, 1]、虚部の区間を[-1, 1]とし、その区間を描画領域とする。
(2) (1)の区間内にある全ての点を、上述の数列{Zn}のCとして与える。
(3) (2)で決めた数列{Zn}においてn->∞としたとき、{Zn}が発散するならば白、収束するならば黒で複素平面上の点であるCの位置に、点を描く。

以上が、基本的な手順となる。ただ、マンデルブロ集合は{Zn}が収束するような点全体として定義されるので、発散する点はマンデルブロ集合に含まれない。けれども、手順(3)からも判るように、ここでは発散する点を白で描いている。

マンデルブロ集合を描く、EGGXを用いたC++のソースコードを次に示す。実際にEGGXを用いてコンパイルする場合は、拡張子を.ccにすること。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0
#define EGGX_WHITE 1

bool not_inf(complex<double> c)
{
    complex<double> z;

    /*
        数列{Zn}を実際にn->∞として計算することは無理なので、
        n->MAX_ITERとして計算している。
    */
    for (int n = 0; n < MAX_ITER; n++) {
        z = z*z + c;

        /*
            |Zn|が2以上に達したら|Zn+1| > |Zn|なので、
            数列は必ず発散する。
        */
        if (abs(z) >= INF)
            return false;
    }
    return true;
}

/*
//C版(複素数を使わず書く)
//引数のa,bはC++版の
//複素数cをc = a + i*bと表したときのa, b。
int not_inf(double a, double b)
{
    int n;
    double re, im;
    re = im = 0;
    for (n = 0; n < MAX_ITER; n++) {
        double tr = re, ti = im;
        re = tr*tr - ti*ti + a;
        im = 2*tr*ti + b;

        if (sqrt(re*re+im*im) >= INF)
            return 0;
        //また、上のif文は以下と同値
        //if (re*re+im*im >= INF*INF)
        //  return 0;
    }
    return 1;
}
*/

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            bool f = not_inf(complex<double>(re, im));
            newpen(win, f?EGGX_BLACK:EGGX_WHITE);

            /*
                RE2X,IM2Yを呼び出し、複素平面内の点を
                ウィンドウの座標に変換して描いている。
            */
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
}

なお、ウェブ上に載せられているマンデルブロ集合の図は、たいてい、周囲が色付けされている。通常は、数列が無限大に発散するまでに計算された回数を用いて色付けする。上述のプログラムに色付けの機能を加えるためには、上に示した手順(3)において「{Zn}が発散するならば白」としている部分の処理を変えればよい。

Project Euler Problem 9

Problem 9

a, b, cは全て自然数で、a < b < cかつa + b + c = 1000であるから、
0 < a < 1000/3, a < b < (1000-a)/2, c = 1000 - (a+b)という条件の下で調べれば良い。

証明:
a + b + c = 1000より、c = 1000 - (a+b)となり、b < cに代入すると、
b < 1000 - (a+b)
<=> b < (1000-a)/2
よって、a < b < (1000-a)/2となる。
またこれより、
a < (1000-a)/2
<=> a < 1000/3
よって、0 < a < 1000/3となる。

Scheme

(use srfi-42)

(define n 1000)
(define (p009)
  (print (car (list-ec (: a (floor (/ n 3)))
                       (: b a (floor (/ (- n a) 2)))
                       (:let c (- n a b))
                (if (eq? (+ (* a a) (* b b)) (* c c)))
                (* a b c)))))

(p009)

C++

#include <cstdio>

int main()
{
    for (int a = 1; a < 1000/3; a++)
    for (int b = a; b < (1000-a)/2; b++)
    {
        int c = 1000-(a+b);
        if (a*a+b*b==c*c) {
            printf("%d\n", a*b*c);
            goto end;
        }
    }
end:
    return 0;
}