Amazon.co.jp ウィジェット
スポンサードリンク

2010年02月06日

nの階乗計算(nは任意)

n の階乗を求めよ(nは任意)

このクイズを見たとき、「ワンライナーで書けるじゃん」と思いました。


>>> import operator
>>> factorial = lambda n: n==0 and 1 or reduce(operator.mul, xrange(1, n+1))
>>> factorial(10)
3628800

でも、階乗は結果が指数関数的に増大します。 int をオーバーフローしたらどうなるのでしょうか。


>>> factorial(100)
933262154439441526816992388562667004907159682643
816214685929638952175999932299156089414639761565
182862536979208272237582511852109168640000000000
00000000000000L

maxint を超えたら自動的に long になるのは良いとしても、 64 bit 長整数型の最大値も 9223372036854775807 のはず。とっくに超えているのにエラーが発生せず、どうやら正しい結果が出ています。上記の値は何型で保存され、オブジェクトサイズはどのくらいなのでしょうか。調べてみます。


>>> for i in xrange(50):
...   r = factorial(i)
...   print i, sys.getsizeof(r), type(r), r
...
0 12 <type 'int'> 1
1 12 <type 'int'> 1
2 12 <type 'int'> 2
3 12 <type 'int'> 6
4 12 <type 'int'> 24
5 12 <type 'int'> 120
6 12 <type 'int'> 720
7 12 <type 'int'> 5040
8 12 <type 'int'> 40320
9 12 <type 'int'> 362880
10 12 <type 'int'> 3628800
11 12 <type 'int'> 39916800
12 12 <type 'int'> 479001600
13 20 <type 'long'> 6227020800
14 20 <type 'long'> 87178291200
15 20 <type 'long'> 1307674368000
16 20 <type 'long'> 20922789888000
17 22 <type 'long'> 355687428096000
18 22 <type 'long'> 6402373705728000
19 22 <type 'long'> 121645100408832000
20 24 <type 'long'> 2432902008176640000
21 24 <type 'long'> 51090942171709440000
22 24 <type 'long'> 1124000727777607680000
23 24 <type 'long'> 25852016738884976640000
24 26 <type 'long'> 620448401733239439360000
25 26 <type 'long'> 15511210043330985984000000
26 26 <type 'long'> 403291461126605635584000000
27 28 <type 'long'> 10888869450418352160768000000
28 28 <type 'long'> 304888344611713860501504000000
29 28 <type 'long'> 8841761993739701954543616000000
30 30 <type 'long'> 265252859812191058636308480000000
31 30 <type 'long'> 8222838654177922817725562880000000
32 30 <type 'long'> 263130836933693530167218012160000000
33 32 <type 'long'> 8683317618811886495518194401280000000
34 32 <type 'long'> 295232799039604140847618609643520000000
35 32 <type 'long'> 10333147966386144929666651337523200000000
36 34 <type 'long'> 371993326789901217467999448150835200000000
37 34 <type 'long'> 13763753091226345046315979581580902400000000
38 34 <type 'long'> 523022617466601111760007224100074291200000000
39 36 <type 'long'> 20397882081197443358640281739902897356800000000
40 36 <type 'long'> 815915283247897734345611269596115894272000000000
41 36 <type 'long'> 33452526613163807108170062053440751665152000000000
42 38 <type 'long'> 1405006117752879898543142606244511569936384000000000
43 38 <type 'long'> 60415263063373835637355132068513997507264512000000000
44 40 <type 'long'> 2658271574788448768043625811014615890319638528000000000
45 40 <type 'long'> 119622220865480194561963161495657715064383733760000000000
46 40 <type 'long'> 5502622159812088949850305428800254892961651752960000000000
47 42 <type 'long'> 258623241511168180642964355153611979969197632389120000000000
48 42 <type 'long'> 12413915592536072670862289047373375038521486354677760000000000
49 42 <type 'long'> 608281864034267560872252163321295376887552831379210240000000000

おお、long 型でありながらサイズが少しずつ増えている!

Python マニュアルを見ると以下のように書かれています。

Plain integers (also just called integers) are implemented using long in C, which gives them at least 32 bits of precision (sys.maxint is always set to the maximum plain integer value for the current platform, the minimum value is -sys.maxint - 1). Long integers have unlimited precision. Floating point numbers are implemented using double in C. All bets on their precision are off unless you happen to know the machine you are working with.

"Long integers have unlimited precision" だなんて素晴らしい気遣い。いくらでも大きな値を扱えるんですね。結局、はじめに示した factorial 関数はそのままで良いようです。

posted by junya at 08:26 | Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。