Обработка чрезвычайно больших чисел на языке, который не может?

15

Я пытаюсь подумать о том, как бы я делал вычисления для чрезвычайно больших чисел (до бесконечности - без целых чисел), если языковая конструкция не способна обрабатывать числа, превышающие определенное значение.

Я уверен, что я не первый и не последний, кто задает этот вопрос, но используемые мной поисковые термины не дают мне алгоритма для решения этих ситуаций. Скорее большинство предложений предлагают изменение языка или изменение переменной, или говорят о вещах, которые кажутся не относящимися к моему поиску. Так что мне нужно немного руководства.

Я бы набросал алгоритм так:

  1. Определите максимальную длину целочисленной переменной для языка.

  2. Если число больше половины длины максимальной длины переменной, разбейте ее на массив. (дать небольшую игровую комнату)

  3. Порядок массива [0] = наиболее правые числа [n-max] = наиболее левые числа

    Ex. Num: 29392023 Массив [0]: 23, Массив [1]: 20, массив [2]: 39, массив [3]: 29

Поскольку я установил половину длины переменной в качестве точки разметки, я могу затем вычислить единицы, десятые, сотые и т. Д. Поместить через полпути так, чтобы, если максимальная длина переменной составляла 10 цифр от 0 до 9999999999, я знал, что наполовину до пяти цифр дайте мне немного игровой комнаты.

Поэтому, если я добавлю или умножу, у меня может быть функция проверки переменных, которая видит, что шестая цифра (справа) массива [0] находится в том же месте, что и первая цифра (справа) массива [1].

У деления и вычитания есть свои проблемы, о которых я еще не думал.

Я хотел бы знать о лучших реализациях поддержки больших чисел, чем программа может.

мальва
источник
1
Первое, что приходит на ум, - это BigInteger Java: docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html
Иван
Это тот язык, который кто-то здесь может знать и уметь давать конкретные рекомендации, или это что-то неясное и частное?
FrustratedWithFormsDesigner
Я не знаю, на каком языке я бы этого хотел. Я знаю php больше всего, но я не хочу делать это на этом языке. Lisp привлекателен, поскольку из того, что я прочитал, он не имеет ограничений по длине. Однако мой личный недостаток желания знать, как это работает, заставляет меня захотеть сделать это в qbasic, если я застрял на острове. (Это тоже для забавы, я всегда думаю о вычислении больших чисел, и некоторые онлайн-калькуляторы слишком громоздки для этой задачи.)
Mallow

Ответы:

25

Вы ищете библиотеку арифметики произвольной точности (также называемую «множественной точностью» или «большим числом») для языка, с которым вы работаете. Например, если вы работаете с C, вы можете использовать библиотеку GNU Bignum -> http://gmplib.org/

Если вы хотите понять, как это работает, вы также можете написать свою собственную большую библиотеку num и использовать ее. Самый простой способ справиться с этим - использовать массивы, где каждый элемент является цифрой числа, с которым вы работаете. После этого вам нужно реализовать все функции для сложения, вычитания, умножения, деления, возведения в степень и так далее.

Даниэль Скокко
источник
5
конечно «цифра» относительна, многие библиотеки bignum используют цифры в базе 256 (unsigned byte []) до 2 ^ 64 (unsigned long [])
трещотка урод
1
Просто убедившись, что я понял, «цифра» может быть массивом из 256 основных цифр? Я думаю, что я могу ошибаться, делать математику на базе 256 легче, чем на базе 88, но все еще довольно сложно ... (По крайней мере, когда я делал это вчера вечером на листе бумаги, ха-ха)
Мэллов
1
msgstr "делать математику на базе 256 проще, чем на базе 88". Ложь. Они одинаково легки.
S.Lott
2
@ S.Lott: хм ... когда у вас есть побитовые операции, математика на базе 256 определенно проще, чем на базе 88.
Джейсон С.
1
Создание собственного сложения / вычитания / умножения довольно просто. Однако деление сложно, если вы не реализуете его в двоичном виде, где оно становится упражнением в условном вычитании и сдвиге битов.
Джейсон С
13

Это хорошо известная проблема: арифметика произвольной точности

Если используемый вами язык не решает эту проблему, сначала попробуйте найти стороннюю библиотеку, которая это делает. Если вы не нашли его или вам любопытно, попробуйте реализовать его; В статье Википедии есть хорошие ссылки на классические реализации.

jgomo3
источник
6

При работе с большими числами, вероятно, одно из самых фундаментальных проектных решений - как я собираюсь представлять большое число?

