Возведение в квадрат в компьютерах.

[slavav]

Прошу прощения, плохо написал. Надо так:

$$(A_{1} + 2^{k}A_{2})^2 = (2^k + 1)A_1^2 - 2^k(A_2 - A_1)^2 + (2^{2k} + 2^k)A_2^2$$

[B@R5uk]

Да, это рабочая формула. Только вместо квадрата разности лучше взять квадрат суммы. Реализовал код:

Используется синтаксис Java

import java.util.*;

class BigNumber {
        
        private final static int base = 1000000000;
        private static int karatsubaThreshold = 25;
        
        private int[] digits;
        
        private BigNumber() {
        }
        
        public BigNumber(int arg) {
                if (0 > arg) {
                        throw new IllegalArgumentException("Numbers must be positive");
                }
                digits = new int[2];
                digits[0] = arg % base;
                digits[1] = arg / base;
        }
        
        public BigNumber(String arg) {
                BigNumber temp, ten;
                ten = new BigNumber(10);
                temp = new BigNumber(0);
                for (int k = 0; arg.length() > k; ++k) {
                        char c = arg.charAt(k);
                        if (('0' <= c) && (c <= '9')) {
                                temp = temp.multiplySimple(ten).add(new BigNumber(c - '0'));
                        }
                }
                digits = temp.digits;
        }
        
        public BigNumber(BigNumber arg) {
                digits = new int[arg.digits.length];
                for (int k = 0; arg.digits.length > k; ++k) {
                        digits[k] = arg.digits[k];
                }
        }
        /*
        private BigNumber(BigNumber arg, int padSize) {
                if (0 > padSize) {
                        throw new IllegalArgumentException("Pad size must be positive");
                }
                digits = new int[arg.digits.length + padSize];
                for (int k = 0; arg.digits.length > k; ++k) {
                        digits[k] = arg.digits[k];
                }
        }
        //*/
        public BigNumber(Random rng, int size) {
                digits = new int[size];
                for (int k = 0; size > k; ++k) {
                        digits[k] = rng.nextInt(base);
                }
        }
        
        public BigNumber add(BigNumber arg) {
                int k, size1, size2, sum;
                BigNumber augend, addend, result;
                size1 = this.digits.length - 1;
                if (0 != this.digits[size1]) {
                        ++size1;
                }
                size2 = arg.digits.length - 1;
                if (0 != arg.digits[size2]) {
                        ++size2;
                }
                if (size1 < size2) {
                        augend = arg;
                        addend = this;
                        sum = size1;
                        size1 = size2;
                        size2 = sum;
                } else {
                        augend = this;
                        addend = arg;
                }
                result = new BigNumber();
                result.digits = new int[size1 + 1];
                for (k = 0; size1 > k; ++k) {
                        result.digits[k] = augend.digits[k];
                }
                sum = 0;
                for (k = 0; size2 > k; ++k) {
                        sum += result.digits[k];
                        sum += addend.digits[k];
                        if (base > sum) {
                                result.digits[k] = sum;
                                sum = 0;
                        } else {
                                result.digits[k] = sum - base;
                                sum = 1;
                        }
                }
                while (0 != sum) {
                        sum += result.digits[k];
                        if (base > sum) {
                                result.digits[k] = sum;
                                sum = 0;
                        } else {
                                result.digits[k] = sum - base;
                                sum = 1;
                        }
                        ++k;
                }
                return result;
        }
        
