Быстро рассчитать мощность числа (библиотека MPFR) - PullRequest
Новая
       164

Быстро рассчитать мощность числа (библиотека MPFR)

0 голосов
/ 08 марта 2020

Я использую библиотеки GMP и MPFR для работы с большими числами, и мне нужно быстро рассчитать мощность числа. Результат потенцирования всегда будет целым числом, но потенция может быть или не быть плавающим числом. библиотека GMP вычисляет мощности очень быстро, но не принимает плавающие полномочия (с помощью функции mpz_pow_ui), библиотека MPFR принимает значения плавающих мощностей, но очень медленная, так как требует высокой точности для правильного вычисления целых чисел (используя функцию mpfr_pow). Есть ли решение для этого? Как GMP принимать плавающие полномочия или MPFR быстро (и правильно) вычислять целые числа? 


//Ex:

mpz_pow_ui(mpz_power, base, 4790)  //Fast

// power = 4790.60
mpfr_pow(mpfr_power, base, power, MPFR_RNDN)  //Slow

1 Ответ

0 голосов
/ 10 марта 2020

Функция mpz_pow_ui быстрая, так как вычисление может быть выполнено с умножением. Обратите внимание, что mpfr_pow_ui с MPFR_RNDN должно быть быстрее, если вам не нужен точный целочисленный результат (который будет огромен, если показатель большой), поскольку умножения можно выполнять с меньшей точностью и округлять.

Если показатель не является не слишком большим целым числом, mpfr_pow будет медленнее, потому что ему нужно вычислить логарифм и экспоненту, которые являются более сложными, чем умножения. Я не думаю, что вы можете избежать этого, даже если вы знаете, что результатом будет целое число. Но если вы знаете, что результатом будет целое число, вы можете вычислить его с ошибкой менее 1/2. Таким образом, с помощью анализа ошибок вы сможете уменьшить точность входных и выходных переменных, чтобы mpfr_pow был быстрее.

Примечание: вы говорите

библиотека MPFR принимает плавающие полномочия, но очень медленная, так как требует высокой точности для правильного вычисления целых чисел (используя функцию mpfr_pow)

Это не так. MPFR тщательно выберет промежуточные значения точности, чтобы дать ответ с требуемой точностью (хотя иногда он может делать неправильный выбор).

Однако, если точный результат очень близок к «номеру машины», может возникнуть проблема, связанная с тем, что MPFR должен возвращать знак ошибки (точное округление MPFR_RNDF вместо MPFR_RNDN может помочь, но оно еще не оптимизировано для mpfr_pow): возникнет дилемма Table Maker, требующая внутренние вычисления в более высокой точности. Но если вы тщательно выбрали точность входных данных, это вряд ли произойдет в вашем случае; действительно, снижение точности входных данных приведет к добавлению некоторой ошибки к точному результату, и это отодвинет точный результат от ожидаемого целого числа (под точным результатом я имею в виду точный результат с приблизительными входными данными). Вы также можете использовать некоторые приемы. Например, если вы знаете, что ваше целое число не является идеальным квадратом, то вместо вычисления x y вы можете вычислить x y / 2 (который не соответствует номеру машины, поэтому не должен иметь проблемы из-за дилеммы Table Maker), а затем возведите в квадрат результат.

...