3

Basically, I would like help designing an algorithm that takes a given number, and returns a random number that is unrelated to the first number. The stipulations being that a) the given output number will always be the same for a similar input number, and b) within a certain range (ex. 1-100), all output numbers are distinct. ie., no two different input numbers under 100 will give the same output number.

I know it's easy to do by creating an ordered list of numbers, shuffling them randomly, and then returning the input's index. But I want to know if it can be done without any caching at all. Perhaps with some kind of hashing algorithm? Mostly the reason for this is that if the range of possible outputs were much larger, say 10000000000, then it would be ludicrous to generate an entire range of numbers and then shuffle them randomly, if you were only going to get a few results out of it.

Doesn't matter what language it's done in, I just want to know if it's possible. I've been thinking about this problem for a long time and I can't think of a solution besides the one I've already come up with.

Edit: I just had another idea; it would be interesting to have another algorithm that returned the reverse of the first one. Whether or not that's possible would be an interesting challenge to explore.

Maurdekye
  • 3,597
  • 5
  • 26
  • 43
  • you can do it via some simple calculations, and caching some piece of information (mainly, which random number was returned for input X, so that you can have the consistent return values you asked for). – MaxOvrdrv Dec 22 '15 at 14:45
  • 1
    I would prefer if no caching of any kind were done at all. Besides, that algorithm may become inefficient after a while, when a random result would have to be generated multiple times to make sure it doesn't match any other answers. Also, this does not preserve the similarity between runtimes. A purely mathematical result would not only give the same output for an input between different runtimes, but on different computers entirely as well. That's the kind of solution i'm looking for. – Maurdekye Dec 22 '15 at 14:48
  • You're looking for a [multiplicative inverse](https://en.wikipedia.org/wiki/Multiplicative_inverse). – Jim Mischel Dec 22 '15 at 14:49
  • Would you care to put answers, even simple ones, as answers instead of comments? – Roberto Dec 22 '15 at 14:50
  • No, i'm not Jim. The input and output numbers ought to have zero relation to one another, other than the algorithm. It should be akin to a random generation algorithm. – Maurdekye Dec 22 '15 at 14:51
  • @Maurdekye: If you scroll down to the "Applications" section of that article, you'll see this: **The expansion of the reciprocal 1/q in any base can also act as a source of pseudo-random numbers.** See [A practical use of multiplicative inverses](http://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/) for an example. – Jim Mischel Dec 22 '15 at 14:56
  • ok so basically you're looking for a kind of "seed" mechanism... e.g.: if the seed is X, then the result of the calculation is always Y... however, i do not know of any algorithm/seeder that would also return the "same result for similar seeds" ... that is the piece that is contradicting a bit in your requirements... – MaxOvrdrv Dec 22 '15 at 14:57
  • Huh, I think that may be relevant to my problem Jim. I'll look into it. Although I'd prefer if you post it as an answer. – Maurdekye Dec 22 '15 at 15:00
  • 1
    The question is bizarre. You ask for a relation between numbers such that the numbers are *unrelated except for the relation*. I can't think of how to distinguish between relationships where the related numbers are unrelated except for the relationship, and relationships where the related numbers are related in ways other than the relationship. How ought one to begin to answer this question? – Eric Lippert Dec 23 '15 at 04:32
  • You could try Skip32 Encryption (warning: do not use for actual encryption), but a multiplicative inverse is a much better fit. – Brian Dec 23 '15 at 14:19

3 Answers3

1

This sounds like a non-repeating random number generator. There are several possible approaches to this.

As described in this article, we can generate them by selecting a prime number p and satisfies p % 4 = 3 that is large enough (greater than the maximum value in the output range) and generate them this way:

int randomNumberUnique(int range_len , int p , int x)
    if(x * 2 < p)
       return (x * x) % p
    else
       return p - (x * x) % p

