Всем привет :). Получил одно из заданий. написать тест рабина милера(на delphi). нашел уже готовый алгоритм написанный на python на wikipedia.org. Проблема в том, что языка совсем не знаю этого. Мог быть кто нибудь рассказать по алгоритму что в нем делается, что бы мне потом его под delphi переделать. Заранее спасибо

Сам алгоритм вот:


def nod(a, b):
assert a != 0 or b != 0
while b != 0:
a, b = b, a % b
return a

def mr(p):
n = 0
import random
a = random.randrange(0,p)
k = 4

s=0
while ((p-1)%2 !=0):
(p-1) % 2
s+=1

t = (p-1)/(2**s)

metka=0
while n < k:
while nod(p,a) != 1:
a = random.randrange(0,p)
if a**(t)%p != 1:
print “shislo sostavnoe”#n
metka=1
break
n += 1
if metka == 0:
print “shislo prostoe s veroyatnost'u”,1-(0.25**k),“%”

print “ = ”,
k = int(raw_input())
mr(k)

Мда :) алгоритм достаточной простой. Я не знаю дельфи, но в большинстве случаев, понимаю код, а с питоном должно быть еще легче. Я думаю, ты обратился не по адресу, здесь вряд ли помогут переделать код на дельфи, тем более, если это лабораторная работа.

вот здесь http://forum2007.algolist.ru/showflat.php?Number=10764&page= алгоритм описан словами. А тот код, что на педивикии кривой как моя жизнь :)

сюда погляди

я же не просил вас переписать код на делфи. просто объяснить за что этот код отвечает. где объявление перемен, процедур(функций)…. прям по коду. типо комментария. вот это меня интересовало

1. def nod и def mr это методы/функции. return выход/возврат результат. return a возвращает значение переменной a.
2. Блоки определяются отступами (begin/end). Один отступ для нескольких строк, идущих подряд, одни за другими, это один блок.
3. assert a != 0 or b != 0 - assert и в африке assert.
4. != - <>.
5. a, b = b, a % b - temp := a mod b; a := b; b := temp;
6. import random - импортируется модуль random (типа uses random).
7. random.randrange(0,p) - функция модуля random, целочисленное значение от 0 до p не включая p, т.е. randrange(0, 1) будт всегда возвращать 0.
8. (p-1) % 2 - какой-то бред, результат этого выражения никуда не девается, т.е. тает в воздухе. Да и вообще этот цикл (тот что while ((p-1)%2 !=0):) не будет выполнять своей функции, т.е. он бессмысленен, а чего у него за функция не понятно.
9. %, как ты понял, это mod, а ** - это степень.
10. break - без комментариев (Break).
11. n += 1 - Inc(n) или n := n + 1;
12. if metka == 0: - if metka = 0 then.
13. print - без комментариев (WriteLn).
14. int(raw_input()) - ввод строки пользователем и преобразование её к целому (ReadLn + IntStr).
15. Переменные нигде не объявляются, типизация динамическая.

..bw

Из вашего первого поста, я понял, что питон вас не интересует. вот и привел вам ссылку, где есть словестное описание и даже код на паскаль :)

зёма
где объявление перемен, процедур(функций)…. прям по коду. типо комментария. вот это меня интересовало

Все это есть в любой книжке по питону :) Открываете книжку и, через 10 минут, вы поймете весть приведенный вами код, который неработает :) хотя бы потому что

bw
(p-1) % 2 - какой-то бред, результат этого выражения никуда не давается, т.е. тает в воздухе.

bw
(p-1) % 2 - какой-то бред, результат этого выражения никуда не давается, т.е. тает в воздухе.

Ну почему же? Если объект p обрабатывает “-” возвращает что-то, что обрабатывает “%” (да хоть себя же!), то там может быть всё что угодно! Хоть запуск ядерных ракет… :-)

ZZZ, да, такое возможно. Но мы обсуждаем именно тот код, что был приведен в первом сообщении данной темы. Из него очевидно - p это целое число, исходя из этого я сделал заключение относительно проблемного выражения - это бред.

..bw

bw, это у меня просто настроение пошутить было… Не удачно. Простите. :-)