中間数(mediant)を使った、小数の既約分数表現

結城浩

2005年4月16日

Graham, Knuth, Patashnikの『コンピュータの数学』(p.116)を読んでいて、 何となくプログラミングしてみました。 スターン・ブロコット木の構成を用いて、 与えられた小数を表現する既約分数を見つけるというもの。

プログラム

use strict;
# use bignum;

package Fraction;
use overload '""' => \&as_string, '0+' => \&as_value;

my $DEBUG = 1;
my $ZERO = Fraction->new2(0, 1);
my $INFINITY = Fraction->new2(1, 0);

sub new2 {
    my ($class, $up, $down) = @_;
    return bless {
        up => $up,
        down => $down,
    }, $class;
}

sub new1 {
    my ($class, $target) = @_;
    my $left = $ZERO;
    my $right = $INFINITY;
    while (1) {
        my $mediant = $left->mediant($right);
        my $value = $mediant->as_value;
        print "$value $mediant\n" if ($DEBUG);
        if ($value < $target) {
            $left = $mediant;
        } elsif ($value > $target) {
            $right = $mediant;
        } else {
            return $mediant;
        }
    }
}

sub mediant {
    my ($self, $right) = @_;
    return Fraction->new2(
        $self->{up} + $right->{up},
        $self->{down} + $right->{down},
    );
}

sub as_value {
    my ($self) = @_;
    if ($self->{down} == 0) {
        die;
    } else {
        return $self->{up} / $self->{down};
    }
}

sub as_string {
    my ($self) = @_;
    return "$self->{up}/$self->{down}";
}

package main;

my $half = Fraction->new2(1, 2);
print "\$half = $half\n\n";

my $quarter = Fraction->new1(0.25);
print "\$quarter = $quarter\n\n";

my $sqrt2 = Fraction->new1(sqrt(2));
print "\$sqrt2 = $sqrt2\n\n";

my $pi = Fraction->new1(3.14159265358979);
print "\$pi = $pi\n\n";

実行結果

$half = 1/2

1 1/1
0.5 1/2
0.333333333333333 1/3
0.25 1/4
$quarter = 1/4

1 1/1
2 2/1
1.5 3/2
1.33333333333333 4/3
1.4 7/5
1.42857142857143 10/7
1.41666666666667 17/12
1.41176470588235 24/17
1.41379310344828 41/29
1.41463414634146 58/41
1.41428571428571 99/70
1.41414141414141 140/99
1.41420118343195 239/169
1.41422594142259 338/239
1.41421568627451 577/408
1.41421143847487 816/577
1.41421319796954 1393/985
1.41421392677674 1970/1393
1.41421362489487 3363/2378
1.41421349985132 4756/3363
1.41421355164605 8119/5741
1.41421357310014 11482/8119
1.41421356421356 19601/13860
1.41421356053263 27720/19601
1.41421356205732 47321/33461
1.41421356268887 66922/47321
1.41421356242727 114243/80782
1.41421356231892 161564/114243
1.4142135623638 275807/195025
1.41421356238239 390050/275807
1.41421356237469 665857/470832
1.4142135623715 941664/665857
1.41421356237282 1607521/1136689
1.41421356237337 2273378/1607521
1.41421356237314 3880899/2744210
1.41421356237305 5488420/3880899
1.41421356237309 9369319/6625109
1.4142135623731 13250218/9369319
1.4142135623731 22619537/15994428
1.41421356237309 31988856/22619537
1.41421356237309 54608393/38613965
1.4142135623731 77227930/54608393
1.4142135623731 131836323/93222358
$sqrt2 = 131836323/93222358

