** Am I unique **

Today I consider the idea of uniqueness of identities and mixing identities. Basically the problem is that for a set of objects I want to assign an identity or a set of identities so that construction of identities of combinations of the objects are fast enough and also give enough randomness to be used as keys. It is a good exercise to test out the generator framework and as always working gives inspiration.

So the first question you should ask is do I need to guarantee uniqueness? Can I assume that collisions will be negligible. Sometimes clashes is rare and a cheap extra check at the end of the analysis can be used to verify correctness of the analysis and in the minuscule number of clash cases a mitigating strategy can be used.

Hmm, assume that we have objects X1,X2,... and identities I1,I2,... What I'm wondering is if one can use random double precision numbers between in [0.1,0.9] as identities. Then the combination [X1,X2] could be build by simply use (R * X1 + (1-R)*X2), with =.1<R>0.9 a random double. This is rather fast to compute and should mix well and a key should be possible to extract from this operation. Anyone knows about the properties of such an approach?

Here is another approach where clashes do not happen for correct choices of p and q which also has the potential to mix well.

q**(k1*k2*k3..km) mod p,if you are going to mix X:s and Y:s (X x Y) you could generate identities q**i mod p, for X and q**(k1*i) mod p, for Y and just multiply the identities modulo p to get new identities. This could mix well, lets happily hack some generators for this...

(define id-gen K -> (mlet ((N (for X in (li K) (mul X))) (P (get-prime N)) (Q (MOD (get-prime (* 100 N)) P)) (R (for X in (li K) (mk-ar (.powmod Q ** (mul X 1..) mod P)))))The input K is a list that describes the number of objects in each channel (number of X:s , number of Y:s) and so on. N is simply the total number of combinations-. P will be a prime larger then N according to some method (like the first one) Q is just another prime number (we assume that P >> 100 here) R will be q**1, q**k1, q**(k1*k2),... not including N. The 1.. in mul tells the transformer to start from 1.., eg 1, k1, k1*k2, etc. powmod is just a function to quickly evaluate q**k (g**k = q**(k/2) * q**(k/2)).[P (slet ((N (for X in (ar R) (mk-ar X)))) (mk-g [(/. IS (for I in (li IS) (coll (.NTH N I)))) (sig IS (for I in (li IS) (.SETF (.ELT R I) (.MOD (.* (.ELT N I) (.ELT R I)) P)))) (/. IS (for I in (li IS) (coll (.NTH N I)))) (/. _ (setok)) |(pop-like)]))])

The slet is a let construct that allows the value of N to be pop and pushable e.g. internal state. N just initializes to a copy of R. mk-g will generate the generator (this is poor mans object system but it's prototyping so I don't care very much and the functionality is similar) Now the list should be a list of lambdas according to 1. get the value e.g. the identity and we have a selector here that picks up the correct identity channel (identity for X or for Y). 2. finding the next value. just updates q^(i*k) -> q^/(++i k) mod p. Sig is a macro mainly introduce code so that we only take the next value ones in each iteration. the third one is the final value and the fourth is the construct to make sure the updating is correct. and the rest is basically memory management. Not a perfect interface but you never get it right if you do not try.

What I learned from my work with this was that it's nice to have lambdas that generate generators e.g.

(mlet (([P G] (id-gen [10 1000 1000])) (Fxy (./. (_) (next [1 2] G))) (Ff (./. (_) (next [0] G)))) (gen Key in (li H) (coll (switch-if (.= Key f) (Ff) (Fxy)))))P is the prime number used in the modulo code, now /. is the lambda construct in qi, and ./. is a similar lambda construct for generators. So G will be a generator and Fxy will be a generator generating lambda that captures in the closure G. I coded ./. by using something like,

(defmacro ./. [X Y] -> (mlet ((F (gensym "f")) (F. (gensym "f.")) (F.. (gensym "f.."))) (do (eval (splice [[*X* X]] [define F *X* -> Y])) (.mk F F. F.. X id) F.)))This is ugly but it should work. (I know pure lisp can express this logic better) .mk basically constructs a point-wise generator generating function F. and a lazy and delayable version of it in F..

Enjoy!