— Кто является автором метода "Binary Splitting" ?
— А. А. Карацуба. «Binary plitting» — это другое имя метода «Divide and Conquer».
— Кто развивал метод «Binary Splitting» (= «Divide and Conquer») ?
— Если под словом «развивал» иметь ввиду основанные на «Divide and Conquer» алгоритмы, то его развивали и применяли на практике сотни людей, и среди этих алгоритмов наиболее широко известными являются алгоритмы Быстрого Преобразования Фурье (FFT) и Быстрого Умножения Матриц.
— Кто является автором метода Быстрого суммирования рядов (специального вида) и когда этот метод возник?
— Этот метод (названный впоследствии БВЕ) найден мной в 1990 году. Особенностью метода БВЕ является то, что с его помощью можно вычислять быстро не только все элементарные трансцендентные функции, но и многие высшие трансцендентные функции (такие, например, как гамма-функция Эйлера, функции Бесселя, гипергеометрические ряды), для вычисления которых до этого быстрых алгоритмов не было.
— Существовал ли до этого какой-либо метод быстрого вычисления константы e, константы π ?
— Только метод Арифметико-Геометрически Средних (Гаусса). Под «быстрым вычислением» подразумевается вычисление, битовая сложность которого близка, асимптотически, к оптимальной (неулучшаемой).
— Почему Вы утверждаете, что метод быстрого вычисления сумм путём попарного сложения возник в 1990 году? Ведь люди с давних времён складывали числа попарно для получения их суммы.
— Сложить несколько чисел попарно (или не попарно) не является проблемой. Проблемой является быстрое вычисление сумм вида (1),(2) (см. текст «Быстрые алгоритмы и метод БВЕ»). Попарного сложения для быстрого вычисления таких сумм не достаточно.
— Используется ли при вычислениях с помощью «БВЕ» метод «Divide and Conquer» (= «Binary Splitting»)?
— Да, конечно. Подразумевается, что произведения чисел вычисляются с помощью «Binary Splitting».
— До 1990 года предлагались алгоритмы для вычисления экспоненциальной функции с помощью «Binary Splitting».
— Действительно, такие алгоритмы были. Метод «Binary Splitting» применяется для быстрого вычисления произведения, и кажется естественным применить его для вычисления мультипликативной функции. Однако, быстрого алгоритма для вычисления экспоненциальной функции построено не было, потому что представить эту функцию в виде «удачно организованного» произведения оказалось недостаточно для создания быстрого алгоритма. Нужно было ещё быстро вычислить каждый множитель этого произведения, который в свою очередь представлял собой «сложную» функцию. Чтобы быстро вычислять такие множители-функции как раз и нужен метод БВЕ.
— Как отличить методы «Binary Splitting» и БВЕ ?
— Очень просто. Если от шага (процесса) к шагу количество участвующих в процессе (вычисления) чисел увеличивается, а их длина (количество их знаков) уменьшается, то это «Binary Splitting» (= «Divide and Conquer»): название процесса соответстует процессу; «splitting» — это «расщепление». Если же от шага к шагу количество участвующих в процессе чисел уменьшается, а их длина растёт, то это метод БВЕ. На последнем шаге в «Divide and Conquer» производится перемножение и сложение многих малозначных чисел. На последнем шаге БВЕ производится деление одного большого целого числа на другое.
— Методы «Binary Splitting» и БВЕ похожи: в первом из них перемножаемые числа представляются в виде суммы двух чисел, во втором числа складываются попарно. Можно ли считать метод БВЕ «параллельным Binary Splittingом»?
— Нет. Это совершенно разные, в некотором смысле обратные друг другу процессы. Кроме того. Недостаточно пошагового расщепления перемножаемых чисел для того, чтобы построить метод быстрого умножения, такой как «Binary Splitting». Недостаточно складывать слагаемые ряда попарно чтобы получить быстрый процесс вычисления сумм (вида (1),(2) и схожих с ними), такой как БВЕ. Об особенностях этих методов см. текст «Быстрые алгоритмы и метод БВЕ».
— В некоторых западных пакетах программ, в том числе в таких, как Mathematica и Maple, по словам разработчиков, метод БВЕ внедрён под именем «Binary Splitting». Может быть стоит согласиться с этим названием, раз многие программисты из западных стран называют этот метод таким именем?
— Нет. Даже если все, как западные, так и восточные, программисты будут называть интегрирование дифференцированием, оно, интегрирование, от этого дифференцированием не станет. Метод быстрого суммирования рядов специального вида — БВЕ — с увеличивающимися от шага к шагу вычисляемыми значениями не может называться «splitting» — расщепление. Это ошибочное название. Это ошибка.