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

Я возился с написанием класса, похожего на 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>? Кроме того, я могу игнорировать остаток, так как это целочисленное деление.


person Mithrax    schedule 25.02.2010    source источник
comment
+1: мне очень нравится этот вопрос. Я составлю алгоритм просто для удовольствия.   -  person d..    schedule 26.02.2010
comment
Получисловые алгоритмы Кнута очень подробно рассматривают эту тему.   -  person President James K. Polk    schedule 26.02.2010


Ответы (4)


Вы можете просто выполнить полное деление, но это определенно не оптимальный способ ( редактировать: хотя кажется, что что-то вроде этого — хороший способ сделать это). Вы можете посмотреть другие реализации больших целочисленных библиотек и немного < href="http://www.google.com.au/search?q=division+of+big+integers" rel="nofollow noreferrer">поиск в Google дает немало полезной информации.

person David Johnstone    schedule 25.02.2010
comment
Фактически, метод длинного деления с помощью бумаги и карандаша довольно близок к тому, как многие алгоритмы деления больших целых чисел работают для обычных размеров. Чтобы сильно упростить, вы используете небольшое количество первых цифр для оценки частного числа, затем вычисляете частичный остаток и повторяете. Вам нужно определить, когда ваша оценка неверна, и восстановиться после нее. - person President James K. Polk; 27.02.2010

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

person AVB    schedule 26.02.2010

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

person monoceres    schedule 25.02.2010
comment
Однако это не цифра за цифрой. Я думаю, он хочет подражать длинному делению. - person Bill K; 26.02.2010
comment
Я думал об этом, но предположил, что это будет ужасно неэффективно. Теперь мне интересно, будет ли этого достаточно или, как сказал Билл К., лучше всего будет эмулировать длинное деление. - person Mithrax; 26.02.2010
comment
@Mithrax, да, это было бы очень неэффективно при делении на небольшие числа, такие как 1. Вы бы повторили N раз, где N - ваше большое целое число. (И если бы вы не хранили свой счет в другом большом целом числе, вы бы рисковали переполнить примитивные целочисленные типы.) - person Mike Daniels; 26.02.2010
comment
@Mike: я не думал об этом подробно, но изначально я не думаю, что вам нужно перебирать каждое целое число по отдельности; вы можете получить довольно высокую нижнюю границу результата, основанную на разнице в количестве цифр. Если эта разница равна нулю, вам нужно всего лишь выполнить цикл от 1 до 9. - person d..; 26.02.2010
comment
Хммм ... Если подумать, не уверен, насколько высоким будет довольно высокий, в некоторых случаях кажется, что не слишком высокий. - person d..; 26.02.2010

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

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

person wageoghe    schedule 26.05.2010