Не намирам точна тема за това нещо и реших да създам нова... Ако администраторите решат че има по-добро място - да я преместят!

Темата е за споделяне на алгоритми или кратки решения, които могат да бъдат полезни и на другите.

Първото нещо което може да ви е полезно е целочислен алгоритъм за изчисляване на корен квадратен. Понякога се налага на процесор който няма FPU да се смятат много корени и тогава това нещо помага страшно много. Тествал съм го задълбочено на x86 и е около 6 - 7 пъти по бързо в сравнение с емулация на FPU и около 15% по-бавно от FPU варианта на sqrt. Предполагам че АРМ-овете с ядра М0 или М3 ще могат да сметнат почти толкова корена колкото и M4 на същата честота (това трябва да се тества разбира се)!

Виж как се прави без делене

ами то деленето не бави (поне не и на процесорите на които може да ми потрябва)

Даниеле, идеята ти за тема с алгоритми е добра, но но защо не спомена, че това е метода на Newton-Raphson. Имам някакъв спомен, ако разликата между предната стойност и текущата е 1, алгоритъма зацикля.

Ето още малко алгоритми:
http://www.mathpath.org/Algor/squareroot/algor.square.root.iterations.htm

Деленето е едно от нещата, които бавят абсолютно навсякъде. За разлика от умножението и шифтовете, които в общия случай са по 1-2 цикъла (за сравнение, делението е 10-30 цикъла за 32 битови числа).

Моя код не зацикля.

На процесора с който в момента се занимавам делението е 3 такта винаги. Току що пробвах скоростта на sqrt_u32 на моя компютър и е доста добра - fastSqrt прави 981 мил. сметки в секунда, а sqrt_u32 прави 974 мил. Хубавото на втория алгоритъм е че времето за изпълнение е по-предвидимо (ще варира в по-малки граници).

Класиката за нещо близко (FP):

https://en.wikipedia.org/wiki/Fast_inverse_square_root

Има огромна разлика между микроконтролер и процесор, когато говорим за делене и плаваща запетая.

Абе то и доста контролери имат DIV ама ... ей сега погледнах последното на коеот писах, дърта 51-ка, 8 цикъла е тая команда срещу 2-4 за всички останали, а има и не малко по 1 цикъл ... не може да мериш х86 с контролер, дори и от по-модерните. Това от линка на woody е доста добро и работи със задоволителна грешка.

Кой е процесора и колко битово е делението?

Кода съм го оптимизирал за ARM и GCC ... компилирай и дизасемблирай с включени оптимизации да видиш разликата - всяка итерация я бях докарал до няколко инструкции доколкото помня ... за х86 не ме интересува кой е по бърз - двата процесора имат големи разлики на ниво инструкции така, че този код компилиран за х86 е нормално да е бавен

Процесорчето с което се занимавам в момента е LPC1833, а делението е 32-битово... обаче току-що проверих в документацията и се оказа, че съм запомнил грешно - делението е от 2 до 12 такта! Ще пробвам кой от двата метода ще е по-бърз на него конкретно защото на PC-то всичко е доста различно.

Браво, много добра оптимизация, почти 1 000 MIPS-а от 180MHz процесор.

Все още не съм тествал скоростта на микроконтролера. Това което писах по-горе като скорост е на Intel P8600 на 2.4 GHz

За SQRT деленето все ще клони към 12 такта, няма да е страшно бързо но пък и едва ли ти трябва да го смяташ 10 млн пъти в секунда, предполагам функцията ще хаби по около 100-200 такта средно, освен ако нямаш кълбо за гадаенето.