Performance improvments for Python large integer multiplication

Question

In python, I'm working on a project that involves very large number multiplication due to taking the nth factorial of x where x is n 1s in a row.

The whole things work very efficiently, but I'm spending 80%+ of my computation time calculating the product of the integers for the factorial.

This bottleneck becomes especially noticeable at n = 7 where I effectively hit a brick wall. 6 takes under 0.1 seconds, 7 takes 7.5 seconds, and 8 takes so long I've stopped it after a few minutes without it completing.

Any way I can improve the efficiency of this? More specifically the efficiency of the math.prod(arr).

import argparse
import MyFormatter
import datetime
import math

def first_n_digits(num, n):
    return num // 10 ** (int(math.log(num, 10)) - n + 1)

start = datetime.datetime.now()  

parser = argparse.ArgumentParser(
    formatter_class=MyFormatter.MyFormatter,
    description="Calcs x factorial",
    usage="",
)

parser.add_argument("-n", "--number", type=int)

args = parser.parse_args()

if args.number == 1 :
    print(1)
    exit()

s = ""

for _ in range(0, args.number) :
    s = s + "1"
    n = 1

s = int(s)
arr = []

while (s > 1) :
    arr.append(s)
    s -= args.number

n = math.prod(arr)

fnd = str(first_n_digits(n,3))  
print("{}.{}{}e{}".format(fnd[0], fnd[1], fnd[2], int(math.log10(n))))

end = datetime.datetime.now()

print(end-start)

Answer 1

You don't need an exact product. You just need 3 leading digits and an order of magnitude. You're wasting tremendous amounts of time and memory doing the computation in exact integer arithmetic.

One initial step would be to add up logarithms instead of multiplying integers:

log_prod = 0
while s > 1:
    log_prod += math.log10(s)
    s -= args.number

magnitude = int(log_prod)
normalized = 10**(log_prod-magnitude)

This discards millions of digits of precision you don't need, computing results in approximate floating-point arithmetic that still has enough precision for your use case. normalized is a number between 1 and 10 that has the same leading digits as the full product, and magnitude is the full product's order of magnitude.

This still has to add up a lot of logarithms as the input size increases, taking exponentially more time and losing more precision. Further steps might involve using a more sophisticated summation routine (helping with precision, but not runtime), or finding a different way to express the multifactorial that's more amenable to computation.