在.NET中使用令人难以置信的大数字

时间:2022-01-02 16:47:57

I'm trying to work through the problems on projecteuler.net but I keep running into a couple of problems.

我正在尝试解决projecteuler.net上的问题,但我一直遇到一些问题。

The first is a question of storing large quanities of elements in a List<t>. I keep getting OutOfMemoryException's when storing large quantities in the list.

第一个问题是在List 中存储大量元素。在列表中存储大量数据时,我一直收到OutOfMemoryException。

Now I admit I might not be doing these things in the best way but, is there some way of defining how much memory the app can consume?

现在我承认我可能没有以最好的方式做这些事情但是,有没有办法定义应用程序可以消耗多少内存?

It usually crashes when I get abour 100,000,000 elements :S

当我满足100,000,000个元素时,它通常会崩溃:S

Secondly, some of the questions require the addition of massive numbers. I use ulong data type where I think the number is going to get super big, but I still manage to wrap past the largest supported int and get into negative numbers.

其次,一些问题需要增加大量数字。我使用ulong数据类型,我认为这个数字会变得非常大,但我仍然设法绕过最大的受支持的int并进入负数。

Do you have any tips for working with incredibly large numbers?

你有任何使用难以置信的大数字的技巧吗?

9 个解决方案

#1


19  

Consider System.Numerics.BigInteger.

考虑System.Numerics.BigInteger。

#2


27  

You need to use a large number class that uses some basic math principals to split these operations up. This implementation of a C# BigInteger library on CodePoject seems to be the most promising. The article has some good explanations of how operations with massive numbers work, as well.

您需要使用一个使用一些基本数学原理的大量类来拆分这些操作。在CodePoject上实现C#BigInteger库似乎是最有希望的。本文对大量数字的操作如何运作有一些很好的解释。

Also see: Big integers in C#

另见:C#中的大整数

#3


11  

As far as Project Euler goes, you might be barking up the wrong tree if you are hitting OutOfMemory exceptions. From their website:

就Euler项目而言,如果你遇到OutOfMemory异常,你可能会咆哮错误的树。从他们的网站:

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

每个问题都是根据“一分钟规则”设计的,这意味着尽管设计一个成功的算法可能需要几个小时才能解决更加困难的问题,但是有效的实施方案将允许在适当的计算机上获得解决方案。不到一分钟。

#4


4  

As user Jakers said, if you're using Big Numbers, probably you're doing it wrong.

正如用户Jakers所说,如果你使用大数字,可能你做错了。

Of the ProjectEuler problems I've done, none have required big-number math so far. Its more about finding the proper algorithm to avoid big-numbers.

在我所做的ProjectEuler问题中,到目前为止还没有人需要大数学数学。它更多的是找到适当的算法来避免大数字。

Want hints? Post here, and we might have an interesting Euler-thread started.

想提示吗?发布在这里,我们可能会有一个有趣的欧拉线程开始。

#5


3  

I assume this is C#? F# has built in ways of handling both these problems (BigInt type and lazy sequences).

我认为这是C#? F#内置了处理这些问题的方法(BigInt类型和延迟序列)。

You can use both F# techniques from C#, if you like. The BigInt type is reasonably usable from other languages if you add a reference to the core F# assembly.

如果您愿意,可以使用C#中的两种F#技术。如果添加对核心F#程序集的引用,则BigInt类型可以从其他语言中合理使用。

Lazy sequences are basically just syntax friendly enumerators. Putting 100,000,000 elements in a list isn't a great plan, so you should rethink your solutions to get around that. If you don't need to keep information around, throw it away! If it's cheaper to recompute it than store it, throw it away!

懒惰序列基本上只是语法友好的枚举器。将100,000,000个元素放在列表中并不是一个好计划,因此您应该重新考虑您的解决方案以解决这个问题。如果您不需要保留信息,请将其扔掉!如果重新计算它比存储它便宜,扔掉它!

#6


1  

See the answers in this thread. You probably need to use one of the third-party big integer libraries/classes available or wait for C# 4.0 which will include a native BigInteger datatype.

请参阅此主题中的答案。您可能需要使用可用的第三方大整数库/类之一,或等待包含本机BigInteger数据类型的C#4.0。

