Портал аспирантов
 

Вернуться   Портал аспирантов > Общие > Дискуссионный зал > Физико-математические науки

Ответ
 
Опции темы
Старый 20.12.2014, 19:29   #1
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию Вычисление целочисленного логарифма

Пусть заданы произвольные целые числа 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:
  u:= ilog[2](a):
  if (b = 2) then
    n:= u:
    return(n):
  end if:
  v:= ilog[2](b) + 1:
  n:= trunc(u/v): 
  c:= b^n: 
  while (a > c) do
    w:= trunc((u-ilog[2](c))/v):
    if (w > 0) then
      n:= n + w:
    else 
      n:= n + 1: 
    end if:
    c:= b^n:
  end do:
  if (a < c) then 
    n:= n - 1: 
  end if:
  return(n):
end proc:

a:= 2^1024000:
b:= 19^5000:

FastIntLog(a,b);

48
ilog[2] - это по сути номер старшего бита числа в двоичном представлении.
Вычисляется достаточно быстро при поддержке команд сканирования битов.
Paul Kellerman вне форума   Ответить с цитированием
Реклама
Старый 21.12.2014, 16:01   #2
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Собственная реализация целочисленного логарифма. В верхнее поле вводим целое
положительное число (максимум 2^1024000-1), во второе поле вводим основание
для логарифмирования: тоже целое положительное число (максимум 2^1024000-1),
и нажимаем кнопку LOG, в третьем поле высветится рассчитанный целый логарифм.
Вложения
Тип файла: zip Inttest.zip (386.6 Кб, 2 просмотров)
Paul Kellerman вне форума   Ответить с цитированием
Старый 22.12.2014, 07:46   #3
individ
Full Member
 
Аватар для individ
 
Регистрация: 14.12.2013
Сообщений: 219
По умолчанию

Я не понял.
Вы вычисляете округляя до целого числа?
А что это к целым числам потянуло?
individ вне форума   Ответить с цитированием
Старый 22.12.2014, 15:32   #4
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Я и сам ничего не понимаю, но оно работает. В этом, наверное, и заключается дзен.
Paul Kellerman вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.



Текущее время: 23:33. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2024, «Аспирантура. Портал аспирантов»
Рейтинг@Mail.ru