Быстрый путь к вручную ультрасовременному число
Вы можете форсировать сборку, используя функцию build_external_project ниже.
Он работает, генерируя простой вспомогательный проект внутри дерева сборки, а затем вызывает конфигурацию cmake и сборку cmake на помощнике.
Настройте по желанию для фактической команды ExternalProject_add.
Обратите внимание, что конечные аргументы используются для передачи CMAKE_ARGS. Усовершенствования Furthur оставлены в качестве упражнения для читателя: -)
# This function is used to force a build on a dependant project at cmake configuration phase.
#
function (build_external_project target prefix url) #FOLLOWING ARGUMENTS are the CMAKE_ARGS of ExternalProject_Add
set(trigger_build_dir ${CMAKE_BINARY_DIR}/force_${target})
#mktemp dir in build tree
file(MAKE_DIRECTORY ${trigger_build_dir} ${trigger_build_dir}/build)
#generate false dependency project
set(CMAKE_LIST_CONTENT "
cmake_minimum_required(VERSION 2.8)
include(ExternalProject)
ExternalProject_add(${target}
PREFIX ${prefix}/${target}
URL ${url}
CMAKE_ARGS ${ARGN}
INSTALL_COMMAND \"\"
)
add_custom_target(trigger_${target})
add_dependencies(trigger_${target} ${target})
")
file(WRITE ${trigger_build_dir}/CMakeLists.txt "${CMAKE_LIST_CONTENT}")
execute_process(COMMAND ${CMAKE_COMMAND} ..
WORKING_DIRECTORY ${trigger_build_dir}/build
)
execute_process(COMMAND ${CMAKE_COMMAND} --build .
WORKING_DIRECTORY ${trigger_build_dir}/build
)
endfunction()
11 ответов
Быстрое модульное возведение в степень (я думаю, так оно и называется) может сработать.
Given a, b, c and a^b (mod c):
1. Write b as a sum of powers of 2. (If b=72, this is 2^6 + 2^3 )
2. Do:
(1) a^2 (mod c) = a*
(2) (a*)^2 (mod c) = a*
(3) (a*)^2 (mod c) = a*
...
(n) (a*)^2 (mod c) = a*
3. Using the a* from above, multiply the a* for the powers of 2 you identified. For example:
b = 72, use a* at 3 and a* at 6.
a*(3) x a*(6) (mod c)
4. Do the previous step one multiplication at a time and at the end, you'll have a^b % c.
Я не знаю, как вы собираетесь это делать с типами данных. Если ваш тип данных поддерживает c ^ 2, я думаю, у вас все будет хорошо.
Если вы используете строки, просто создайте строковые версии операций сложения, вычитания и умножения (не слишком сложно). Этот метод должен быть достаточно быстрым. (и вы можете начать шаг 1 с мода c, чтобы a никогда не было больше c).
РЕДАКТИРОВАТЬ: О, посмотрите, вики-страница на Modular Exponentiation .
Можете ли вы разложить на множители a, b или c? Есть ли у C известный диапазон?
Это 32-битные целые числа! Посетите этот сайт
. Например, вот как вы получаете мод n% d, где d 1 >> s (1,2,4,8, ...)
int n = 137; // numerator
int d = 32; // denom d will be one of: 1, 2, 4, 8, 16, 32, ...
int m; // m will be n % d
m = n & (d - 1);
Есть код для n% d, где d равно 1 >> s - 1 (1, 3, 7, 15, 31, ...)
Это действительно поможет, только если c мало, как вы сказали.
У Python есть pow (a, b, c), который возвращает (a ** b)% c (только быстрее), поэтому должен быть какой-то умный способ сделать это. Может, они просто делают то, что вы упомянули.
Думаю, вы ищете: http://en.wikipedia.org/wiki/Montgomery_reduction или более простой способ, основанный на модульном возведении в степень (из википедии)
Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
Bignum result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) {
// multiply in this bit's contribution while using modulus to keep result small
result = (result * base) % modulus;
}
// move to the next bit of the exponent, square (and mod) the base accordingly
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
Here's an example of Fast Modular Exponentiation (suggested in one of the earlier answers) in java. Shouldn't be too hard to convert that to C#
http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html
and the source...
За исключением написания собственного быстрого модульного возведения в степень , самая простая идея, которую я могу придумать, - это использовать тип F # BigInt: Microsoft.FSharp.Math .Types.BigInt , который поддерживает операции с произвольным масштабом, включая возведение в степень и модульную арифметику.
Это встроенный тип, который станет частью полной платформы .NET в следующем выпуске. Вам не нужно использовать F # для использования BitInt - вы можете использовать его непосредственно в C #.
Мне кажется, что есть какая-то связь между мощностью и модом. Мощность - это просто повторное умножение, а мода связана с делением. Мы знаем, что умножение и деление являются обратными, поэтому с помощью этой связи я бы предположил, что существует корреляция между мощностью и модулем.
Например, возьмем степень 5:
5 % 4 = 1
25 % 4 = 1
125 % 4 = 1
625 % 4 = 1
...
Схема очевидна, что 5 ^ b% 4 = 1 для всех значений b.
В этой ситуации все менее ясно:
5 % 3 = 2
25 % 3 = 1
125 % 3 = 2
625 % 3 = 1
3125 % 3 = 2
15625 % 3 = 1
78125 % 3 = 2
...
Но все же есть шаблон.
Если бы вы могли вычислить математику, лежащую в основе шаблонов, я бы не удивился, если бы вы смогли выяснить значение мода без учета фактической мощности.
Я бы рекомендовал ознакомиться с документацией Decimal и посмотреть, соответствует ли она вашим требованиям, поскольку это встроенный тип и может использовать оператор модификации. В противном случае вам понадобится библиотека произвольной точности, например Bignum от java.
Вы можете попробовать следующее:
C #: выполнение операции модуля (mod) над очень большим числом (> Int64.MaxValue)
http://www.del337ed.com /blog/index.php/2009/02/04/c-doing-a-modulus-mod-operation-on-a-very-large-number-int64maxvalue/
Вы можете попробовать разложить 'a' на достаточно малые числа.
Если множители 'a' равны 'x', 'y' и 'z ', затем
a ^ b = (x ^ b) (y ^ b) (z ^ b).
Тогда вы можете использовать свою личность: (a ^ b)% c = (a% c) ^ b% c
Похоже на домашнее задание по криптографии.
Подсказка: ознакомьтесь с маленькой теоремой Ферма .