F # Power проблемы, которые принимают оба аргумента как bigints - PullRequest
Новая
       56

F # Power проблемы, которые принимают оба аргумента как bigints

11 голосов
/ 02 декабря 2011

Я сейчас экспериментирую с F #.Статьи, найденные в Интернете, полезны, но, как программист на C #, я иногда сталкиваюсь с ситуациями, когда думаю, что моё решение поможет, но оно не помогло или помогло частично.

Так что мое отсутствие знаний F #(и, скорее всего, то, как работает компилятор), вероятно, является причиной, по которой я иногда просто поражен.

Например, я написал программу на C # для определения идеальных чисел.Он использует известную форму доказательства Евклида, что идеальное число может быть сформировано из простого Мерсенна 2p-1 (2p-1) (где 2p-1 - простое число, а p обозначено как степень).

Поскольку с помощью F # утверждается, что для вычисления степени можно использовать «**», но используются числа с плавающей запятой, я попытался создать простую функцию с оператором побитового сдвига (<<<) (обратите внимание, что я редактировалэтот код указывает на необходимость): </p> 

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

Однако при запуске теста и поиске улучшений производительности я также попробовал форму, которую я помню, используя Miranda (также функциональный язык программирования),который использует рекурсию и сопоставление с образцом для расчета мощности.Основное преимущество заключается в том, что я могу использовать переменную y в качестве 64-разрядного целого числа, что невозможно при использовании стандартного оператора битового сдвига.

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

Оказывается, эта функция на самом деле быстрее, но я не могу (пока) понять причину этого.Возможно, это менее интеллектуальный вопрос, но мне все еще любопытно.

Тогда возникает второй вопрос: при вычислении совершенных чисел вы сталкиваетесь с тем фактом, что int64 не может отобразить пересечение больших чисел после нахождения9-й совершенный номер (который образован из силы 31).Я пытаюсь выяснить, можно ли тогда использовать объект BigInteger (или тип bigint), но здесь мои знания F # немного меня блокируют.Можно ли создать функцию power, которая принимает оба аргумента как bigints?

В настоящее время у меня есть это: 

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

Но выдает ошибку, что bigint.Zero не определен.Так что я тоже что-то не так делаю.0 Я не принят в качестве замены, так как он выдает эту ошибку: 

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.

Но сопоставитель шаблонов не может использовать оператор «когда».Есть ли другое решение для этого?

Заранее спасибо, и, пожалуйста, прости мой длинный пост.Я только пытаюсь выразить свои «вызовы» как можно яснее.

Ответы [ 4 ]

8 голосов
/ 02 декабря 2011

Я не смог понять, почему вам нужно y, чтобы быть int64 или bigint.Согласно этой ссылке , самое большое известное число Мерсенна - это число с p = 43112609, где p действительно находится в диапазоне int.

Имея y в качествецелое число, вместо этого вы можете использовать стандартный оператор pown : ^T -> int -> ^T, потому что: 

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

Что касается вашего вопроса о сопоставлении с шаблоном bigint, сообщение об ошибке совершенно ясно указывает на то, что вы можете использовать сопоставление с шаблоном через when охранников: 

let rec PowBigInt x y = 
    match y with
    | _ when y = 0I -> 1I
    | _ -> x * PowBigInt x (y - 1I)
5 голосов
/ 02 декабря 2011

Вам не нужно создавать функцию Pow.Оператор (**) перегружен для bigint -> int -> bigint.Только второй параметр должен быть целым числом, но я не думаю, что это проблема для вашего случая.Просто попробуйте

bigint 10 ** 32 ;; 

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}
5 голосов
/ 02 декабря 2011

Я думаю, что самый простой способ определить PowBigInt - это использовать if вместо сопоставления с шаблоном: 

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

Проблема в том, что bigint.Zero является статическим свойством, которое возвращает значение, ношаблоны могут содержать только (постоянные) литералы или активные шаблоны F #.Они не могут напрямую содержать свойства (или другие) вызовы.Тем не менее, вы можете написать дополнительные ограничения в предложении where, если вы по-прежнему предпочитаете match: 

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

В качестве дополнительного примечания, вы можете сделать функцию более эффективной, используя tail-recursion (идея заключается в том, что если функция выполняет рекурсивный вызов как последнюю вещь, то она может быть скомпилирована более эффективно): 

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

Относительно функции PowBitShift - я не знаю, почемуэто медленнее, но это определенно не делает то, что вам нужно.Использование сдвига битов для реализации питания работает только тогда, когда база равна 2.

3 голосов
/ 02 декабря 2011

Другой вариант - встроить вашу функцию, чтобы она работала со всеми числовыми типами (которые поддерживают необходимые операторы: (*), (-), get_One и 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

Я бы порекомендовал сделать его хвост-рекурсивным, как предложил Томас.

...