Быстрое экспонирование, когда требуется только k цифр — продолжение

Question

Быстрое экспонирование, когда требуется только k цифр — продолжение

Где мне нужна помощь …

Теперь я хочу перевести это решение, которое вычисляет мантиссачисла до c ++:

n^m = exp10(m log10(n)) = exp(q (m log(n)/q)) where q = log(10)

Найти первые n цифр из результата можно следующим образом:

"the first K digits of exp10(x) = the first K digits of exp10(frac(x))
where frac(x) = the fractional part of x = x - floor(x)."

Мои попытки (вызванные математикой и этот код) не удалось…:

u l l function getPrefix(long double pow /*exponent*/, long double length /*length of prefix*/)
{
long double dummy; //unused but necessary for modf
long double q = log(10);

u l l temp = floor(pow(10.0, exp(q * modf( (pow * log(2)/q), &dummy) + length - 1));
return temp;
}

Если кто-то может правильно реализовать это решение, мне нужна ваша помощь!

РЕДАКТИРОВАТЬ

Пример вывода из моих попыток:

n: 2

м: 0

п ^ м: 1

Расчетная мантисса: 1.16334

n: 2

м: 1

п ^ м: 2

Рассчитанная мантисса: 2.32667

n: 2

м: 2

п ^ м: 4

Рассчитанная мантисса: 4.65335

n: 2

м: 98

n ^ m: 3,16913e + 29

Рассчитанная мантисса: 8.0022

n: 2

м: 99

n ^ m: 6,33825e + 29

Рассчитанная мантисса: 2.16596

4

algorithm c++exponentiation math

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я бы избежал pow за это. Как известно, это трудно реализовать правильно. Есть много ТАКИХ вопросов, где люди сгорели от плохого pow реализация в их стандартной библиотеке.

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

long double foo = m * logl(n);
foo = fmodl(foo, logl(10.0)) + some_epsilon;
sprintf(some_string, "%.9Lf", expl(foo));
/* boring string parsing code here */

вычислить соответствующий аналог m log(n), Обратите внимание, что самый большой m * logl(n) что может возникнуть немного больше, чем 2e10, Когда вы делите это на 2⁶⁴ и округляя до ближайшей степени двух, вы видите, что foo это 2^-29 в худшем случае. Это означает, в частности, что вы не можете получить более 8 цифр из этого метода, используя long doubleс, даже с идеальной реализацией.

some_epsilon будет самым маленьким long double что делает expl(foo) всегда превышать математически правильный результат; Я не рассчитал это точно, но это должно быть порядка 1e-9,

В свете трудностей с точностью здесь, я мог бы предложить использовать библиотеку типа MPFR вместо long doubles. Вы также можете получить что-то для работы, используя double double трюк и четкость exp, log, а также fmod,

3