11

私は現在F#を試しています。インターネットで見つけた記事は役に立ちますが、C# プログラマーとして、自分のソリューションが役立つと思っていたのに、役に立たなかった、または部分的にしか役に立たなかったという状況に遭遇することがあります。

したがって、F# (およびおそらくコンパイラのしくみ) に関する知識が不足しているため、ときどき完全にびっくりすることがあります。

たとえば、完全数を決定する C# プログラムを作成しました。完全数はメルセンヌ素数 2p−1(2p−1) (2p-1 は素数、p はべき乗) から形成できるというユークリッド証明の既知の形式を使用します。

F# のヘルプでは、累乗の計算に '**' を使用できますが、浮動小数点を使用すると記載されているため、ビットシフト演算子 (<<<) を使用して単純な関数を作成しようとしました (このコードを編集したことに注意してください必要性を指摘):

 let PowBitShift (y:int32) = 1 <<< y;;

ただし、テストを実行してパフォーマンスの改善を探すときは、再帰とパターン マッチャーを使用して電力を計算する Miranda (関数型プログラミング言語でもあります) を使用したことを覚えている形式も試しました。主な利点は、変数yを 64 ビット整数として使用できることです。これは、標準のビットシフト演算子では不可能です。

    let rec Pow (x : int64) (y : int64) = 
    match y with
        | 0L -> 1L
        | y -> x * Pow x (y - 1L);;

この関数は実際には高速であることがわかりましたが、その理由は (まだ) 理解できません。おそらくそれはあまり知的な質問ではありませんが、私はまだ興味があります.

2 番目の問題は、完全数を計算するときに、9 番目の完全数 (31 のべき乗から形成される) を見つけた後に、int64 が交差する大きな数を表示できないという事実に遭遇することです。BigInteger オブジェクト (または bigint 型) を使用できるかどうかを調べようとしていますが、ここでは F# に関する私の知識が少し妨げになっています。両方の引数を bigint として受け入れる powerfunction を作成することは可能ですか?

私は現在これを持っています：

let rec PowBigInt (x : bigint) (y : bigint) = 
    match y with
        | bigint.Zero -> 1I
        | y -> x * Pow x (y - 1I);;

しかし、bigint.Zero が定義されていないというエラーがスローされます。だから私もそこで何か間違ったことをしています。0I は、次のエラーが発生するため、置換として受け入れられません。

Non-primitive numeric literal constants cannot be used in pattern matches because they    
can be mapped to multiple different types through the use of a NumericLiteral module.  
Consider using replacing with a variable, and use 'when <variable> = <constant>' at the 
end of the match clause.

ただし、パターン マッチャーは「when」ステートメントを使用できません。これを行う別の解決策はありますか？

前もって感謝し、私の長い投稿を許してください。私は自分の「挑戦」をできるだけ明確に表現しようとしているだけです。

4

4 に答える 4

8

なぜあなたが または である必要があるのか​​ 理解できませんでしyた。このリンクによると、既知の最大のメルセンヌ数はの範囲内にあるです。int64bigintp = 43112609pint

y整数として持つと、pown : ^T -> int -> ^T代わりに標準演算子を使用できます。理由は次のとおりです。

let Pow (x : int64) y = pown x y
let PowBigInt (x: bigint) y = pown x y

pattern matching の質問に関して、エラー メッセージは、ガードbigintを介してパターン マッチングを使用できることを明確に示しています。when

let rec PowBigInt x y = 
    match y with
    | _ when y = 0I -> 1I
    | _ -> x * PowBigInt x (y - 1I)
于 2011-12-02T13:21:02.587 に答える
5

Pow関数を作成する必要はありません。（**）演算子には、bigint->int->bigintのオーバーロードがあります。2番目のパラメーターのみが整数である必要がありますが、それがあなたの場合の問題ではないと思います。ちょうど試して

bigint 10 ** 32 ;;

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}
于 2011-12-02T14:04:10.163 に答える
5

定義する最も簡単な方法は、パターン マッチングの代わりにPowBigInt使用することだと思います。if

let rec PowBigInt (x : bigint) (y : bigint) =  
  if y = 0I then 1I   
  else x * PowBigInt x (y - 1I)

問題はbigint.Zero、値を返す静的プロパティであることですが、パターンには (定数) リテラルまたは F# アクティブ パターンしか含めることができません。プロパティ (またはその他の) 呼び出しを直接含めることはできません。whereただし、引き続き必要な場合は、句に追加の制約を記述することができますmatch。

let rec PowBigInt (x : bigint) (y : bigint) =  
  match y with 
  | y when y = bigint.Zero -> 1I 
  | y -> x * PowBigInt x (y - 1I)

補足として、おそらく末尾再帰を使用して関数をより効率的にすることができます (関数が最後に再帰呼び出しを行う場合、より効率的にコンパイルできるという考えです):

let PowBigInt (x : bigint) (y : bigint) =   
  // Recursive helper function that stores the result calculated so far
  // in 'acc' and recursively loops until 'y = 0I'
  let rec PowBigIntHelper (y : bigint) (acc : bigint) =
    if y = 0I then acc 
    else PowBigIntHelper (y - 1I) (x * acc)
  // Start with the given value of 'y' and '1I' as the result so far
  PowBigIntHelper y 1I

機能に関してPowBitShift- なぜ遅いのかはわかりませんが、必要なことは間違いなく実行されません。累乗を実装するためにビット シフトを使用するのは、基数が 2 の場合にのみ機能します。

于 2011-12-02T13:03:30.020 に答える
3

(*)別のオプションは、関数をインライン化して、すべての数値型 (必要な演算子をサポートするもの: 、(-)、get_One、および)で機能するようにすることですget_Zero。

let rec inline PowBigInt (x:^a) (y:^a) : ^a =  
  let zero = LanguagePrimitives.GenericZero 
  let one = LanguagePrimitives.GenericOne
  if y = zero then one
  else x * PowBigInt x (y - one) 

let x = PowBigInt 10 32     //int
let y = PowBigInt 10I 32I   //bigint
let z = PowBigInt 10.0 32.0 //float

Tomasが提案したように、おそらく末尾再帰にすることをお勧めします。

于 2011-12-02T15:24:32.990 に答える