Блог

Главная - Вопросы по программированию - Повышение 2 до больших показателей

Повышение 2 до больших показателей

#python #python-3.x #performance #exponent

#python #python-3.x #Производительность #экспонента

Вопрос:

Я пытаюсь вычислить большие показатели из двух, такие как следующие: 2^48572234 (* примечание: это пример и не является одним из чисел, которые я вычисляю). Однако встроенная нотация python для повышения показателей довольно медленно справляется с этой задачей:

 number = 2**<exponent>

Для выполнения этой задачи на моем компьютере требуется более 80 часов (используя приведенный выше пример). Однако может быть более быстрый метод pow . Вот пример:

 number = pow(<exponent>)

Это составляет до 68 часов. Но это все еще слишком долго, особенно когда показатели начинают становиться действительно большими. Другой способ сделать это — с math.pow помощью функции, но она выдает ошибку OverflowError .

Я также попробовал другой подход, когда я добавил n количество единиц в строку, преобразовал ее в int и добавил единицу, чтобы получить ответ. Это было бы похоже на следующий подход:

 def genExponent(n): # generate large exponents of two.
    x = ""
    for i in range(n):
        x  = "1"
    z = int(x,2)
    z =1
    return z

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

У кого-нибудь есть идеи по более эффективным алгоритмам?

Комментарии:

1. Используя ваш пример, 2^48572234 это будет число, для хранения и представления которого потребуется приблизительно 48 мегабит / 6 мегабайт ( 2^X требуются X 1 биты). На земле нет процессора, который мог бы вычислить такое число, используя аппаратное ускорение, поэтому это будет сделано только с помощью программного обеспечения. Поэтому неудивительно, что для вычисления требуется некоторое время.

2. Однако, чтобы использовать это свойство, вероятно, было бы проще вычислить это обходным путем. 2^X в двоичном формате 1, за которым следует X нулей, поэтому вместо математического вычисления другим подходом может быть построение этой строки, а затем ее анализ в (чрезвычайно большое) целое число.

3. В вопросе, который я сказал, я пробовал это*

4. При таких размерах вам все равно следует рассмотреть возможность работы с представлением экспоненты. Что бы вы сделали с этим числом: добавьте 1 к результату? это не имело бы никакого эффекта.

5. Честно говоря, я действительно не хотел ничего с этим делать — Я просто хотел посмотреть, смогу ли я, и каким будет самый быстрый вариант его вычисления.

Ответ №1:

Вот шестнадцатеричный подход, который я описал в комментарии:

 def hex(exponent):
    sig_exp = exponent % 4
    sig = 2**sig_exp
    zeroes = (exponent - sig_exp) // 4
    return str(sig)   (zeroes * '0')

x = hex(1234567)
ix = int(x, 16)

# Equivalent exponential operator
# ix = 2*1234567

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