title: Python fast XOR over range algorithm
body: <p>There is a programming challenge that requires one to generate an <strong>XOR</strong> checksum based on sequence start number and an interval length.</p>
  
  <p>It requires you to iterate the sequence based on the interval length and at each iteration keep reducing the number of elements picked for the checksum calculation.</p>
  
  <p><em>Example:</em></p>
  
  <hr>
  
  <p>if the start number is <strong>0</strong> and the interval length is <strong>3</strong>, the process would look like this:</p>
  
  <p><strong>0 1 2</strong>/</p>
  
  <p><strong>3 4</strong> / 5</p>
  
  <p><strong>6</strong> / 7 8</p>
  
  <p>where the  XOR (^) checksum is <strong>0^1^2^3^4^6</strong> == <strong>2</strong></p>
  
  <p>Likewise, if the start is <strong>17</strong> and the interval length <strong>4</strong>, the process would look like:</p>
  
  <p><strong>17 18 19 20</strong> /</p>
  
  <p><strong>21 22 23</strong> / 24</p>
  
  <p><strong>25 26</strong> / 27 28</p>
  
  <p><strong>29</strong> / 30 31 32</p>
  
  <p>which produces the checksum <strong>17^18^19^20^21^22^23^25^26^29</strong> == <strong>14</strong></p>
  
  <p><em>My solutions approach</em></p>
  
  <hr>
  
  <p>Using Recursion</p>
  
  <pre><code>import operator
  import sys
  
  sys.setrecursionlimit(20000)
  
  def answer(start, length):
      lst = [range(start+length*n, start+length*n+length) for n in xrange(length)]
      return my_reduce(lst, length)
  
  def my_reduce(lst, length):
      if not lst: return 0
      l = lst.pop(0)
      return reduce(operator.xor, l[:length], 0) ^ my_reduce(lst, length-1)
  </code></pre>
  
  <p>Iterative approach using a generator</p>
  
  <pre><code>def answer(start, length):
      return reduce(operator.xor, gen_nums(start, length))
  
  
  def gen_nums(start, length):
      l = length
      while l &gt; 0:
          for x in xrange(start, start+l):
              yield x
          start = start + length
          l = l - 1
  </code></pre>
  
  <p><em>Problem</em></p>
  
  <hr>
  
  <p><strong>My two approaches do not run fast enough.</strong></p>
  
  <p>They do fine for trivial calculations e.g the ones in the examples but take significantly more time when the interval length is large e.g <strong>1000</strong></p>
  
  <h2><strong>Questions</strong></h2>
  
  <ul>
  <li>What computer science concepts are being tested by this challenge?</li>
  <li>What is the right algorithmic approach?</li>
  <li>what are the right data structures to use?</li>
  </ul>
  
  <p>I need to understand why my solution performs poorly and what algorithm and data structures fit this challenge.</p>