SciFi (10.02.2021 11:24, просмотров: 4696)Недавно захотелось кое-где немного ускорить квадратный корень.
Оказывается, это очень просто >>>
ส็็็็็็็็็็็็็็็็็็็็็็็็็༼ ຈل͜ຈ༽ส้้้้้้้้้้้้้้้้้้้้้้้
https://stackoverflow.com/questions/34187171/fast-integer-square-root-approximation
В приведённом коде можно подкручивать число итераций и начальную точку, подстраивая рабочий диапазон и точность:
-
- Формула из квейка не о том? - LightElf(11.02.2021 01:53, ссылка)
- А если Ньютоном считать a = 1/sqrt(val), то можно обойтись и без
деления.. :) Xaoc(68 знак., 10.02.2021 17:44,
)
- Там вроде бы первый из предложенных методов - Ньютон. Без деления
никак. Или нужен трюк. - Kpoк(10.02.2021 17:55)
- Упс.. ----- Xaoc(46 знак., 10.02.2021 18:08, )
- ну мы же делим остаток на производную, чтобы посчитать довесок к
аргументу. В эпоху дорогого деления принимали наклон (производную)
постоянными для всех точек итерации. Это позволяло подменить
деление умножением. Но совсем без я что-то не припомню. - Kpoк(10.02.2021 18:17)
- Вот формула для итераций: Xaoc(54 знак., 10.02.2021 18:24, )
- Да. В пять шагов сходится. - Kpoк(10.02.2021 18:52)
- Вот формула для итераций: Xaoc(54 знак., 10.02.2021 18:24,
- ну мы же делим остаток на производную, чтобы посчитать довесок к
аргументу. В эпоху дорогого деления принимали наклон (производную)
постоянными для всех точек итерации. Это позволяло подменить
деление умножением. Но совсем без я что-то не припомню. - Kpoк(10.02.2021 18:17)
- Метод Ньютона применим для поиска корней любых уравнений от одной
переменной. Xaoc(229 знак., 10.02.2021 18:06, )
- Ну не совсем любых... Вторая производная - против Вашего утверждения - argus98(10.02.2021 22:23)
- Упс.. ----- Xaoc(46 знак., 10.02.2021 18:08,
- Там вроде бы первый из предложенных методов - Ньютон. Без деления
никак. Или нужен трюк. - Kpoк(10.02.2021 17:55)
- Вот годные реализации от Александра Редчука aka ReAl и Марка Ямпольского aka my504 --> - MBedder(10.02.2021 13:13, ссылка, ссылка)
- Изящный способ от МУ504. Главное, универсальный. - Kpoк(10.02.2021 13:47)
- Он не содержит деления, поэтому во всех архитектурах, где деления
либо нет, либо оно долгое, последовательное приближение выигрывает
у Н-Р. - my504(10.02.2021 18:02)
- Сейчас ПИКи сделали деление 32/16 за 6 тактов. Может быть на них
Н-Р будет быстрее, но там надо смотреть на сходимость. - Kpoк(10.02.2021 18:20)
- В алгоритме Н-Р для 16-разрядных Микрочипов есть одна неприятная засада. Если допустить входную разрядность 32, возникает деление 32/16 с результатом более 16 разрядов. Такшта в этой платформе Н-Р будет быстрее последовательного приближения при входной разрядности не более 30. Независимо от 19 или 7 тактового деления, с учетом инструкции repeat, конечно... - my504(11.02.2021 04:22)
- Сейчас ПИКи сделали деление 32/16 за 6 тактов. Может быть на них
Н-Р будет быстрее, но там надо смотреть на сходимость. - Kpoк(10.02.2021 18:20)
- Я когда-то его слегка допилил, использовав адаптивный стартовый бит
с помощью дспичной команды FF1L вместо фиксированного 0х8000, но не
нашел исходника - MBedder(10.02.2021 13:58)
- Я так понял, по моей ссылке ответ номер 3 как раз про это же, но
без птичьего пик-языка... - SciFi(10.02.2021 14:05)
- Именно. Но я про ассемблерную реализацию в dsPIC, где этот засев
делается в один такт специальной командой поиска битовой позиции
левой единицы в делимом - MBedder(10.02.2021 14:28)
- Ну так по моей ссылке тоже. Этого добра везде навалом. Извини,
табличка в вике скромно молчит про твой любимый пик
>>> - SciFi(10.02.2021 14:30, ссылка)
- Вика обосралась :)) - MBedder(10.02.2021 14:35)
- Ну так по моей ссылке тоже. Этого добра везде навалом. Извини,
табличка в вике скромно молчит про твой любимый пик
>>> - SciFi(10.02.2021 14:30, ссылка)
- Именно. Но я про ассемблерную реализацию в dsPIC, где этот засев
делается в один такт специальной командой поиска битовой позиции
левой единицы в делимом - MBedder(10.02.2021 14:28)
- Я так понял, по моей ссылке ответ номер 3 как раз про это же, но
без птичьего пик-языка... - SciFi(10.02.2021 14:05)
- Он не содержит деления, поэтому во всех архитектурах, где деления
либо нет, либо оно долгое, последовательное приближение выигрывает
у Н-Р. - my504(10.02.2021 18:02)
- Изящный способ от МУ504. Главное, универсальный. - Kpoк(10.02.2021 13:47)
- Откуда взял, не помню, но явно проще Andreas(576 знак., 10.02.2021 12:37)
- Операция деления как-то не рифмуется у меня с "ускорить" - Kpoк(10.02.2021 12:02)
- До этого была софтовая плавучка, там вообще кошмар, если сравнивать :-) - SciFi(10.02.2021 12:05)
- +1 почему не заменить на сдвиг? хотя может компилер сам сделает.. - Aleksey_75(10.02.2021 12:05)