Как быстрее возводить число в степень?

Question

В степень поднимать можно некоторыми способами, тут нам интересуют две - Math.Pow и умножение в цикле (для 2 степени не надо цикл). Какая из этих работает быстрее когда

степень равна 2
степень больше 2 и теоретически стремиться к бесконечности.

Есть какая-то граница где до этого умножение работает быстрее, а после - Math.Pow, или наоборот?

П.Н.
Степень должен быть натуральное число.

Answer 1

Я попробовал ради интереса. Расхождение начинается прямо уже с первых степеней и дальше всё довольно линейно.

import time
import math
import pandas as pd
from matplotlib import pylab as plt
%matplotlib inline

def timeit(method):
    def timed(*args, **kw):
        ts = time.monotonic()
        for i in range(100000):
          result = method(*args, **kw)
        te = time.monotonic()
        return (te - ts)
    return timed

@timeit
def pow_by_mul(x, y):
  s = x
  for i in range(y - 1):
    s *= x
  return s

@timeit
def pow_by_asterisk(x, y):
  return x ** y

@timeit
def pow_by_math(x, y):
  return math.pow(x, y)

k = 13
n = 13
df = pd.DataFrame({'pow_by_mul': [pow_by_mul(k, y) for y in range(n)], 'pow_by_asterisk': [pow_by_asterisk(k, y) for y in range(n)], 'pow_by_math': [pow_by_math(k, y) for y in range(n)]})

df.plot();

По горизонтальной оси - степень, в которую возводим. По вертикальной оси - время в условных единицах.

pow_by_mul - возведение в степень умножением
pow_by_asterisk - возведение в степень с помощью оператора Python **
pow_by_math - возведение с помощью math.pow

P.S. У меня сейчас два рабочих языка: Python и C#, и я, кажется не в тот раздел написал. Если это не в тему, я могу снести ответ. :)

Answer 2

Обычно степень, в которую возводится число, не будет слишком большим. Например, .NET позволяет поместить в double результат 3^646. Дальше результат воспринимается как бесконечность. Если тестировать производительность возведения степени с помощью цикла и с помощью библиотеки Math, то ощутимой разницы вы не почувствуете. И то и то вычисляется менее чем за милисекунду. Однако если считать количество тиков процессора, то цикл немного выигрывает за счет того, что библиотека Math позволяет возводить в вещественную степень (double), из-за чего возведение в целочисленную степень будет не самым оптимальным. На моем процессоре для вычисления 3^646 результаты получились следующими:

Math lib pow: 350-450 ticks

Manual pow: 250-400 ticks

Тестирующий код:

static void Main(string[] args)
{
    const double number = 3;
    const int pow = 646;

    /*
    var watch = Stopwatch.StartNew();
    var powResult = Math.Pow(number, pow);
    watch.Stop();
    */

    var watch = Stopwatch.StartNew();
    var powResult = 1.0d;
    for (var i = 0; i < pow; i++)
    {
        powResult *= number;
    }
    watch.Stop();

    Console.WriteLine($"Pow result:   {powResult}");
    Console.WriteLine($"Time execution: {watch.ElapsedTicks} ticks");
}

БЛОГ НА HUSL

Как быстрее возводить число в степень?

Ответы (2 шт):