Расчет очень большой мощности
Я хочу рассчитать очень большие числа, такие как n = 10 ^ 15.
Почему-то не могу, из-за OverflowError.
xd = lambda n : ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/((2 ** (n+1)) * sqrt(17)))
даже для n=1000 он не будет рассчитан.
Хотя, я должен упомянуть, что я хочу его модульность (1000000007)
Каким будет решение?
@Spektre как насчет чисел с плавающей запятой? в моем случае (3 + sqrt(17)) ^ n. Это тоже модпау?
хм, это проблема, потому что это зависит от того, что вы считаете модом поплавка?
вы можете легко использовать power путем возведения в квадрат или log/exp подхода к числам с плавающей запятой и фиксированной точке так же, как и к целым числам, но mod - это особый случай ... поэтому, если вы усекаете свой float до int и thed mod, тогда да, если вы используйте что-то вроде fmod, тогда вам нужно умножить на число, которое вы по модулю, чтобы усечь до целого числа, а затем каким-то образом восстановить результат...
@Spektre Я имею в виду, что мод не нужен, но я также не могу рассчитать очень большое n для (3 + sqrt (17)) ^ n :-??
Следить за этим. Надеюсь, это будет эффективно stackoverflow.com/a/538583/5929910
@toRex Спасибо, я видел это раньше, и я использую Python 3.8, но мои числа очень-очень велики, я думаю, что он не справится с этим.
Возможно, вам стоит немного пояснить обстоятельства, приведшие к этой формуле, потому что она кажется немного странной: видимо, вы хотите заняться модульной арифметикой, но здесь тоже присутствует (обязательно неточный) квадратный корень из 17, а 17 есть не квадратичный вычет по модулю 1000000007
@Spektre Спасибо, я буду искать мощность в квадрате :-?
@harold это о этом. (Сн)
проблема в том, что реализация функции мощности для чисел с плавающей запятой, скорее всего, использует подход log/exp, и вычисление этого для произвольных больших чисел с плавающей запятой не просто, поскольку о LUT не может быть и речи... если это нормально для результата, попробуйте усечь (3 + sqrt(17)) в целое число x, а затем используйте x**n, что должно заставить использовать целочисленную мощность, что должно быть хорошо ... однако я не пишу код на python, поэтому я точно не знаю, насколько хорошо это реализовано. Вы также можете выполнить вычисление с фиксированной точкой, если вам нужно также несколько знаков после запятой после точки...
@Spektre, это дало бы мне неправильный ответ (я думаю)
@Spektre это об этом math.stackexchange.com/a/686374/842598 (часть Sn)
Используйте целочисленную арифметику повсюду: вы можете вычислить xd(n), найдя n-ю степень целочисленной матрицы 2 на 2 [[3, 2], [1, 0]] и умножив ее на вектор [4, 1], что даст вам xd(n+1) вместе с xd(n). Чтобы эффективно вычислить энную степень матрицы по модулю 1000000007, используйте стандартный алгоритм модульного возведения в степень (но применяемый к целочисленным матрицам 2 на 2, а не к простым целым числам).
@MikeyFreeman Хорошо, я рекомендую использовать другое математическое решение, например, основанное на степени матрицы (это, вероятно, возможно, но я не разобрался), которое не будет включать квадратные корни или деления.
просто попробуйте, если он переполнится ... если нет, то сделайте что-то вроде a = (x*1000)**n; b =1000**n;, а затем преобразуйте в число с плавающей запятой y = a/b, что должно дать вам ваш ответ с ограниченной точностью, но все же лучше, чем одни целые числа ... 1000 можно увеличить .... до повысить точность
@MarkDickinson Спасибо, я думаю, это будет решением, я буду над этим работать.
@harold Да, я поработаю над этим. Спасибо
@Spektre я попробую, спасибо
@MarkDickinson Извините, как вы придумали [[3, 2], [1, 0]] или [4, 1]?
@MikeyFreeman: Если вы выражаете xd(n+1) и xd(n) через xd(n) и xd(n-1), вы получаете матричное уравнение: [xd(n+1), xd(n)] = [[3, 2], [1, 0]] * [xd(n), xd(n-1)] (неудобно писать в комментарии — думайте о векторах как о векторах-столбцах здесь). Верхняя строка матрицы исходит из рекуррентного соотношения xd(n+1) = 3*xd(n) + 2*xd(n-1); нижняя строка просто указывает личность xd(n) = 1*xd(n) + 0*xd(n-1). Начальный вектор [4, 1] равен [xd(1), xd[0]].
xd(n+1) = xd(n+2) + xd(n+1). Это Sn (xd=Sn), а не An (math.stackexchange.com/a/686374/842598). Или я ошибаюсь?
@MarkDickinson Нет, я был неправ, спасибо, я ценю вашу помощь
Ответы 3
Поскольку значение n очень велико, переполнение целых чисел очевидно.
Следуйте следующим правилам модульной арифметики:
- Дополнение: (a+b)%m = (a%m + b%m)%m
- Вычитание: (a-b)%m = (a%m + b%m + m)%m
- Умножение: (a*b)%m = (a%m * b%m)%m
- Экспоненциальный: используйте цикл.
Пример: для a^n используйте a = (a%m * a%m)%m, n раз.
Для больших значений n используйте функцию Python pow(x, e, m), чтобы вычислить модуль, что занимает намного меньше времени.
это будет хорошо только для маленьких n в a^n для больших показателей вам нужна мощность путем возведения в квадрат ...
Исправьте @Spektre.
Однако ОП пояснил, что в a^ba есть float !!! поэтому требуется либо фиксированная мощность, либо мощность с плавающей запятой ... Я бы выбрал фиксированную, поскольку это можно сделать с целыми числами без проблем с произвольным журналом точности, exp, которые, по моему мнению, являются причиной переполнения
@Spektre, но OP использует принципиально неверный подход к исходной проблеме, ни мощность с плавающей запятой, ни мощность с фиксированной запятой не решат ее.
Рабочий способ вычислить его только с целыми числами - разработать выражение с использованием биномиального расширения. Немного переформировав его, мы получаем довольно простой способ его вычисления с почти идентичной формулой для членов четной и нечетной степени:
def form(n, mod):
cnk = 1
total = 0
for k in range(n+1):
term = cnk * 3**k * 17**((n-k)//2)
if (n-k) % 2 == 1:
term *= 5
total += term
cnk *= (n-k)
cnk //= (k+1)
return (total // (2**n)) #% mod
Мы можем сравнить ее с вашей исходной формулой, чтобы проверить результаты:
from math import sqrt
def orig(n):
return ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/((2 ** (n+1)) * sqrt(17)))
for n in range(20):
print(n, orig(n), form(n, mod))
Выход:
0 1.0000000000000002 1
1 4.0 4
2 14.000000000000002 14
3 50.0 50
4 178.0 178
5 634.0000000000001 634
6 2258.0 2258
7 8042.0 8042
8 28642.000000000004 28642
9 102010.00000000001 102010
10 363314.0 363314
11 1293962.0000000002 1293962
12 4608514.0 4608514
13 16413466.000000004 16413466
14 58457426.00000001 58457426
15 208199210.00000003 208199210
16 741512482.0000001 741512482
17 2640935866.000001 2640935866
18 9405832562.0 9405832562
19 33499369418.000004 33499369418
Это «довольно» быстро для не больших значений n (проверено на старой машине):
#%timeit form(1000, mod)
# 9.34 ms ± 87.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#%timeit form(10000, mod)
# 3.79 s ± 14.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
#%timeit form(20000, mod)
# 23.6 s ± 37.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Для последнего теста, прежде чем взять модуль, у нас есть число из 11033 цифр.
Основная проблема с этим подходом заключается в том, что, поскольку в конце мы должны делить на 2**n, мы не можем брать по модулю на каждом шаге и сохранять числа, с которыми мы работаем, небольшими.
Однако использование предложенного подхода с матричным умножением (я не видел ссылку на формулу рекурсии, когда начал с этого ответа, очень плохо!) позволит вам это сделать.
Спасибо, я ценю ваше время и концентрацию.
Я собираюсь пойти с умножением матриц
Глядя на ответ на maths.stackexchange, откуда берется формула, кажется, что проще всего вычислить a(n).
Итак, это можно вычислить с помощью рекуррентности очень просто, и на этот раз, поскольку мы используем только умножения и сложения, мы можем воспользоваться правилами арифметики по модулю и сохранить числа, с которыми мы работаем, небольшими:
def s(n, mod):
a1 = 1
a2 = 3
for k in range(n-1):
a1, a2 = a2, (3*a2 + 2* a1) % mod
return (a1 + a2) % mod
mod = 1000000007
print(s(10, mod))
# 363314, as with the other formulas...
print(s(10**6, mod))
# 982192189
%timeit s(10**6, mod)
# 310 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit s(10**7, mod)
# 3.39 s ± 93.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Мы получаем те же результаты, что и с другими формулами (что действительно хорошо...). Поскольку числа, используемые во время вычисления, сохраняют тот же размер, максимум в 5 раз больше по модулю, время вычисления составляет около O (n) - s(10**7) занимает всего в 10 раз больше времени, чем s(10**6).
Вы абсолютно правы, что решение с точки зрения a[n] намного чище, чем работа с поплавками. Следует отметить, что любое линейное повторение допускает O(log n) решение.
google modpow ... это намного быстрее сделать
modpow(a,b,c), чемpow(a,b) mod c, потому что вам не нужны большие числа ... Я видел, как некоторые люди (моложе и на более новых языках, таких как JAVA или python) используют имяpowmodвместо этого, однако IIRC должен bemodpowТак что просто возведите мощность в квадрат с модульной арифметикой... как я сделал в связаннойmodpowреализации