VPF::Нужен алгоритм строкового МОДа на PHP

azproduction

Дата 8.11.2006, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 8.11.2006

Репутация: нет
Всего: нет

Недавно написал под Делфи жду советов по оптимизации сего (выкидываю весь юнит):

Код


unit StrNumber;

interface
const
  CHAR_TO_INT:array['0'..'9'] of Byte = (0,1,2,3,4,5,6,7,8,9);
  INT_TO_CHAR:array[0..9] of Char = ('0','1','2','3','4','5','6','7','8','9');
  function STR_ADD(S1,S2:AnsiString):AnsiString;
  function STR_MUL_CHAR(S:AnsiString;C:Char):AnsiString;
  function STR_MUL(S1,S2:AnsiString):AnsiString;
  function STR_SUB(S1,S2:AnsiString):AnsiString;
  function STR_MOD(S1,S2:AnsiString):AnsiString;
implementation

  function CheckBuf(B:AnsiString):boolean;
  var
    j:integer;
  begin
    j:=1;
    Result:=false;
    while j<=Length(B) do
    begin
      if B[j]='1' then
      begin
        Result:=true;
        j:=Length(B)+1;
      end;
      inc(j);
    end;
  end;

  function STR_ADD(S1,S2:AnsiString):AnsiString;
  var
    i:integer;
    Buf,
    S3:AnsiString;
    C1,
    C2,
    C3:Byte;
  begin
    Buf:='0';
    if Length(S2)>Length(S1) then
    begin
      Result:=STR_ADD(S2,S1);
    end
    else
    begin
      for i:=1 to Length(S1)-Length(S2) do
      begin
        S2:='0'+S2;
      end;

      for i:=Length(S2) downto 1 do
      begin
        C1:=CHAR_TO_INT[S1[i]];
        C2:=CHAR_TO_INT[S2[i]];
        C3:=C1+C2;
        if C3>=10 then
        begin
          Buf:='1'+Buf;
          C3:=C3-10;
        end
        else
        begin
          if i<>1 then
          begin
            Buf:='0'+Buf;
          end;
        end;
        S3:=INT_TO_CHAR[C3]+S3;
      end;

      if CheckBuf(Buf) then
      begin
        Result:=STR_ADD(Buf,S3);
      end
      else
      begin
        Result:=S3;
      end;
    end;
  end;

  function STR_MUL_CHAR(S:AnsiString;C:Char):AnsiString;
  var
    i:integer;
    S3,
    Buf:AnsiString;
    C1,
    C2,
    C3:Byte;
  begin
    C1:=CHAR_TO_INT[C];
    Buf:='0';
    S3:='';
    for i:=Length(S) downto 1 do
    begin
      C2:=CHAR_TO_INT[S[i]];
      C3:=C2*C1;
      Buf:=INT_TO_CHAR[(C3 div 10)]+Buf;
      S3:=INT_TO_CHAR[(C3 mod 10)]+S3;
    end;
    Result:=STR_ADD(Buf,S3);
  end;

  function STR_MUL(S1,S2:AnsiString):AnsiString;
  var
    Buf,
    S3:AnsiString;
    i,
    j:integer;
  begin
    S3:='0';
    Buf:='0';
    if Length(S2)>Length(S1) then
    begin
      Result:=STR_MUL(S2,S1);
    end
    else
    begin
      for i:=Length(S2) downto 1 do
      begin
        Buf:=STR_MUL_CHAR(S1,S2[i]);
        for j:=1 to Length(S2)-i do
        begin
          Buf:=Buf+'0';
        end;
        S3:=STR_ADD(Buf,S3);
      end;
      while S3[1]='0' do
      begin
        Delete(S3,1,1);
      end;
      if S3='' then S3:='0';
      Result:=S3;
    end;
  end;

  function STR_CMP(S1,S2:AnsiString):boolean;
  var
    i:integer;
  begin
    Result:=false;
    if Length(S1)>Length(S2) then
    begin
      Result:=true;
    end;

    if Length(S2)>Length(S1) then
    begin
      Result:=false;
    end;

    if Length(S2)=Length(S1) then
    begin
      i:=1;
      Result:=true;
      while i<=Length(S1) do
      begin
        if CHAR_TO_INT[S2[i]]>CHAR_TO_INT[S1[i]] then
        begin
          i:=Length(S1);
          Result:=false;
        end
        else
        begin
          if CHAR_TO_INT[S2[i]]<>CHAR_TO_INT[S1[i]] then
          begin
            i:=Length(S1);
            Result:=true;
          end;
        end;
        inc(i);
      end;
    end;
  end;

  function STR_SUB(S1,S2:AnsiString):AnsiString;
  var
    i:integer;
    Buf,
    S3:AnsiString;
  begin
    Buf:='0';
    if not STR_CMP(S1,S2) then
    begin
      Result:='0';
    end
    else
    begin
      for i:=1 to Length(S1)-Length(S2) do
      begin
        S2:='0'+S2;
      end;
      for i:=Length(S1) downto 1 do
      begin
        if CHAR_TO_INT[S1[i]]<CHAR_TO_INT[S2[i]] then
        begin
          Buf:='1'+Buf;
          S3:=INT_TO_CHAR[CHAR_TO_INT[S1[i]]-CHAR_TO_INT[S2[i]]+10]+S3;
        end
        else
        begin
          Buf:='0'+Buf;
          S3:=INT_TO_CHAR[CHAR_TO_INT[S1[i]]-CHAR_TO_INT[S2[i]]]+S3;
        end;
      end;

      if CheckBuf(Buf) then
      begin
        while Buf[1]='0' do
        begin
          Delete(Buf,1,1);
        end;
        Result:=STR_SUB(S3,Buf);
      end
      else
      begin
        Result:=S3;
      end;
    end;
  end;

  function STR_MOD(S1,S2:AnsiString):AnsiString;
  var
    S3,
    Z,
    Mul:AnsiString;
    i:integer;
  begin
    if not STR_CMP(S1,S2) then
    begin
      Result:=S1;
    end
    else
    begin
      Z:='';
      for i:=1 to Length(S1)-Length(S2) do
      begin
        Z:=Z+'0';
      end;

      while Z<>'' do
      begin
        i:=1;
        while i<10 do
        begin

          if not STR_CMP(S1,STR_MUL(S2,INT_TO_CHAR[i]+Z)) then
          begin
            dec(i);
            if i>0 then
            begin
              S1:=STR_SUB(S1,STR_MUL(S2,INT_TO_CHAR[i]+Z));
            end;
            Delete(Z,1,1);
            i:=11;
            while S1[1]='0' do
            begin
              Delete(S1,1,1);
            end;
            if S1='' then S1:='0';
          end;

          if i=9 then
          begin
            S1:=STR_SUB(S1,STR_MUL(S2,INT_TO_CHAR[i]+Z));
            Delete(Z,1,1);
            while S1[1]='0' do
            begin
              Delete(S1,1,1);
            end;
            if S1='' then S1:='0';
          end;
          inc(i);
        end;
      end;
      While STR_CMP(S1,S2) do
      begin
        S1:=STR_SUB(S1,S2);
        while S1[1]='0' do
        begin
          Delete(S1,1,1);
        end;
        if S1='' then S1:='0';
      end;
      Result:=S1;
    end;
  end;

