F # Problemi di alimentazione che accettano entrambi gli argomenti come bigint

Question

Attualmente sto sperimentando con F #. Gli articoli trovati su Internet sono utili, ma come programmatore C #, a volte mi imbatto in situazioni in cui pensavo che la mia soluzione sarebbe stata d'aiuto, ma non ha aiutato o è stato solo di aiuto.

Quindi la mia mancanza di conoscenza di F # (e molto probabilmente di come funziona il compilatore) è probabilmente il motivo per cui a volte sono completamente sbalordito.

Ad esempio, ho scritto un programma C # per determinare i numeri perfetti. Usa la forma nota della dimostrazione di Euclide, che un numero perfetto può essere formato da un Mersenne Prime 2p − 1 (2p − 1) (dove 2p-1 è un numero primo e p è indicato come la potenza di).

Poiché l'aiuto di F # afferma che '**' può essere utilizzato per calcolare una potenza, ma utilizza punti mobili, ho provato a creare una semplice funzione con un operatore bitshift (<<<) (nota che ho modificato questo codice per segnalare la necessità):

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

Tuttavia, durante l'esecuzione di un test e alla ricerca di miglioramenti delle prestazioni, ho anche provato un modulo che ricordo di aver usato Miranda (anche un linguaggio di programmazione funzionale), che utilizza la ricorsione e un pattern matcher per calcolare la potenza. Il vantaggio principale è che posso usare la variabile y come numero intero a 64 bit, cosa che non è possibile con l'operatore bitshift standard.

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

Si scopre che questa funzione è effettivamente più veloce, ma non riesco (ancora) a capire il motivo. Forse è una domanda meno intellettuale, ma sono comunque curioso.

La domanda dei secondi quindi sarebbe che, quando si calcolano i numeri perfetti, ci si imbatte nel fatto che l'int64 non può visualizzare i grandi numeri che si incrociano dopo aver trovato il nono numero perfetto (che è formato dalla potenza di 31). Sto cercando di scoprire se puoi usare l'oggetto BigInteger (o tipo bigint), ma qui la mia conoscenza di F # mi sta bloccando un po '. È possibile creare una funzione di alimentazione che accetti entrambi gli argomenti come bigint?

Al momento ho questo:

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

Ma genera un errore che bigint.Zero non è definito. Quindi sto facendo qualcosa di sbagliato anche lì. 0I non è accettato come sostituto, poiché dà questo errore:

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.    

Ma un pattern matcher non può usare un'istruzione "when". C'è un'altra soluzione per farlo?

Grazie in anticipo e perdona il mio lungo post. Sto solo cercando di esprimere le mie "sfide" nel modo più chiaro possibile.

Answer 1

Non sono riuscito a capire perché è necessario che y sia un int64 o un bigint.Secondo questo link , il numero Mersenne più noto è quello con p = 43112609, dove p è effettivamente all'internol'intervallo di int.

Avendo y come numero intero, puoi utilizzare l'operatore standard pown : ^T -> int -> ^T invece perché:

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

Per quanto riguarda la tua domanda sul pattern matching bigint, il messaggio di errore indica abbastanza chiaramente che puoi usare il pattern matching tramite when guards:

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

Answer 2

Penso che il modo più semplice per definire PowBigInt sia utilizzare if invece del pattern matching:

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

Il problema è che bigint.Zero è una proprietà statica che restituisce il valore, ma i modelli possono contenere solo valori letterali (costanti) o modelli attivi F #.Non possono contenere direttamente chiamate di proprietà (o altro).Tuttavia, puoi scrivere ulteriori vincoli nella clausola where se preferisci ancora match:

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

Come nota a margine, puoi probabilmente rendere la funzione più efficiente usando la ricorsione in coda (l'idea è che se una funzione fa una chiamata ricorsiva come ultima cosa, allora può essere compilata di piùin modo efficiente):

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

Per quanto riguarda la funzione PowBitShift, non sono sicuro del motivo per cui sia più lenta, ma sicuramente non fa quello che ti serve.L'uso dello spostamento di bit per implementare la potenza funziona solo quando la base è 2.

Answer 3

Non è necessario creare la funzione Pow. L'operatore (**) ha un sovraccarico per bigint -> int -> bigint. Solo il secondo parametro dovrebbe essere un numero intero, ma non credo che sia un problema per il tuo caso. Prova

bigint 10 ** 32 ;;

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

Answer 4

Un'altra opzione è incorporare la funzione in modo che funzioni con tutti i tipi numerici (che supportano gli operatori richiesti: (*), (-), get_One e 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

Probabilmente consiglierei di renderlo ricorsivo di coda, come suggerito da Tomas.