purebasic.info

PureBasic forum
Текущее время: Чт дек 12, 2019 3:16 am

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
СообщениеДобавлено: Сб ноя 30, 2019 1:07 pm 
Не в сети
студент

Зарегистрирован: Вс май 29, 2016 9:42 am
Сообщений: 9
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Пункты репутации: 0
Всем доброго дня.
Прошу вашего совета.
Написал функция вычисления "Остаток от деления числа в степени", но меня совсем не утраивает скорость обработки
Эта функция тестовая, потом она будет переведена для работы с большими числами, но как прототип должна работать быстро, очень быстро.
Код:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
Procedure apowmbmodc(a,b,c)
  k=1
  a = a%c
  d =a
  Debug "("+Str(k)+")"+Str(d)
 
  If d<>0
    Repeat
      k+1
      d=(d*a)%c
      Debug "("+Str(k)+")"+Str(d)
    Until d=1 Or d=a Or d=0 Or k>=b
    If k<b
      If d=a
        k-1
      EndIf
      If d<>0
        Debug "длина периода:"+Str(k)
        pos = b%k
        Debug "строка:"+Str(pos)
        Debug"------"
        d =a%c
        For i = 1 To pos-1
          d=(d*a)%c
          Debug d        
        Next i
        Debug "результат:"+Str(d)
      EndIf
    Else
      Debug "k>=b"
      Debug "результат:"+Str(d)
    EndIf
  EndIf
ProcedureReturn d
EndProcedure
 
OpenConsole()
start=ElapsedMilliseconds()
PrintN("Result: "+Str(apowmbmodc(10,19895564,34347)))
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
Delay(5000)
CloseConsole()
End
 
 


Я наверное прогулял теорию чисел, поэтому сделал функция с учетом практических знаний.
Может она кому-то и подойдет в таком виде, но мне важна скорость.
Подскажите как можно оптимизировать ее.
Заранее спасибо.


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: Сб ноя 30, 2019 1:52 pm 
Не в сети
МОДЕРАТОР
Аватар пользователя

Зарегистрирован: Пн апр 09, 2007 4:53 pm
Сообщений: 11551
Благодарил (а): 4 раз.
Поблагодарили: 476 раз.
Etayson писал(а):
меня совсем не утраивает скорость обработки
Скорость 0 мс не устроила?

_________________
Компьютер позволяет решать все те проблемы, которые до его изобретения не существовали. :) :)


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: Сб ноя 30, 2019 1:54 pm 
Не в сети
профессор

Зарегистрирован: Пт фев 20, 2009 12:57 pm
Сообщений: 1786
Откуда: Алматы
Благодарил (а): 18 раз.
Поблагодарили: 49 раз.
Пункты репутации: 5
надо видимо для уточнения еще узнать конфигурацию компьютера.


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: Сб ноя 30, 2019 1:55 pm 
Не в сети
МОДЕРАТОР
Аватар пользователя

Зарегистрирован: Пн апр 09, 2007 4:53 pm
Сообщений: 11551
Благодарил (а): 4 раз.
Поблагодарили: 476 раз.
Дело не в компе, а в том что был включен отладчик, а в коде много Debug, которые требуют времени. При измерении скорости работы, отладчик нужно отключать.

_________________
Компьютер позволяет решать все те проблемы, которые до его изобретения не существовали. :) :)


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: Сб ноя 30, 2019 3:58 pm 
Не в сети
студент

Зарегистрирован: Вс май 29, 2016 9:42 am
Сообщений: 9
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Пункты репутации: 0
Пётр писал(а):
Etayson писал(а):
меня совсем не утраивает скорость обработки
Скорость 0 мс не устроила?

Да ну ребят, если 2^2 mod 3 считать, то конечно 0 мс))
Пробуйте хотя бы
apowmbmodc(10546546, 19895564, 3434765465) заняло 255мс
Тут скорее вопрос в алгоритме. Потому что цифры будут в диапазоне 0 до 2^256-1
Сами понимаете, что это совсем другое время будет. А в питоне молниеносно делается. вот и хотел узнать, может переделать как-то надо алгоритм.
Вот немного переделал так как выявил баг
Код:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
Procedure apowmbmodc(a,b,c)
  k=1
  a = a%c
  d = a
  Debug "("+Str(k)+")"+Str(d)
 
  If d<>0
    Repeat
      k+1
      d=(d*a)%c
      Debug "("+Str(k)+")"+Str(d)
    Until d=1 Or d=a Or d=0 Or k>=b
    If k<b
     
      If d=a
        k-1
      EndIf
      If d<>0
        Debug "длина периода:"+Str(k)
        pos = b%k
        Debug "строка:"+Str(pos)
        Debug"------"
       
        If pos<>0
          ;-------отсюда
          d = a%c
          For i = 1 To pos-1
            d=(d*a)%c
            Debug d        
          Next i
          ;сюда можно заменить просто на d = Int(Pow(d,pos))%c
         
        Else
          d=1
        EndIf
        Debug "результат:"+Str(d)
      EndIf
    Else
      Debug "k>=b"
      Debug "результат:"+Str(d)
    EndIf
  EndIf
ProcedureReturn d
EndProcedure
 
OpenConsole()
start=ElapsedMilliseconds()
PrintN("Result: "+Str(apowmbmodc(10546546, 19895564, 3434)))
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
Delay(5000)
CloseConsole()
End
 



или вот например apowmbmodc(10546546, 198955647, 198955645)
283974 итераций умножения, хоть и занимает вычисление 6мс - это вечность))
Явно, что процедура не рационально работает.


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: Сб ноя 30, 2019 7:20 pm 
Не в сети
студент

Зарегистрирован: Вс май 29, 2016 9:42 am
Сообщений: 9
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Пункты репутации: 0
Все оказалось гораздо проще!!!

Код:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
Procedure apowmbmodc(base,exp,modulus)
Protected result=1
  base = base % modulus;
 
  While exp > 0
    If (exp & 1)
      result = (result * base) % modulus;
    EndIf
    base = (base * base) % modulus
    exp = exp>> 1
  Wend
  ProcedureReturn result
EndProcedure
 
OpenConsole()
start=ElapsedMilliseconds()
PrintN("Result: "+Str(apowmbmodc(2, 344, 1000)))
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
 
start=ElapsedMilliseconds()
PrintN("Result: "+Str(apowmbmodc(10546546, 198955647, 198955645)))
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
 
start=ElapsedMilliseconds()
PrintN("Result: "+Str(apowmbmodc(10546546, 19895564, 3434765465)))
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
 
Delay(5000)
CloseConsole()
End
 



Надеюсь, что это кому-то сэкономит время)


Вернуться наверх
 Профиль  
 
Показать сообщения за:  Сортировать по:  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group (блог о phpBB)
Сборка создана CMSart Studio
Русская поддержка phpBB