factをやろう
１．再帰なしに階乗計算できる？
このワークシートはMath by Codeの一部です。
＜factorial＞
フィボナッチ数列の一般項は、意外なことに、
黄金比にかかわる無理数を使った式になる。
くわしい計算はしませんが、
漸化式から特性方程式を作り一般項を作ると無理数が残るんだ。
それに対してNの階乗fact(N)は１からNまでの積だから、一般項は単純だ。
だから、再帰関数でも表せるけど、forで十分かけるね。
#再帰を使うならキャッシュを使おう。
#==================
from functools import cache
@cache
def factorial(n):
return n * factorial(n-1) if n else 1
factorial(100)
#再帰なしなら、どんどんかけ算して上書きしよう。
#==================
def fact(n):
res=1
for i in range(1,n+1):
res *=i
return res
fact(100)
#==================
[OUT]
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
階乗はIterationListかProductか？
geogbraでは
fibを再帰を使わずに素早く求めることができた。そのときの手段がIterationListだった。
同じようにIterationListやIterationでfactも再帰を使わず求めることができる。
geogebraにはProductというコマンドがあったね。
1から100までの数列をlst=Sequence(100)で作っておき、
それの積をProduct(lst)するとfactorial(100)が計算できる。
でも、有効数字には課題が残った。
２．再帰と反復
pythonにはmathパッケージの関数一覧をリスト表示すると、factorialという関数がすでにありました。
[IN]
#===========
import math
print(dir(math))
#============
[OUT]
['__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'cbrt', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'exp2', 'expm1', 'fabs', 'factorial', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'lcm', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'nextafter', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'sumprod', 'tan', 'tanh', 'tau', 'trunc', 'ulp']
[IN]
#===========
from math import factorial as fact
fact(100)
#============
factorial関数だけを factという別名をつけて、簡単に使えます。
パッケージがあるときは、何でも自力で作るのではなく、それに乗っかるというときもあってよいでしょう。
算数、数学と同じようにコード開発でも、
知識・技術に乗っかって秒殺する快感とかエレガントさというのもあるでしょう。
しかし、それで終わってしまうと、思考が深まりません。
フィボナッチ数列よりも扱いやすいということで、階乗計算を使って、
くり返し（反復iteration）と自分を呼び出す（再帰recurrsion）の関係をさぐってみましょう。
#[IN]C++
#=====================
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i) {
result *= i;
}
return result;
}
C++でforで反復するとこんな風になるでしょう。
これはPythonでもjuliaでも同じようなものです。
＜productの中身＞
haskellでは
#=================
fact n = product [1..n]
#=================
のように、product関数に１からｎのリストをわたすだけで終了です。
ではproduct関数ってどうなっているんでしょう。
リストが空なら１を返し、先頭に残りのproductをかければいいですね。
だから、再帰関数を使うと、
product [] =1
product (n: ns) = n * product ns
と定義できます。
数であれば何でもproductできるという一般化をしましょう。
ghciに尋ねると
ghci>:info product
type Foldable :: (* -> *) -> Constraint
class Foldable t where
...
product :: Num a => t a -> a
-- Defined in ‘Data.Foldable’
ghci> :t product
product :: (Foldable t, Num a) => t a -> a
と答えてきます。
tが畳み込みのできるクラス、aが数のクラスで、数リストt aから数aを返す。
だから、次のようにも定義できるのです。
product = foldl (*) 1
＜foldlを使おう＞
haskellでは、foldlの中はどうなっているのでしょうか？
ghci> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
tが畳み込みのできるクラス、（）内は２項演算と数リストt aがあれば、
数aのうち演算やリストの左側をbとして、畳み込みを続ける。
という型の説明です。これを再帰でかくと次のようになります。
foldl f v [ ] = v
foldl f v (x: xs) = foldl f (f v x ) xs
vを初期値として、演算をｆとする。
リストが[ ]になったらｖを返す。（ベースケース）
リストの左をｘ、残りをxsとしたら、左ｘにｆをしたものをｖとして
残りxsをリストとする。 （再帰ケース）
foldlを使うと、２項演算をリストにくり返し適用するものなら、
簡単に関数定義できますね。
（例）
関数そのものの定義だから、引数としてのリストは省けます。
sum = foldl (+) 0
product = foldl (*) 1
or = foldl (∨) False
and = foldl (∧) True
legth = foldl (\n _ -> n+1) 0
質問：ほかの言語でのfoldlの活用はどうでしょうか。
haskellとはちがって、引数はかっこで閉じる必要があるので、見かけは代わります。
#[IN] julia
#=======================
function sum(lst)
return foldl(+,lst)
end
function product(lst)
return foldl(*,lst)
end
lst=[1,2,3,4,5]
println("lst=$lst, sum(lst)=$(sum(lst)),product(lst)=$(product(lst))")
#=====================================================
[OUT]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
ちゃんと動きました。
次のようにjuliaで数学の関数定義風にかいても動きました。
#[IN] julia
#=======================
Sum(lst) = foldl(+,lst)
Product(lst)= foldl(*,lst)
lst=[1,2,3,4,5]
println("lst=$lst, Sum(lst)=$(Sum(lst)),Product(lst)=$(Product(lst))")
#=====================================================
[OUT]
lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
pythonにはfoldlという名前の関数はないが、実態がfoldlと同じreduce関数がある。
ただし、パッケージfunctoolsにあるからインポートする。別名foldlをつけてみた。
残念ながら、reduceの引数は（演算、リスト）ではなく（関数、リスト）だ。
だから、+,*のまま渡すのではなく、関数にして渡す。
わざわざそのために、関数を外に作るのも手間だから、中にラムダをつかった無名関数
にしている。
pythonは、ラムダ式の発想を忠実に再現しているが、
関数の関数を作ったりしようとすると、簡単な内容なのに難解に見えてしまうのが難点だ。
#[IN] python
#=======================
from functools import reduce as foldl
Sum =lambda lst: foldl(lambda x,y:x+y,lst)
Product = lambda lst: foldl(lambda x,y:x*y,lst)
lst=[1,2,3,4,5]
print(f"lst={lst}, Sum(lst)={Sum(lst)},Product(lst)={Product(lst)}")
lst=[1, 2, 3, 4, 5], Sum(lst)=15,Product(lst)=120
#=====================================================
[[OUT]
lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
geogebraの数式、数式処理(CAS)には、関数を自作する機能はあるが、fold,reduceはない。
Iteration,IterationListはあくまでも初期値に対する反復計算なので、初期値以外を途中から渡すことはできない。漸化式の発想でしょうね。
しかし、sumも、productもすでにあるので、それを使えばよいでしょう。というところか。
また、数式処理(CAS)を使うと、nPr,nCrがあるので、わざわざfactorialを作るところからやらなくても、
すぐに順列、組み合わせがすぐに使えるという実用性を重視している感があるね。
質問：rustでfactorialを計算するにはどうしますか。
もちろんC++のように反復計算できます。
多桁整数に対応できるように、
Cargo.tomlの[dependencies]に
num-bigint = "0.4"
を記入しておきます。
（今後0.5以上のバージョンになるかも）
１を多桁整数として扱うために、use std::str::FromStr;
も宣言しておきましょう。
階乗計算を順次表示するためにはfact関数の中にprintln!()をかきます。
最後の結果だけ表示するにはmain関数の中でprintln!()をかけばいいね。
ただ、rustの場合は変数を盗んではいけないので、&をつけて借用して
表示します。
基本型のデータは所有権は気にならないですが、構造体とかBigIntなど
メモリーを定型スタックするのではなく、ヒープメモリーの領域を
使う場合は、所有権を意識して代入や表示でも借用、参照にしましょう。
ansのように、入れ物として使ったけど、あと使わない変数は前に‗をつけます。
また、数の変換操作などのあとの.unwrap()は成功したらラップをはがす定型句です。
これで、その結果をエラーなしに代入できます。
また、for文のi は多桁整数ではないから、これを変換してからかけましょう。
[IN]rust
use num_bigint::{BigInt, ToBigInt};
use std::str::FromStr;
fn main() {
let idx = 100;
let _ans = fact(idx);
}
fn fact(num:i64) -> BigInt {
let mut result = BigInt::from_str("1").unwrap();
for i in 1..=num {
result = result * i.to_bigint().unwrap();
println!("{}番目：{}",&i, &result);
}
result
}
[OUT]
1番目：1
2番目：2
3番目：6
4番目：24
5番目：120
6番目：720
7番目：5040
8番目：40320
9番目：362880
10番目：3628800
11番目：39916800
12番目：479001600
13番目：6227020800
14番目：87178291200
15番目：1307674368000
16番目：20922789888000
17番目：355687428096000
18番目：6402373705728000
19番目：121645100408832000
20番目：2432902008176640000
21番目：51090942171709440000
22番目：1124000727777607680000
23番目：25852016738884976640000
24番目：620448401733239439360000
25番目：15511210043330985984000000
26番目：403291461126605635584000000
27番目：10888869450418352160768000000
28番目：304888344611713860501504000000
29番目：8841761993739701954543616000000
30番目：265252859812191058636308480000000
31番目：8222838654177922817725562880000000
32番目：263130836933693530167218012160000000
33番目：8683317618811886495518194401280000000
34番目：295232799039604140847618609643520000000
35番目：10333147966386144929666651337523200000000
36番目：371993326789901217467999448150835200000000
37番目：13763753091226345046315979581580902400000000
38番目：523022617466601111760007224100074291200000000
39番目：20397882081197443358640281739902897356800000000
40番目：815915283247897734345611269596115894272000000000
41番目：33452526613163807108170062053440751665152000000000
42番目：1405006117752879898543142606244511569936384000000000
43番目：60415263063373835637355132068513997507264512000000000
44番目：2658271574788448768043625811014615890319638528000000000
45番目：119622220865480194561963161495657715064383733760000000000
46番目：5502622159812088949850305428800254892961651752960000000000
47番目：258623241511168180642964355153611979969197632389120000000000
48番目：12413915592536072670862289047373375038521486354677760000000000
49番目：608281864034267560872252163321295376887552831379210240000000000
50番目：30414093201713378043612608166064768844377641568960512000000000000
51番目：1551118753287382280224243016469303211063259720016986112000000000000
52番目：80658175170943878571660636856403766975289505440883277824000000000000
53番目：4274883284060025564298013753389399649690343788366813724672000000000000
54番目：230843697339241380472092742683027581083278564571807941132288000000000000
55番目：12696403353658275925965100847566516959580321051449436762275840000000000000
56番目：710998587804863451854045647463724949736497978881168458687447040000000000000
57番目：40526919504877216755680601905432322134980384796226602145184481280000000000000
58番目：2350561331282878571829474910515074683828862318181142924420699914240000000000000
59番目：138683118545689835737939019720389406345902876772687432540821294940160000000000000
60番目：8320987112741390144276341183223364380754172606361245952449277696409600000000000000
61番目：507580213877224798800856812176625227226004528988036003099405939480985600000000000000
62番目：31469973260387937525653122354950764088012280797258232192163168247821107200000000000000
63番目：1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000
64番目：126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000
65番目：8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000
66番目：544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000
67番目：36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000
68番目：2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000
69番目：171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000
70番目：11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000
71番目：850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000
72番目：61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000
73番目：4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000
74番目：330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000
75番目：24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000
76番目：1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000
77番目：145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000
78番目：11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000
79番目：894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000
80番目：71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
81番目：5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000
82番目：475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000
83番目：39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000
84番目：3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000
85番目：281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000
86番目：24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000
87番目：2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000
88番目：185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000
89番目：16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000
90番目：1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
91番目：135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000
92番目：12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000
93番目：1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000
94番目：108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000
95番目：10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000
96番目：991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000
97番目：96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000
98番目：9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000
99番目：933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
100番目：93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
質問：rustでfactorialを計算するのにfoldなど使ってできますか。
もちろんhaskellのようにできます。
rustのイテレータクレートにはmap, filterの他にfold,rfold,reduceなどが
あります。これに乗っかる手もありますね。
多桁整数に対応できるように、
Cargo.tomlの[depetndencies]に
num-bigint = "0.4"
を記入しておきます。
対象から要素へという順番で、詳細化していきましょう。
階乗計算の基点になる１を多桁にしておきます。
let one = BigInt::from_str("1").unwrap();
n!のnを100くらいにすると、
let n = 100;
ここからが本番です。
レンジ(1..=n)の要素を多桁整数リストに変換しましょう。
(1..=n).map(|x| x.to_bigint().unwrap())
そのリストから取り出した要素xと累積(accumlator)をaccumとして、
対象.Iter().fold(|対象たち|対象たちへの操作）という順に描きます。
.fold(one, |accum, x| accum * x);
その結果をresultに入れて表示します。
use num_bigint::{BigInt, ToBigInt};
use std::str::FromStr;
fn main() {
let n = 100;
let one = BigInt::from_str("1").unwrap();
let result = (1..=n)
.map(|x| x.to_bigint().unwrap())
.fold(one, |accum, x| accum * x);
println!("{}", result);
}
質問：もっと手軽にrustでイテレーション関数を使えませんか。
使えます。多桁整数でないのなら、範囲のあとに.sum(), .product()をつけるだけで、
たし算やかけ算を繰り返した結果を返します。
だから、次のようにして計算ができますよ。
[IN]rust
fn main() {
let n:i64 = 20;
let sum20:i64 = (1..n).sum();
let fact20:i64 = (1..n).product();
println!("1から20までの和＝{}", sum20);
println!("1から20までの和＝{}", fact20);
}
[OUT]
1から20までの和＝190
1から20までの和＝121645100408832000