CODEWITHSUNDEEP
pythonpython-3.xperformance
Moca
Moca

Reputation: 53

Issues computing double factorials: computer or code?

I'm programming a calculator application using Python 3, and everything functions fine (I think), except when I attempt to use the my double_factorial() function. If I enter a number higher than 3, the program doesn't output anything and my computer overheats (I use a Macbook Pro, fully customized to be as powerful as possible). This is either a straight up computer issue, or a computer issue because of something wrong with my code. Is there anything wrong with my code that I might not be able to spot as a beginner? (note: I'm only posting the relevant sections):

def add(a,b):
    return(a + b)

def subtract(a,b):
    return(a - b)


def multiply(a,b):
    counter = 0
    for i in range(a):
        counter = add(counter, b)
    return(counter)

def divide(a,b):
    quotient = 0
    while a >= b:
        quotient = add(quotient, 1)
        a = subtract(a,b)
    return (quotient, a)

def factorial(a):
    c = 1
    while a > 1:
        c = multiply(c,a)
        a = subtract(a,1)
    return(c)

def double_factorial(a):
    og = factorial(a)
    return factorial(og)    

def equation():
    d = None    
    print("Valid operations: +, -, *, /, !, !!, =")
    c = eval(input("Integer: "))

    while d != "=":
        d = input("Operation: ")

        if d in ('+', '-', '*', '/', '!', '!!', '='):
            if d == "+":
                c = add(c, eval(input("Integer: ")))
            elif d == "-":
                c = subtract(c, eval(input("Integer: ")))
            elif d == "*":
                c = multiply(c, eval(input("Integer: "))) 
            elif d == "/":
                c = divide(c, eval(input("Integer: ")))
            elif d == "!":
                c = factorial(c)
            elif d == "!!":
                c = double_factorial(c)            
        elif d != "=":
            print("invalid")
    print(str(c))

Upvotes: 1

Views: 149

Answers (1)

Ashalynd
Ashalynd

Reputation: 12563

4!! = 24! which is a huge number (as a rough estimation: 24! > 24 * 5^5 * 10^14, which means 4!! ~ 10^20 which is already close to sys.maxsize.

The next one, 5!! = 120! which is immensely larger. (120! >> 10^90 * 100^20 ~ 10^130).

If you provide the code for your multiply function, it might help to detect what exactly is going on (in theory, Python3 can calculate e.g. 10^100 successfully), but I suspect your computer has reached its limits here.

Update: now that you have provided your code, there is at least one more potential issue: in your multiply method, you use range(a), which actually instantiates the requested sequence in memory. Assuming 4 bytes per int, this results in at least a*4 bytes needed. E.g. if your machine had e.g. 1TB free memory (which it probably doesn't have) this already would limit the value of a: a < 10^12/4.

Also, your "a" is the larger of the multiplied values, so changing the order of the operands sent to multiply would help as well, because then the range will be smaller (corresponding to n! instead of partially computed n!!)

You can mitigate this somewhat by using xrange instead, which is a sequence iterator.

Upvotes: 1

Related Questions