trabalhando com incrivelmente grandes números em .NET

Question

Eu estou tentando trabalhar com os problemas em projecteuler.net mas eu continuo correndo em um par de problemas.

O primeiro é uma questão de armazenar grandes quanities de elementos em um List<t>. Recebo OutOfMemoryException, quando armazenar grandes quantidades na lista.

Agora, eu admito que eu não poderia estar fazendo essas coisas da melhor maneira, mas, há alguma maneira de definir o quanto de memória o aplicativo pode consumir?

Ele geralmente cai quando eu chegar abour 100.000.000 elementos: S

Em segundo lugar, algumas das perguntas que requerem a adição de um número maciço. Eu uso tipo de dados ulong onde eu acho que o número vai ficar super grande, mas eu ainda conseguem quebrar passado a maior int apoiado e entrar em números negativos.

Você tem alguma dica para trabalhar com incrivelmente grandes números?

Answer 1

System.Numerics.BigInteger .

Answer 2

Você precisa usar uma grande classe número que usa alguns princípios básicos de matemática para dividir estas operações se. Este de uma biblioteca C # BigInteger em CodePoject parece ser a mais promissora. O artigo tem algumas boas explicações de como operações com números enorme trabalho, também.

Veja também: inteiros grandes em C #

Answer 3

Quanto Projeto Euler vai, você pode estar latindo para a árvore errada, se você está batendo exceções OutOfMemory. De seu site:

Cada problema foi projetado de acordo com uma "regra de um minuto", o que significa que, embora possa demorar várias horas para projetar um algoritmo bem sucedido com problemas mais difíceis, uma implementação eficiente permitirá uma solução a ser obtido em uma modesta computador alimentado em menos de um minuto.

Answer 4

Como Jakers usuário disse, se você estiver usando Big Numbers, provavelmente você está fazendo errado.

Entre os problemas Project Euler eu fiz, nenhum required-número grande de matemática até agora. É mais sobre encontrar o algoritmo apropriado para evitar big-números.

Quer dicas? Poste aqui, e nós pode ter um interessante Euler-thread iniciado.

Answer 5

Eu suponho que este é C #? F # foi construído em maneiras de lidar com ambos os problemas (tipo BigInt e seqüências preguiçoso).

Você pode usar ambas as técnicas F # de C #, se você gosta. O tipo BigInt é razoavelmente utilizável de outras línguas, se você adicionar uma referência para o núcleo F # montagem.

seqüências preguiçosos são basicamente apenas recenseadores amigáveis ??sintaxe. Colocando 100.000.000 elementos em uma lista não é um grande plano, então você deve repensar suas soluções para contornar isso. Se você não precisa manter as informações em torno, jogá-lo fora! Se é mais barato para recalcular-lo do que armazená-lo, jogá-lo fora!

Answer 6

Veja as respostas neste fio . Você provavelmente precisará usar um dos terceiros bibliotecas grande inteiros / classes disponíveis ou esperar para C # 4.0, que incluirá um tipo de dados nativo BigInteger.

Answer 7

Quanto definir a quantidade de memória de um aplicativo irá usar, você pode verificar a memória disponível antes de realizar uma operação usando a MemoryFailPoint classe.

Isso permite que você memória preallocate antes de fazer a operação, para que possa verificar se uma operação irá falhar antes de executá-lo.

Answer 8

Você não precisa usar BigInteger Você pode fazer este evento com matriz de cadeia 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

Eu não tenho certeza se é uma boa maneira de lidar com ele, mas eu uso o seguinte no meu projeto.

Eu tenho uma variável "double theRelevantNumber" e um "int PowerOfTen" para cada item e na minha classe relevante eu tenho um "relevantDecimals int" variável.

Então ... quando um grande número for encontrado eles são tratados como isto:

Primeiro, eles são alterados para x, forma yyy. Então, se o número 123456.789 foi inputed eo "powerOfTen" tinha 10 anos, ele iria começar assim:

theRelevantNumber = 123456.789 PowerOfTen = 10 O número foi então: 123456,789 * 10 ^ 10

Em seguida, é alterada para: 1,23456789 * 10 ^ 15

Em seguida, é arredondado ao número de casas decimais relevantes (por exemplo 5) a 1,23456 e então guardada juntamente com "PowerOfTen = 15"

Ao adicionar ou subtraindo números juntos, qualquer número fora das casas decimais relevantes são ignoradas. Significado se tomar:

1 * 10 ^ 15 + 1 * 10 ^ 10 ele vai mudar a 1,00001 se "relevantDecimals" é 5, mas não vai mudar em tudo se "relevantDecimals" são 4.

Este método torná-lo capaz de lidar com números até doubleLimit * 10 ^ intLimit sem qualquer problema, e pelo menos por OOP não é tão difícil de acompanhar.