|
полезные алгоритмы
|
|
| electrik | Дата: Воскресенье, 12.10.2014, 00:23 | Сообщение # 1 |
|
Полковник
Группа: Друзья
Сообщений: 180
Статус: 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 |
 Генералиссимус
Группа: Администраторы
Сообщений: 1361
Статус: Offline
| Проверил время работы алгоритмов. Алгоритм , встроенный в FB быстрее получается. Хотя все равно хороший маленький код с POW, спасибо.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| electrik | Дата: Понедельник, 13.10.2014, 02:53 | Сообщение # 3 |
|
Полковник
Группа: Друзья
Сообщений: 180
Статус: 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 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1361
Статус: 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 |
|
Полковник
Группа: Друзья
Сообщений: 180
Статус: 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 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1361
Статус: Offline
| Все равно проигрывает по скорости встроенному варианту. Ну оно и понятно, все таки над алгоритмом pow из СИ работали хорошо подкованные люди.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| electrik | Дата: Среда, 15.10.2014, 01:17 | Сообщение # 7 |
|
Полковник
Группа: Друзья
Сообщений: 180
Статус: Offline
| согласен, там не дураки работали. потом можно ещё будет помудрить, например развернуть цикл. будет больше кода, но не значит, что хуже. сишники так часто делают, когда цикл в десяток итераций. даже сишные компиляторы умеют разворачивать циклы.
видимо на разных машинах по разному работает, у меня было чуток быстрее.
|
| |
| |
|
