Быстрое возведение в степень, когда только первые k цифры требуются?
Да, но только в тех случаях, когда прямая навигация запускается с помощью «Перейти к определению». После этого команда Alt+LeftArrow перейдет к предыдущему местоположению. Существует билет для расширения навигации для обработки более общих случаев, поэтому не стесняйтесь комментировать и вносить свой вклад.
3 ответа
не уверенный, но идентификационные данные nm = exp10 (m log10 (n)) = exp (q (m журнал (n)/q)), где q = журнал (10) приходит на ум, наряду с тем, что первые цифры K exp10 (x) = первые цифры K exp10 (frac (x)) где frac (x) = дробная часть x = x - пол (x).
Быть более явным: первые цифры K nm являются первыми цифрами K его мантиссы = exp (frac (m журнал (n)/q) * q), где q = журнал (10).
Или Вы могли даже пойти далее в этом бухгалтерском осуществлении и использовать exp ((frac (m журнал (n)/q)-0.5) * q) * sqrt (10), который также имеет ту же мантиссу (+ следовательно то же сначала K цифры) так, чтобы аргумент exp () функция центрировался приблизительно 0 (и между + журнал/-0.5 10 = 1.151) для быстрой сходимости.
(Некоторые примеры: предположите желание первых 5 цифр 2100. Это равняется первым 5 цифрам exp ((frac (100 журналов (2)/q)-0.5) *q), *sqrt (10) = 1.267650600228226. Фактическое значение 2100 1.267650600228229e+030 согласно MATLAB, у меня нет библиотеки сверхбольшого числа удобной. Для мантиссы 21,000,000,000 я добираюсь 4.612976044195602, но у меня действительно нет способа проверить.... Существует страница на началах Mersenne где чей-то уже сделана тяжелая работа; 220996011-1 = 125,976,895,450... и моя формула дает 1,259768950493908 вычисленных в MATLAB, который перестал работать после 9-й цифры.)
Я мог бы использовать Ряд Тейлора (для exp и журнала, не для nm) наряду с их ошибочными границами, и продолжать добавлять условия, пока ошибочные границы не опускаются ниже первых цифр K. (обычно я не использую Ряд Тейлора для функционального приближения - их ошибка оптимизирована, чтобы быть самой точной вокруг единственной точки, а не по желаемому интервалу - но у них действительно есть преимущество, что они математически просты, и Вы можете увеличенная точность к произвольной точности просто путем добавления дополнительных условий),
Для логарифмов я использовал бы то, что Ваше любимое приближение.
Предположим, что Вы усекаете на каждом шаге? Не уверенный, насколько точный это было бы, но, например, берут n=11 m=some большое количество, и Вы хотите первые 2 цифры.
рекурсивно:
- 11 x 11-> 121, усеченный-> 12 (1 усечение или округление) затем принимают усеченное значение и повышение снова
12 x 11-> 132 усеченных-> 13 повторений,
(132 усеченных) x 11-> 143...
и наконец добавьте эквивалент # 0 количеству усечений, которые Вы сделали.
Вы смотрели на возведение в степень путем обработки на квадрат? Вы смогли изменять один из методов, таким образом, что Вы только вычисляете то, что необходимо.
В моем последнем классе алгоритмов мы должны были реализовать что-то подобное тому, что Вы делаете, и я неопределенно помню ту страницу, являющуюся полезным.