F # Power-Probleme, bei denen beide Argumente als Bigints akzeptiert werden

Question

Ich experimentiere gerade mit F #. Die Artikel im Internet sind hilfreich, aber als C # -Programmierer stoße ich manchmal auf Situationen, in denen ich dachte, meine Lösung würde helfen, aber es hat nicht oder nur teilweise geholfen.

Meine mangelnde Kenntnis von F # (und höchstwahrscheinlich der Funktionsweise des Compilers) ist wahrscheinlich der Grund, warum ich manchmal total verblüfft bin.

Zum Beispiel habe ich ein C # -Programm geschrieben, um perfekte Zahlen zu bestimmen. Es verwendet die bekannte Form des Euklid-Beweises, dass eine perfekte Zahl aus einem Mersenne-Prim 2p-1 (2p-1) gebildet werden kann (wobei 2p-1 ein Prim ist und p als Potenz von bezeichnet wird).

Da die Hilfe von F # besagt, dass '**' zur Berechnung einer Potenz verwendet werden kann, aber Gleitkommazahlen verwendet, habe ich versucht, eine einfache Funktion mit einem Bitshift-Operator (<<<) zu erstellen (beachten Sie, dass ich bearbeitet habe dieser Code, um auf die Notwendigkeit hinzuweisen):

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

Als ich jedoch einen Test durchführte und nach Leistungsverbesserungen suchte, versuchte ich auch ein Formular, an das ich mich erinnere, als ich Miranda (auch eine funktionale Programmiersprache) verwendete, das Rekursion und einen Mustervergleicher verwendet, um die Leistung zu berechnen. Der Hauptvorteil ist, dass ich die Variable y als 64-Bit-Ganzzahl verwenden kann, was mit dem Standard-Bitverschiebungsoperator nicht möglich ist.

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

Es stellt sich heraus, dass diese Funktion tatsächlich schneller ist, aber ich kann (noch) den Grund dafür nicht verstehen. Vielleicht ist es eine weniger intellektuelle Frage, aber ich bin immer noch neugierig.

Die zweite Frage wäre dann, dass Sie bei der Berechnung perfekter Zahlen auf die Tatsache stoßen, dass der int64 die großen Zahlen, die sich kreuzen, nicht anzeigen kann, nachdem Sie die 9. perfekte Zahl gefunden haben (die aus der Potenz von 31 gebildet wird). Ich versuche herauszufinden, ob Sie dann das BigInteger-Objekt (oder den Bigint-Typ) verwenden können, aber hier blockiert mich mein Wissen über F # ein wenig. Ist es möglich, eine Potenzfunktion zu erstellen, die beide Argumente als Bigint akzeptiert?

Ich habe derzeit Folgendes:

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

Es wird jedoch ein Fehler ausgegeben, dass bigint.Zero nicht definiert ist. Also mache ich auch dort etwas falsch. 0Ich werde nicht als Ersatz akzeptiert, da dieser Fehler auftritt:

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.    

Ein Pattern Matcher kann jedoch keine 'when'-Anweisung verwenden. Gibt es eine andere Lösung, um dies zu tun?

Vielen Dank im Voraus und bitte verzeihen Sie meinen langen Beitrag. Ich versuche nur, meine "Herausforderungen" so klar wie möglich auszudrücken.

Answer 1

Ich habe nicht verstanden, warum Sie y benötigen, um ein int64 oder ein bigint zu sein.Laut diesem Link ist die größte bekannte Mersenne-Nummer die mit p = 43112609, in der sich tatsächlich p befindetden Bereich des int.

Wenn Sie y als Ganzzahl haben, können Sie stattdessen den Standardoperator pown : ^T -> int -> ^T verwenden, weil:

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

In Bezug auf Ihre Frage zum Mustervergleich von bigint zeigt die Fehlermeldung ganz klar an, dass Sie den Mustervergleich über when-Schutzvorrichtungen verwenden können:

let rec PowBigInt x y = 
    match y with
    | _ when y = 0I -> 1I
    | _ -> x * PowBigInt x (y - 1I)

Answer 2

Ich denke, der einfachste Weg, PowBigInt zu definieren, besteht darin, if anstelle des Mustervergleichs zu verwenden:

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

Das Problem ist, dass bigint.Zero eine statische Eigenschaft ist, die den Wert zurückgibt, Muster jedoch nur (konstante) Literale oder aktive F # -Muster enthalten können.Sie können keine Eigenschaftsaufrufe (oder andere) aufrufen.Sie können jedoch zusätzliche Einschränkungen in die where-Klausel schreiben, wenn Sie weiterhin match bevorzugen:

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

Als Randnotiz können Sie die Funktion wahrscheinlich mithilfe von Schwanzrekursion effizienter gestalten (die Idee ist, dass eine Funktion, die als letztes rekursiv aufgerufen wird, besser kompiliert werden kanneffizient):

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

In Bezug auf die PowBitShift-Funktion - Ich bin mir nicht sicher, warum sie langsamer ist, aber sie macht definitiv nicht das, was Sie brauchen.Die Verwendung der Bitverschiebung zum Implementieren der Leistung funktioniert nur, wenn die Basis 2 ist.

Answer 3

Sie müssen die Pow-Funktion nicht erstellen. Der Operator (**) hat eine Überladung für bigint -> int -> bigint. Nur der zweite Parameter sollte eine Ganzzahl sein, aber ich denke nicht, dass dies ein Problem für Ihren Fall ist. Versuchen Sie es einfach

bigint 10 ** 32 ;;

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}

Answer 4

Eine weitere Option besteht darin, Ihre Funktion so zu integrieren, dass sie mit allen numerischen Typen funktioniert (die die erforderlichen Operatoren unterstützen: (*), (-), get_One und 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

Ich würde wahrscheinlich empfehlen, es schwanzrekursiv zu machen, wie Tomas vorgeschlagen hat.