Estoy bastante seguro de que esto nunca será un problema. Sin embargo, todavía tengo curiosidad, ¿cuántas iteraciones puede generar una semilla determinada un número aleatorio antes de que su alcance se agote por completo y vuelva a generar los mismos números nuevamente?

Como ejemplo:

Supongamos que tiene una matriz que consta de ocho índices enteros; durante una iteración dada, el random.Next llenaría cada índice con un valor de 0-31. Y la prueba intenta ver cuánto tiempo tomaría generar una matriz perfecta de todos los 31.

Matemáticamente, las probabilidades son aproximadamente 1 en 1,099,511,627,776 por iteración para producir una matriz perfecta de todos los 31. Sin embargo, esto supone que el generador de números aleatorios C # podría incluso llegar al rango proyectado de 1 billón de iteraciones sin tener que retroceder sobre sí mismo.

Entonces, para resumir mi pregunta real, ¿podría la clase Aleatoria lograr la prueba que he presentado? ¿O alcanzaría una marca de mitad de camino y simplemente se condenaría al fracaso independientemente de cuántas iteraciones atraviese? ¿Cuál es exactamente el número de iteraciones antes de que se alcance el final del generador de números aleatorios? También quería mencionar que solo toma alrededor de 20 minutos generar con éxito una matriz de 6 31 perfectos. Esto fue probado por mí y verificado.

También debo mencionar que actualmente estoy ejecutando un mecanismo de prueba que está tratando de lograr esto. Hasta ahora, este es el informe actual, que se muestra cada minuto:

##### Report #####
Elapsed Simulation Time: 00:49:00.1759559
Total Iterations: 20784834152
Perfect Eight Success: 0
Failure: 20784834152
##### End Report #####

He estimado que el tiempo requerido para encontrar 1 conjunto perfecto de 31 es de aproximadamente 47 horas y 56 minutos para acercarse al rango de encontrar incluso 1 conjunto perfecto de 31. Eso es con mi computadora llenando mi matriz 383,500,572 cada minuto. Parece que esta prueba tomará mucho más tiempo de lo que originalmente proyecté.

Actualización de 2 horas

##### Report #####
Elapsed Simulation Time: 02:00:00.4483950
Total Iterations: 55655726300
Success: 0
Failure: 55655726300
##### End Report #####

Desearía haber roscado esto ... probablemente podría haber reducido el tiempo a la mitad ...

2
Krythic 11 mar. 2017 a las 21:58

2 respuestas

La mejor respuesta

Solo quería publicar mi código de prueba y explicar algunas cosas. Primero, aquí está mi código:

using System;
using System.Diagnostics;

namespace ConsoleApplication1
{
    public static class Program
    {

        public static long Success;
        public static long Failure;
        public static long TotalIterations;
        public static long TotalCallsToRandom;
        public static readonly int CurrentSeed = Environment.TickCount;
        public static Random Random = new Random(CurrentSeed);
        public static Stopwatch TotalSimulationTime = new Stopwatch();
        public static Stopwatch ReportWatchTime = new Stopwatch();
        public static bool IsRunning = true;

        //
        public const int TotalTestingIndices = 7;
        public const int MaximumTestingValue = 31;
        public const int TimeBetweenReports = 30000; // Report every 30 Seconds.
        //

        public static void Main(string[] args)
        {
            int[] array = new int[TotalTestingIndices];
            TotalSimulationTime.Start();
            ReportWatchTime.Start();
            while (IsRunning)
            {
                if (ReportWatchTime.ElapsedMilliseconds >= TimeBetweenReports)
                {
                    Report();
                    ReportWatchTime.Restart();
                }
                Fill(array);
                if (IsPerfect(array))
                {
                    Success++;
                    Console.WriteLine("A Perfect Array was found!");
                    PrintArray(array);
                    Report();
                    IsRunning = false;
                }
                else
                {
                    Failure++;
                }
                TotalIterations++;
            }
            Console.Read();
        }

        public static void Report()
        {
            Console.WriteLine();
            Console.WriteLine("## Report ##");
            Console.WriteLine("Current Seed: " + CurrentSeed);
            Console.WriteLine("Desired Perfect Number: " + MaximumTestingValue);
            Console.WriteLine("Total Testing Indices: " + TotalTestingIndices);
            Console.WriteLine("Total Simulation Time: " + TotalSimulationTime.Elapsed);
            Console.WriteLine("Total Iterations: " + TotalIterations);
            Console.WriteLine("Total Random.NextInt() Calls: " + TotalCallsToRandom);
            Console.WriteLine("Success: " + Success);
            Console.WriteLine("Failure: " + Failure);
            Console.WriteLine("## End of Report ##");
            Console.WriteLine();
        }