Будет ли это строка, массив, список или пользовательский (доморощенный) класс хранения.

После того, как это решение принято, фактические математические операции могут быть разбиты на более мелкие части и затем выполнены с типами родного языка, такими как int или integer.

Я включил очень простой пример ADDITION в C # .Net, который хранит полученное большое число в виде строки. Входящие «числа» также являются строками, поэтому нужно иметь возможность отправлять очень «большие» числа. Имейте в виду, что пример только для целых чисел, чтобы сделать его простым.

Даже со строками есть ограничение на количество символов или «цифр» в числе, как указано здесь:

Какова максимально возможная длина строки .NET?

Но вы можете добавить несколько действительно больших чисел, выходящих за рамки собственных типов int32 или int64 для .Net.

В любом случае, вот реализация хранилища строк.

/// <summary>
/// Adds two "integers".  The integers can be of any size string.
/// </summary>
/// <param name="BigInt1">The first integer</param>
/// <param name="BigInt2">The second integer</param>
/// <returns>A string that is the addition of the two integers passed.</returns>
/// <exception cref="Exception">Can throw an exception when parsing the individual parts     of the number.  Callers should handle. </exception>
public string AddBigInts(string BigInt1, string BigInt2)
{
    string result = string.Empty;

    //Make the strings the same length, pre-pad the shorter one with zeros
    int length = (BigInt1.Length > BigInt2.Length ? BigInt1.Length : BigInt2.Length);
    BigInt1 = BigInt1.PadLeft(length, '0');
    BigInt2 = BigInt2.PadLeft(length, '0');

    int remainder = 0;

    //Now add them up going from right to left
    for (int i = (BigInt1.Length - 1); i >= 0; i--)
    {
        //If we don't encounter a number, this will throw an exception as indicated.
        int int1 = int.Parse(BigInt1[i].ToString());
        int int2 = int.Parse(BigInt2[i].ToString());

        //Add
        int add = int1 + int2 + remainder;

        //Check to see if we need a remainder;
        if (add >= 10)
        {
            remainder = 1;
            add = add % 10;
        }
        else
        {
            remainder = 0;
        }

        //Add this to our "number"
        result = add.ToString() + result;
    }

    //Handle when we have a remainder left over at the end
    if (remainder == 1)
    {
        result = remainder + result;
    }

    return result;
}

Я надеюсь, что это даст вам некоторые идеи относительно вашей собственной реализации. Обратите внимание, что пример кода, вероятно, не оптимизирован или что-то в этом роде. Это должно дать некоторые идеи о том, как это можно сделать.

Джон Рейнор
источник
Здорово!! Спасибо, это помогает разобраться с остатками, которые я бы усложнил.
Мэллов
-2

Этот работает быстрее для меня:

static string Add(string a, string b)
        {
            string c = null;

            if (Compare(a, b) < 0)
            {
                c = a;
                a = b;
                b = c;
            }

            StringBuilder sb = new StringBuilder();

            b = b.PadLeft(a.Length, '0');

            int r = 0;

            for (int i = a.Length - 1; i >= 0; i--)
            {
                int part = a[i] + b[i] + r - 96;

                if (part <= 9)
                {
                    sb.Insert(0, part);

                    r = 0;
                }
                else
                {
                    sb.Insert(0, part - 10);

                    r = 1;
                }
            }

            if (r == 1)
            {
                sb.Insert(0, "1");
            }

            return sb.ToString();
        }
Андраник Саргсян
источник
2
Этот сайт о концептуальных вопросах, и ответы должны объяснить вещи. Создание дампов кода вместо объяснения похоже на копирование кода из IDE на доску: это может показаться знакомым и даже иногда понятным, но это кажется странным ... просто странным. У доски нет компилятора
gnat
Этот сайт - ОБМЕН, поэтому мы стараемся помогать друг другу как можно больше. Может быть, я должен сделать такие комментарии в StackOverflow, но я попытался помочь с моим подходом. Если кому-то все еще нужно объяснение, он попросит его. Я делаю здесь стандартное математическое сложение цифра за цифрой, начиная с конца.
Андраник Саргсян
Согласитесь с комарием. По крайней мере, объясните алгоритм перед сбросом кода.
Фрэнк Хилман
Простой сброс кода без объяснения - это все равно что поощрять копирование, прохождение и удаление. Я не понимаю, как это может быть полезно в SoftwareEngineering. Может быть, у StackOverflow есть, но оба сайта на самом деле имеют совершенно разные цели.
Laiv