Print Story My dream() function.
Puzzles & Riddles
By dark nowhere (Tue Mar 06, 2007 at 05:37:34 AM EST) (all tags)
For a while now I've been noticing that a certain odd little pair of functions would be useful in a variety of applications. Programmers can consider this a challenge if they like (your reward is kudos and esteem.)

Details inside.



The I/O is fairly simple. Given a range and a number within that range, produce another number with within that range. Distribution should be essentially pseudorandom, not succession or anything like that. The trick is that the complimentary function has to reverse the first function. So, with the range implied, b(a(x)) gets x.

The added difficulty is that all values within the range have to be a product of the function, with the whole range being exhausted from a single starting point (no gaps), and it has to return to its starting point. I don't mind if ranges are increased in blocks.

I haven't started thinking deeply about this, but I thought I'd share it before I forget about it.

< that's the story of my life | BBC White season: 'Rivers of Blood' >
My dream() function. | 11 comments (11 topical, 0 hidden) | Trackback
Reverse the fist() function. by ambrosen (3.00 / 1) #1 Tue Mar 06, 2007 at 05:56:22 AM EST
My understanding is that when the fist() function has been inappropriately applied, there's very little chance of any further function application to the receiving structure, let alone reversing the one originally applied.</smutty mind>

What on earth are you on about? by komet (3.75 / 4) #2 Tue Mar 06, 2007 at 06:00:58 AM EST
The reverse of the fist() function is the goatse() function. Don't they teach you anything at University nowadays?

--
<ni> komet: You are functionally illiterate as regards trashy erotica.
[ Parent ]
rand() and lookup tables [nt] by gazbo (3.00 / 1) #3 Tue Mar 06, 2007 at 06:01:09 AM EST


I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

Then you're by yicky yacky (4.00 / 1) #5 Tue Mar 06, 2007 at 06:36:06 AM EST

yoked to the implementation of the rand function which, IIRC, only specifies that the period must be greater than or equal to 2^32. There's no reason it couldn't be 2^bazillion. I'm not disputing the idea -- which is valid -- just saying that, for any given state of the tech, you can make the look-up intractable by specifying a large enough bazillion. If you knew the PRNG algorithm (pace The Fool), you could possibly do the reverse operation algorithmically.
----
Vacuity abhors a vacuum.

[ Parent ]
Well by gazbo (2.00 / 0) #9 Tue Mar 06, 2007 at 07:33:11 AM EST
I considered a solution using modular arithmetic, but deliberately discounted it because it didn't really seem to fit with the pseudo-random spec.  Of course I don't really know how random it has to be to be useful, but that was the reason.

I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

[ Parent ]
LCG is random enough, by dark nowhere (2.00 / 0) #10 Tue Mar 06, 2007 at 07:42:06 AM EST
I believe it is anyway. The problem is that it doesn't seem to be exhaustive in the way I want. I should be able to start with (say) 1 and get every number in the range with the new succession.

I'm generally against lookup tables. It seems to take the magic out of it.

Chill out, snowflake.

[ Parent ]
Simple answer by The Fool (4.00 / 2) #4 Tue Mar 06, 2007 at 06:15:33 AM EST
You're looking for a simple linear congruential PRNG. There's a good reason why these are considered to be bad choices for use in crypto systems.

int get_next(int number) {
    return (number * BASE) % MODULUS;
}

int get_previous(int number) {
    return (number * BASE_INVERSE) % MODULUS;
}

where BASE is defined to be some large number coprime to MODULUS, and BASE_INVERSE is the multiplicative inverse of BASE in the modulo MODULUS ring.

(For example, if BASE is 3 and MODULUS is 11, BASE_INVERSE is some number such that:

(3 * BASE_INVERSE) % 11 = 1

So BASE_INVERSE = 4 works here.

get_next(5) = (5*3) % 11 = 4
get_previous(4) = (4*4) % 11 = 5

I'll have to check it out. by dark nowhere (2.00 / 0) #6 Tue Mar 06, 2007 at 06:59:51 AM EST
I'd no idea that this was something that was already solved. I'll have to say I'm not surprised to see modulus operations.

Chill out, snowflake.

[ Parent ]
Oh also... by dark nowhere (2.00 / 0) #7 Tue Mar 06, 2007 at 07:01:37 AM EST
I wasn't thinking about crypto applications. Usually simple reversible things are bad for crypto, or so my intuition tells me.

Chill out, snowflake.

[ Parent ]
Ok, I see a problem by dark nowhere (2.00 / 0) #8 Tue Mar 06, 2007 at 07:27:47 AM EST
It's not exhaustive from a single starting point. I think I see a way to fix that, though. Thanks for the great starting point regardless!

Chill out, snowflake.

[ Parent ]
Yeah, by ambrosen (2.00 / 0) #11 Wed Mar 07, 2007 at 01:32:36 AM EST
I was browsing through here and thought 'I can solve that' and then I notice you've done it.

Surely you want to % RANGESIZE though, and to multiply by a larger number coprime with RANGESIZE, then add an offsetting factor, though.

Mod RANGESIZE to make it exhaustive and multiply by larger number to avoid repeating within RANGESIZE iterations. The multiplicative inverse is left for the reader.

[ Parent ]
My dream() function. | 11 comments (11 topical, 0 hidden) | Trackback