Re: Feistel cipher, shorter string and hex to int

Ivan Sergio Borgonovo wrote:

> I don't get the 1366.0 and the 714025.0.
> Writing 1366.0 isn't going to use float arithmetic?

Yes, that's on purpose. Now that you mention it, I think that 1366.0
could be an integer instead, but the division by 714025 and
multiplication by 32767 have to be floating point operations.

> I'm going to see if using bigint is going to make any difference in
> speed.

If you're after more speed, using the C language may be the solution.

> Finally... if I were (and I'm not) interested in using 30 bit,
> should I turn that *32767 into a *16383?
> For shift and bit mask it looks more obvious.

To generate a 31 bits (positive) result from a 30 bits input, I would
modify the initialisation of the 16 bits blocks so that each of them
has the most significant bit set to 0, but without loosing any of the
30 bits. The MSB bits have to be kept at 0 throughout the algorithm.

So I'd to that:

l1:= ((value >> 16) & 16383) | (value&32768);
r1:= value&32767;

and indeed reduce the output range of the function:

r2:=l1 # ((((1366.0*r1+150889)%714025)/714025.0)*16383)::int;

the rest being identical excepts that it could now return int (and it
would be unsigned) instead of bigint.
I haven't tested that variant, though.

> Do you remember the name of this particular F?

Not sure it has a specific name, but you'll find related stuff by
searching for "linear congruential generator".

> Everything else seems to need more processing at no real added value.
> Turning the int into base 32 [0-9A-N] with plpgsql looks expensive
> just to shorten the string to 4 char.

Note that 4 chars would cover a range of 32^4, which is only about one
million different values.
I think you'd need 7 chars to express up to 2^31 in base 32, because
32^7 < 2^31 < 32^6

Best regards,
--
Daniel
PostgreSQL-powered mail user agent and storage:
http://www.manitou-mail.org