        public BigNumber multiplyKaratsuba(BigNumber arg) {
                int k, l, size1, size2, offset, limit, sum;
                BigNumber result, a, b, a1, a2, b1, b2, axb1, axb2, apa, bpb, temp;
                size1 = digits.length;
                if (0 == digits[size1 - 1]) {
                        --size1;
                }
                size2 = arg.digits.length;
                if (0 == arg.digits[size2 - 1]) {
                        --size2;
                }
                if (karatsubaThreshold > size1 || karatsubaThreshold > size2) {
                        return this.multiplySimple(arg);
                }
                if (size2 < size1) {
                        a = this;
                        b = arg;
                        offset = (size1 + 1) / 2;
                } else {
                        a = arg;
                        b = this;
                        offset = size2;
                        size2 = size1;
                        size1 = offset;
                        offset = (size1 + 1) / 2;
                }
                //==============================
                result = new BigNumber();
                result.digits = new int[size1 + size2];
                a1 = new BigNumber();
                a2 = new BigNumber();
                a1.digits = new int[offset];
                a2.digits = new int[size1 - offset];
                for (k = 0; offset > k; ++k) {
                        a1.digits[k] = a.digits[k];
                }
                for (l = 0; size1 > k; ++k, ++l) {
                        a2.digits[l] = a.digits[k];
                }
                //==============================
                if (size2 > offset) {
                        b1 = new BigNumber();
                        b2 = new BigNumber();
                        b1.digits = new int[offset];
                        b2.digits = new int[size2 - offset];
                        for (k = 0; offset > k; ++k) {
                                b1.digits[k] = b.digits[k];
                        }
                        for (l = 0; size2 > k; ++k, ++l) {
                                b2.digits[l] = b.digits[k];
                        }
                        //==============================
                        axb1 = a1.multiplyKaratsuba(b1);
                        axb2 = a2.multiplyKaratsuba(b2);
                        apa = a1.add(a2);
                        bpb = b1.add(b2);
                        temp = apa.multiplyKaratsuba(bpb);
                        //==============================
                        limit = axb1.digits.length - 1;
                        if (0 != axb1.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0; limit > k; ++k) {
                                sum += temp.digits[k];
                                sum -= axb1.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                        }
                        while (0 != sum) {
                                sum += temp.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                                ++k;
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0; limit > k; ++k) {
                                sum += temp.digits[k];
                                sum -= axb2.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                        }
                        while (0 != sum) {
                                sum += temp.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                                ++k;
                        }
                        //==============================
                        limit = axb1.digits.length;
                        for (k = 0; limit > k; ++k) {
                                result.digits[k] = axb1.digits[k];
                        }
                        //==============================
                        limit = temp.digits.length - 1;
                        while (0 == temp.digits[limit]) {
                                --limit;
                        }
                        ++limit;
                        sum = 0;
                        for (k = 0, l = offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += temp.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0, l = 2 * offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += axb2.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                } else {
                        axb1 = a1.multiplyKaratsuba(b);
                        axb2 = a2.multiplyKaratsuba(b);
                        //==============================
                        limit = axb1.digits.length;
                        for (k = 0; limit > k; ++k) {
                                result.digits[k] = axb1.digits[k];
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0, l = offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += axb2.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                }
                return result;
        }
        
        public BigNumber multiplySimple(BigNumber arg) {
                int k, l, size1, size2;
                long mult, sum;
                BigNumber result;
                size1 = digits.length - 1;
                if (0 != digits[size1]) {
                        ++size1;
                }
                size2 = arg.digits.length - 1;
                if (0 != arg.digits[size2]) {
                        ++size2;
                }
                result = new BigNumber();
                result.digits = new int[size1 + size2];
                for (k = 0; size1 > k; ++k) {
                        mult = digits[k];
                        sum = 0;
                        for (l = 0; size2 > l; ++l) {
                                sum += result.digits[k + l];
                                sum += mult * arg.digits[l];
                                result.digits[k + l] = (int) (sum % base);
                                sum /= base;
                        }
                        if (0 != sum) {
                                result.digits[k + l] = (int) sum;
                        }
                }
                return result;
        }
        
        public BigNumber squareKaratsuba() {
                int k, l, size, offset, limit, sum;
                BigNumber result, a, b, a2, b2, apb, temp;
                size = digits.length - 1;
                if (0 != digits[size]) {
                        ++size;
                }
                offset = (size + 1) / 2;
                if (karatsubaThreshold > size) {
                        return this.multiplySimple(this);
                }
                result = new BigNumber();
                result.digits = new int[2 * size];
                a = new BigNumber();
                b = new BigNumber();
                a.digits = new int[offset];
                b.digits = new int[size - offset];
                for (k = 0; offset > k; ++k) {
                        a.digits[k] = digits[k];
                }
                for (l = 0; size > k; ++k, ++l) {
                        b.digits[l] = digits[k];
                }
                //==============================
                a2 = a.squareKaratsuba();
                b2 = b.squareKaratsuba();
                apb = a.add(b);
                temp = apb.squareKaratsuba();
                //==============================
                limit = a2.digits.length - 1;
                if (0 != a2.digits[limit]) {
                        ++limit;
                }
                sum = 0;
                for (k = 0; limit > k; ++k) {
                        sum += temp.digits[k];
                        sum -= a2.digits[k];
                        if (0 > sum) {
                                temp.digits[k] = sum + base;
                                sum = -1;
                        } else {
                                temp.digits[k] = sum;
                                sum = 0;
                        }
                }
                while (0 != sum) {
                        sum += temp.digits[k];
                        if (0 > sum) {
                                temp.digits[k] = sum + base;
                                sum = -1;
                        } else {
                                temp.digits[k] = sum;
                                sum = 0;
                        }
                        ++k;
                }
                //==============================
                limit = b2.digits.length - 1;
                if (0 != b2.digits[limit]) {
                        ++limit;
                }
                sum = 0;
                for (k = 0; limit > k; ++k) {
                        sum += temp.digits[k];
                        sum -= b2.digits[k];
                        if (0 > sum) {
                                temp.digits[k] = sum + base;
                                sum = -1;
                        } else {
                                temp.digits[k] = sum;
                                sum = 0;
                        }
                }
                while (0 != sum) {
                        sum += temp.digits[k];
                        if (0 > sum) {
                                temp.digits[k] = sum + base;
                                sum = -1;
                        } else {
                                temp.digits[k] = sum;
                                sum = 0;
                        }
                        ++k;
                }
                //==============================
                limit = a2.digits.length;
                for (k = 0; limit > k; ++k) {
                        result.digits[k] = a2.digits[k];
                }
                //==============================
                limit = temp.digits.length - 1;
                while (0 == temp.digits[limit]) {
                        --limit;
                }
                ++limit;
                sum = 0;
                for (k = 0, l = offset; limit > k; ++k, ++l) {
                        sum += result.digits[l];
                        sum += temp.digits[k];
                        if (base > sum) {
                                result.digits[l] = sum;
                                sum = 0;
                        } else {
                                result.digits[l] = sum - base;
                                sum = 1;
                        }
                }
                if (0 != sum) {
                        result.digits[l] = sum;
                }
                //==============================
                limit = b2.digits.length - 1;
                if (0 != b2.digits[limit]) {
                        ++limit;
                }
                sum = 0;
                for (k = 0, l = 2 * offset; limit > k; ++k, ++l) {
                        sum += result.digits[l];
                        sum += b2.digits[k];
                        if (base > sum) {
                                result.digits[l] = sum;
                                sum = 0;
                        } else {
                                result.digits[l] = sum - base;
                                sum = 1;
                        }
                }
                if (0 != sum) {
                        result.digits[l] = sum;
                }
                //==============================
                return result;
        }
        
        public int compareTo(BigNumber arg) {
                int k, flag;
                BigNumber a, b;
                if (this.digits.length > arg.digits.length) {
                        a = this;
                        b = arg;
                        flag = 1;
                } else {
                        a = arg;
                        b = this;
                        flag = -1;
                }
                k = a.digits.length;
                while (b.digits.length > k) {
                        --k;
                        if (0 != a.digits[k]) {
                                return flag;
                        }
                }
                do {
                        --k;
                        if (b.digits[k] < a.digits[k]) {
                                return flag;
                        } else if (b.digits[k] > a.digits[k]) {
                                return -flag;
                        }
                } while (0 != k);
                return 0;
        }
        
        public String toString() {
                int k, l, value;
                l = 12 * digits.length;
                char[] buffer = new char[l];
                for (k = 0; digits.length > k; ++k) {
                        value = digits[k];
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = ' ';
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = ' ';
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value);
                        buffer[--l] = ' ';
                }
                return new String(buffer);
        }
}

public class Study_Karatsuba_method_2 {
        
