fのintのオーバーフロー＃

Question

私はいくつかの宿題に取り組んでおり、F＃で組み合わせ関数を作成することになっています。私は階乗関数をダウンさせましたが、階乗を使用するために大きな数値を取得すると、あふれているようです。 （20としましょう）int64やfloatを使うことができますが、それはコードのすべての入力を変更することになります。どのデータ型を使用する必要がありますか？

let rec Fact (a:int)= 
    if (a = 0) then 1 else a*Fact(a-1);; 

let combo (n:int) (k:int)= 
    if (n = 0) then 0 else (Fact n)/((Fact k)*(Fact (n-k)));; 

今のコードでは、コンボ20 5 ;;それは私に2147を与える。それは明らかに間違った答えである。私は階乗関数を見ました。私がそこに20を置くと、それは私に大きな負の数を与えました。どんな助けでも大歓迎です。前もって感謝します。

Answer 1

まず、驚きを避けたい場合は、ファイルの先頭にCheckedモジュールを開くことができます。彼らはオーバーフローのチェックを行うように、これは、数値演算子を再定義します - あなたは、予期しない数ではなく、例外を取得します：

open Microsoft.FSharp.Core.Operators.Checked 

フョードルはコメントで指摘するように、あなたはint、あなたに20の階乗をフィットすることはできませんint64が必要です。しかし、あなたのcombo関数は、intに収まるように、combo 20 5の結果を小さくする除算を実行します。

：あなたは除算を実行した後 intに戻し、その後 Factを呼び出す前に int64に変換する必要があるとよ -

1つのオプションは、int64を使用するようにFactを変更するが、取り、整数を返す関数としてcomboを維持することです

let rec Fact (a:int64) = 
    if (a = 0L) then 1L else a * Fact(a-1L) 

let combo (n:int) (k:int) = 
    if (n = 0) then 0 else int (Fact (int64 n)/(Fact (int64 k) * Fact (int64 (n-k)))) 

combo 20 5に電話すると、結果として15504が返されます。

EDIT：他の回答で@pswgで述べたように、int64も非常に限られているので、あなたが大きな階乗のためBigIntegerが必要になります。ただし、同じ方法がBigIntegerで動作するはずです。 comboは、BigIntegerからintに戻ってintを返す関数として保持することができます。

Answer 2

32ビット整数（int）で単純に行うことはできません。 64ビットの整数は20!まで到達しますが、21!で失敗します。数字はあまりにも大きくなり過ぎます。それ以上に進むには、System.Numerics.BigInteger（F＃でbigintと略記）を使用する必要があります。

パラメータは、おそらく合理的であるとintとして滞在することができますが、bigintを返却する必要があります。

let rec Fact (n : int) = 
    if n = 0 then bigint.One else (bigint n) * Fact (n - 1) 

それとももう少し慣用すべき：

let rec Fact = function | 0 -> bigint.One | n -> (bigint n) * Fact (n - 1) 

そして今、中あなたのCombo関数では、これらの数値を内部的にすべての数式に使用する必要があります（ありがたいことに整数除算が必要です）。

let Combo (n : int) (k : int) = 
    if n = 0 then bigint.Zero else (Fact n)/((Fact k) * (Fact (n - k))) 

あなた本当にがComboリターンintを作りたいと思った場合、あなたはここでその変換を行うことができます。

let Combo (n : int) (k : int) = 
    if n = 0 then 0 else (Fact n)/((Fact k) * (Fact (n - k))) |> int 

例：

Combo 20 5 // --> 15504 
Combo 99 5 // --> 71523144 (would break if you used int64) 

編集：あなたを再考することをComboの実装では、いくつかのbを得ることができますこのうちigのパフォーマンスが改善されました。この実装の基礎のためのthis question on Math.SEを参照してください：

let ComboFast (n : int) (k : int) = 
    let rec Combo_r (n : int) = function 
     | 0 -> bigint.One 
     | k -> (bigint n) * (Combo_r (n - 1) (k - 1))/(bigint k) 
    Combo_r n (if (2 * k) > n then n - k else k) 

迅速なベンチマークは、上記Factベースのバージョンよりも大幅に速くするためにこれを示した：！

Function    Avg. Time (ms) 
Combo 99 5   30.12570 
ComboFast 99 5   0.72364