Как разделить гигантское число на python3?

#python #python_3x #float #большие_числа #int

Работаю с большими числами, необходимо разделить int типа этого

4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300


на 17

получаю ошибку:

OverflowError: integer division result too large for a float


Целочисленное деление тоже ведёт к этой ошибке.

Как на питоне разделить такое число? (на результате достаточно целого числа)
    

Ответы

Ответ 1

С делением через /, действительно, эта ошибка повторяется, но не потому, что он не
может делить, а потому, что исходное делимое слишком велико для помещения в double
(даже с неизбежной погрешностью), а при / оба числа конвертируются в double (в Python
- float) перед собственно делением. Вызвать float() на него тоже даёт ту же ошибку.

С делением нацело - знак // - проблем нет, результат возвращается и корректный:


>>> 4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300//3
1619483545396571141194031987498067348193800195994414849827697695020644901569603309483548256621841454949999082341638373036803868579725802618973251442190618480685736815245294560609941251379878112741733150730550428116110968377064399984500804586255079754958204464968956710187431937739827037895113178521763616674625030952297564851991427182128836910016368907686311195350848032221450421783121214652375188565312271728111619201755646720417088983807183513184839717928485841918863580180052643000588655988493354809276377162849419971573749502117562210158766


Если у вас деление нацело тоже не работает - возможно, у вас как-то очень странно
скомпилирован сам Python. В таком случае, вам следует рассмотреть смену версии и/или
поставщика.

Я проверял оба случая на Python 3.6 под Ubuntu 18.04/x86_64 и Python 3.7 на FreeBSD/i386,
так что обычные проблемы 32/64 явно не влияют. Windows под рукой нет, может быть, её
странности недостаточно отражены в коде интерпретатора (например, то, что long в 64-битном
режиме - 32 бита, противоречит не только устоявшимся традициям всех остальных, но и
собственной же .NET).

P.S. Тут есть вопрос, который, возможно, требует жалобы на баг:


>>> float(4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300)
Traceback (most recent call last):
  File "", line 1, in 
OverflowError: int too large to convert to float
>>> float('1e+308')
1e+308
>>> float('1e+309')
inf
>>> float('4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300')
inf


такое неровное поведение требует как минимум обсуждения его целесообразности.


Ответ 2

Используйте оператор целочисленного деления

x // 3 


Или Decimal

Decimal(x) / Decimal(3)

Деление в столбик на Java

#java #деление #большие_числа

Нужно написать класс который бы делил одно число на другое, выводя деление в столбик.
Деление целочисленное. Если остался остаток, просто вывести его в последней строке,
если остается ноль его не выводим. Пример результата, который должен вернуться:



Мой код:

public class LongDivUtil {
    private String result = "";
    private int remDiv = 0;
    private int quotient;
    private int dividend;
    private int divider;
    private int[] numbersDividend;
    private String[] numbersOfDividendInStrVal;

    public LongDivUtil(int dividend, int divider) {
        this.dividend = dividend;
        this.divider = divider;
        this.numbersOfDividendInStrVal = (dividend + "").split("");
        this.numbersDividend = new int[numbersOfDividendInStrVal.length];
        for (int i = 0; i < numbersOfDividendInStrVal.length; i ++){
            numbersDividend[i] = Integer.parseInt(numbersOfDividendInStrVal[i]);
        }
    }

