FreeBasic
Главная
Вход
Регистрация
Среда, 16.10.2024, 07:09Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
полезные алгоритмы
electrikДата: Воскресенье, 12.10.2014, 00:23 | Сообщение # 1
Полковник
Группа: Друзья
Сообщений: 182
Репутация: 3
Статус: 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
Репутация: 49
Статус: Offline
Проверил время работы алгоритмов. Алгоритм , встроенный в FB быстрее получается. Хотя все равно хороший маленький код с POW, спасибо.

Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
electrikДата: Понедельник, 13.10.2014, 02:53 | Сообщение # 3
Полковник
Группа: Друзья
Сообщений: 182
Репутация: 3
Статус: 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
Репутация: 49
Статус: 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
Репутация: 3
Статус: 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
Репутация: 49
Статус: Offline
Все равно проигрывает по скорости встроенному варианту. Ну оно и понятно, все таки над алгоритмом pow из СИ работали хорошо подкованные люди.

Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
electrikДата: Среда, 15.10.2014, 01:17 | Сообщение # 7
Полковник
Группа: Друзья
Сообщений: 182
Репутация: 3
Статус: Offline
согласен, там не дураки работали. потом можно ещё будет помудрить, например развернуть цикл. будет больше кода, но не значит, что хуже. сишники так часто делают, когда цикл в десяток итераций. даже сишные компиляторы умеют разворачивать циклы.
видимо на разных машинах по разному работает, у меня было чуток быстрее.
 
  • Страница 1 из 1
  • 1
Поиск: