Вычислить быстрый бревенчатый фундамент 2 потолка в python

для данного x < 10^15, быстро и точно определить максимальное целое число p такое, что 2^p <= x

Вот некоторые вещи, которые я пробовал:

Сначала я попробовал это, но это не точно для больших чисел:

>>> from math import log
>>> x = 2**3
>>> x
8
>>> p = int(log(x, 2))
>>> 2**p == x
True
>>> x = 2**50
>>> p = int(log(x, 2))
>>> 2**p == x #not accurate for large numbers?
False

Я мог бы попробовать что-то вроде:

p = 1
i = 1
while True:
    if i * 2 > n:
        break
    i *= 2
    p += 1
    not_p = n - p

Это займет до 50 операций, если p было 50

Я мог предварительно вычислить все полномочия 2 до 2 ^ 50 и использовать бинарный поиск для поиска p. Это потребует около log (50) операций, но кажется немного чрезмерным и уродливым?

Я нашел эту тему для решений на основе C: Вычислить быстрый бревенчатый фундамент 2 потолка

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

Ответы

Ответ 1

В Python >= 2.7 вы можете использовать метод .bit_length() целых чисел:

def brute(x):
    # determine max p such that 2^p <= x
    p = 0
    while 2**p <= x:
        p += 1
    return p-1

def easy(x):
    return x.bit_length() - 1

который дает

>>> brute(0), brute(2**3-1), brute(2**3)
(-1, 2, 3)
>>> easy(0), easy(2**3-1), easy(2**3)
(-1, 2, 3)
>>> brute(2**50-1), brute(2**50), brute(2**50+1)
(49, 50, 50)
>>> easy(2**50-1), easy(2**50), easy(2**50+1)
(49, 50, 50)
>>> 
>>> all(brute(n) == easy(n) for n in range(10**6))
True
>>> nums = (max(2**x+d, 0) for x in range(200) for d in range(-50, 50))
>>> all(brute(n) == easy(n) for n in nums)
True

Ответ 2

Вы можете попробовать функцию log2 от numpy, которая работает для работы до 2 ^ 62:

>>> 2**np.log2(2**50) == 2**50
True
>>> 2**np.log2(2**62) == 2**62
True

Выше этого (по крайней мере для меня) не удается из-за ограничений типов внутренних номеров numpy, но это будет обрабатывать данные в диапазоне, о котором вы говорите.

Ответ 3

Вы указываете в комментариях, что ваш x является целым числом, но для тех, кто приходит сюда, где их x уже является float, тогда math.frexp() будет довольно быстро при извлечении базы журнала 2:

log2_slow = int(floor(log(x, 2)))
log2_fast = frexp(x)[1]-1

Функция C, которую frexp() вызывает, просто захватывает и настраивает экспоненту. Еще несколько "splainin:

  • Подстрочный индекс [1] заключается в том, что frexp() возвращает кортеж (значение, показатель).
  • В вычитании -1 учитывается, что значение находится в диапазоне [0,5,1,0). Например, 2 50 хранится как 0,5x2 51.
  • Пол() заключается в том, что вы указали 2^p <= x, поэтому p == floor(log(x,2)).

(Получено из другого ответа.)

Ответ 4

Работает для меня, Python 2.6.5 (CPython) на OSX 10.7:

>>> x = 2**50
>>> x
1125899906842624L
>>> p = int(log(x,2))
>>> p
50
>>> 2**p == x
True

Он продолжает работать, по крайней мере, для показателей с точностью до 1e9, и к этому времени для выполнения математики начинается довольно много времени. Что вы на самом деле получаете за x и p в своем тесте? Какая версия Python, на какой ОС вы работаете?

Ответ 5

В отношении "неточности для больших чисел" ваша задача здесь в том, что представление с плавающей запятой действительно не так точно, как вам нужно (49.999999999993 != 50.0). Отличная ссылка: " Что должен знать каждый компьютерный ученый о арифметике с плавающей точкой.

Хорошей новостью является то, что преобразование подпрограммы C очень просто:

def getpos(value):
    if (value == 0):
        return -1
    pos = 0
    if (value & (value - 1)):
        pos = 1
    if (value & 0xFFFFFFFF00000000):
        pos += 32
        value = value >> 32
    if (value & 0x00000000FFFF0000):
        pos += 16
        value = value >> 16
    if (value & 0x000000000000FF00):
        pos += 8
        value = value >> 8
    if (value & 0x00000000000000F0):
        pos += 4
        value = value >> 4
    if (value & 0x000000000000000C):
        pos += 2
        value = value >> 2
    if (value & 0x0000000000000002):
        pos += 1
        value = value >> 1
    return pos

Другой альтернативой является то, что вы можете округлить до ближайшего целого числа, а не обрезать:

   log(x,2)
=> 49.999999999999993
   round(log(x,2),1)
=> 50.0

Ответ 6

Мне нужно было рассчитать верхнюю границу двух (чтобы выяснить, сколько байтов энтропии было необходимо для генерации случайного числа в заданном диапазоне с использованием оператора модуля).

Из грубого эксперимента я думаю, что приведенный ниже расчет дает минимальное целое число p такое, что val < 2 ^ p

Он, вероятно, так же быстро, как вы можете получить, и использует исключительно побитовую целочисленную арифметику.

def log2_approx(val):
    from math import floor
    val = floor(val)
    approx = 0
    while val != 0:
        val &= ~ (1<<approx)
        approx += 1
    return approx

Ваше немного другое значение будет рассчитано для данного n на

log2_approx(n) - 1

... может быть. Но в любом случае побитовая арифметика может дать вам понять, как это сделать быстро.