        private final static Random rng = new Random();
        
        public static void main(String[] args) {
                int k, numberSize, tableSize;
                long time1, time2, time3;
                double temp, mean1, std1, mean2, std2;
                double[] table1, table2;
                BigNumber a, b, c;
                Locale.setDefault(new Locale("en", "US"));
                tableSize = 12;
                table1 = new double[tableSize];
                table2 = new double[tableSize];
                numberSize = 99000;
                while (109 < numberSize) {
                        mean1 = 0.0;
                        mean2 = 0.0;
                        for (k = 0; tableSize > k; ++k) {
                                a = new BigNumber(rng, numberSize);
                                time1 = System.nanoTime();
                                b = a.multiplyKaratsuba(a);
                                time2 = System.nanoTime();
                                c = a.squareKaratsuba();
                                time3 = System.nanoTime();
                                if (0 != c.compareTo(b)) {
                                        System.out.println("ERROR");
                                }
                                temp = 1e-9 * (time2 - time1);
                                mean1 += temp;
                                table1[k] = temp;
                                temp = 1e-9 * (time3 - time2);
                                mean2 += temp;
                                table2[k] = temp;
                        }
                        mean1 /= tableSize;
                        mean2 /= tableSize;
                        std1 = 0.0;
                        std2 = 0.0;
                        for (k = 0; tableSize > k; ++k) {
                                temp = table1[k] - mean1;
                                std1 += temp * temp;
                                temp = table2[k] - mean2;
                                std2 += temp * temp;
                        }
                        std1 = Math.sqrt(std1 / tableSize / (tableSize - 1));
                        std2 = Math.sqrt(std2 / tableSize / (tableSize - 1));
                        System.out.println(String.format("%6d %12.9f %12.9f %12.9f %12.9f", numberSize, mean1, std1, mean2, std2));
                        numberSize -= numberSize / 8;
                }
        }
}
 

Отличие возведения в квадрат от умножения двух чисел заключается лишь в обработке всяких тонкостей. Код для возведения в квадрат значительно короче, но ключевые вычислительные моменты — это прямой копи-паст с небольшими поправками. Улучшение скорости работы составило всего лишь 9%:



Вывод можно сделать такой: основное время работы набегает на самом дне рекурсии, где элементарные блоки перемножаются в столбик.

[Dmitriy40]

B@R5uk в сообщении #1439298 писал(а):

Вывод можно сделать такой: основное время работы набегает на самом дне рекурсии, где элементарные блоки перемножаются в столбик.

При аккуратной реализации самое дно рекурсии превращается в одно машинное умножение, на x86/x64 выполняемое за 1-5 тактов (как повезёт), т.е. до полу- или двух миллиардов умножений в секунду (для 2ГГц CPU). Ваш тест даёт в 100 раз меньшую скорость (для 85млн умножений элементарных разрядов для правой точки графика), видимо из-за операций деления (не смотрел есть ли они).

Я проверил (грубо) скорость вычислений PARI/GP для возведения в квадрат длинного числа, число с 9000000 знаков (взял число пи в небольшой целой степени) посчиталось за 170мс и это 9 миллионов знаков, т.е. миллион ваших элементарных разрядов, в 300 раз быстрее (лишняя двойка — отношение частот CPU). И уверен в PARI/GP вычисления не оптимальны, мы знаем про его тормознутость.
Возьмите для проверки замените умножение элементарных блоков на их сложение даже без проверки на переполнение (без делений), скорость резко поднимется? Если тормоза там, то должна.

[B@R5uk]

Dmitriy40 в сообщении #1439327 писал(а):

При аккуратной реализации самое дно рекурсии превращается в одно машинное умножение

Это не рационально. Маленькие числа выгоднее умножать столбиком, так как для малых чисел расчленение на блоки и последующая сборка по методу Карацубы приводит к большим накладным расходам. Я пробовал крутить свою пороговую константу: при слишком малых или при слишком больших её значениях скорость вычислений падает.

-- 11.02.2020, 12:02 --

Dmitriy40 в сообщении #1439327 писал(а):

...видимо из-за операций деления (не смотрел есть ли они).

У меня элементарное умножение — это перемножение двух чисел int с величинами до $10^9$, что даёт величину типа long, которую затем делением с остатком на $10^9$ (константа base) я расщепляю на два разряда — старший и младший. Старший, разумеется, может оказаться нулевым. Это всё делается в процедуре multiplySimple, которой в конце-концов пользуются все остальные процедуры умножения.

Используется синтаксис Java

