Python fast XOR over range algorithm

Question

There is a programming challenge that requires one to generate an XOR checksum based on sequence start number and an interval length.

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.

Example:

if the start number is 0 and the interval length is 3, the process would look like this:

0 1 2/

3 4 / 5

6 / 7 8

where the XOR (^) checksum is 0^1^2^3^4^6 == 2

Likewise, if the start is 17 and the interval length 4, the process would look like:

17 18 19 20 /

21 22 23 / 24

25 26 / 27 28

29 / 30 31 32

which produces the checksum 17^18^19^20^21^22^23^25^26^29 == 14

My solutions approach

Using Recursion

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)

Iterative approach using a generator

def answer(start, length):
    return reduce(operator.xor, gen_nums(start, length))


def gen_nums(start, length):
    l = length
    while l > 0:
        for x in xrange(start, start+l):
            yield x
        start = start + length
        l = l - 1

Problem

My two approaches do not run fast enough.

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 1000

Questions

What computer science concepts are being tested by this challenge?
What is the right algorithmic approach?
what are the right data structures to use?

I need to understand why my solution performs poorly and what algorithm and data structures fit this challenge.

Any solution evaluating term by term will do O(length²) operations. You do not need any data structure to speak of. Try to understand dd2's answer. Try to repeat the process with the terms that algorithm handles. — greybeard
– greybeard, Commented Oct 9, 2016 at 21:19

S.S. Anne · Accepted Answer · 2019-08-25 00:49:42Z

10

I am suggesting a simple optimization over your solution.

Use this method to get the xor of a range[a,b]

def f(a):
     res = [a, 1, a+1, 0]
     return res[a%4]

def getXor(a, b):
     return f(b) ^ f(a-1)

Now for a given interval you can compute XOR checksum in O(n) instead of O(n^2).

def gen_nums(start, length):
    l = length
    ans = 0
    while l > 0:
        ans^= getXor(start,start+l-1)
        start = start + length
        l = l - 1
    return ans

Explanation

Let us denote f(n)=1⊕2⊕3⊕⋯⊕n, where ⊕ denotes XOR operation. The XOR of all numbers between A and B can be represented by f(B)⊕f(A−1), because x⊕x=0

Now we can find out easily that,

Time Complexity - O(1)

reference

reference two

edited Aug 25, 2019 at 0:49

S.S. Anne

15.7k8 gold badges42 silver badges82 bronze badges

answered Oct 9, 2016 at 7:29

v78

2,96330 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

greybeard Over a year ago

(Good enough for me if you put the reference before the 1st code block, and/or give it a more descriptive label.)

sbrm1 Over a year ago

@ee2 Hey, this solution does not even work with the sample values given by the OP.

PM 2Ring Over a year ago

To fix gen_nums, put the l = l - 1 before ans^= getXor(start,start+l)

PM 2Ring Over a year ago

No worries. See here for a corrected version of your code, as well as an optimised version.

Collectives™ on Stack Overflow

Python fast XOR over range algorithm

Questions

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Questions

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related