2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Ускорение деления
Сообщение14.12.2019, 20:39 
Аватара пользователя
Попытался предыдущий алгоритм запустить в обратную сторону. То есть от $\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]$ ?

 
 
 
 Re: Ускорение деления
Сообщение14.12.2019, 22:55 
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 компиляцией (потому что без неё о скорости отдельно делений говорить вообще нет смысла) - там обычно есть и достаточно быстрые деления.

 
 
 
 Re: Ускорение деления
Сообщение15.12.2019, 20:06 
Аватара пользователя
Dmitriy40 в сообщении #1430231 писал(а):
задача всё больше выглядит надуманной

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

Dmitriy40 в сообщении #1430231 писал(а):
А зачем?

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

 
 
 
 Re: Ускорение деления
Сообщение16.12.2019, 01:32 
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 раз.

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

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

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

 
 
 [ Сообщений: 20 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group