        public BigNumber multiplySimple(BigNumber arg) {
                int k, l, size1, size2;
                long mult, sum;
                BigNumber result;
                size1 = digits.length - 1;
                if (0 != digits[size1]) {
                        ++size1;
                }
                size2 = arg.digits.length - 1;
                if (0 != arg.digits[size2]) {
                        ++size2;
                }
                result = new BigNumber();
                result.digits = new int[size1 + size2];
                for (k = 0; size1 > k; ++k) {
                        mult = digits[k];
                        sum = 0;
                        for (l = 0; size2 > l; ++l) {
                                sum += result.digits[k + l];
                                sum += mult * arg.digits[l];
                                result.digits[k + l] = (int) (sum % base);
                                sum /= base;
                        }
                        if (0 != sum) {
                                result.digits[k + l] = (int) sum;
                        }
                }
                return result;
        }
 

-- 11.02.2020, 12:21 --

Dmitriy40 в сообщении #1439327 писал(а):

....на x86/x64 выполняемое за 1-5 тактов (как повезёт), т.е. до полу- или двух миллиардов умножений в секунду (для 2ГГц CPU). Ваш тест даёт в 100 раз меньшую скорость...

Что-то по-моему вы не так считали. Время работы умножения в столбик равно $L^2\cdot 6.6\cdot 10^{-9}$ секунд, где L — разрядность обоих множителей. То есть одна итерация цикла умножения длится $6.6\cdot 10^{-9}\times 2\cdot 10^9\approx 13$ тактов. Эти такты тратятся на:
1) расчёт адреса промежуточного результата
2) загрузку промежуточного результата
3) нахождение суммы
4) загрузку множителя
5) вычисление произведения
6) нахождение суммы
7) вычисление остатка и частного
8) сохранение остатка
9) инкремент счётчика цикла
10) проверку окончания цикла
11) условный переход на начало итерации

Некоторые операции, возможно, выполняются за одну инструкцию, но тут есть умножение и деление, так что, как по мне, всё делается очень даже быстро.

[Dmitriy40]

B@R5uk в сообщении #1439336 писал(а):

Это не рационально. Маленькие числа выгоднее умножать столбиком,

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

B@R5uk в сообщении #1439336 писал(а):

Что-то по-моему вы не так считали.

Я считал количество умножений по Карацубе, оно $3^{\log_2 L}$, где $L$ — количество элементарных разрядов, $3^{\log_2 10^5} \approx 8{,}41\cdot 10^7$ умножений за 4с на частоте 2ГГц.
Наклон последнего графика у Вас 25 раз на десятичный порядок по $L$, значит для миллиона элементарных разрядов время будет ~100с — против 0.34с у PARI/GP (0.17с на почти вдвое выше частоте).

B@R5uk в сообщении #1439336 писал(а):

Эти такты тратятся на:

Весь список в сумме за исключением операции деления занимает почти на порядок меньше её одной и можно просто не учитывать. Разумеется после вменяемого компилятора. Именно ради отказа от самой долгой операции (деления на base) и используют двоичные модули, сдвиги выполняются со скоростью сложений/вычитаний и логических операций.

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

[B@R5uk]

Dmitriy40 в сообщении #1439353 писал(а):

Наклон последнего графика у Вас 25 раз на десятичный порядок по $L$

Не, наклон равен $\times10^{\log_23}=\times38.46$ на десятичный порядок (если можно так выразиться для логарифмического масштаба). Это же число можно получить из графика: $\sqrt[3]{{3}/{\left( 5\cdot {{10}^{-5}} \right)}\;}\approx 39$. Но если надо посчитать время работы моей программы, то лучше пользоваться графиком и эмпирической формулой с предыдущей страницы:



Для $L=10^6$ время работы будет $10^{12}\cdot 4.2\cdot 10^{-8}=4.2\cdot 10^4$ секунд или 11 часов 40 минут.

Но я не ставил себе целью получить максимальное быстродействие, задача была просто опробовать метод Карацубы. В конце-концов, даже он не является самым оптимальным. Кроме уже упомянутого на первой странице мозговыносящего алгоритма Шёнхаге—Штрассена с его безумным теоретико-числовым дискретным преобразование Фурье в поле чисел Ферма и сложностью $O(n\log n\log\log n)$ есть ещё человеческий алгоритм, обобщение метода Карацубы, который по английски зовётся Toom–Cook multiplication. Он заключается в том, что умножаемые числа разбиваются не на 2 части, а на 3 или более. Для трёх частей, например, степень сложности будет не $\log_23\approx 1.58$, как у Карацубы, а $\log_35\approx 1.46$. Мелочь, а приятно.

[Xaositect]

Dmitriy40 в сообщении #1439327 писал(а):

Я проверил (грубо) скорость вычислений PARI/GP для возведения в квадрат длинного числа, число с 9000000 знаков (взял число пи в небольшой целой степени) посчиталось за 170мс и это 9 миллионов знаков, т.е. миллион ваших элементарных разрядов, в 300 раз быстрее (лишняя двойка — отношение частот CPU). И уверен в PARI/GP вычисления не оптимальны, мы знаем про его тормознутость.

PARI/GP тормозит из-за его интерпретируемости, тут это не важно. Я практически уверен, что в этом случае основное время занимает библиотечная функция умножения, а над ней несколько простых оберток. PARI умеет использовать GMP, а там используются алгоритмы быстрее Карацубы, для 9 млн. знаков будет уже Шёнхаге-Штрассен.

[B@R5uk]

Dmitriy40 в сообщении #1439353 писал(а):

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

Ну почему же? Вы сами написали, что операция умножения в среднем занимает 3 такта. Это почти четверть от этих 13 тактов.

-- 11.02.2020, 14:30 --

