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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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