end.

Нужая ф-я function STR_MOD(S1,S2:AnsiString):AnsiString;

CyClon

Дата 8.11.2006, 22:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 838
Регистрация: 3.12.2005

Репутация: 3
Всего: 4

Я в дельфи дубовый по пояс, объясни лучше не пальцах, чем тебе помочь относительно PHP.

--------------------

azproduction

Дата 8.11.2006, 22:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 8.11.2006

Репутация: нет
Всего: нет

Нужен алгоритм остатка от деления, челочисленного корня квадратного для больших чисел, реализованных в виде строки

Добавлено @ 23:01
например есть число в виде строки $s1='12456998632545400487465748225346887405087878'; (не влезает в int) есть другое число $s2='5684347374828648263472998'; (не влезает в int) нужно в первом сдучаее вычислить остаток от деления $s1 на $s2, притом результат должен быть строка; во втором целочисленный корень квадратный из $s1 результат тоже строка

Mal Hack

Дата 9.11.2006, 00:24 (ссылка)

(нет голосов)

Загрузка ...

Мудрый...

Профиль
Группа: Участник Клуба
Сообщений: 9926
Регистрация: 15.2.2004

Репутация: 122
Всего: 261

Да, задачка интересная реализоваовал нечто подобное, но для возведения в степень и счетчика... тут посложнее
Тупо переводить код с Делфей не хочу.
Расскажи алгоритм, который ты использовал в Делфи, перепишем его на PHP.

WIPS

Дата 9.11.2006, 01:07 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 199
Регистрация: 22.5.2006
Где: Украина, Киев

Репутация: 1
Всего: 8

Насколько я помню из курса "компьютерная безопасность" для арифметики осатков больших чисел используется алгорим быстрого потенцирования, надо порыть по этой теме

--------------------

Автопроизводители, машины, марки, модели!

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »