@user21820 Well I don't have Unix handy so no resource for me lol

@user21820 I tried it on some random small values (since I run out of resources) and the bez variant was actually slower sometimes. My suspicion is that you are performing fewer big int operations with the bez variant per call, and that the big int operations are the slowest component here.

Also in other news managed to trim quite a significant amount of iterations from my tests for my bracketed root-finding code.

The main improvement was the realization that when a point is significantly closer to one side of the bracket compared to the other (closer than what would be possible on the other side due to machine precision and the nature of the floating-point representation), then it often makes sense to ignore the far point altogether and estimate the root using only the 2 other points.

This, coupled with an over-estimation of the root in an attempt to rapidly pull in the other side of the bracket, makes a big difference when dealing with cases where the initial bracket given is something like $(-\infty, \infty)$.

@SimplyBeautifulArt I'm not so sure about that. The online Python3 compiler now seems to have some time-limit so I can't run as big an example, but slightly smaller gives the same results as 4 years ago:

import resource,sys
sys.setrecursionlimit(1000000)
resource.setrlimit(resource.RLIMIT_STACK,[0x10000000,resource.RLIM_INFINITY])
import time

def bez(a,b):
    # returns [x,y,d] where a*x+b*y = d = gcd(a,b) since (b%a)*y+a*(x+(b//a)*y)=d
    if a==0: return [0,1,b] if b>0 else [0,-1,-b]
    r=bez(b%a,a)
    return [r[1]-(b//a)*r[0],r[0],r[2]]
def inv(a,m):
    r=bez(a,m)
    if r[2]!=1: return None
    return r[0] if r[0]>=0 else r[0]+abs(m)
t = time.time()
print(inv(100**7000,99**4001))
print("--- %s seconds ---" % (time.time()-t))

Run 1:

Run 2:

As explained in my question, both are doing exactly the same number of big-int operations, except one is with twice as many digits.

I think it is some other phenomenon with Python.

@FrownyFrog: Hi. Do you have any idea to explain the behaviour I describe in that SO question?

@SimplyBeautifulArt: Seems like there is a LurkyFrog in this room.

i have no idea no

@FrownyFrog Ok. Anyway what brings you here? You came here before but it seems you didn't say anything.

when something becomes slow my thinking is "it takes a ton of memory now, so it has to swap to disk" that's the extent of my understanding

@FrownyFrog Well, that cannot be right. It has the same behaviour even when the inputs are much tinier than the sample above.

yep, i've no clue

increasing the exponents by 1000 doubles the time for the slow one

@FrownyFrog No that doesn't happen at all in my test.

really?

@FrownyFrog You can reproduce on the same online compiler I linked above. It yields:

Roughly linear, as expected.

Maybe you forgot to reset the timer or something.

Anyway I need to go. Bye!

no that's same result, 3s,7s, timeout

bye

@FrownyFrog: Oh you're talking about the slow one! Sorry.

Let me try and see.

@FrownyFrog You're right. That's really weird. You can see that the recursive calls have exactly the same parameters, right?

@FrownyFrog: Well ok I think I know part of the answer now. Typically the parameters have roughly the same length, so the fast version does not incur much in the integer division, but the slow version does because it does p//q where p is roughly twice the length of q.

This doesn't explain the doubling, but I can believe that Python3's integer division is extremely inefficient.

@FrownyFrog: So closer analysis shows that it's not doubling but cubic for the slow method and quadratic for the fast method.

@SimplyBeautifulArt: I figured it out ^ =)