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

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

У меня есть класс, подобный:

public class HugeInt
{
    public List digits;

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

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

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

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

13
задан Mithrax 25 February 2010 в 23:30
поделиться

4 ответа

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

5
ответ дан 2 December 2019 в 01:49
поделиться

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

2
ответ дан 2 December 2019 в 01:49
поделиться

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

.
0
ответ дан 2 December 2019 в 01:49
поделиться

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

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

0
ответ дан 2 December 2019 в 01:49
поделиться