Sample code of the above idea. Not verified =]
import heapqueue
import strutils
import strformat
import bitops
import algorithm
proc findMinCollision*(nVec: int, xs: seq[float]): (float, seq[int]) =
var n = xs.len
# ps[i] = probability of co
Your problem can be viewed as noisy-channel encoding. Though in practice we map
a block to larger space, your case is mapping to a smaller space, but the
mathematical structure is the same. There is a family of coding call [linear
code](https://en.wikipedia.org/wiki/Linear_code) . Given you **do
As another example, if you had 48-bit addrs with FF's up top and 12-bit-aligned
(4096) say virtual mem page-aligned, then you only have 36 bits. So, if you
literally mask off the top 4 then instead of 64 Gigispots you'd have 4 GiSpots.
If you are doing DLL/shared library load addresses you may n
> is there anything else about this domain i can use to maximize the collision
> resistance of this mapping? say, a way to weight the lower bits more than the
> higher
I don't think you want any used bits to be weighted higher than other. In any
case you'd be better off with testing for your sp
If instead you took the lower bits of the full product of 42*42 of 86 bits
(easy to do - just multiply in a uint64 and then mask to get the lower 32),
then you would get less bit mixing, but more resistance in the small..like (I
_think_ ) guaranteed non-collision of hashes from all or almost all
I mean, if you really want you could assume 16-byte (SSE land) alignment from
allocators and take the 42 bits you have left into two 32-bit misaligned
numbers (say upper 32 and lower 32 of that 42), and then multiply those to
spread them over the full 64-bit register and then mask out the upper
It is important here to distinguish between collision resistance in terms of
like a "self avoiding random walk" \- i.e. minimizing collision, and just
"being close to random".
Assuming you mean the latter, the regular `hash(uint64)` in the stdlib should
be quite resistant when given 32-bit inpu
this isn't Nim specific, of course, but how do i design a mapping from pointers
in a single process's address space to int32 to minimize the likelihood of
collision?
To start with, i know that only the lower 48bits are used.
and if i know the alignment of the pointer type i might be able to eli
