Вычисление целочисленного логарифма
Пусть заданы произвольные целые числа A и B, причем оба могут быть
сверхбольшими (миллионы или миллиарды битов), и попытки свести их к известным 32/64-битным целым типам, или 80-битным вещественным, поддерживаемых аппаратно, априори отпадают. Необходимо вычислить целочисленный логарифм N = ilog[B](A), так что B^N <= A < B^(N+1). Особо отмечу, что A, B принадлежат бесконечному множеству целых чисел, и поэтому целочисленный логарифм не имеет никакого отноше- ния к дискретному логарифму конечных групп, колец или полей целых чисел, где все операции выполняются по модулю некоторого целого p. В математических пакетах есть специальная функция ilog[b](a), однако, быстро она работает только для оснований B = 2 и 10. При других осно- ваниях (даже относительно небольших, например, 3 или 11, очень долго считает, если A - достаточное большое целое число, 1024000-битное). Но может кто-то знает более быстрые и элегантные алгоритмы ilog[b](a). Я долго ломал голову и навскидку набросал следующий алгоритм, кото- рый быстро считает при любых основаниях B, даже сверхбольших целых. Код:
FastIntLog:= proc(a,b) local n, u, v, w, c: Вычисляется достаточно быстро при поддержке команд сканирования битов. |
Вложений: 1
Собственная реализация целочисленного логарифма. В верхнее поле вводим целое
положительное число (максимум 2^1024000-1), во второе поле вводим основание для логарифмирования: тоже целое положительное число (максимум 2^1024000-1), и нажимаем кнопку LOG, в третьем поле высветится рассчитанный целый логарифм. |
Я не понял.
Вы вычисляете округляя до целого числа? А что это к целым числам потянуло? |
Я и сам ничего не понимаю, но оно работает. В этом, наверное, и заключается дзен.
|
Текущее время: 06:33. Часовой пояс GMT +3. |
Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2024, «Аспирантура. Портал аспирантов»