    public void executeDivision(){
        System.out.println("execute");
        System.out.println(this.dividend + "|" + this.divider);
        /////////////////////////////////////////////////////////////////
        int tmpInt = numbersDividend[0];
        boolean  isContinue = false;
        for (int i = 0; i < numbersOfDividendInStrVal.length || isContinue; i++) {
            if (tmpInt >= divider) {
                quotient = tmpInt / divider;
                result += quotient;
                remDiv = tmpInt % divider;
                isContinue = false;
                System.out.println("result = " + result);////////////////
                System.out.println("remDiv = " + remDiv);//////////////
                if (remDiv != 0 && i != numbersOfDividendInStrVal.length - 1){//1
                    tmpInt = Integer.parseInt((remDiv + "") + (numbersDividend[i] + ""));
                    System.out.println(tmpInt);
                    continue;
                }
                if (i < numbersOfDividendInStrVal.length -1){//2
                    tmpInt = numbersDividend[++i];
                    isContinue = true;
                }
                continue;
            } else {
                if (tmpInt == 0){//4
                    result += tmpInt;
                    if (i < numbersOfDividendInStrVal.length){
                        tmpInt = i;
                    }
                    isContinue = false;
                    continue;
                }
                if (tmpInt < divider){
                    tmpInt = Integer.parseInt(numbersOfDividendInStrVal[i] + numbersOfDividendInStrVal[++i]);
                    isContinue = true;
                    continue;
                }
            }
        }
        /////////////////////////////////////////////////////////////
        System.out.println("out");
    }
}


В нете, часто встречающийся вопрос, но ничего не находил в рекомендациях. Пока пишу
сам, но получается, мягко говоря, не очень. Кто ни будь сталкивался с подобным? 
    

Ответы

Ответ 1

Код стоит подправить, но представленный пример показывает основные принципы, которые
необходимо реализовать.

public class LongDivUtil {
private int dividend;
private int divider;
private int n;
private StringBuffer dividendSB;
private StringBuffer result=new StringBuffer("");
private StringBuffer firstSplitedString;
private StringBuffer secondSplitedString;
private StringBuffer print=new StringBuffer("");


public LongDivUtil(int dividend, int divider) {
    this.dividend = dividend;
    this.divider = divider;
    result=new StringBuffer("");
    this.dividendSB=new StringBuffer(Integer.toString(this.dividend));
}
public void printSomeCharSomeTimes(String s,int n){
    for (int i = 0; i =this.divider;i++){
        print.append("\n"+t.toString()+this.getLeftDividendNumber());
        count();
        print.append("\n"+t.toString()+n*divider);
        t.append(" ");
    }

    if (this.dividend!=0)
        result.append(".");

    int numberOfDigits=5;

    while(this.dividend!=0&&numberOfDigits!=0){
        for (int i =0;dividend0){
                result.append("0");
            }
        }
        count();
        numberOfDigits--;
    }
return result;
}

