title: Strange Python Speedup for Modular Inverse
body: <p>Usually I am lazy and calculate modular inverses as follows:</p>
  
  <pre><code>def inv(a,m):
      return 1 if a==1 else ((a-inv(m%a,a))*m+1)//a
  print(inv(100**7000,99**7001))
  </code></pre>
  
  <p>But I was curious to know whether the method of passing more information back, namely the solution to Bezout's theorem (instead of just one of the pair), yields a faster or slower algorithm in practice:</p>
  
  <pre><code>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&gt;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]&gt;=0 else r[0]+abs(m)
  print(inv(100**7000,99**7001))
  </code></pre>
  
  <p>I was amazed to find that the latter ran more than 50 times faster than the former! But both use nearly the same number of recursive calls and 1 integer division and 1 modulo operation per call, and the bit-length of the operands is roughly twice in the former on average (because the arguments involved are identical), so I only expect its time complexity to be roughly 4 times that of the latter, not 50 times.</p>
  
  <blockquote>
    <p>So why am I observing this strange speedup?</p>
  </blockquote>
  
  <p>Note that I am using Python 3, and I observed this when running <a href="https://www.tutorialspoint.com/execute_python3_online.php" rel="nofollow noreferrer">online</a>, with the following code added at the top to stop the Python interpreter complaining about exceeding maximum recursion depth or stack space:</p>
  
  <pre><code>import resource,sys
  sys.setrecursionlimit(1000000)
  resource.setrlimit(resource.RLIMIT_STACK,[0x10000000,resource.RLIM_INFINITY])
  </code></pre>