Dmitriy40 в сообщении #1439353 писал(а):

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

Я бы так не сказал. Каждое "углубление" по методу Карацубы приводит к тому, что размер умножаемых чисел уменьшается в двое, а число умножений увеличивается в 3 раза. Это значит, что одно углубление уменьшает число элементарных операций в $4/3$ раза. Обрывание "погружения" на длине числа 25 приводит к "недопогружению" на 4-5 уровней, то есть число элементарных умножений становится больше в 3-4 раза. Тут правда, не учитывается быстро нарастающее с погружением количество суммирований.

[Dmitriy40]

B@R5uk в сообщении #1439361 писал(а):

Dmitriy40 в сообщении #1439353 писал(а):

Наклон последнего графика у Вас 25 раз на десятичный порядок по $L$

Не, наклон равен $\times10^{\log_23}=\times38.46$ на десятичный порядок (если можно так выразиться для логарифмического масштаба).

Я Вас не понимаю. Смотрю на Ваш прошлый график, точки $L=600$ и $L=10000$, вижу отношение $100$ раз по величине при изменении аргумента в $16$ раз, т.е. порядок по значениям набегает примерно за $4$ раза по аргументу, или значения растут в $2{,}5$ раза быстрее аргумента. Проверяю, $L=2000$ и $L=8000$, значения снова отличаются в $10$ раз при отличии аргумента вчетверо. Значит наклон правильный. И значит при возрастании $L$ с $10^5$ до $10^6$ значение увеличится с 4с до 100с (примерно). Что не так?

B@R5uk в сообщении #1439361 писал(а):

Для $L=10^6$ время работы будет $10^{12}\cdot 4.2\cdot 10^{-8}=4.2\cdot 10^4$ секунд или 11 часов 40 минут.

Квадратичный алгоритм не интересен, считаем Карацубу.

B@R5uk в сообщении #1439365 писал(а):

Ну почему же? Вы сами написали, что операция умножения в среднем занимает 3 такта. Это почти четверть от этих 13 тактов.

Нет, я написал что она может занимать от 1 до 5 тактов (смотря сможет ли спариться с другими умножениями), но деление то занимает 22-29 такта! Если не спарится или 8-11 тактов если все деления спарятся. Под спариванием я имею в виду как минимум (прочие условия лень обговаривать) отсутствие зависимости по данным между командами. Так как здесь означенная зависимость явно есть, то время выполнения будет 27-34 такта минимум (разброс зависит от конкретных чисел делимого и делителя). А у Вас 84млн итераций выполняется за 4с на частоте 2ГГц, т.е. $\frac{4 \cdot 2 \cdot 10^9}{8{,}41 \cdot 10^7} \approx 95$ тактов на итерацию Карацубы. Не 13.
Да, если нижние уровни считаются квадратично, то количество умножений будет выше и соответственно тактов на итерацию меньше, но 13 всё равно не получается, в лучшем случае 22-25.
Кстати первый уровень, где возводятся в квадрат двухразрядные числа, можно квадрат считать тоже за 3 умножения вместо 4-х (потому что произведение старшей части на младшую одинаково для обоих вариантов комбинации сомножителей) даже без Карацубы. Правда только квадрат, не умножение, но вроде бы квадратов там вдвое больше произведений. Это вроде даёт около 20% ускорения ...

-- 11.02.2020, 15:27 --

Xaositect в сообщении #1439364 писал(а):

