4 ms·
Instead of sorting, just count the occurrences of the distinct values. For 8-bit values, this requires only 256 registers, each with a relatively small number o
by jiggawatts 3y ago
Instead of sorting, just count the occurrences of the distinct values. For 8-bit values, this requires only 256 registers, each with a relatively small number of bits. E.g.: if the maximum matrix size is 16K*16K, then only 14 bits per accumulator is required.
This is just Radix sort and is very easy to implement in digital circuits. It can even reuse the same adder circuits.
- daniel-cussen 3y agoSorting is very fast since i designed a sorting algorithm tailor-made for this problem, which is about as fast as your approach. Difference being the numbers are 32-bit, so iterating through the entire array of all possible 24-bit mantissas (i know they're 23 bit, but the implicit initial 1 of normal (vs denormal) values is explicit here) would be way too slow. Otherwise you'd be right, 8-bit values you can just use counting-sort, no problem. Or 14 bits, same deal. Now also notice there's a difference between the matrix size and the mantissa size, we care about the mantissa size, so it's 24 bits.