| Микроконтролери и електроника http://mcu-bg.com/mcu_site/ |
|
| Полезни алгоритми http://mcu-bg.com/mcu_site/viewtopic.php?f=3&t=13873 |
Страница 1 от 2 |
| Автор: | DanielDimov [ Съб Юни 27, 2015 9:10 am ] | ||
| Заглавие: | Полезни алгоритми | ||
Не намирам точна тема за това нещо и реших да създам нова... Ако администраторите решат че има по-добро място - да я преместят! Темата е за споделяне на алгоритми или кратки решения, които могат да бъдат полезни и на другите. Първото нещо което може да ви е полезно е целочислен алгоритъм за изчисляване на корен квадратен. Понякога се налага на процесор който няма FPU да се смятат много корени и тогава това нещо помага страшно много. Тествал съм го задълбочено на x86 и е около 6 - 7 пъти по бързо в сравнение с емулация на FPU и около 15% по-бавно от FPU варианта на sqrt. Предполагам че АРМ-овете с ядра М0 или М3 ще могат да сметнат почти толкова корена колкото и M4 на същата честота (това трябва да се тества разбира се)!
|
|||
| Автор: | palavrov [ Съб Юни 27, 2015 9:23 am ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Виж как се прави без делене
|
||||||||||
| Автор: | DanielDimov [ Съб Юни 27, 2015 9:52 am ] |
| Заглавие: | Re: Полезни алгоритми |
ами то деленето не бави (поне не и на процесорите на които може да ми потрябва) |
|
| Автор: | Desert Leo [ Съб Юни 27, 2015 10:45 am ] |
| Заглавие: | Re: Полезни алгоритми |
Даниеле, идеята ти за тема с алгоритми е добра, но но защо не спомена, че това е метода на Newton-Raphson. Имам някакъв спомен, ако разликата между предната стойност и текущата е 1, алгоритъма зацикля. Ето още малко алгоритми: http://www.mathpath.org/Algor/squareroot/algor.square.root.iterations.htm |
|
| Автор: | sparkybg [ Съб Юни 27, 2015 11:10 am ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Деленето е едно от нещата, които бавят абсолютно навсякъде. За разлика от умножението и шифтовете, които в общия случай са по 1-2 цикъла (за сравнение, делението е 10-30 цикъла за 32 битови числа). |
||||||||||
| Автор: | DanielDimov [ Съб Юни 27, 2015 11:24 am ] |
| Заглавие: | Re: Полезни алгоритми |
Моя код не зацикля. На процесора с който в момента се занимавам делението е 3 такта винаги. Току що пробвах скоростта на sqrt_u32 на моя компютър и е доста добра - fastSqrt прави 981 мил. сметки в секунда, а sqrt_u32 прави 974 мил. Хубавото на втория алгоритъм е че времето за изпълнение е по-предвидимо (ще варира в по-малки граници). |
|
| Автор: | woody [ Съб Юни 27, 2015 11:26 am ] |
| Заглавие: | Re: Полезни алгоритми |
Класиката за нещо близко (FP): https://en.wikipedia.org/wiki/Fast_inverse_square_root |
|
| Автор: | ike [ Съб Юни 27, 2015 12:40 pm ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Има огромна разлика между микроконтролер и процесор, когато говорим за делене и плаваща запетая. |
||||||||||
| Автор: | ToHu [ Съб Юни 27, 2015 2:07 pm ] |
| Заглавие: | Re: Полезни алгоритми |
Абе то и доста контролери имат DIV ама ... ей сега погледнах последното на коеот писах, дърта 51-ка, 8 цикъла е тая команда срещу 2-4 за всички останали, а има и не малко по 1 цикъл ... не може да мериш х86 с контролер, дори и от по-модерните. Това от линка на woody е доста добро и работи със задоволителна грешка. |
|
| Автор: | sparkybg [ Съб Юни 27, 2015 2:40 pm ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Кой е процесора и колко битово е делението? |
||||||||||
| Автор: | palavrov [ Съб Юни 27, 2015 5:28 pm ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Кода съм го оптимизирал за ARM и GCC ... компилирай и дизасемблирай с включени оптимизации да видиш разликата - всяка итерация я бях докарал до няколко инструкции доколкото помня ... за х86 не ме интересува кой е по бърз - двата процесора имат големи разлики на ниво инструкции така, че този код компилиран за х86 е нормално да е бавен |
||||||||||
| Автор: | DanielDimov [ Нед Юни 28, 2015 8:10 am ] |
| Заглавие: | Re: Полезни алгоритми |
Процесорчето с което се занимавам в момента е LPC1833, а делението е 32-битово... обаче току-що проверих в документацията и се оказа, че съм запомнил грешно - делението е от 2 до 12 такта! Ще пробвам кой от двата метода ще е по-бърз на него конкретно защото на PC-то всичко е доста различно. |
|
| Автор: | ike [ Нед Юни 28, 2015 9:30 am ] | ||||||||||||||||||
| Заглавие: | Re: Полезни алгоритми | ||||||||||||||||||
Браво, много добра оптимизация, почти 1 000 MIPS-а от 180MHz процесор. |
|||||||||||||||||||
| Автор: | DanielDimov [ Нед Юни 28, 2015 10:16 am ] | |||||||||
| Заглавие: | Re: Полезни алгоритми | |||||||||
Все още не съм тествал скоростта на микроконтролера. Това което писах по-горе като скорост е на Intel P8600 на 2.4 GHz |
||||||||||
| Автор: | ToHu [ Нед Юни 28, 2015 11:43 am ] |
| Заглавие: | Re: Полезни алгоритми |
За SQRT деленето все ще клони към 12 такта, няма да е страшно бързо но пък и едва ли ти трябва да го смяташ 10 млн пъти в секунда, предполагам функцията ще хаби по около 100-200 такта средно, освен ако нямаш кълбо за гадаенето. |
|
| Страница 1 от 2 | Часовете са според зоната UTC + 2 часа [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|