Как проверить, меньше ли a^b, чем n

учитывая 2 положительных целых числа a и b (1 ‹ a,b ‹ 10000), я хочу убедиться, что a^b ‹ 10000.

проблема в том, что я не могу просто решить a ^ b, учитывая, что 64 ^ 64 достаточно долго, чтобы разбить целочисленный размер.

как я могу получить этот ответ быстро? Я думал об использовании возведения в степень путем возведения в квадрат, но пока не нашел ответа.

Благодарность


algorithm exponentiation
person Community    schedule 09.04.2017    source источник
comment
Когда логарифм 10000 по основанию a больше b?   -  person GSerg    schedule 09.04.2017

Ответы (4)


arrow_upward
0
arrow_downward

Возьмем логарифм по основанию a обеих частей неравенства.

Для положительных целых чисел a и b следующие неравенства эквивалентны:

аб ‹ 10000

loga(ab) ‹ loga(10000)

b ‹ loga(10000)

Последнее можно рассчитать без проблем с переполнением.

Также обратите внимание, что при изменении базовой формулы это может быть записан с помощью функции log10:

блог10(а) ‹ 4

person trincot    schedule 09.04.2017
comment
Обратите внимание, что для вычисления логарифма может потребоваться покинуть область целых чисел, поэтому могут возникнуть проблемы с точностью. - person RiaD; 09.04.2017

arrow_upward
6
arrow_downward

Поскольку и a, и b являются целыми числами, мы можем заключить, что

  1. Особый случай a = 1

     a ^ b < 10000 for any b

  2. Другие значения a можно организовать в простую таблицу.

            a | critical b
-----------------------------
        2 |    13
        3 |     8
        4 |     6
     5..6 |     5
     7..9 |     4
   10..21 |     3
   22..99 |     2
100..9999 |     1
  10000.. |     no solutions

Итак, имея, скажем, a = 4, b = 7, мы можем сделать вывод, что 4**7 > 10000, так как b = 7 больше критического значения (6) для a = 4

person Dmitry Bychenko    schedule 09.04.2017

arrow_upward
2
arrow_downward

Считая a, b положительным:

Вы можете установить переменную result равной 1, а затем умножить ее на a b раз. Как только оно превысит 10000, так будет всегда, поэтому вы можете вернуться

Значение result никогда не будет больше 10000 в квадрате, ведь оно соответствует целочисленным типам. (если a не больше этого, но это означает, что вы вернетесь немедленно).

Если a>1, то потребуется не более log2 10000 итераций.

Если a = 1, то вы сразу знаете, что ab=1

person RiaD    schedule 09.04.2017
comment
Я тоже об этом думал, но a может быть равно 10 газиллионам, так что начните с result=a и умножьте b-1 раза. - person danh; 09.04.2017
comment
@danh: a дано, поэтому он будет соответствовать некоторому типу (typeof (a)), поэтому он все еще не может переполниться. Таким образом, у вас нет особого случая для b = 0 (я знаю, что сказал, что b должен быть положительным) - person RiaD; 09.04.2017
comment
Верно, не то, что 10 газиллионов переливаются, а на случай, если первый продукт переполнится (10 газиллионов в квадрате). Мы сохраняем первую итерацию цикла и избегаем переполнения для первого продукта. - person danh; 09.04.2017
comment
то, что я имел в виду, и ваш, и мой алгоритм не вычислили бы 10 gazillion в квадрате. В любом случае, выбор — это вопрос стиля. - person RiaD; 09.04.2017
comment
Я так не думаю. result=a; iteration=0; while(result<1000 && iteration<b-1) {...} мы никогда не доберемся до тела цикла, когда a почти чрезмерно велико. (я хотел бы снова проголосовать здесь. Я думаю, что это лучший ответ с точки зрения практических вычислений). - person danh; 10.04.2017
comment
@danh, если я не упущу то, что вы имеете в виду, в моем случае мы вводим это один раз, но единственное, что мы будем делать, это умножать на 1 - person RiaD; 10.04.2017

arrow_upward
1
arrow_downward

Если a>1, то есть только несколько допустимых показателей степени, поэтому вы можете просто найти наибольшее допустимое значение a для каждого из них:

maxBases=[0,9999,99,21,9,6,4,3,3,2,2,2,2,2];
if (b<1)
    return true;
if (b>13)
    return (a <= 1);
else
    return (a <= maxBases[b]);
person Matt Timmermans    schedule 09.04.2017