This algorithm will cover all values in [0 , p) for an input in range [0 , p).

  • I tried using your method, but the results were not unique. Using a range limit of 101, I generated all numbers from 0 to 100 and there were only 51 unique results. – Maurdekye Dec 22 '15 at 16:41
  • @Maurdekye sry, i've forgotten a property of `p`. I've edited the post. The code itself works just fine, if `p` satisfies `p % 4 = 3`. It works with `p = 103` for example. –  Dec 22 '15 at 17:32
  • So p has to both be prime and one less than a divisor of 4? that's a decent number of stipulations for a range limit. Is it possible for an arbitrary limit without those requirements? – Maurdekye Dec 22 '15 at 20:16
  • @Maurdekye sure. Only p needs to meet those constraints. The range itself can have an arbitrary limit as long as the maximum-value is smaller than p. Only some values that are in range won't be covered, if p is greater than the range-limit. –  Dec 23 '15 at 01:09
0

You can not have completely unrelated (particularly if you want the reverse as well).

There is a concept of modulo inverse of a number, but this would work only if the range number is a prime, eg. 100 will not work, you would need 101 (a prime). This can provide you a pseudo random number if you want.

Here is the concept of modulo inverse:

If there are two numbers a and b, such that

(a * b) % p = 1

where p is any number, then

a and b are modular inverses of each other.

For this to be true, if we have to find the modular inverse of a wrt a number p, then a and p must be co-prime, ie. gcd(a,p) = 1

So, for all numbers in a range to have modular inverses, the range bound must be a prime number.

A few outputs for range bound 101 will be:

1 == 1
2 == 51
3 == 34
4 == 76
etc.

EDIT:

Hey...actually you know, you can use the combined approach of modulo inverse and the method as defined by @Paul. Since every pair will be unique and all numbers will be covered, your random number can be:

random(k) = randomUniqueNumber(ModuloInverse(k), p)      //this is Paul's function
vish4071
  • 5,135
  • 4
  • 35
  • 65
  • Very interesting. Although you seem to have a relatively complete answer, I have also been linked [this article](http://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/) which seems to say that it *is* possible to have a range of arbitrary size that's not a prime number. I'll continue looking into the problem, unless there's something you have to say about it. – Maurdekye Dec 22 '15 at 15:13
  • @Maurdekye, please look at the EDIT (in answer). It might be of help. – vish4071 Dec 23 '15 at 06:30
0

Here's an example in C#:

    private void DoIt()
    {
        const long m = 101;
        const long x = 387420489; // must be coprime to m

        var multInv = MultiplicativeInverse(x, m);

        var nums = new HashSet<long>();
        for (long i = 0; i < 100; ++i)
        {
            var encoded = i*x%m;
            var decoded = encoded*multInv%m;
            Console.WriteLine("{0} => {1} => {2}", i, encoded, decoded);
            if (!nums.Add(encoded))
            {
                Console.WriteLine("Duplicate");
            }
        }
    }

    private long MultiplicativeInverse(long x, long modulus)
    {
        return ExtendedEuclideanDivision(x, modulus).Item1%modulus;
    }

    private static Tuple<long, long> ExtendedEuclideanDivision(long a, long b)
    {
        if (a < 0)
        {
            var result = ExtendedEuclideanDivision(-a, b);
            return Tuple.Create(-result.Item1, result.Item2);
        }
        if (b < 0)
        {
            var result = ExtendedEuclideanDivision(a, -b);
            return Tuple.Create(result.Item1, -result.Item2);
        }
        if (b == 0)
        {
            return Tuple.Create(1L, 0L);
        }
        var q = a/b;
        var r = a%b;
        var rslt = ExtendedEuclideanDivision(b, r);
        var s = rslt.Item1;
        var t = rslt.Item2;
        return Tuple.Create(t, s - q*t);
    }

That generates numbers in the range 0-100, from input in the range 0-100. Each input results in a unique output.

It also shows how to reverse the process, using the multiplicative inverse.

You can extend the range by increasing the value of m. x must be coprime with m.

Code cribbed from Eric Lippert's article, A practical use of multiplicative inverses, and a few of the previous articles in that series.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351