Проблемы с F # Power, в которых оба аргумента считаются важными

Question

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

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

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

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

родовое слово

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

родовое слово

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

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

Сейчас у меня есть это:

родовое слово

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

родовое слово

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

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

Answer 1

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

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

родовое слово

Что касается вашего вопроса о сопоставлении с шаблоном pown : ^T -> int -> ^T, сообщение об ошибке довольно четко указывает, что вы можете использовать сопоставление с образцом с помощью средств защиты bigint:

родовое слово

Answer 2

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

родовое слово

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

родовое слово

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

родовое слово

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

Answer 3

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

<цитата>

bigint 10 ** 32 ;;

родовое слово

Answer 4

Другой вариант - встроить функцию, чтобы она работала со всеми числовыми типами (которые поддерживают необходимые операторы: (*), (-), get_One и get_Zero).

родовое слово

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