結城浩
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