F # problèmes d'alimentation qui accepte les arguments pour être bigints

Question

J'expérimentent actuellement des F #. Les articles trouvés sur Internet sont utiles, mais en tant que programmeur C #, je parfois courir dans des situations où je pensais que ma solution aiderait, mais il n'a pas ou que partiellement aidé.

Donc, mon manque de connaissance de F # (et très probablement, le fonctionnement du compilateur) est probablement la raison pour laquelle je suis totalement sidéré parfois.

Par exemple, je l'ai écrit un programme C # pour déterminer les nombres parfaits. Il utilise la forme connue de la preuve Euclids, qu'un nombre parfait peut être formé à partir d'un Mersenne Prime 2 p-1 (2 p-1) (où 2p-1 est un premier et p est désigné comme la puissance de).

Depuis l'aide de F # stipule que « ** » peut être utilisé pour calculer une puissance, mais utilise des points flottants, j'ai essayé de créer une fonction simple avec un opérateur bitshift (<<<) (note que j'ai modifier ce code pour souligner la nécessité):

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

Cependant, lors de l'exécution d'un test, et la recherche d'amélioration de la performance, j'ai essayé aussi une forme que je me souviens de l'utilisation Miranda (un langage de programmation fonctionnelle aussi), qui utilise la récursivité et un matcher modèle pour calculer la puissance. Le principal avantage est que je peux utiliser la variable y en tant que 64 bits entier, ce qui est impossible avec l'opérateur standard Bitshift.

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

Il se trouve que cette fonction est plus rapide, mais je ne peux pas (encore) comprendre la raison pour laquelle. Peut-être est une question moins intellectuelle, mais je suis toujours curieux.

Les secondes la question serait alors, que le calcul de nombres parfaits, vous courez dans le fait que le int64 ne peut pas afficher les grands nombres de passage après avoir trouvé le 9 perfectnumber (qui est formé à partir de la puissance 31). J'essaie de savoir si vous pouvez utiliser l'objet BigInteger (ou le type bigint) puis, mais voici ma connaissance de F # me bloquait un peu. Est-il possible de créer un powerfunction qui accepte les arguments pour être bigints?

J'ai actuellement ceci:

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

Mais il renvoie une erreur que bigint.Zero n'est pas défini. Donc, je fais quelque chose de mal là-bas aussi. 0I ne sont pas acceptées en remplacement, car il donne cette erreur:

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.    

Mais un matcher modèle ne peut pas utiliser une instruction « quand ». Y at-il une autre solution pour le faire?

Merci à l'avance, et s'il vous plaît pardonnez mon long post. Je n'essaie d'exprimer mes « défis » aussi clair que possible.

Answer 1

Je ne comprend pas pourquoi vous avez besoin y d'être un int64 ou un bigint. Selon ce lien , le plus grand nombre Mersenne connu est celui avec p = 43112609, où p est en effet à l'intérieur la plage de int.

Avoir y comme un entier, vous pouvez utiliser l'opérateur norme pown : ^T -> int -> ^T à la place parce que:

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

En ce qui concerne votre question de bigint de correspondance de motif, le message d'erreur indique très clairement que vous pouvez utiliser la correspondance de modèle par les gardes de when:

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

Answer 2

Je pense que la meilleure façon de définir PowBigInt est d'utiliser if au lieu de correspondance de motif:

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

Le problème est que bigint.Zero est une propriété statique qui retourne la valeur, mais les modèles ne peuvent contenir que (constants) littéraux ou F # modèles actifs. Ils ne peuvent pas contenir directement des appels propriété (ou autre). Cependant, vous pouvez écrire des contraintes supplémentaires dans la clause where si vous préférez encore match:

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

Comme un côté note, vous pouvez probablement faire fonctionner plus efficent avec tail-récursion (l'idée est que si une fonction fait appel récursif que la dernière chose, alors il peut être compilé plus efficace):

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

En ce qui concerne la fonction PowBitShift - Je ne sais pas pourquoi il est plus lent, mais il ne faut absolument faire pas ce dont vous avez besoin. En utilisant peu de décalage pour mettre en œuvre la puissance ne fonctionne que lorsque la base est 2.

Answer 3

Vous n'avez pas besoin de créer la fonction Pow. L'opérateur (**) a une surcharge pour bigint -> int -> bigint. Seul le second paramètre doit être un entier, mais je ne pense pas que ce soit un problème pour votre cas. Juste essayer

bigint 10 ** 32 ;;

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

Answer 4

Une autre option est de inline fonctionner, de sorte qu'il fonctionne avec tous les types numériques (que de soutien aux opérateurs requis: (*), (-), get_One et 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

Je vous recommande probablement ce qui en fait récursive, comme le suggère Tomas.