Ускорение деления

[B@R5uk]

Попытался предыдущий алгоритм запустить в обратную сторону. То есть от $\sqrt{x}$ в сторону нуля. У меня получилась, а рабочий диапазон из эксперимента вышел $\left[\sqrt{x/2},\sqrt{x}\right]$. В этом нет ничего удивительно, если так подумать. Остаток от деления величины $x$ на величины $\sqrt{x}+y$ ведёт себя как квадратичная функция $y$, поэтому, что в сторону роста делителя, что в сторону убывания, — всё равно.

Потом я заметил, что условие (divisor > remainderShift) слишком жёсткое, и, когда оно нарушается, в цифрах меняется не так уж много: стандартное приращение quotient увеличивается на 1, стандартное приращение remainderShift увеличивается на 2, плюс происходят разовые поправки типа сброса значения remainderShift. Замеченные особенности сразу же пустил в дело. В результате получился новый алгоритм, который перебирает делители в обратную сторону, а диапазон работы у него оказался равным $\left[ \sqrt[3]{2x},\sqrt{x} \right]$. Качественное улучшение!!!

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

import java.util.*;

public class StudyDivisionReplacement3 {
        
        private static final Random rng = new Random();
        
        public static void main(String[] args) {
                long dividend, divisor, startDivisor, quotientRef, remainderRef,
                                        quotient, quotientShift, remainder, remainderShift, remainderSuperShift;
                dividend = 100000000l + rng.nextInt(10000000);
                //dividend = 1000000;
                startDivisor = (long) Math.sqrt(dividend);
                divisor = startDivisor;
                quotient = dividend / divisor;
                quotientShift = 1;
                remainder = dividend % divisor;
                if (divisor == quotient) {
                        remainderShift = -1;
                } else {
                        remainderShift = 0;
                }
                remainderSuperShift = 2;
                boolean flag = true;
                while (divisor > remainderSuperShift) {
                        //*
                        quotientRef = dividend / divisor;
                        remainderRef = dividend % divisor;
                        if (quotientRef != quotient || remainderRef != remainder) {
                                System.out.println(String.format("Error: %d / %d = %d (%d) not %d (%d)",
                                                dividend, divisor, quotientRef, remainderRef, quotient, remainder));
                                flag = false;
                                break;
                        }
                        //*/
                        --divisor;
                        remainderShift += remainderSuperShift;
                        if (remainderShift >= divisor) {
                                ++quotientShift;
                                remainderShift -= divisor;
                                remainderSuperShift += 2;
                        }
                        remainder += remainderShift;
                        if (remainder >= divisor) {
                                ++quotient;
                                remainder -= divisor;
                                ++remainderShift;
                        }
                        quotient += quotientShift;
                }
                if (flag) {
                        System.out.println(String.format("Dividend: %d\nStart: %d\nFinish: %d\n",
                                                                dividend, startDivisor, divisor));
                        System.out.println(String.format("%6d%6d%6d%6d%6d%6d",
                                        divisor, quotient, quotientShift, remainder,
                                                                remainderShift, remainderSuperShift));
                }
        }
}

/*
 *    1000  12
 *    2000  15
 *    5000  20
 *   10000  26
 *   20000  33
 *   50000  46
 *  100000  58
 *  200000  73
 *  500000  99
 * 1000000 125
 */
 

Теперь размышляю над двумя вопросами. Первый: можно ли будет пустить этот алгоритм в прямую сторону, а не в обратную? И второй: а нельзя ли ввести ещё одну-другую поправочную величину и получить рабочий диапазон $\left[ \sqrt[4]{C\cdot x},\sqrt{x} \right]$ ?

[Dmitriy40]

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

И второй: а нельзя ли ввести ещё одну-другую поправочную величину и получить рабочий диапазон $\left[ \sqrt[4]{C\cdot x},\sqrt{x} \right]$ ?

