Стоит показать, что строчку long t = (T - m * N) >>> 32; можно заменить на long t = (T >> 32) - (m * N) >> 32; То есть для произведения m * N нужные только верхняя часть результата.
А значит на языке java, где пока нет 128-битного типа данных, для 64-битных чисел можно написать что-то вроде:
static long redc(long Thi, long Tlo, long N, long M) { long m = Tlo * M; long t = Math.unsignedMultiplyHigh(m, N);
return Thi - t + (Thi < t ? N : 0); }
static long montgomeryMultiply(long a, long b, long N, long M) { return redc(Math.unsignedMultiplyHigh(a, b), a * b, N, M); }
Получается для умножения Монтгомери нужно сделать: одно полное умножение; одно умножение с получением верхней части результата одно умножение с получением нижней части результата
Кстати, умножение Монтгомери можно делать и тогда когда только одно число в форме Монтгомери, тогда результат будет тоже не в форме.
Я боюсь что в этом случае количество умножений может сильно вырасти. Если кто-то подсунет плохие данные на входе. Тут можно было бы отсортировать или ещё что-то сделать, но это затормозит общий случай. В условии к задаче на хайлоад к сожалению ничего не сказано про данные. Вдруг там на входе все числа составные и код который печатает ноль побеждает.
А как проверять сразу по 4? Там же код делает умножения в зависимости от числа нулей числа n-1. Ну и в возведении в степень тоже кол-во умножений зависит от входного числа.
Умножение Монтгомери позволило бы работать с 32-битным диапазонов, но что-то в данном конкретном случае для 26-битного диапазона оно не быстрее double, почему? И векторизовать там непонятно как, нехватает сильно функций возвращающих верхние биты умножения двух целых чисел.
Круто
.
Я смотрю вы про чужие сиеста любите думать, может и мне подскажите как быть
Это третий абзац , не второй
Ну золотая пропорция это алгебраическое число
Хабр заблокирует, он хорошо устроился - договаривается
Что? 19 лет назад Исполнителем был интернет провайдер
Автор этого канала сам то уже заполнил форму? Где ссылка?
Где вы были 12 лет?
Стоит показать, что строчку
long t = (T - m * N) >>> 32;
можно заменить наlong t = (T >> 32) - (m * N) >> 32;
То есть для произведения m * N нужные только верхняя часть результата.А значит на языке java, где пока нет 128-битного типа данных, для 64-битных чисел можно написать что-то вроде:
static long redc(long Thi, long Tlo, long N, long M) {long m = Tlo * M;
long t = Math.unsignedMultiplyHigh(m, N);
return Thi - t + (Thi < t ? N : 0);}
static long montgomeryMultiply(long a, long b, long N, long M) {return redc(Math.unsignedMultiplyHigh(a, b), a * b, N, M);
}
Получается для умножения Монтгомери нужно сделать:
одно полное умножение;
одно умножение с получением верхней части результата
одно умножение с получением нижней части результата
Кстати, умножение Монтгомери можно делать и тогда когда только одно число в форме Монтгомери, тогда результат будет тоже не в форме.
Я боюсь что в этом случае количество умножений может сильно вырасти. Если кто-то подсунет плохие данные на входе. Тут можно было бы отсортировать или ещё что-то сделать, но это затормозит общий случай. В условии к задаче на хайлоад к сожалению ничего не сказано про данные. Вдруг там на входе все числа составные и код который печатает ноль побеждает.
А как проверять сразу по 4? Там же код делает умножения в зависимости от числа нулей числа n-1. Ну и в возведении в степень тоже кол-во умножений зависит от входного числа.
Поделитесь пожалуйста секретом какой же код самый быстрый
Умножение Монтгомери позволило бы работать с 32-битным диапазонов, но что-то в данном конкретном случае для 26-битного диапазона оно не быстрее double, почему? И векторизовать там непонятно как, нехватает сильно функций возвращающих верхние биты умножения двух целых чисел.
P.S. Кстати, в Java же добавляют Vector API.