#7


1  

As far as defining how much memory an app will use, you can check the available memory before performing an operation by using the MemoryFailPoint class.

至于定义应用程序将使用多少内存,您可以在使用MemoryFailPoint类执行操作之前检查可用内存。

This allows you to preallocate memory before doing the operation, so you can check if an operation will fail before running it.

这允许您在执行操作之前预先分配内存,因此您可以在运行之前检查操作是否会失败。

#8


1  

You don't need to use BigInteger You can do this event with string array of numbers.

您不需要使用BigInteger您可以使用字符串数组来执行此事件。

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;
    }
}

#9


0  

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;
}

#1


19  

Consider System.Numerics.BigInteger.

考虑System.Numerics.BigInteger。

#2


27  

You need to use a large number class that uses some basic math principals to split these operations up. This implementation of a C# BigInteger library on CodePoject seems to be the most promising. The article has some good explanations of how operations with massive numbers work, as well.

您需要使用一个使用一些基本数学原理的大量类来拆分这些操作。在CodePoject上实现C#BigInteger库似乎是最有希望的。本文对大量数字的操作如何运作有一些很好的解释。

Also see: Big integers in C#

另见:C#中的大整数

#3


11  

As far as Project Euler goes, you might be barking up the wrong tree if you are hitting OutOfMemory exceptions. From their website:

就Euler项目而言,如果你遇到OutOfMemory异常,你可能会咆哮错误的树。从他们的网站:

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

每个问题都是根据“一分钟规则”设计的,这意味着尽管设计一个成功的算法可能需要几个小时才能解决更加困难的问题,但是有效的实施方案将允许在适当的计算机上获得解决方案。不到一分钟。

#4


4  

As user Jakers said, if you're using Big Numbers, probably you're doing it wrong.

正如用户Jakers所说,如果你使用大数字,可能你做错了。

Of the ProjectEuler problems I've done, none have required big-number math so far. Its more about finding the proper algorithm to avoid big-numbers.

在我所做的ProjectEuler问题中,到目前为止还没有人需要大数学数学。它更多的是找到适当的算法来避免大数字。

Want hints? Post here, and we might have an interesting Euler-thread started.

想提示吗?发布在这里,我们可能会有一个有趣的欧拉线程开始。

#5


3  

I assume this is C#? F# has built in ways of handling both these problems (BigInt type and lazy sequences).

我认为这是C#? F#内置了处理这些问题的方法(BigInt类型和延迟序列)。

You can use both F# techniques from C#, if you like. The BigInt type is reasonably usable from other languages if you add a reference to the core F# assembly.

如果您愿意,可以使用C#中的两种F#技术。如果添加对核心F#程序集的引用,则BigInt类型可以从其他语言中合理使用。

Lazy sequences are basically just syntax friendly enumerators. Putting 100,000,000 elements in a list isn't a great plan, so you should rethink your solutions to get around that. If you don't need to keep information around, throw it away! If it's cheaper to recompute it than store it, throw it away!

懒惰序列基本上只是语法友好的枚举器。将100,000,000个元素放在列表中并不是一个好计划,因此您应该重新考虑您的解决方案以解决这个问题。如果您不需要保留信息,请将其扔掉!如果重新计算它比存储它便宜,扔掉它!

#6


1  

See the answers in this thread. You probably need to use one of the third-party big integer libraries/classes available or wait for C# 4.0 which will include a native BigInteger datatype.

请参阅此主题中的答案。您可能需要使用可用的第三方大整数库/类之一,或等待包含本机BigInteger数据类型的C#4.0。

#7


1  

As far as defining how much memory an app will use, you can check the available memory before performing an operation by using the MemoryFailPoint class.

至于定义应用程序将使用多少内存,您可以在使用MemoryFailPoint类执行操作之前检查可用内存。

This allows you to preallocate memory before doing the operation, so you can check if an operation will fail before running it.

这允许您在执行操作之前预先分配内存,因此您可以在运行之前检查操作是否会失败。

#8


1  

You don't need to use BigInteger You can do this event with string array of numbers.

您不需要使用BigInteger您可以使用字符串数组来执行此事件。

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;
    }
}

#9


0  

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;
}