В Паскале/Делфи есть и процедуры и функции.
Функции возвращают некоторое значение, а процедуры нет.

В коде на Си есть ошибка – зацикливание, т.к. u не изменяется (результат u>>1 никуда не записывается). Если я правильно понял, как надо правильно было это пофиксить, то:






Какая разница? В том разделе меньше людей которые знают Си, в этом Pascal. 

сорри..недоглядел..исправлю

Добавлено через 4 минуты и 44 секунды

прочитать легче, чем написать 
то есть намного вероятнее что правильно переведет тебе прогу в паскаль человек который слегка знает с++(так как ему надо лишь понять условие)
чем тот который слегка знает паскаль (ведь ему надо построить правильный код).   

На самом деле это реализация алгоритма цепочки сложений, или метода двоичных квадратов и умножения:
rez=x^y mod n
(например, rez=23^25 mod 45=23, ни один тип данных такие числа не вмещает)
Только этот код работает совершенно неправильно!
У меня нет возможности проверить оригинал на Си, может кто-нибудь проверит?
Результат проверять на виндозном калькуляторе инженерного вида.

Есть альтернативный алгоритм с рекурсией,но он тоже не работает :(

unsigned long fast_exp (unsigned long x, unsigned long y, unsigned long n) {
unsigned long tmp;
  If (y==1) return(x%n);
  If (1^(x&1)) {
      tmp=fast_exp(x,y/2,n);
      return ((tmp*tmp) % n);}
  Else {
      tmp=fast_exp(x,(y-1)/2,n);
      tmp=(tmp*tmp) % n;
      tmp=(tmp*x) % n;
      return (tmp);
  }
}

Проверил - работает
А вот ему бы я доверять не стал - промежуточные вычисления делаются в плавающей точке, возможно несовпадение результатов.
(Хотя 23^25 mod 45=23, это тоже проверил)

Фух, сделал всё таки этот алгоритм на Delphi. Кривовато, зато работает:

function TForm1.CepochkaSlozhenii(x:Cardinal;y:Cardinal;n:Cardinal):Cardinal;
Var
  tmp1,tmp2:Cardinal;
  i:Integer;
Begin
  If y=1 Then CepochkaSlozhenii:=x mod n;
  If y=2 Then CepochkaSlozhenii:=x*x mod n;
  If y=3 Then CepochkaSlozhenii:=x*x*x mod n;
  If y>3 Then
    Begin
      If (y mod 2)=0 Then
        Begin
          tmp1:=(x*x mod n);
          tmp2:=1;
          If Round(y/2)>3 Then
            Begin
              CepochkaSlozhenii:=CepochkaSlozhenii((x*x mod n),Round(y/2),n);
              Exit;
            End;
          For i:=1 To Round(y/2) Do
            Begin
              tmp2:=tmp2*tmp1;
            End;
          CepochkaSlozhenii:=tmp2 mod n;
        End
      Else
        Begin
          tmp1:=(x*x mod n);
          tmp2:=1;
          If Round((y-1)/2)>3 Then
            Begin
              CepochkaSlozhenii:=(CepochkaSlozhenii((x*x mod n),Round((y-1)/2),n)*(x mod n)) mod n;
              Exit;
            End;
          For i:=1 To Round((y-1)/2) Do
            Begin
              tmp2:=tmp2*tmp1;
            End;
          CepochkaSlozhenii:=tmp2*x mod n;
        End;
    End;
End;

Может можно как то оптимизировать?

см ниже.

Это сообщение отредактировал(а) mes - 28.4.2008, 16:19

вроде так :


Это сообщение отредактировал(а) mes - 28.4.2008, 16:23

Вот короткий и 100% рабочий вариант:

function TForm1.CepochkaSlozhenii(x:Cardinal;y:Cardinal;n:Cardinal):Cardinal;
Var
  s,t,u:Cardinal;
Begin
  s:=1;
  t:=x;
  u:=y;
  While u<>0 Do
    Begin
      If (u mod 2)=1 Then
        s:=(s*t) mod n;
      u:=u shr 1;
      t:=(t*t) mod n;
    End;
  CepochkaSlozhenii:=s;
End;

Всем спасибо за помощь, тема закрыта.

SashaOSC, 

M MAKCim

Модератор: Пользуйтесь тегом код!