Question Details

No question body available.

Tags

python algorithm

Answers (2)

Accepted Answer Available
Accepted Answer
February 25, 2026 Score: 4 Rep: 483 Quality: High Completeness: 40%

Because you are not using 'standard' fixed length (32/64 bit) integers and are using arbitrary lengths python is likely using the implemented Karatsuba algorithm which multiplies in O(N1.58).

In test1 your denominator grows like a running product so you start multiplying large numbers very early on.

In test2 you're utilizing a balanced reduction tree which keeps your denominators smaller for more iterations which delays operations on larger numbers reducing operations and time.

February 25, 2026 Score: 3 Rep: 28,008 Quality: Medium Completeness: 80%

Replace all multiplications of two ints with calls to this function, which does the multiplication but also analyzes the operand sizes:

def mul(a, b):
    adigits = -(-a.bitlength() // sys.intinfo.bitsperdigit)
    bdigits = -(-b.bitlength() // sys.intinfo.bitsperdigit)
    if adigits > 40 and bdigits > 40:
        print(adigits, bdigits)
    return a  b

The output then shows that the only multiplications where both operands have over 40 digits are:

  • 56 digits multiplied by 57 digits
  • 112 digits multiplied by 48 digits

Python uses Karatsuba only when both are over 70 digits, so that's not happening and isn't the reason.

So all multiplications use the grade school algorithm. We can count how many digit multiplications are done:

def mul(a, b):
    a_digits = -(-a.bit_length() // sys.int_info.bits_per_digit)
    b_digits = -(-b.bit_length() // sys.int_info.bits_per_digit)
    global count
    count += a_digits  bdigits
    return a * b

Set the global count to 0, then run one of your tests, then print count. We get 85041 for test1 and only 40197 for test2. So test2 has a lot less work to do.

But why does test2 have that much less work to do? Note that "digit" here means digit in base 2sys.intinfo.bitsperdigit, which nowadays is 230 for pretty much everyone. So a number like 360 is just one digit. Even 1073741823 (that's 230-1) is still just one digit. Your fractions have numerators and denominators only up to 258481 (that's 3592+3602). And test1 has multiplications always including one of those, which is wasteful, as digits can be so much larger. Whereas test2 only starts with such small digits, but then quickly works with numbers using the full potential of most digits.