title: Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3?
body: <p>It is my understanding that the <code>range()</code> function, which is actually <a href="https://docs.python.org/3/library/stdtypes.html#typesseq-range" rel="nofollow noreferrer">an object type in Python 3</a>, generates its contents on the fly, similar to a generator.</p>
  <p>This being the case, I would have expected the following line to take an inordinate amount of time because, in order to determine whether 1 quadrillion is in the range, a quadrillion values would have to be generated:</p>
  <pre><code>1_000_000_000_000_000 in range(1_000_000_000_000_001)
  </code></pre>
  <p>Furthermore: it seems that no matter how many zeroes I add on, the calculation more or less takes the same amount of time (basically instantaneous).</p>
  <p>I have also tried things like this, but the calculation is still almost instant:</p>
  <pre><code># count by tens
  1_000_000_000_000_000_000_000 in range(0,1_000_000_000_000_000_000_001,10)
  </code></pre>
  <p>If I try to implement my own range function, the result is not so nice!</p>
  <pre><code>def my_crappy_range(N):
      i = 0
      while i &lt; N:
          yield i
          i += 1
      return
  </code></pre>
  <p>What is the <code>range()</code> object doing under the hood that makes it so fast?</p>
  <hr />
  <p><a href="https://stackoverflow.com/a/30081318/2437514">Martijn Pieters's answer</a> was chosen for its completeness, but also see <a href="https://stackoverflow.com/a/30081894/2437514">abarnert's first answer</a> for a good discussion of what it means for <code>range</code> to be a full-fledged <em>sequence</em> in Python 3, and some information/warning regarding potential inconsistency for <code>__contains__</code> function optimization across Python implementations. <a href="https://stackoverflow.com/a/30088140/2437514">abarnert's other answer</a> goes into some more detail and provides links for those interested in the history behind the optimization in Python 3 (and lack of optimization of <code>xrange</code> in Python 2). Answers <a href="https://stackoverflow.com/a/30081467/2437514">by poke</a> and <a href="https://stackoverflow.com/a/30081470/2437514">by wim</a> provide the relevant C source code and explanations for those who are interested.</p>