полезные алгоритмы
|
|
electrik | Дата: Воскресенье, 12.10.2014, 00:23 | Сообщение # 1 |
Полковник
Группа: Друзья
Сообщений: 182
Статус: Offline
| данные алгоритмы взял из "(C++) Algorithms in C++ source code"
Код ' факториал function Factorial (byval n as uinteger) as uinteger if (n = 0) then function = 1 else function = n * Factorial (n - 1) end if end function
' число фибоначчи function Fibonacci (byval n as uinteger) as uinteger dim as integer previous = -1 dim as integer result = 1 for i as uinteger = 0 to n dim as const integer sum = result + previous previous = result result = sum next function = result end function
' схема горнера function Horner (a() as integer, byval n as uinteger, byval x as integer) as integer dim as integer result = a (n) for i as integer= n - 1 to 0 step -1 result = result * x + a (i) next function = result end function
' возведение в степень function Power (byval x as integer, byval n as uinteger) as integer if (n = 0) then function = 1 ElseIf (n mod 2 = 0) then ' n is even function = Power (x * x, n / 2) else ' n is odd function = x * Power (x * x, n / 2) end if end function "Добавлено (12.10.2014, 00:23) --------------------------------------------- алгоритм быстрого возведения в степень. тут я уже представлял функцию pow, но насамом деле, она ни какая не быстрая. почитать можете: http://tonycode.ru/algorithms-fast-power/ идея алгоритма такова, чтоб число a возвести в степень n за меньшее число умножений.
Код function pow(byval a as double,byval n as double) as double dim as double result = 1 while ( n > 0 ) if ((n and 1)) then result *= a n shr= 1 a *= a wend return result end function
print pow(2,4) ' алгоритм быстрого возведения в степень print 2 ^ 4 ' встроенный во FreeBasic print pow(5,15) print 5 ^ 15 print pow(23,5) print 23 ^ 5 sleep
|
|
| |
haav | Дата: Воскресенье, 12.10.2014, 07:44 | Сообщение # 2 |
Генералиссимус
Группа: Администраторы
Сообщений: 1366
Статус: Offline
| Проверил время работы алгоритмов. Алгоритм , встроенный в FB быстрее получается. Хотя все равно хороший маленький код с POW, спасибо.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
electrik | Дата: Понедельник, 13.10.2014, 02:53 | Сообщение # 3 |
Полковник
Группа: Друзья
Сообщений: 182
Статус: Offline
| тут, мне кажется, из-за плохой оптимизации асма fb. asm листинг получается здоровый. кстати, функция встроенная во FreeBasic, юзает тоже pow из библиотеки c. как ты тестируешь скорость выполнения? через queryPerformanceCounter? то что когда-то я класс выкладывал, или на асме? Добавлено (13.10.2014, 02:53) --------------------------------------------- и да, ещё вопрос, как ты тестировал алгоритм, дело в том что если записать так:
Код print pow(5,15) print 5 ^ 15
второй вариант естественно будет работать быстрее, ибо тут мы подсовываем константы, и он при компиляции расчитывает и тупо засовывает значения в секцию data. посути, работает только print надо проверить с переменными, чтоб вызывалась реально функция расчета. что-то типа:
Код dim a as double = 9 dim n as double = 17 dim result as double = a^n result=pow(a,n
|
|
| |
haav | Дата: Понедельник, 13.10.2014, 04:48 | Сообщение # 4 |
Генералиссимус
Группа: Администраторы
Сообщений: 1366
Статус: Offline
| Вот такой код я использовал для тестирования:
Код function pow(byval a as double,byval n as double) as double dim as double result = 1 while ( n > 0 ) if ((n and 1)) then result *= a n shr= 1 a *= a wend return result end function
dim as double t = Timer
For i As Integer = 1 To 100000 Var res = pow(i,2) Next
? Timer- t
t = Timer
For i As Integer = 1 To 100000 Var res = i ^ 2 Next
? Timer- t
Sleep
Результаты:
0.004863270023543809 <- POW 0.0002303977585786932 <- FB ^
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
electrik | Дата: Вторник, 14.10.2014, 16:48 | Сообщение # 5 |
Полковник
Группа: Друзья
Сообщений: 182
Статус: Offline
| немного оптимизированный вариант pow:
Код function pow (byval a as double,byval n as double) as double dim as double result=1 while ( n)> 0 if ((n and 1)) then n-=1 result *= a else n shr= 1 a *= a end if wend function = result end function
и в догонку, немного оптимизированный асм код приведенного выше:
Код function pow naked(byval a as double,byval n as double) as double asm push ebp mov ebp, esp sub esp, 8 .Lb_0004: push dword ptr [_Lb_000A] push dword ptr [_Lb_000A+4] pop dword ptr [ebp-4] pop dword ptr [ebp-8] .Lb_0006: fld qword ptr [ebp+16] fcomp qword ptr [_Lb_000B] fnstsw ax test ah, 0b01000000 jnz .Lb_0007 fld qword ptr [ebp+16] sub esp, 4 fistp dword ptr [esp]pop eax and eax, 1 je .Lb_0009 fld qword ptr [_Lb_000C] fadd qword ptr [ebp+16] fstp qword ptr [ebp+16] fld qword ptr [ebp+8] fmul qword ptr [ebp-8] fstp qword ptr [ebp-8] jmp .Lb_0008 .Lb_0009: fld qword ptr [ebp+16] sub esp, 4 fistp dword ptr [esp]pop eax sar eax, 1 push eax fild dword ptr [esp]add esp, 4 fstp qword ptr [ebp+16] fld qword ptr [ebp+8] fmul qword ptr [ebp+8] fstp qword ptr [ebp+8] .Lb_0008: jmp .Lb_0006 .Lb_0007: .Lb_0005: fld qword ptr [ebp-8] mov esp, ebp pop ebp ret 16 .section .data .balign 8 _Lb_000A: .quad 0x3FF0000000000000 .balign 8 _Lb_000B: .quad 0x0000000000000000 .balign 8 _Lb_000C: .quad 0xBFF0000000000000 end asm end function
|
|
| |
haav | Дата: Вторник, 14.10.2014, 17:17 | Сообщение # 6 |
Генералиссимус
Группа: Администраторы
Сообщений: 1366
Статус: Offline
| Все равно проигрывает по скорости встроенному варианту. Ну оно и понятно, все таки над алгоритмом pow из СИ работали хорошо подкованные люди.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
electrik | Дата: Среда, 15.10.2014, 01:17 | Сообщение # 7 |
Полковник
Группа: Друзья
Сообщений: 182
Статус: Offline
| согласен, там не дураки работали. потом можно ещё будет помудрить, например развернуть цикл. будет больше кода, но не значит, что хуже. сишники так часто делают, когда цикл в десяток итераций. даже сишные компиляторы умеют разворачивать циклы. видимо на разных машинах по разному работает, у меня было чуток быстрее.
|
|
| |