F # questões de poder que aceita ambos os argumentos como bigints

Question

Atualmente, estou testando F #. Os artigos encontrados na Internet são úteis, mas, como programador C #, às vezes me deparo com situações em que pensei que minha solução ajudaria, mas não ajudou ou apenas ajudou parcialmente.

Portanto, minha falta de conhecimento de F # (e muito provavelmente, de como o compilador funciona) é provavelmente a razão pela qual fico totalmente pasmo às vezes.

Por exemplo, escrevi um programa C # para determinar números perfeitos. Ele usa a forma conhecida de prova de Euclides, de que um número perfeito pode ser formado a partir de um Primo de Mersenne 2p − 1 (2p − 1) (onde 2p-1 é um primo e p é denotado como a potência de).

Visto que a ajuda de F # afirma que '**' pode ser usado para calcular uma potência, mas usa pontos flutuantes, tentei criar uma função simples com um operador bitshift (<<<) (observe que eu editei este código para apontar a necessidade):

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

No entanto, ao executar um teste, e procurando melhorias de desempenho, também tentei um formulário que me lembro de usar Miranda (uma linguagem de programação funcional também), que usa recursão e um matcher de padrão para calcular a potência. O principal benefício é que posso usar a variável y como um inteiro de 64 bits, o que não é possível com o operador bithift padrão.

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

Acontece que esta função é realmente mais rápida, mas não consigo (ainda) entender o motivo. Talvez seja uma questão menos intelectual, mas ainda estou curioso.

A segunda questão seria, então, que ao calcular números perfeitos, você se depara com o fato de que o int64 não pode exibir os grandes números que se cruzam após encontrar o nono número perfeito (que é formado a partir da potência 31). Estou tentando descobrir se você pode usar o objeto BigInteger (ou tipo bigint), mas aqui meu conhecimento de F # está me bloqueando um pouco. É possível criar uma função de potência que aceite ambos os argumentos como bigints?

Atualmente tenho este:

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

Mas ele lança um erro de que bigint.Zero não está definido. Então, estou fazendo algo errado também. 0I não é aceito como substituto, pois dá este erro:

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.    

Mas um combinador de padrão não pode usar uma instrução 'quando'. Existe outra solução para fazer isso?

Agradeço antecipadamente e perdoe minha longa postagem. Estou apenas tentando expressar meus 'desafios' da forma mais clara possível.

Answer 1

Não consegui entender por que você precisa que y seja um int64 ou um bigint.De acordo com este link , o maior número de Mersenne conhecido é aquele com p = 43112609, onde p está realmente dentroo intervalo de int.

Tendo y como um inteiro, você pode usar o operador padrão pown : ^T -> int -> ^T porque:

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

Em relação à sua questão de correspondência de padrões bigint, a mensagem de erro indica claramente que você pode usar a correspondência de padrões por meio de guardas when:

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

Answer 2

Acho que a maneira mais fácil de definir PowBigInt é usar if em vez de correspondência de padrão:

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

O problema é que bigint.Zero é uma propriedade estática que retorna o valor, mas os padrões só podem conter literais (constantes) ou padrões ativos F #.Eles não podem conter chamadas de propriedade (ou outras) diretamente.No entanto, você pode escrever restrições adicionais na cláusula where se ainda preferir match:

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

Como uma observação, você provavelmente pode tornar a função mais eficiente usando recursão de cauda (a ideia é que se uma função faz uma chamada recursiva como a última coisa, então ela pode ser compilada maiseficientemente):

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

Com relação à função PowBitShift - não sei por que é mais lenta, mas definitivamente não faz o que você precisa.Usar o deslocamento de bits para implementar energia só funciona quando a base é 2.

Answer 3

Você não precisa criar a função Pow. O operador (**) tem uma sobrecarga para bigint -> int -> bigint. Apenas o segundo parâmetro deve ser um inteiro, mas não acho que isso seja um problema para o seu caso. Apenas tente

bigint 10 ** 32 ;;

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

Answer 4

Outra opção é embutir sua função para que funcione com todos os tipos numéricos (que suportam os operadores necessários: (*), (-), 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

Provavelmente, eu recomendaria torná-lo recursivo na cauda, como o Tomas sugeriu.