Микроконтролери и електроника
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 на същата честота (това трябва да се тества разбира се)!

Прикачени файлове:
FastSquareRoot.pdf [140.39 KiB]
322 пъти

Автор:  palavrov [ Съб Юни 27, 2015 9:23 am ]
Заглавие:  Re: Полезни алгоритми

Виж как се прави без делене ;)
Код:
#define iter1(N)      \
    try = root + (1 << (N));   \
    if (n >= try << (N))   \
    {            \
   n -= try << (N);   \
        root |= 2 << (N);   \
    }

u32 sqrt_u32 (u32 n)
{
    u32 root = 0, try;

    iter1 (15);
    iter1 (14);
    iter1 (13);
    iter1 (12);
    iter1 (11);
    iter1 (10);
    iter1 ( 9);
    iter1 ( 8);
    iter1 ( 7);
    iter1 ( 6);
    iter1 ( 5);
    iter1 ( 4);
    iter1 ( 3);
    iter1 ( 2);
    iter1 ( 1);
    iter1 ( 0);

    return root >> 1;
}

Автор:  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: Полезни алгоритми

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


Деленето е едно от нещата, които бавят абсолютно навсякъде. За разлика от умножението и шифтовете, които в общия случай са по 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: Полезни алгоритми

DanielDimov написа:
Моя код не зацикля.

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

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

Автор:  ToHu [ Съб Юни 27, 2015 2:07 pm ]
Заглавие:  Re: Полезни алгоритми

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

Автор:  sparkybg [ Съб Юни 27, 2015 2:40 pm ]
Заглавие:  Re: Полезни алгоритми

DanielDimov написа:
На процесора с който в момента се занимавам делението е 3 такта винаги.


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

Автор:  palavrov [ Съб Юни 27, 2015 5:28 pm ]
Заглавие:  Re: Полезни алгоритми

DanielDimov написа:
Моя код не зацикля.

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

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

Автор:  DanielDimov [ Нед Юни 28, 2015 8:10 am ]
Заглавие:  Re: Полезни алгоритми

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

Автор:  ike [ Нед Юни 28, 2015 9:30 am ]
Заглавие:  Re: Полезни алгоритми

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


DanielDimov написа:
Процесорчето с което се занимавам в момента е LPC1833, а делението е 32-битово...

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

Автор:  DanielDimov [ Нед Юни 28, 2015 10:16 am ]
Заглавие:  Re: Полезни алгоритми

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


Все още не съм тествал скоростта на микроконтролера. Това което писах по-горе като скорост е на 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/