trabajando con increíblemente grandes números .NET

Question

Estoy tratando de trabajar a través de problemas en projecteuler.net pero sigo corriendo en un par de problemas.

La primera es una cuestión de almacenar grandes cantidades de elementos en un List<t>.Sigo recibiendo OutOfMemoryException cuando el almacenamiento de grandes cantidades en la lista.

Admito que yo no podría estar haciendo estas cosas de la mejor manera, pero, ¿hay alguna manera de definir la cantidad de memoria de la aplicación se puede consumir?

Normalmente se bloquea cuando llego a 100.000.000 de elementos :S

En segundo lugar, algunas de las preguntas que requieren la adición de cantidades masivas.Yo uso ulong tipo de datos que creo que el número que se va a poner super grande, pero yo todavía se las arreglan para envolver pasado la mayor compatibles int y entrar en números negativos.

¿Tienes alguna sugerencias para trabajar con los increíblemente grandes números?

Answer 1

Considere System.Numerics.BigInteger .

Answer 2

Debe usar una clase de números grandes que use algunos principios matemáticos básicos para dividir estas operaciones. Esta implementación de una biblioteca C # BigInteger en CodePoject parece ser la más prometedora. El artículo tiene algunas buenas explicaciones de cómo funcionan también las operaciones con números masivos.

Ver también: Grandes enteros en C #

Answer 3

En lo que respecta al Proyecto Euler, puede estar ladrando el árbol equivocado si está alcanzando las excepciones OutOfMemory. Desde su sitio web:

  

Cada problema se ha diseñado de acuerdo con una & "; regla de un minuto &"; lo que significa que aunque puede llevar varias horas diseñar un algoritmo exitoso con problemas más difíciles, una implementación eficiente permitirá una solución que debe obtenerse en una computadora con poca potencia en menos de un minuto.

Answer 4

Como dijo el usuario Jakers, si está usando Big Numbers, probablemente lo esté haciendo mal.

De los problemas de ProjectEuler que he hecho, ninguno ha requerido matemática de números grandes hasta ahora. Se trata más de encontrar el algoritmo adecuado para evitar números grandes.

¿Quieres pistas? Publique aquí, y podríamos tener un interesante hilo de Euler iniciado.

Answer 5

¿Asumo que esto es C #? F # ha creado formas de manejar estos problemas (tipo BigInt y secuencias perezosas).

Puede usar ambas técnicas F # de C #, si lo desea. El tipo BigInt es razonablemente utilizable desde otros idiomas si agrega una referencia al ensamblaje principal de F #.

Las secuencias perezosas son básicamente enumeradores amigables con la sintaxis. Poner 100,000,000 elementos en una lista no es un gran plan, por lo que debe repensar sus soluciones para evitarlo. Si no necesita guardar información, ¡bótela! Si es más barato recalcularlo que almacenarlo, ¡tírelo!

Answer 6

Vea las respuestas en este hilo . Probablemente necesite usar una de las bibliotecas / clases de enteros grandes de terceros disponibles o esperar C # 4.0, que incluirá un tipo de datos nativo de BigInteger.

Answer 7

En cuanto a la cantidad de memoria que usará una aplicación, puede verificar la memoria disponible antes de realizar una operación utilizando clase MemoryFailPoint .

Esto le permite preasignar memoria antes de realizar la operación, para que pueda verificar si una operación fallará antes de ejecutarla.

Answer 8

No necesita usar BigInteger. Puede hacer este evento con una serie de cadenas de números.

class Solution
{

    static void Main(String[] args)
    {
        int n = 5;
        string[] unsorted = new string[6] { "3141592653589793238","1", "3", "5737362592653589793238", "3", "5" };

        string[] result = SortStrings(n, unsorted);

        foreach (string s in result)
            Console.WriteLine(s);
        Console.ReadLine();
    }
    static string[] SortStrings(int size, string[] arr)
    {

        Array.Sort(arr, (left, right) =>
        {

            if (left.Length != right.Length)
                return left.Length - right.Length;
            return left.CompareTo(right);
        });

        return arr;
    }
}

Answer 9

string Add(string s1, string s2)
{
        bool carry = false;
        string result = string.Empty;

        if (s1.Length < s2.Length)
            s1 = s1.PadLeft(s2.Length, '0');
        if(s2.Length < s1.Length)
            s2 = s2.PadLeft(s1.Length, '0');

        for(int i = s1.Length-1; i >= 0; i--)
        {
            var augend = Convert.ToInt64(s1.Substring(i,1));
            var addend = Convert.ToInt64(s2.Substring(i,1));
            var sum = augend + addend;
            sum += (carry ? 1 : 0);
            carry = false;
            if(sum > 9)
            {
                carry = true;
                sum -= 10;
            }
            result = sum.ToString() + result;
        }
        if(carry)
        {
            result = "1" + result;
        }

    return result;
}

Answer 10

No estoy seguro de si es una buena manera de manejarlo, pero yo uso el siguiente en mi proyecto.

Tengo un "doble theRelevantNumber" variable y un "int PowerOfTen" para cada elemento y en mi clase tengo un "int relevantDecimals" de la variable.

Así que...cuando grandes números se encontró con que son manejados como este:

En primer lugar se cambia a x,yyy forma.Así que si el número de 123456,789 fue inputed y el "powerOfTen" fue de 10, se podría empezar así:

theRelevantNumber = 123456,789 PowerOfTen = 10 El número fue entonces:123456,789*10^10

Luego se cambió a:1,23456789*10^15

Es entonces redondeado por el número de decimales (por ejemplo 5) a 1,23456 y, a continuación, guardar junto con "PowerOfTen = 15"

Cuando la adición o subracting números de cualquier número de fuera de la pertinente decimales son ignorados.Lo que significa que si usted toma:

1*10^15 + 1*10^10 se va a cambiar a 1,00001 si "relevantDecimals" es de 5, pero no va a cambiar en absoluto si "relevantDecimals" son 4.

Este método puede ayudar a lidiar con los números hasta doubleLimit*10^intLimit sin ningún problema, al menos para la programación orientada a objetos no es difícil seguir la pista de.