Как я могу выполнять деление в программе, цифра за цифрой?

Я возился с написанием класса, подобного mpz (C) или BigInteger (Java). Это просто для удовольствия, поэтому, пожалуйста, не продолжайте рассказывать о том, как я не должен писать свои собственные.

У меня есть класс, похожий на:

public class HugeInt
{
    public List<Integer> digits;

    public HugeInt(String value)
    {
        // convert string value into its seperate digits. 
        // store them in instance variable above
    }
}

Теперь выполнение метода add() и subtract() этого класса довольно просто. Вот пример:

private List<Integer> add(List<Integer> a, List<Integer> b)
    {
        List<Integer> smallerDigits = (compareDigits(a,b) < 0) ? a : b;
        List<Integer> largerDigits = (compareDigits(a,b) >= 0) ? a : b;
        List<Integer> result = new ArrayList<Integer>();

        int carry = 0;

        for(int i = 0; i < largerDigits.size(); i++)
        {
            int num1 = largerDigits.get(i);
            int num2 = (i < smallerDigits.size()) ? smallerDigits.get(i) : 0;

            result.add((num1 + num2 + carry) % 10);
            carry = ((num1 + num2 + carry) / 10);
        }

        if (carry != 0) result.add(carry);

        return result;
    }

Точно так же выполнение умножения также не было таким трудным.

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

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

Однако, может ли кто-нибудь указать мне в правильном направлении для деления двух чисел, которые представлены как List<Integer > ? Кроме того, я могу игнорировать остаток, поскольку это целочисленное деление.

Ответы

Ответ 1

Вы можете просто long division, но это, конечно, не оптимальный способ сделать это (отредактируйте: хотя кажется, что что-то как это хороший способ сделать это). Вы можете посмотреть другие реализации больших целочисленных библиотек и немного Googling отображает полезную информацию.

Ответ 2

Это может быть небольшой перебор, но если это то, что вы делаете для удовольствия, вам понравится читать следующее: http://www.fizyka.umk.pl/nrbook/c20-6.pdf ( "Арифметика при произвольной точности" из "Численных рецептов в C" ). Довольно увлекательный, как и большая часть этой книги, с хорошими пояснениями и большим количеством кода.

Ответ 3

Так как я предполагаю, что вы просто имеете дело с целым делением, это не очень сложно. Умножение повторяется сложение, деление противоположное - повторное вычитание. Итак, что вы будете делать, это проверить, сколько раз вы можете вычесть дивизор из дивиденда. Например, 3 можно вычесть из 10 3 раз без перехода < 0, поэтому частное деление делителя равно 3.

Ответ 4

В этой статье "Больше целого" не показано, как реализовать операции с цифрой по цифрам для "больших целых чисел", но она показывает, как реализовать (по-видимому, полностью функциональное) 128-битное целое число в двух типах Int64. Я бы предположил, что было бы слишком сложно расширить подход к использованию массива типов Int64, чтобы получить двоичное целое число. Я просто потратил несколько минут, оглядываясь на статью, и реализация многократного просмотра выглядит так, будто она может быть задействована для произвольной длины.

В статье показано, как реализовать деление (коэффициент и остаток) с помощью двоичного деления.