        public static void PrintArray(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i]);
                if (i != array.Length - 1)
                {
                    Console.Write(",");
                }
            }
        }

        /// <summary>
        /// Optimized to terminate quickly.
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static bool IsPerfect(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] != MaximumTestingValue)
                {
                    return false;
                }
            }
            return true;
        }

        public static void Fill(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = Random.Next(MaximumTestingValue + 1);
                TotalCallsToRandom++;
            }
        }
    }
}

Después de aproximadamente tres horas de prueba, he llegado a algunas realizaciones. Creo que es posible obtener ocho índices perfectos de 31 ... pero solo si tienes suerte dentro de los primeros mil millones de llamadas a Random.Next (). Sé que esto puede parecer algo subjetivo, pero es lo que he experimentado a través de estas pruebas. Nunca tuve 8-Perfect 31's, pero obtuve 7-Perfect 31's. La primera vez fue después de 13 minutos. Aquí está la impresión:

A Perfect Array was found!
31,31,31,31,31,31,31
## Report ##
Total Simulation Time: 00:13:32.4293323
Total Iterations: 7179003125
Success: 1
Failure: 7179003125
## End of Report ##

No lo codifiqué en ese momento para imprimirlo, pero esa impresión significaría que hubo 50,253,021,875 llamadas individuales a Random.NextInt (); Esto significa que la resolución se mantuvo hasta 50 mil millones de llamadas .

Y el otro 7-Perfect fue solo después de unos 30 segundos de ejecución del programa. Eso significa que hay "Good Seeds" para obtener este tipo de rareza con bastante rapidez. También realicé la prueba de los índices 7-Perfect durante treinta minutos y no obtuve ninguno. Se basa en la suerte, pero al mismo tiempo siento mucho que hay un umbral invisible; si no lo golpeas pronto, no sucederá en absoluto. Un póster anterior decía que la resolución de la clase Random es "281,474,976,710,656". Pero mis pruebas parecen concluir que la resolución puede ser mucho más pequeña que eso. Pruébelo usted mismo, comience con 4-6 índices (sucede en cuestión de segundos) y suba hasta 7 y 8. No es solo que aumente la probabilidad, es que hay un umbral ... o tal vez estoy equivocado. ¿Quién sabe?

0
Krythic 11 mar. 2017 a las 23:38

Ya hay suficientes comentarios. Aquí está la respuesta definitiva.

Primero : el RNG puede, en el mejor de los casos, operar con valores de 64 bits. Hay una cantidad finita de valores de 64 bits, por lo que, de acuerdo con el principio de casillero, con suficientes iteraciones (n> 2 ^ 64) definitivamente obtendrá al menos un valor repetitivo.

El algoritmo subyacente utiliza un número finito y arbitrario de parámetros para decidir el siguiente valor aleatorio. Si suponemos que hay N variables de estado, cada una con 64 bits, puede haber como máximo (2 ^ 64) ^ N estados internos diferentes. Como antes, con suficientes iteraciones, su RNG tendrá el mismo estado interno. Esto provocará un bucle, y ciertamente ocurrirá en algún momento. En cuanto a cuántas iteraciones se necesitan para retroceder, basta con decir que habrá más de lo que necesitará para la generación diaria de números aleatorios. Todavía no me he encontrado con ese ciclo (se ha generado durante 20 minutos seguidos en mi CPU i7, y si su código genera tantos números, probablemente esté haciendo algo muy mal).

Segundo : no sé unos ocho 31 seguidos, pero ese es solo un caso especial. Lo que estás preguntando, básicamente, es esto: dada una secuencia arbitraria S_QUERY de números, ¿generará el RNG S_QUERY?

Para responder, primero debemos notar que el RNG genera una secuencia finita S_RNG de números. Entonces la verdadera pregunta es esta: ¿S_QUERY es una subsecuencia de S_RNG? Como S_RNG es finito, solo puede tener finitamente muchas subsecuencias. Sin embargo, hay infinitos S_QUERY posibles para elegir, por lo que por cada RNG puede encontrar algunos S_QUERY que no pueden ser generados por ese RNG. En cuanto al caso especial de ocho 31, no lo sé y no puedo saberlo. Mantén ese código en funcionamiento y descúbrelo.

4
Arshia001 11 mar. 2017 a las 19:48