Checksum for an integer array?

Question

I have an array of size 4,9,16 or 25 (according to the input), and the numbers in the array are the same, but less by one (if the size of the array is 9, then the largest element in the array will be 8) the numbers start at 0 and I wanted would do some kind of algorithm to create some checksum for the array so that I can compare that the 2 arrays are equal without looping the whole array and checking each element one by one.

Where can I get this information? I need something as simple as possible. Thanks.

edit: just to understand what I want:

-All the numbers in the array are different, so [0,1,1,2] is not valid, because there is a repeating element (1)

- the position of the numbers matters, therefore [0,1,2,3] does not coincide with [3,2,1,0]

- the array will contain the number 0, so this should also be taken into account.

EDIT:

Ok, I tried to implement the Fletcher algorithm: http://en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){ int i; int sum1=0; int sum2=0; for(i=0;i<size;i++){ sum1=(sum1+array[i])%255; sum2=(sum2+sum1)%255; } return (sum2 << 8) | sum1; } 

Honestly, I have no idea what the return line does, but unfortunately the algorithm does not work. For arrays [2,1,3,0] and [1,3,2,0] I get the same checksum.

EDIT2:

here is another Adler checksum http://en.wikipedia.org/wiki/Adler-32#Example_implementation

 #define MOD 65521; unsigned long adler(int array[], int size){ int i; unsigned long a=1; unsigned long b=0; for(i=0;i<size;i++){ a=(a+array[i])%MOD; b=(b+a)%MOD; } return (b <<16) | a; } 

This also does not work. Arrays [2,0,3,1] and [1,3,0,2] generate the same checksum. I'm losing hope here, any ideas?

Answer 1

Take the case of your array of 25 integers. You explain that it can contain any permutations of unique integers from 0 to 24. According to this page , there are 25! (25 factorials) of possible permutations, that is, 15511210043330985984000000. More than 32-bit integer may be present.

The conclusion is that you will have a collision, no matter how hard you try.

Now, here is a simple algorithm that takes position into account:

 int checksum(int[] array, int size) { int c = 0; for(int i = 0; i < size; i++) { c += array[i]; c = c << 3 | c >> (32 - 3); // rotate a little c ^= 0xFFFFFFFF; // invert just for fun } return c; } 

Answer 2

I think what you want in response to the following thread:

Quick permutation → number → permutation mapping algorithms

You simply take the number to which your permutation has been reassigned, and take it as your checksum. Since each permutation has exactly one checksum, it cannot be less than a checksum that does not contain conflicts.

Answer 3

How about a checksum of a weighted sum? Let's take an example for [0,1,2,3]. First select the seed and limit, let me select the seed as 7 and the limit as 10000007.

 a[4] = {0, 1, 2, 3} limit = 10000007, seed = 7 result = 0 result = ((result + a[0]) * seed) % limit = ((0 + 0) * 7)) % 10000007 = 0 result = ((result + a[1]) * seed) % limit = ((0 + 1) * 7)) % 10000007 = 7 result = ((result + a[2]) * seed) % limit = ((7 + 2) * 7)) % 10000007 = 63 result = ((result + a[3]) * seed) % limit = ((63 + 3) * 7)) % 10000007 = 462 

Your checksum is 462 for this [0, 1, 2, 3]. Link http://www.codeabbey.com/index/wiki/checksum

Answer 4

For an array of N unique integers from 1 to N, just adding elements will always be N * (N + 1) / 2. Therefore, the only difference is ordering. If by “checksum” you mean that you are experiencing some collisions, then one way is to summarize the differences between consecutive numbers. So, for example, the delta checksum for {1,2,3,4} is 1 + 1 + 1 = 3, but the delta checksum for {4,3,2,1} is -1 + -1 + - 1 = -3.

No requirements for collision speed or computational complexity were made, but if this does not fit above, I recommend a position- specific checksum

Answer 5

From what I understand, your array contains a permutation of numbers from 0 to N-1 . One checksum that will be useful is the rank of the array in its lexicographic order. What does it mean? Given 0, 1, 2 you have possible permutations

  1: 0, 1, 2 2: 0, 2, 1 3: 1, 0, 2 4: 1, 2, 0 5: 2, 0, 1 6: 2, 1, 0 

The checksum will be the first number and is calculated when the array is created. There are solutions proposed in

Find the index of a given permutation in the list of permutations in lexicographic order

which may be useful, although apparently the best algorithm has quadratic complexity. To improve it to linear complexity, you should cache factorial values ​​before starting work.

Advantage? ZERO.

EDIT: Calculation The value is similar to the polynomial estimate, where the factorial is used for the monomial instead of energy. So the function

 f(x0,....,xn-1) = X0 * (0!) + X1 * (1!) + X2 * (2!) +...+ Xn-1 * (n-1!) 

The idea is to use each value to get a subrange of permutations, and with sufficient values ​​you define a unique permutation.

Now for the implementation (for example, one of the polynomial):

• precalculate 0! .... to n-1! at the beginning of the program
• Each time you install an array, you use f (elements) to calculate its checksum
• you compare in O (1) with this checksum