1 1/1
2 2/1
3 3/1
4 4/1
3.5 7/2
3.33333333333333 10/3
3.25 13/4
3.2 16/5
3.16666666666667 19/6
3.14285714285714 22/7
3.125 25/8
3.13333333333333 47/15
3.13636363636364 69/22
3.13793103448276 91/29
3.13888888888889 113/36
3.13953488372093 135/43
3.14 157/50
3.14035087719298 179/57
3.140625 201/64
3.14084507042254 223/71
3.14102564102564 245/78
3.14117647058824 267/85
3.14130434782609 289/92
3.14141414141414 311/99
3.14150943396226 333/106
3.14159292035398 355/113
3.14155251141552 688/219
3.14156626506024 1043/332
3.14157303370787 1398/445
3.1415770609319 1753/558
3.14157973174367 2108/671
3.14158163265306 2463/784
3.14158305462653 2818/897
3.14158415841584 3173/1010
3.14158504007124 3528/1123
3.1415857605178 3883/1236
3.14158636026686 4238/1349
3.14158686730506 4593/1462
3.1415873015873 4948/1575
3.14158767772512 5303/1688
3.14158800666296 5658/1801
3.14158829676071 6013/1914
3.14158855451406 6368/2027
3.14158878504673 6723/2140
3.14158899245451 7078/2253
3.14158918005072 7433/2366
3.14158935054457 7788/2479
3.14158950617284 8143/2592
3.14158964879852 8498/2705
3.14158977998581 8853/2818
3.14158990105766 9208/2931
3.1415900131406 9563/3044
3.14159011719987 9918/3157
3.14159021406728 10273/3270
3.14159030446349 10628/3383
3.14159038901602 10983/3496
3.14159046827376 11338/3609
3.14159054271897 11693/3722
3.14159061277705 12048/3835
3.14159067882472 12403/3948
3.14159074119675 12758/4061
3.14159080019166 13113/4174
3.14159085607651 13468/4287
3.14159090909091 13823/4400
3.14159095945048 14178/4513
3.14159100734976 14533/4626
3.14159105296476 14888/4739
3.14159109645507 15243/4852
3.14159113796576 15598/4965
3.14159117762899 15953/5078
3.1415912155654 16308/5191
3.14159125188537 16663/5304
3.14159128669005 17018/5417
3.14159132007233 17373/5530
3.14159135211767 17728/5643
3.1415913829048 18083/5756
3.14159141250639 18438/5869
3.14159144098964 18793/5982
3.14159146841674 19148/6095
3.14159149484536 19503/6208
3.14159152032906 19858/6321
3.14159154491763 20213/6434
3.1415915686574 20568/6547
3.14159159159159 20923/6660
3.14159161376052 21278/6773
3.14159163520186 21633/6886
3.14159165595085 21988/6999
3.14159167604049 22343/7112
3.14159169550173 22698/7225
3.14159171436359 23053/7338
3.14159173265333 23408/7451
3.14159175039662 23763/7564
3.14159176761756 24118/7677
3.1415917843389 24473/7790
3.14159180058206 24828/7903
3.14159181636727 25183/8016
3.14159183171362 25538/8129
3.14159184663917 25893/8242
3.14159186116098 26248/8355
3.14159187529523 26603/8468
3.14159188905722 26958/8581
3.14159190246147 27313/8694
3.14159191552174 27668/8807
3.14159192825112 28023/8920
3.14159194066202 28378/9033
3.14159195276624 28733/9146
3.14159196457501 29088/9259
3.14159197609902 29443/9372
3.14159198734844 29798/9485
3.14159199833299 30153/9598
3.14159200906189 30508/9711
3.14159201954397 30863/9824
3.14159202978766 31218/9937
3.141592039801 31573/10050
3.14159204959166 31928/10163
3.14159205916699 32283/10276
3.14159206853403 32638/10389
3.14159207769949 32993/10502
3.14159208666981 33348/10615
3.14159209545116 33703/10728
3.14159210404944 34058/10841
3.14159211247033 34413/10954
3.14159212071926 34768/11067
3.14159212880143 35123/11180
3.14159213672186 35478/11293
3.14159214448536 35833/11406
3.14159215209654 36188/11519
3.14159215955983 36543/11632
3.14159216687952 36898/11745
3.14159217405971 37253/11858
3.14159218110434 37608/11971
3.14159218801721 37963/12084
3.141592194802 38318/12197
3.14159220146223 38673/12310
3.14159220800129 39028/12423
3.14159221442246 39383/12536
3.14159222072891 39738/12649
3.14159222692368 40093/12762
3.14159223300971 40448/12875
3.14159223898984 40803/12988
3.1415922448668 41158/13101
3.14159225064326 41513/13214
3.14159225632175 41868/13327
3.14159226190476 42223/13440
3.14159226739467 42578/13553
3.14159227279379 42933/13666
3.14159227810436 43288/13779
3.14159228332853 43643/13892
3.1415922884684 43998/14005
3.141592293526 44353/14118
3.14159229850327 44708/14231
3.14159230340212 45063/14344
3.14159230822439 45418/14457
3.14159231297186 45773/14570
3.14159231764626 46128/14683
3.14159232224926 46483/14796
3.14159232678248 46838/14909
3.1415923312475 47193/15022
3.14159233564585 47548/15135
3.14159233997901 47903/15248
3.14159234424842 48258/15361
3.14159234845547 48613/15474
3.14159235260153 48968/15587
3.1415923566879 49323/15700
3.14159236071587 49678/15813
3.14159236468668 50033/15926
3.14159236860153 50388/16039
3.14159237246161 50743/16152
3.14159237626806 51098/16265
3.14159238002198 51453/16378
3.14159238372446 51808/16491
3.14159238737654 52163/16604
3.14159239097924 52518/16717
3.14159239453357 52873/16830
3.14159239804049 53228/16943
3.14159240150094 53583/17056
3.14159240491584 53938/17169
3.14159240828608 54293/17282
3.14159241161253 54648/17395
3.14159241489605 55003/17508
3.14159241813745 55358/17621
3.14159242133754 55713/17734
3.14159242449711 56068/17847
3.14159242761693 56423/17960
3.14159243069773 56778/18073
3.14159243374024 57133/18186
3.14159243674518 57488/18299
3.14159243971323 57843/18412
3.14159244264507 58198/18525
3.14159244554137 58553/18638
3.14159244840275 58908/18751
3.14159245122986 59263/18864
3.14159245402329 59618/18977
3.14159245678366 59973/19090
3.14159245951153 60328/19203
3.1415924622075 60683/19316
3.1415924648721 61038/19429
3.14159246750588 61393/19542
3.14159247010939 61748/19655
3.14159247268312 62103/19768
3.1415924752276 62458/19881
3.14159247774332 62813/19994
3.14159248023077 63168/20107
3.14159248269041 63523/20220
3.14159248512271 63878/20333
3.14159248752812 64233/20446
3.1415924899071 64588/20559
3.14159249226006 64943/20672
3.14159249458744 65298/20785
3.14159249688965 65653/20898
3.1415924991671 66008/21011
3.14159250142019 66363/21124
3.14159250364929 66718/21237
3.1415925058548 67073/21350
3.14159250803709 67428/21463
3.14159251019651 67783/21576
3.14159251233344 68138/21689
3.14159251444822 68493/21802
3.14159251654118 68848/21915
3.14159251861267 69203/22028
3.14159252066302 69558/22141
3.14159252269255 69913/22254
3.14159252470157 70268/22367
3.14159252669039 70623/22480
3.14159252865932 70978/22593
3.14159253060865 71333/22706
3.14159253253867 71688/22819
3.14159253444968 72043/22932
3.14159253634194 72398/23045
3.14159253821574 72753/23158
3.14159254007133 73108/23271
3.141592541909 73463/23384
3.14159254372899 73818/23497
3.14159254553155 74173/23610
3.14159254731695 74528/23723
3.14159254908542 74883/23836
3.1415925508372 75238/23949
3.14159255257252 75593/24062
3.14159255429162 75948/24175
3.14159255599473 76303/24288
3.14159255768206 76658/24401
3.14159255935384 77013/24514
3.14159256101027 77368/24627
3.14159256265158 77723/24740
3.14159256427795 78078/24853
3.14159256588961 78433/24966
3.14159256748674 78788/25079
3.14159256906955 79143/25192
3.14159257063821 79498/25305
3.14159257219293 79853/25418
3.14159257373389 80208/25531
3.14159257526127 80563/25644
3.14159257677525 80918/25757
3.141592578276 81273/25870
3.14159257976369 81628/25983
3.1415925812385 81983/26096
3.1415925827006 82338/26209
3.14159258415014 82693/26322
3.14159258558729 83048/26435
3.1415925870122 83403/26548
3.14159258842504 83758/26661
3.14159258982595 84113/26774
3.14159259121509 84468/26887
3.14159259259259 84823/27000
3.14159259395862 85178/27113
3.1415925953133 85533/27226
3.14159259665679 85888/27339
3.14159259798922 86243/27452
3.14159259931072 86598/27565
3.14159260062143 86953/27678
3.14159260192149 87308/27791
3.14159260321101 87663/27904
3.14159260449013 88018/28017
3.14159260575898 88373/28130
3.14159260701767 88728/28243
3.14159260826633 89083/28356
3.14159260950508 89438/28469
3.14159261073403 89793/28582
3.1415926119533 90148/28695
3.14159261316301 90503/28808
3.14159261436327 90858/28921
3.14159261555418 91213/29034
3.14159261673586 91568/29147
3.14159261790841 91923/29260
3.14159261907194 92278/29373
3.14159262022655 92633/29486
3.14159262137234 92988/29599
3.14159262250942 93343/29712
3.14159262363789 93698/29825
3.14159262475783 94053/29938
3.14159262586936 94408/30051
3.14159262697255 94763/30164
3.14159262806751 95118/30277
3.14159262915433 95473/30390
3.14159263023309 95828/30503
3.14159263130389 96183/30616
3.14159263236682 96538/30729
3.14159263342196 96893/30842
3.14159263446939 97248/30955
3.14159263550921 97603/31068
3.14159263654148 97958/31181
3.14159263756631 98313/31294
3.14159263858376 98668/31407
3.14159263959391 99023/31520
3.14159264059685 99378/31633
3.14159264159264 99733/31746
3.14159264258137 100088/31859
3.14159264356312 100443/31972
3.14159264453795 100798/32085
3.14159264550593 101153/32198
3.14159264646715 101508/32311
3.14159264742166 101863/32424
3.14159264836955 102218/32537
3.14159264931087 102573/32650
3.1415926502457 102928/32763
3.14159265117411 103283/32876
3.14159265209615 103638/32989
3.1415926530119 103993/33102
3.14159265392142 104348/33215
3.14159265346744 208341/66317
3.14159265361894 312689/99532
3.14159265355836 521030/165849
3.14159265358108 833719/265381
3.1415926535914 1146408/364913
3.14159265358706 1980127/630294
3.14159265358865 3126535/995207
3.14159265358939 4272943/1360120
3.14159265358982 5419351/1725033
3.14159265358963 9692294/3085153
3.1415926535897 15111645/4810186
3.14159265358973 20530996/6535219
3.14159265358975 25950347/8260252
3.14159265358976 31369698/9985285
3.14159265358977 36789049/11710318
3.14159265358977 42208400/13435351
3.14159265358978 47627751/15160384
3.14159265358978 53047102/16885417
3.14159265358978 58466453/18610450
3.14159265358979 63885804/20335483
3.14159265358979 69305155/22060516
3.14159265358979 74724506/23785549
3.14159265358979 144029661/45846065
$pi = 144029661/45846065