А зачем? Для вашего заявленного $x=0..10^{30}$ значение $\sqrt[3]{2x} \approx 0..1{,}26\cdot10^{10}$, что составляет жалкие тысячную долю процента от всего диапазона $0..10^{15}$. Так что если даже деление для всех чисел $0..10^{10}$ в тысячу раз медленнее, всё равно общая скорость из-за него не уменьшится более чем на 1%. А чрезмерное усложнение кода приводит к ухудшению предсказания переходов и замедлению.
Простите, но задача всё больше выглядит надуманной: где есть Java с JIT компиляцией (потому что без неё о скорости отдельно делений говорить вообще нет смысла) - там обычно есть и достаточно быстрые деления.

[B@R5uk]

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

задача всё больше выглядит надуманной

Не цените вы всю красоту целочисленной арифметики и магию цифирь!!! Ой, не цените...

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

А зачем?

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

[Dmitriy40]

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

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

Уж поверьте тому кто писал на ассемблере свою процедуру извлечения кубического корня из 128 битного числа - разница совсем непринципиальна. Как в сложности кода, так и в скорости работы. Это первое.
Второе, корень считается лишь один раз, а потом делается $10^{15}$ каких-то вычислений. Уже при таких соотношениях корень можно вычислять хоть через логарифм с делением и экспоненту, реализованных хоть на перле, всё равно результат будет получен за считанные доли секунды и итоговая скорость существенно не уменьшится. А если Вы хотите и ещё расширять диапазон, то проигрыш будет ещё меньше.
Третье, кубический корень вообще считать не нужно, деление нужно, а корни нет, никакие. Достаточно проверять некоторое простое условие (что точность следующей точки стала достаточной) и переходить от делений к сложениям/вычитаниям. Это уже исключает деления из 99.99% диапазона, а с увеличением чисел и ещё больше.
Четвёртое. Заявления про BigInteger несколько наивны, $10^{15}$ итераций ещё можно выполнить за более-менее разумное время (пару недель/месяцев), а вот скажем $10^{20}$ - уже нет, даже за тысячу лет. Ну за сотни, если грамотно GPU использовать.

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

Не цените вы всю красоту целочисленной арифметики и магию цифирь!!! Ой, не цените...

И пятое. Одно из правил оптимизации гласит "избегайте чрезмерной оптимизации". В вашем случае - если расчётный прирост скорости в самом идеальном случае менее 0.1%, то надо остановиться и заняться другими участками кода, оптимизация которых даст на порядки больший выигрыш.

Так что исходная задача практически решена, а дальше уже извращения ради любви к искусству спортивного интереса, IMHO.

(PS. Насчёт не ценю целочисленной арифметики)

Ну-ну, вообще-то я делал например вычисление d=(a+b)%c за, внимание, 1/16 такта процессора, т.е. 16 чисел за такт!
Или в следующем сообщении там же пример ускорения кода с делениями с 100-130 тактов на число до 4 чисел на такт. В 500 раз.

[arseniiv]

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

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

Можно кстати особо не считать: взять профайлер и поездить им по вариантам кода. Тем более что если есть нужда экономить такты и байты, он необходим. Я недавно наконец-таки попользовался живым настоящим профайлером (правда, для питона, и он там в комплекте, ну и что ж), и это оказалось просто и совсем не больно. А, ну и заодно я увидел как обманчивы иногда наши ожидания о том, что ускорит код, а что нет; точнее, не внесут ли ускоряющие изменения дополнительно и замедление, сводящее первые на нет. (Хотя это были относительно высокоуровневые части с причинами, которые действительно a posteriori очевидны и вообще с опытом должны прогнозироваться сразу, ну в любом случае опасность без профиля поиска ещё более мелких оптимизаций пара эпизодов работы с профайлером прямо глазам смотрящего показывает.) Так что посоветуем этого и ТС. Я думаю, для JVM тоже найдутся понятные в использовании.

-- Пн дек 16, 2019 06:37:59 --

Я тут опять заскобочился, но надеюсь что читаемо.