[Я практически уверен, что в этом случае основное время занимает библиотечная функция умножения,

Замерялось время именно только её, кодом t=getabstime(); z=x^2; t=getabstime()-t; print(t);. Время вызова getabstime() на порядки меньше миллисекунд и погрешности не вносит. Тем более что реальная точность порядка 10% (тик времени 16мс). Сюда же уходит и время размещения новой переменной z (а число в x подобрано так чтобы z не сильно превышало x).

[B@R5uk]

B@R5uk в сообщении #1439361 писал(а):

Для $L=10^6$ время работы будет $10^{12}\cdot 4.2\cdot 10^{-8}=4.2\cdot 10^4$ секунд или 11 часов 40 минут.

Не правильно посчитал. Надо так: $(10^6)^{\log_23}\cdot 4.2\cdot 10^{-8}\approx 136$ секунд.

-- 11.02.2020, 17:30 --

Dmitriy40 в сообщении #1439374 писал(а):

А у Вас 84млн итераций выполняется за 4с на частоте 2ГГц, т.е. $\frac{4 \cdot 2 \cdot 10^9}{8{,}41 \cdot 10^7} \approx 95$ тактов на итерацию Карацубы. Не 13.

Нет такого понятия в моей программе, как итерация Карацубы. Просто потому что алгоритм не доходит до элементарных разрядов и переходит к умножению в столбик, когда длина числа становится меньше 25. Более того, для разных частей множителей этот переход может происходить на разных значениях длины числа.

И про 13 тактов я писал для умножения в столбик.

-- 11.02.2020, 17:36 --

Dmitriy40 в сообщении #1439374 писал(а):

но деление то занимает 22-29 такта!

Я считал, что процессор с частотой 2 ГГц за секунду выполняет $2\cdot 10^9$ тактов. Из эксперимента и этого предложения я получил, что длина итерации умножения 13 тактов. Так что либо на моём процессоре деление выполняется значительно быстрее, чем пишите вы, либо моё предположение не верно, и за один тик тактовой частоты может выполняться несколько тактов процессора. Есть ещё вероятность, что я обсчитался (но я что-то не вижу, где я мог это сделать) или что функция измерения времени в Java врёт, что тоже маловероятно.

[Dmitriy40]

B@R5uk в сообщении #1439397 писал(а):

Я считал, что процессор с частотой 2 ГГц за секунду выполняет 2 млн. тактов.

А на самом деле два миллиарда.

B@R5uk в сообщении #1439397 писал(а):

за один тик тактовой частоты может выполняться несколько тактов процессора.

Это простите бред и тавтология.

Введите счётчик умножений в программу и посчитайте точную скорость.

-- 11.02.2020, 17:47 --

Хорошо, по другому. На графике есть точка $L=10000$ со значением 0.1с, для $10000$ разрядов Карацуба выполняет $3^{\log_2 10^4} \approx 2.187\cdot 10^6$ умножений. 2ГГц умножить на 0.1с и поделить на 2.2млн умножений получаем снова 90 тактов умножение.
Снова, что посчитал не так?

[B@R5uk]

Dmitriy40 в сообщении #1439402 писал(а):

и посчитайте точную скорость.

Для метода Карацубы нет смысла, а для умножения в столбик уже посчитано.

-- 11.02.2020, 17:48 --

Dmitriy40 в сообщении #1439402 писал(а):

для $10000$ разрядов Карацуба выполняет $3^{\log_2 10^4} \approx 2.187\cdot 10^6$ умножений.

Нет. В моей программе выполняется значительно больше умножений.

-- 11.02.2020, 18:06 --

ОК. Вы меня убедили посчитать количество элементарных умножений. Вот код:

Используется синтаксис Java

import java.util.*;

class BigNumber {
        
        private final static int base = 1000000000;
        private static int karatsubaThreshold = 25;
        
        private static long counter = 0;
        
        private int[] digits;
        
        private BigNumber() {
        }
        
        public BigNumber(int arg) {
                if (0 > arg) {
                        throw new IllegalArgumentException("Numbers must be positive");
                }
                digits = new int[2];
                digits[0] = arg % base;
                digits[1] = arg / base;
        }
        
        public BigNumber(String arg) {
                BigNumber temp, ten;
                ten = new BigNumber(10);
                temp = new BigNumber(0);
                for (int k = 0; arg.length() > k; ++k) {
                        char c = arg.charAt(k);
                        if (('0' <= c) && (c <= '9')) {
                                temp = temp.multiplySimple(ten).add(new BigNumber(c - '0'));
                        }
                }
                digits = temp.digits;
        }
        
        public BigNumber(BigNumber arg) {
                digits = new int[arg.digits.length];
                for (int k = 0; arg.digits.length > k; ++k) {
                        digits[k] = arg.digits[k];
                }
        }
        
        public BigNumber(Random rng, int size) {
                digits = new int[size];
                for (int k = 0; size > k; ++k) {
                        digits[k] = rng.nextInt(base);
                }
        }
        
        public BigNumber add(BigNumber arg) {
                int k, size1, size2, sum;
                BigNumber augend, addend, result;
                size1 = this.digits.length - 1;
                if (0 != this.digits[size1]) {
                        ++size1;
                }
                size2 = arg.digits.length - 1;
                if (0 != arg.digits[size2]) {
                        ++size2;
                }
                if (size1 < size2) {
                        augend = arg;
                        addend = this;
                        sum = size1;
                        size1 = size2;
                        size2 = sum;
                } else {
                        augend = this;
                        addend = arg;
                }
                result = new BigNumber();
                result.digits = new int[size1 + 1];
                for (k = 0; size1 > k; ++k) {
                        result.digits[k] = augend.digits[k];
                }
                sum = 0;
                for (k = 0; size2 > k; ++k) {
                        sum += result.digits[k];
                        sum += addend.digits[k];
                        if (base > sum) {
                                result.digits[k] = sum;
                                sum = 0;
                        } else {
                                result.digits[k] = sum - base;
                                sum = 1;
                        }
                }
                while (0 != sum) {
                        sum += result.digits[k];
                        if (base > sum) {
                                result.digits[k] = sum;
                                sum = 0;
                        } else {
                                result.digits[k] = sum - base;
                                sum = 1;
                        }
                        ++k;
                }
                return result;
        }
        
        public BigNumber multiplyKaratsuba(BigNumber arg) {
                int k, l, size1, size2, offset, limit, sum;
                BigNumber result, a, b, a1, a2, b1, b2, axb1, axb2, apa, bpb, temp;
                size1 = digits.length;
                if (0 == digits[size1 - 1]) {
                        --size1;
                }
                size2 = arg.digits.length;
                if (0 == arg.digits[size2 - 1]) {
                        --size2;
                }
                if (karatsubaThreshold > size1 || karatsubaThreshold > size2) {
                        return this.multiplySimple(arg);
                }
                if (size2 < size1) {
                        a = this;
                        b = arg;
                        offset = (size1 + 1) / 2;
                } else {
                        a = arg;
                        b = this;
                        offset = size2;
                        size2 = size1;
                        size1 = offset;
                        offset = (size1 + 1) / 2;
                }
                //==============================
                result = new BigNumber();
                result.digits = new int[size1 + size2];
                a1 = new BigNumber();
                a2 = new BigNumber();
                a1.digits = new int[offset];
                a2.digits = new int[size1 - offset];
                for (k = 0; offset > k; ++k) {
                        a1.digits[k] = a.digits[k];
                }
                for (l = 0; size1 > k; ++k, ++l) {
                        a2.digits[l] = a.digits[k];
                }
                //==============================
                if (size2 > offset) {
                        b1 = new BigNumber();
                        b2 = new BigNumber();
                        b1.digits = new int[offset];
                        b2.digits = new int[size2 - offset];
                        for (k = 0; offset > k; ++k) {
                                b1.digits[k] = b.digits[k];
                        }
                        for (l = 0; size2 > k; ++k, ++l) {
                                b2.digits[l] = b.digits[k];
                        }
                        //==============================
                        axb1 = a1.multiplyKaratsuba(b1);
                        axb2 = a2.multiplyKaratsuba(b2);
                        apa = a1.add(a2);
                        bpb = b1.add(b2);
                        temp = apa.multiplyKaratsuba(bpb);
                        //==============================
                        limit = axb1.digits.length - 1;
                        if (0 != axb1.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0; limit > k; ++k) {
                                sum += temp.digits[k];
                                sum -= axb1.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                        }
                        while (0 != sum) {
                                sum += temp.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                                ++k;
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0; limit > k; ++k) {
                                sum += temp.digits[k];
                                sum -= axb2.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                        }
                        while (0 != sum) {
                                sum += temp.digits[k];
                                if (0 > sum) {
                                        temp.digits[k] = sum + base;
                                        sum = -1;
                                } else {
                                        temp.digits[k] = sum;
                                        sum = 0;
                                }
                                ++k;
                        }
                        //==============================
                        limit = axb1.digits.length;
                        for (k = 0; limit > k; ++k) {
                                result.digits[k] = axb1.digits[k];
                        }
                        //==============================
                        limit = temp.digits.length - 1;
                        while (0 == temp.digits[limit]) {
                                --limit;
                        }
                        ++limit;
                        sum = 0;
                        for (k = 0, l = offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += temp.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0, l = 2 * offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += axb2.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                } else {
                        axb1 = a1.multiplyKaratsuba(b);
                        axb2 = a2.multiplyKaratsuba(b);
                        //==============================
                        limit = axb1.digits.length;
                        for (k = 0; limit > k; ++k) {
                                result.digits[k] = axb1.digits[k];
                        }
                        //==============================
                        limit = axb2.digits.length - 1;
                        if (0 != axb2.digits[limit]) {
                                ++limit;
                        }
                        sum = 0;
                        for (k = 0, l = offset; limit > k; ++k, ++l) {
                                sum += result.digits[l];
                                sum += axb2.digits[k];
                                if (base > sum) {
                                        result.digits[l] = sum;
                                        sum = 0;
                                } else {
                                        result.digits[l] = sum - base;
                                        sum = 1;
                                }
                        }
                        if (0 != sum) {
                                result.digits[l] = sum;
                        }
                }
                return result;
        }
        
        public BigNumber multiplySimple(BigNumber arg) {
                int k, l, size1, size2;
                long mult, sum;
                BigNumber result;
                size1 = digits.length;
                if (0 == digits[size1 - 1]) {
                        --size1;
                }
                size2 = arg.digits.length;
                if (0 == arg.digits[size2 - 1]) {
                        --size2;
                }
                result = new BigNumber();
                result.digits = new int[size1 + size2];
                for (k = 0; size1 > k; ++k) {
                        mult = digits[k];
                        sum = 0;
                        for (l = 0; size2 > l; ++l) {
                                sum += result.digits[k + l];
                                sum += mult * arg.digits[l];
                                result.digits[k + l] = (int) (sum % base);
                                sum /= base;
                                ++counter;
                        }
                        if (0 != sum) {
                                result.digits[k + l] = (int) sum;
                        }
                }
                return result;
        }
        
        public int compareTo(BigNumber arg) {
                int k, flag;
                BigNumber a, b;
                if (this.digits.length > arg.digits.length) {
                        a = this;
                        b = arg;
                        flag = 1;
                } else {
                        a = arg;
                        b = this;
                        flag = -1;
                }
                k = a.digits.length;
                while (b.digits.length > k) {
                        --k;
                        if (0 != a.digits[k]) {
                                return flag;
                        }
                }
                do {
                        --k;
                        if (b.digits[k] < a.digits[k]) {
                                return flag;
                        } else if (b.digits[k] > a.digits[k]) {
                                return -flag;
                        }
                } while (0 != k);
                return 0;
        }
        
        public String toString() {
                int k, l, value;
                l = 12 * digits.length;
                char[] buffer = new char[l];
                for (k = 0; digits.length > k; ++k) {
                        value = digits[k];
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = ' ';
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = ' ';
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value % 10);
                        value /= 10;
                        buffer[--l] = (char) ('0' + value);
                        buffer[--l] = ' ';
                }
                return new String(buffer);
        }
        
        public static void resetCounter() {
                counter = 0;
        }
        
        public static long getCounter() {
                return counter;
        }
}

public class Study_Karatsuba_method_3 {
        
        private final static Random rng = new Random();
        
        public static void main(String[] args) {
                int k, numberSize;
                long time1, time2;
                BigNumber a, b, c;
                Locale.setDefault(new Locale("en", "US"));
                numberSize = 10000;
                for (k = 0; 35 > k; ++k) {
                        a = new BigNumber(rng, numberSize);
                        b = new BigNumber(rng, numberSize);
                        BigNumber.resetCounter();
                        time1 = System.nanoTime();
                        c = a.multiplyKaratsuba(b);
                        time2 = System.nanoTime();
                        System.out.println(String.format("%6d %12d %12.9f", numberSize, BigNumber.getCounter(), 1e-9 * (time2 - time1)));
                }
        }
}
 

И вот результат работы:

Используется синтаксис Text

 10000      7762625  0.299442430
 10000      7761123  0.152028134
 10000      7760900  0.121062726
 10000      7763604  0.093609154
 10000      7760661  0.096817640
 10000      7761604  0.091336370
 10000      7763891  0.092610832
 10000      7764258  0.091099750
 10000      7762719  0.098989308
 10000      7767487  0.095488256
 10000      7760553  0.089790384
 10000      7762614  0.091653572
 10000      7764258  0.092279254
 10000      7763740  0.089931020
 10000      7765877  0.092003114
 10000      7762639  0.090920102
 10000      7763503  0.090572616
 10000      7763651  0.089537850
 10000      7763839  0.090674758
 10000      7762070  0.091432864
 10000      7762531  0.089760614
 10000      7761867  0.090322138
 10000      7764511  0.090200490
 10000      7762740  0.091925610
 10000      7762946  0.092419380
 10000      7763667  0.090887766
 10000      7762169  0.090279022
 10000      7763453  0.088911142
 10000      7761458  0.090633696
 10000      7763972  0.091469310
 10000      7762862  0.090464312
 10000      7763901  0.091342016
 10000      7763873  0.091504724
 10000      7762665  0.092062140
 10000      7762524  0.090809236
 

Количество умножений в 3,5 раза больше, как я предсказывал ранее.

-- 11.02.2020, 18:21 --

Кстати, к вопросу о накладных расходах метода Карацубы. В программе выше я изменил пороговую константу с 25 на 100. В результате число элементарных умножений увеличилось почти в 2 раза, а общее время работы возросло всего на 15%:

Используется синтаксис Text

 10000     13462206  0.186089100
 10000     13461717  0.142993454
 10000     13457864  0.102000696
 10000     13462274  0.106213150
 10000     13459682  0.102767016
 10000     13463599  0.102805512
 10000     13462183  0.104826792
 10000     13463912  0.107848960
 10000     13461637  0.102975922
 10000     13461799  0.102083334
 10000     13458580  0.102359478
 10000     13462588  0.102815266
 10000     13461956  0.105659838
 10000     13462108  0.102811160
 10000     13461492  0.103465584
 10000     13462271  0.103337266
 10000     13464394  0.106935328
 10000     13460140  0.105830246
 10000     13459911  0.106004246
 10000     13460698  0.106162336
 10000     13459131  0.105200972
 10000     13459757  0.103760206
 10000     13460219  0.104334562
 10000     13463139  0.103151972
 10000     13459521  0.103030842
 10000     13459356  0.103042646
 10000     13463611  0.140746336
 10000     13463218  0.104086650
 10000     13462737  0.102839902
 10000     13463136  0.105179926
 10000     13459132  0.103151974
 10000     13464544  0.103300824
 10000     13463217  0.102754184
 10000     13460866  0.102460080
 10000     13461252  0.102064344
 

[Dmitriy40]

Может у меня математика другая ... Делю 7.76млн на 2.81млн и получаю 2.76 раза вместо 3.5 раз ... 0.1с умножаю на 2ГГц и делю на 7.76млн и получаю 26 тактов ... Очень близко к времени выполнения деления, да.
Ладно, Вас скорость устраивает, меня тем более.

[B@R5uk]

Dmitriy40 в сообщении #1439402 писал(а):

Это простите бред и тавтология.

Да нет, тактовая частота процессора и частота тактов процессора — это обычно разные вещи. Правда как правило последняя не выше первой.

Накладные расходы лучше смотреть для более длинных чисел:

Используется синтаксис Text

karatsubaThreshold = 100
100000    566794047  4.357720768
100000    566769733  4.231156238
100000    566780669  4.230192824
100000    566779807  4.275271254
100000    566789408  4.237325298
100000    566783642  4.233262722
100000    566778046  4.283848602
100000    566793261  4.232994794
100000    566787917  4.231131604
100000    566772570  4.249148606
100000    566774151  4.235209580

karatsubaThreshold = 25
100000    271906431  4.103525638
100000    271883695  3.764891538
100000    271911651  3.696830162
100000    271922053  3.698495228
100000    271909434  3.704785936
100000    271869285  3.708154562
100000    271873103  3.741753586
100000    271932559  3.761765688
100000    271882355  3.746463916
100000    271891842  3.731030746
100000    271929168  3.728472580
100000    271933021  3.775034890
100000    271900668  3.713098946
100000    271937707  3.701850514
100000    271909856  3.716171930
 

-- 11.02.2020, 18:34 --

Dmitriy40 в сообщении #1439423 писал(а):

Делю 7.76млн на 2.81млн и получаю 2.76 раза вместо 3.5 раз

Вы ж писали вот что:

Dmitriy40 в сообщении #1439402 писал(а):

для $10000$ разрядов Карацуба выполняет $3^{\log_2 10^4} \approx 2.187\cdot 10^6$ умножений.

$7.76/2.187=3.55$

-- 11.02.2020, 18:37 --

Dmitriy40 в сообщении #1439423 писал(а):

0.1с умножаю на 2ГГц и делю на 7.76млн и получаю 26 тактов ... Очень близко к времени выполнения деления, да.

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

-- 11.02.2020, 18:40 --

Dmitriy40 в сообщении #1439423 писал(а):

Ладно, Вас скорость устраивает, меня тем более.

А какой есть выбор? Если делать всё в двоичной системе счисления, то конвертация в десятичную займёт годы. Во всяком случае я не владею быстрым алгоритмом.

[arseniiv]

Пожалуйста: https://gmplib.org/manual/Binary-to-Radix.html.

-- Вт фев 11, 2020 21:26:54 --

Тут: https://stackoverflow.com/questions/36664780/binary-to-decimal-on-huge-numbers ещё поминаются два решения уже конкретно для основания 10, но я не нашёл пока никаких сравнений общего из GMP с этими; спрашивавший собирался сравнить, но там не отписался.