F # Problemas de poder que aceptan ambos argumentos como grandes

Question

Actualmente estoy experimentando con F #. Los artículos que se encuentran en Internet son útiles, pero como programador de C #, a veces me encuentro con situaciones en las que pensé que mi solución ayudaría, pero no lo hizo o simplemente ayudó parcialmente.

Entonces, mi falta de conocimiento de F # (y muy probablemente, cómo funciona el compilador) es probablemente la razón por la que a veces me quedo totalmente asombrado.

Por ejemplo, escribí un programa en C # para determinar números perfectos. Utiliza la forma conocida de la prueba de Euclides, de que se puede formar un número perfecto a partir de un Mersenne Prime 2p − 1 (2p − 1) (donde 2p-1 es un primo y p se denota como la potencia de).

Dado que la ayuda de F # establece que '**' se puede usar para calcular una potencia, pero usa puntos flotantes, intenté crear una función simple con un operador de desplazamiento de bits (<<<) (tenga en cuenta que he editado este código para señalar la necesidad):

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

Sin embargo, al ejecutar una prueba y buscar mejoras en el rendimiento, también probé una forma que recuerdo de usar Miranda (un lenguaje de programación funcional también), que usa recursividad y un patrón de comparación para calcular la potencia. El principal beneficio es que puedo usar la variable y como un entero de 64 bits, lo que no es posible con el operador de desplazamiento de bits estándar.

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

Resulta que esta función es en realidad más rápida, pero no puedo (todavía) entender la razón. Quizás sea una pregunta menos intelectual, pero aún tengo curiosidad.

La pregunta de los segundos entonces sería, que al calcular números perfectos, te encuentras con el hecho de que el int64 no puede mostrar los números grandes que se cruzan después de encontrar el noveno número perfecto (que se forma a partir de la potencia de 31). Estoy tratando de averiguar si puede usar el objeto BigInteger (o el tipo bigint), pero aquí mi conocimiento de F # me bloquea un poco. ¿Es posible crear una función de potencia que acepte que ambos argumentos sean grandes?

Actualmente tengo esto:

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

Pero arroja un error de que bigint.Zero no está definido. Así que también estoy haciendo algo mal. 0I no se acepta como reemplazo, ya que da este error:

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.    

Pero un comparador de patrones no puede usar una declaración "cuando". ¿Existe otra solución para hacer esto?

Gracias de antemano y, por favor, perdone mi larga publicación. Solo intento expresar mis "desafíos" lo más claro que puedo.

Answer 1

No entendí por qué necesita y para ser un int64 o un bigint.Según este enlace , el número de Mersenne más grande conocido es el que tiene p = 43112609, donde p se encuentra dentroel rango de int.

Teniendo y como un número entero, puede usar el operador estándar pown : ^T -> int -> ^T en su lugar porque:

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

Con respecto a su pregunta sobre la coincidencia de patrones bigint, el mensaje de error indica con bastante claridad que puede utilizar la coincidencia de patrones a través de los protectores de when:

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

Answer 2

Creo que la forma más fácil de definir PowBigInt es usar if en lugar de la coincidencia de patrones:

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

El problema es que bigint.Zero es una propiedad estática que devuelve el valor, pero los patrones solo pueden contener literales (constantes) o patrones activos de F #.No pueden contener directamente llamadas de propiedad (u otras).Sin embargo, puede escribir restricciones adicionales en la cláusula where si aún prefiere match:

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

Como nota al margen, probablemente puedas hacer que la función sea más eficiente usando tail-recurssion (la idea es que si una función hace una llamada recursiva como última cosa, entonces se puede compilar máseficientemente):

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

Con respecto a la función PowBitShift, no estoy seguro de por qué es más lenta, pero definitivamente no hace lo que necesita.Usar el cambio de bits para implementar la potencia solo funciona cuando la base es 2.

Answer 3

No es necesario crear la función Pow. El operador (**) tiene una sobrecarga para bigint -> int -> bigint. Solo el segundo parámetro debería ser un número entero, pero no creo que eso sea un problema para su caso. Solo prueba

bigint 10 ** 32 ;;

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

Answer 4

Otra opción es alinear su función para que funcione con todos los tipos numéricos (que admitan los operadores requeridos: (*), (-), get_One y 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

Probablemente recomendaría que sea recursivo en la cola, como sugirió Tomas.