public int getLeftDividendNumber(){
    int i=1;
    while (Integer.parseInt(Integer.toString(this.dividend).substring(0, i))
Ответ 2

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

public class Division {

    private StringBuilder result = new StringBuilder();
    private StringBuilder quotient = new StringBuilder();
    private StringBuilder reminder= new StringBuilder();

    public String makeDivision(int dividend, int divisor) {

        if (divisor == 0) {
            throw new IllegalArgumentException("Divisor cannot be 0, division by zero");
        }

        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);

        if (dividend < divisor) {
            return "" + dividend + "/" + divisor + "=0";
        }

        String[] digits = String.valueOf(dividend).split("");
        Integer reminderNumber;
        Integer multiplyResult;
        Integer divisorDigit = calculateDigit(divisor);
        Integer mod;

        for (int i = 0; i < digits.length; i++) {
            reminder.append(digits[i]);
            reminderNumber = Integer.parseInt(reminder.toString());

            if (reminderNumber >= divisor) {
                mod = reminderNumber % divisor;
                multiplyResult = reminderNumber / divisor * divisor;

                String lastReminder = String.format("%" + (i + 2) + "s", "_" + reminderNumber.toString());
                result.append(lastReminder).append("\n");

                String multiply = String.format("%" + (i + 2) + "d", multiplyResult);
                result.append(multiply).append("\n");

                Integer tab = lastReminder.length() - calculateDigit(multiplyResult);
                result.append(makeDivider(reminderNumber, tab)).append("\n");

                quotient.append(reminderNumber / divisor);

                reminder.replace(0, reminder.length(), mod.toString());
                reminderNumber = Integer.parseInt(reminder.toString());
            } else {
                if (i >= divisorDigit) {
                    quotient.append(0);
                }
            }

            if (i == digits.length - 1) {
                result.append(String.format("%" + (i + 2) + "s", reminderNumber.toString())).append("\n");
            }
        }
        modifyResultToView(dividend, divisor);
        return result.toString();
    }

    private String makeDivider(Integer reminderNumber, Integer tab) {
        return assemblyString(tab, ' ') + assemblyString(calculateDigit(reminderNumber),
'-');
    }

    private void modifyResultToView(Integer dividend, Integer divisor) {
        int[] index = new int[3];
        for (int i = 0, j = 0; i < result.length(); i++) {
            if (result.charAt(i) == '\n') {
                index[j] = i;
                j++;
            }

            if (j == 3) {
                break;
            }
        }

        int tab = calculateDigit(dividend) + 1 - index[0];
        result.insert(index[2], assemblyString(tab, ' ') +"│" + quotient.toString());
        result.insert(index[1], assemblyString(tab, ' ') +"│" + assemblyString(quotient.length(),
'-'));
        result.insert(index[0], "│" + divisor);
        result.replace(1, index[0], dividend.toString());
    }

    private int calculateDigit(int i) {
        return (int) Math.log10(i) + 1;
    }
    private String assemblyString(int numberOfSymbols, char symbol) {
        StringBuilder string = new StringBuilder();
        for (int i = 0; i < numberOfSymbols; i++) {
            string.append(symbol);
        }
        return string.toString();
    }
}


пример результата:

_10210│5
 10   │----
 --   │2042
  _21
   20
   --
   _10
    10
    --
     0


Пример теста:

Division division = new Division();

    @Test
    public void shouldMakeDivision() {
        String expected =   "_14789│20\n" + 
                            " 140  │---\n" + 
                            " ---  │739\n" + 
                            "  _78\n" + 
                            "   60\n" + 
                            "   --\n" + 
                            "  _189\n" + 
                            "   180\n" + 
                            "   ---\n" + 
                            "     9\n";
        assertEquals(expected, division.makeDivision(14789, 20));
    }

Распараллеливание обработки комбинаций

Моя программа генерирует 27 512 614 111 (27,5 миллиардов) комбинаций чисел. Кажется, что нереально страшная цифра, но всё не так. Программа в чистом виде делает это за 10 мин на одном ядре. Однако мне нужно производить некоторые вычисления с полученной комбинацией чисел, соответственно программа начинает резко притормаживать:
Используется арифметика с плавающей запятой Добавляются несколько циклов для вычисления использование оператора ЕСЛИ на каждой итерации, вплоть до 27,5 миллиарда так же вставляет палки в колёса (сам убедился, что проверка условия сильно тормозит любую программу при больших вычисления)
Возможно ли распараллелить обработку комбинаций? У меня 8 ядер в процессоре. Как разбить все комбинации по 27,5 / 8 = 3.4 миллиарда комбинаций. Это очень ускорит работу, но я не понимаю как для каждой функции, запускаемой в поток, отделить мои комбинации. Комбинации по 7 элементов, туда входят число от 0 до 30
0 0 0 0 0 0 ... 0 31 0 31 31 31 0
и т.д. Заранее спасибо!

Ответ

Нашёл решение проблемы. Если вы перебираете размещения с повторениями, то возьмите счётчик, который считает от 0 до 2 млрд (__int64 подойдет для этих целей), далее останавливаете цикл, когда дойдет до 2 млрд и смотрите на состав элементов последовательности. Если у вас начальные элементы это все нули, а на 2 млрд, к примеру 9 8 1 2 7 1 8, то запомните этот состав, и далее начните перебор, задав начальной последовательностью не нули, а вышеуказанной, и опять считаете 2 млрд и т.д.! Это очень простое решение в лоб! Спасибо всем кто участвовал