Even better, store array A instead as a bit set, take the complement, then return the number of trailing zeros plus one.
That XOR Trick (2020)
121–130 of 243 posts
Re: That XOR Trick (2020)
#122Earlier quoted context omitted.
I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?
Since you asked this question in two different locations, I'll give a 2nd answer here. One way to construct a Reed Solomon code is to create a Vandemonde Matrix. 1 a^1 a^2 a^3 a^4 a^5 ... 1 a^2 a^4 a^6 a^8 a^10 ... 1 a^3 a^6 a^9 a^12 a^15 ... ... All of the "1" values are from a^0. As long as a^1, a^2, a^3... are distinct, then this matrix is invertible (aka: all rows / columns are linearly independent). In a GF(2^8)…
Thanks a lot for the detailed answer!
I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example).
Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible.
I see that many codes contain a parity bit (for example the extended Golay code), however I don't see how the operation of recovering "the missing number" could be implemented in terms of a code and its encoding/decoding algorithms.
I've found this on stackoverflow: https://stackoverflow.com/a/3492967/3868157
It describes a way to recover the missing number by constructing a Vandermonde matrix using the given numbers. This would correspond to constructing a generator matrix of a specific RS code [1]. However, after this I'm not so sure about the relation between encoding/decoding and recovering the missing number.
In the end they also factor a polynomial (that could be something analogous to the error locator polynomial?).
[1]: although I'm not sure if it's strictly an RS code
Re: That XOR Trick (2020)
#123A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…
The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty.
I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it's not a big downside.
Re: That XOR Trick (2020)
#124Earlier quoted context omitted.
Since you asked this question in two different locations, I'll give a 2nd answer here. One way to construct a Reed Solomon code is to create a Vandemonde Matrix. 1 a^1 a^2 a^3 a^4 a^5 ... 1 a^2 a^4 a^6 a^8 a^10 ... 1 a^3 a^6 a^9 a^12 a^15 ... ... All of the "1" values are from a^0. As long as a^1, a^2, a^3... are distinct, then this matrix is invertible (aka: all rows / columns are linearly independent). In a GF(2^8)…
Thanks a lot for the detailed answer! I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example). Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible. I see that many codes contain a parity bit (for example the extended Golay code)…
https://www.backblaze.com/blog/reed-solomon/
In particular, these two images:
* https://www.backblaze.com/blog/wp-content/uploads/2015/06/bl...
* https://www.backblaze.com/blog/wp-content/uploads/2015/06/RS...
Note: Backblaze here uses "vertical data" (G * data) instead of what I did earlier "horizontal data" in the form of (data*G). But otherwise, still a good blogpost.
------------
So if you have 5 data + 1 parity, you now have a 5x6 generator matrix, giving you one extra column for erasures.
If one column is erased, you replace the erased column with the parity column, creating a 5x5 matrix.
As long as all columns were linearly independent, the resulting 5x5 matrix remains invertable.
The specific matrix multiplications / inversions / operations are well documented in that blogpost.
-----------
EDIT: Erasure decoding is much easier than error decoding. Error decoding requires figuring out the "locator", and then applying the calculated errors at those locations. Since we already know the locations in an "erasure" situation, we can just manipulate the matrix in an obvious manner.
--------
EDIT2: Ah right, the "systematic form" of the Vandemonde-Reed Solomon construction is to perform Gaussian Elimination on the non-systematic matrix (with the goal of forming an identity-sub-matrix). After gaussian elimination, the "column of ones" (or the simple XOR) disappears. (Erm... row of ones in the Backblaze pictures)
So maybe the Golay code you're thinking of is a better example as a matrix with an explicit parity bit.
Re: That XOR Trick (2020)
#125I'd been using xor swapping for years as x ^= y ^= x ^= y; until some point it occurred to me that this has undefined behavior in C.
That's one thing missing from BASIC in other programming languages, the SWAP statement: SWAP x y
So few other languages have it, some languages even make it impossible to write a swap function by not supporting pass by reference or pointers. Python has something interesting except it requires typing the name of each variable twice
Re: That XOR Trick (2020)
#126Re: That XOR Trick (2020)
#127> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be mad…
This is a really neat result.
I bet Euler or Gauss already thought of it and the solution is somewhere in a book full of such solutions.
Re: That XOR Trick (2020)
#128Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…
n00b question: What is the ^= operator, and what language is it from?
Re: That XOR Trick (2020)
#129A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…
The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next addr…
Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?
Re: That XOR Trick (2020)
#130Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…
n00b question: What is the ^= operator, and what language is it from?
x ^= y is the same as x = x ^ y, with ^ being XOR. Bunch of languages have it, e.g. C, C++, Java, ...