Ведущие цифры и четырехместные

В моем  предыдущем посте по Вопросу Гельфанда  рассматривалась проблема, которая требует многократного нахождения первой цифры  k ^n,  где k  — это одна цифра, но  n  может быть порядка миллионов или миллиардов.

Наиболее прямым подходом было бы сначала вычислить  k ⁿ  как очень большое целое число, а затем найти его первую цифру. Этот подход медленный и становится медленнее с   ростом n . Более быстрый способ — посмотреть на дробную часть log  k ⁿ  =  n  log  k  и посмотреть, какой цифре она соответствует.

Если  n  не очень большое, это можно сделать с обычной точностью. Но когда  n  большое, умножение log k  на  n  и взятие дробной части приводит к значению менее значимых цифр. Поэтому для очень большого  n вам нужна дополнительная точность. Сначала я сделал это в Python с использованием SymPy, а затем переключился на C ++ для большей скорости. Там я использовал  quadmath библиотеку для  gcc. (Если  n  достаточно велико, даже четверной точности недостаточно. Преимущество SymPy по сравнению с тем  quadmath , что первое имеет  произвольную точность. Например, можно установить точность на 10 больше, чем число десятичных разрядов в  n чтобы сохранить 10 значащих цифр в дробной части  n  log  k .)

quadmath.h Заголовочный файл должен быть обернут в  extern C декларации. В противном случае  gccвы получите вводящие в заблуждение сообщения об ошибках.

#include <cmath>
extern "C" {
#include <quadmath.h>
}
 
__float128 logs[11];
 
for (int i = 2; i <= 10; i++)
    logs[i] = log10q(i + 0.0);
 
int first_digit(int base, long long exponent)
{
    __float128 t = fmodq(exponent*logs[base], 1.0);
    for (int i = 2; i <= 10; i++)
        if (t < logs[i])
            return i-1;
}