[Delphi] Длинная арифметика , Давно уже пишется модуль... по кускам

Странно... наверное я был не прав на счет FFFF... в конце перевода... Попробуйте перевести у себя число размером в 2000 9-ок (девяток) и результат скиньте сюда... Неужели правильно переводит?

Кстати, сравнил оба варианта перевода - свой и BugHunter'а... результаты одинаковые, а вот по времени:
исходное число 48000 по '9'
Моя: 122 секунды
против
BugHunter'a: 3 секунды - молодчина!!!
или 100000 девяток за 15 секунд - я просто изумлён!

BugHunter, снимаю шляпу! Будишь в Кишиневе - обязательно пойдем тресним

Дождусь еще ваших результатов тестирования и выложу код функции в первый пост с пометкой "Вопрос решен"

Сообщение отредактировано: Navi1982 - 12.11.09, 22:13

Цитата Navi1982 @ 12.11.09, 20:26

Странно... наверное я был не прав на счет FFFF... в конце перевода... Попробуйте перевести у себя число размером в 2000 9-ок (девяток) и результат скиньте сюда... Неужели правильно переводит?

Все очень просто: (65535*10+9) mod 65536 = (65535*10+10-1) mod 65536 =
= ((65535+1)*10-1) mod 65536 = ((65536)*10-1) mod 65536 =
= ((65536)*9+65536-1) mod 65536 = ((65536)*9+65535) mod 65536 =
= 65535

Т.е. когда ты переводишь число из одних девяток, то в определенный момент получаешь в остатке $FFFF и далее остатки всегда будут $FFFF - это не ошибка, это это число действительно такое двоичное представление имеет.

Переведи число из 2000 восьмерок - и ты увидишь разные значения в num.int до самого конца.

Добавлено 13.11.09, 21:45
Гы - для восьмерок получается периодическое повторение девяток слов

По просьбе Navi1982 сообщаю результаты своего теста.
При переводе строки из 48000 девяток:

Функция Bug Hunter на моем компьютере дала в среднем 9,5 секунд.

Мой интерфейсный объект ( немного доработанный вариант того что выкладывал )
перевел строку в цифровой массив за 95 миллисекунд

unit BigInt;
 
interface
 
type
  TElemTyp = Cardinal;// word;
 
  IBigInt = interface
    function Count: Integer;
    function IsNegative(): Boolean;
 
    function ToHex(): String;
 
    function Compare(const Val: IBigInt):Integer;
    function Invert():IBigInt;
 
    function plus(const Val: IBigInt):IBigInt; overload;
    function plus(const Val: TElemTyp):IBigInt; overload;
 
    function minus(const Val: IBigInt):IBigInt; overload;
    function minus(const Val: TElemTyp):IBigInt; overload;
 
    function multiply(const Val: IBigInt):IBigInt; overload;
    function multiply(const Val: TElemTyp):IBigInt; overload;
  end;
 
function GetBigInt(const Val: Int64):IBigInt; overload;
function GetBigInt(const Val: String):IBigInt; overload;
 
implementation

Вариант Navi1982 пробовать не стал.

Сообщение отредактировано: sCreator - 15.11.09, 05:47

Прикреплённый файлLongMath.zip (7.29 Кбайт, скачиваний: 229)

Цитата sCreator @ 14.11.09, 22:15

Функция Bug Hunter на моем компьютере дала в среднем 9,5 секунд.

Мой интерфейсный объект ( немного доработанный вариант того что выкладывал )
перевел строку в цифровой массив за 95 миллисекунд

На моем получилось 4.87 и 0.12 соответственно.

Однако!

Принцип понятен, попробую для сравнения реализовать чисто на Дельфи.

Цитата Bug Hunter @ 16.11.09, 20:48

Принцип понятен, попробую для сравнения реализовать чисто на Дельфи.

Попробовал:

type
  THugeInt = record
    data: array of longword;
    flag: longint;
    end;
 
{Функция преобразования форматированой строки-10сс в массив-2^32сс}
{ Функция ожидает строку, содержащую корректную запись целого числа,  }
{ форматированую в соответствии со спецификацией: строка должна       }
{ содержать только цифры и возможно знак '+', '-' или один лидирующий }
{ пробел вместо знака '+'. Для входящей строки, не соответствующей    }
{ спецификации, результат работы функции непредсказуем.               }
Function StrToHugeInt(const s: string): THugeInt;
  Var
    i, rdlen, j, toend, k: integer;
    a: int64;
    alw: array[0..1] of longword absolute a;
    aa, inmind: longword;
  begin
    result.data:=nil;
    result.flag:=0;
 
    if (s[1] in ['+','-',' ']) then i:=2 else i:=1;
    toend:=length(s)-i+1;
    rdlen:=0;
 
    while (toend>0) do begin
      {йцукен фыва ячсми}
      if (toend>=9) then begin
        aa:=1000000000;
        k:=9;
        end
      else begin
        aa:=10; for k:=2 to toend do aa:=aa*10;
        k:=toend;
        end;
      {умножаем result.data на aa}
      inmind:=0;
      for j:=0 to rdlen-1 do begin
        a:=int64(result.data[j])*aa+inmind;
        result.data[j]:=alw[0];
        inmind:=alw[1];
        end;
      if (inmind>0) then begin
        setlength(result.data, rdlen+1); inc(rdlen);
        result.data[rdlen-1]:=inmind;
        end;
      {йцукен фыва ячсми}
      aa:=strtoint(copy(s, i, k));
      {складываем result.data и aa}
      inmind:=aa;
      for j:=0 to rdlen-1 do begin
        a:=int64(result.data[j])+inmind;
        result.data[j]:=alw[0];
        inmind:=alw[1];
        if (inmind=0) then break;
        end;
      if (inmind>0) then begin
        setlength(result.data, rdlen+1); inc(rdlen);
        result.data[rdlen-1]:=inmind;
        end;
      {йцукен фыва ячсми}
      inc(i, k); dec(toend, k);
      if (toend=0) then break;
      end;
 
    if (s[1]='-') then
      result.flag:=-rdlen
    else
      result.flag:=rdlen;
  end;

Результат - 0.20 против 0.12 для функции от sCreator, использующей модуль на asm.

sCreator, ++ за идею

Вообще-то основная моя идея была в том, что бы сперва разработать операции длинной арифметики и на их основе уже преобразовывать строку в длинное число.
А старые знания асма немного попользовал для убыстрения (хотя врядли он оптимальный ) . Работа с longword значительно быстрее работы с word, но longword * longword не влезает в Int64.
Хорошо что миллиард на longword влезает.

А мой алгоритм и без асма тоже неплохо работает ( правда убрал проверку строки ):

Function FStrToBigNumDWL(const Val: string): THugeInt;
 
  function MulMemWithDWordD(pp1:PCardinal; p2:Cardinal; len: Integer): Cardinal;
  var
    ak, ap2: Int64;
    akl:array[0..1] of Cardinal absolute ak;
  begin
    akl[1] := 0;
    ap2 := p2;
    while true do
    begin
      dec(len);
      ak := ap2 * pp1^ + akl[1];
      pp1^ := akl[0];
      if len = 0 then
        break;
      Inc(pp1);
    end;
    Result := akl[1];
  end;
  // и выдает следующую длинну
  function AddMemDWordD(pp1:PCardinal; p2:Cardinal; len: Integer): Integer;
  var
    i: Integer;
    ak: Int64;
    akl:array[0..1] of Cardinal absolute ak;
  begin
    ak := p2;
    i := len;
    while true do
    begin
      Dec(i);
      ak := ak + pp1^;
      pp1^ := akl[0];
      if (akl[1] = 0) or (i = 0) then
        break;
      ak := akl[1];
      Inc(pp1);
    end;
    if i > 0 then
      Inc(pp1,i);
    if pp1^ > 0 then
      Inc(len);
    Result := len;
  end;
 
var
  i, len, slen, olen, sDw: Integer;
  s: string;
begin
  len := Length(Val);
  if len = 0 then
  begin
    Result.data := nil;
    Result.flag := 0;
    Exit;
  end;
  if (Val[1] in ['+','-',' ']) then i:=2 else i:=1;
 
  olen := (len - i + 1);
  slen := (olen div 9);
  olen := olen mod 9;
 
  SetLength(Result.data, (slen + 2));
    FillChar(Result.data[0],Length(Result.data)*4,0);
 
  slen := slen * 9;
  sDw := 1;
 
//  for i := 1 to len do
  while i < slen do
  begin
    s := Copy(Val, i, 9);
    Inc(i,9);
        if sDw > 1 then
          if MulMemWithDWordD(@Result.data[0], 1000000000, sDw) > 0 then
            raise Exception.Create('Overflow  in GetBigInt(const Val: String):IBigInt; (for)');
        sDw := AddMemDWordD(@Result.data[0], StrToInt(s), sDw);
 
  end;
 
  if olen > 0 then
  begin
    s := Copy(Val, i, olen);
    len := 1; for i := 1 to olen do len := len * 10;
    if sDw > 1 then
      if MulMemWithDWordD(@Result.data[0], len, sDw) > 0 then
        raise Exception.Create('Overflow  in GetBigInt(const Val: String):IBigInt;');
    sDw := AddMemDWordD(@Result.data[0], StrToInt(s), sDw);
  end;
 
  i := sDw;
  while (Result.data[i] = 0) and (i > 0) do
    Dec(i);
 
  SetLength(Result.data, i+1);
  if (Val[1] = '-') then
    result.flag := cardinal(i) or $80000000
  else
    result.flag := cardinal(i);
end;

Извиняюсь что пропал... Сегодня попробывал функцию BugHunter'а и его-же написанную по мотивам sCreator'а...
Вот результаты среднего времени конвертирования:
FStrToBigNum, '9' x 48000шт => 3,469 сек
FStrToBigNum, '9' x 100000шт => 14,968 сек

StrToHugeInt, '9' x 48000шт => 0,203 сек
StrToHugeInt, '9' x 100000шт => 0,797 сек
StrToHugeInt, '9' x 1000000шт => 76,375 сек

Долго отходя от шока, не знал шо сюда написать... Щас собираю провисшую челюсть с пола...
++ обоим!

Ага... мне тоже темка помогла с универскими лабами разобраться, респект!
__________________
Респект и уважуха! http://www.iskusstvenniy-kamen.ru/ - мой сайт

Сообщение отредактировано: imgavario - 25.11.09, 02:48

Вот!... Наконец-таки удалось вычислить максимальное промежуточное значение в основной программе. Это число состоит из 134886 цыфр в 10сс. И равняется оно... ой... даже боюсь приводить...
...
...и правильно боялся - выдает ошибку, мол сообщение длинноватое... хех... еще-бы. Так что результат смотрите в файле тхт:

Сообщение отредактировано: Navi1982 - 24.11.09, 20:11

Прикреплённый файлMax_Intermediate_Value.zip (59.47 Кбайт, скачиваний: 216)

В принцыпе вопрос можно считать решенным... Однако хотел бы еще спросить, особенно BugHunter'a и sCreator'а:

Как на счет продолжить реализовать удобный и быстрый модуль длинной арифметики для дельфи?

Ведь, штука очень интересная и может пригодится многим! И место как раз подходящее - т.е. "исходники"
И в связи с этим другой вопрос:

Стоит открыть новую тему где будут выкладыватся готовые коды? Или же лучше выкладывать все в первом посте и продолжать тему?

Если продолжать делать реализацию, то лучше новую тему.
Только сперва определиться хотя бы с каркасом ( базовой моделью ) модуля, чтобы в новой теме в первом посте было краткое описание и прикреплен исходник, который по мере разработки обновлялся.
Не искать же его по всей теме.

Будет время подмогну реализовать.
И, кстати, Navi1982 - если Ты получил промежуточный результат, значит у Тебя уже есть реализации основных операций, в том числе и преобразования числа в строку.

Кстати, посмотрел свежим взглядом на свою последнюю функцию перевода - нашел еще что оптимизировать.
Ведб можно одновременно умножать и прибавлять

Function FStrToBigNumDWL(const Val: string): THugeInt;
 
  function MulAddMemWithDWordD(pp1: PCardinal; p2, pAdd: cardinal; len: integer)
    : integer;
  var
    ak, ap2: Int64;
    akl: array [0 .. 1] of cardinal absolute ak;
    k: Integer;
  begin
    akl[1] := pAdd;
    ap2 := p2;
    for k := 1 to len do
    begin
      ak := ap2 * pp1^ + akl[1];
      pp1^ := akl[0];
      inc(pp1);
    end;
    if akl[1] <> 0 then
    begin
      pp1^ := akl[1];
      Inc(len);
    end;
    Result := len;
  end;
 
var
  i, len, slen, olen, sDw: integer;
  s: string;
begin
  len := length(Val);
  if len = 0 then
  begin
    result.data := nil;
    result.flag := 0;
    Exit;
  end;
  if (Val[1] in ['+', '-', ' ']) then
    i := 2
  else
    i := 1;
 
  olen := (len - i + 1);
  slen := (olen div 9);
  olen := olen mod 9;
 
  setlength(result.data, slen + 2);
 
  slen := slen * 9;
  sDw := 0;
 
  while i < slen do
  begin
    s := Copy(Val, i, 9);
    inc(i, 9);
    sDw := MulAddMemWithDWordD(@result.data[0], 1000000000, StrToInt(s), sDw);
 
  end;
 
  if olen > 0 then
  begin
    s := Copy(Val, i, olen);
    len := 10;
    for i := 2 to olen do
      len := len * 10;
    sDw := MulAddMemWithDWordD(@result.data[0], len, StrToInt(s), sDw);
  end;
  setlength(result.data, sDw);
  if (Val[1] = '-') then
    result.flag := cardinal(sDw) or $80000000
  else
    result.flag := cardinal(sDw);
end;

Добавлено 25.11.09, 10:25
И тоже с асмом

Function FStrToBigNumDWL(const Val: string): THugeInt;
 
  function MulAddMemWithDWordD(pp1: PCardinal; p2, pAdd: cardinal; len: integer)
      : integer;  assembler;
  asm
          PUSH    ESI
          PUSH    EDI
          PUSH    EBX
          MOV     EDI,pp1
          MOV     ESI,pAdd
 
          MOV     EBX,P2
          MOV     ECX,len
          TEST    ECX,ECX
          JLE     @exit
          CLD
 
          TEST    EBX,EBX
          JNZ     @@2       { p2 = 0 }
          { p1 = pAdd }
          MOV     [EDI],ESI
          XOR     EAX,EAX
          XOR     ESI,ESI
          ADD     EDI,4
          SUB     ECX,1
          REP     STOSD
          JMP     @exit
 
  @@2:
          MOV     EAX,[EDI]
          MUL     EBX        {res= EDX:EAX}
          ADD     EAX,ESI
          STOSD              {Res = dest ( P1 )++}
          ADC     EDX,0
          MOV     ESI,EDX    {save EDX}
          SUB     ECX,1
          JNZ     @@2
 
  @exit:  MOV     EAX,len
          TEST    ESI,ESI
          JZ      @@1
          MOV     [EDI],ESI
          INC     EAX
 
  @@1:    POP     EBX
          POP     EDI
          POP     ESI
  end;
 
var
  i, len, slen, olen, sDw: integer;
  s: string;
begin
  len := length(Val);
  if len = 0 then
  begin
    result.data := nil;
    result.flag := 0;
    Exit;
  end;
  if (Val[1] in ['+', '-', ' ']) then
    i := 2
  else
    i := 1;
 
  olen := (len - i + 1);
  slen := (olen div 9);
  olen := olen mod 9;
 
  setlength(result.data, slen + 2);
 
  slen := slen * 9;
  sDw := 0;
 
  while i < slen do
  begin
    s := Copy(Val, i, 9);
    inc(i, 9);
    sDw := MulAddMemWithDWordD(@result.data[0], 1000000000, StrToInt(s), sDw);
 
  end;
 
  if olen > 0 then
  begin
    s := Copy(Val, i, olen);
    len := 10;
    for i := 2 to olen do
      len := len * 10;
    sDw := MulAddMemWithDWordD(@result.data[0], len, StrToInt(s), sDw);
  end;
  setlength(result.data, sDw);
  if (Val[1] = '-') then
    result.flag := cardinal(sDw) or $80000000
  else
    result.flag := cardinal(sDw);
end;

Исправил асм по замечаниям leo

Сообщение отредактировано: sCreator - 25.11.09, 20:30

Навскидку парочка замечаний по асму:

Цитата sCreator @ 25.11.09, 09:57

     AND     ECX,ECX
     JLE     @exit
     ...
     AND     EBX,EBX
     JNZ     @@2

Вместо and лучше юзать test - как рекомендуют во всех мануалах Intel и AMD

Цитата sCreator @ 25.11.09, 09:57

        JNC     @@nc
          INC     EDX
  @@nc:   MOV     ESI,EDX    {save EDX}
          LOOP    @@2

1) jnc+inc = adc edx,0
2) на современных компах loop - это тормоз, лучше dec ecx + jnz @@2 (а еще лучше sub ecx,1 )

Сообщение отредактировано: leo - 25.11.09, 11:15

leo,
Замечания - подсказки с благодарностью принимаю.
Мое последнее общение с асмом до этого было еще на Синклере.
А сейчас похоже и самому немного пригодится - немного мучу с обработкой звука и склоняюсь к небольшим асмовским вставкам.
Вот только скачал в последнее время более 200 метром литературы по асму ( почти вся в карзину ), а про оптимизацию под современные процессоры ничего толком не нашел.
Если что посоветуете 9 ссылочка или электронная литература ) - буду благодарен.

Цитата sCreator

Если продолжать делать реализацию, то лучше новую тему.
Только сперва определиться хотя бы с каркасом ( базовой моделью ) модуля,...

Я тоже об этом много думал... Так и сделаю. На счет каркаса - покамись думаю сделать простой модуль, т.е. без классов (мало практики с ними). Чисто набор функций (и процедур) - возвращающие результат.

Цитата sCreator

...если Ты получил промежуточный результат, значит у Тебя уже есть реализации основных операций,...

Сразу извиняюсь за офф-топ, но... Я пользовался не своими реализациями, а языком программирования Ruby, который достаточно медлителен из за того что у него отсувствует стадия компиляции. Код программы вводится в интерпретатор команд которые исполняются "по ходу считывания". Два дня назад стал изучать элементы программирования на этом языке, но лишь в целях предварительных иследований для основной программы и оценки скорости будущего модуля длинной арифметики (в будущем) реализованного на дельфи. В Ruby жутко неудобно писать код из-за отсувствия привычных цыклов. Вместо последних там сделан упор на манипуляции обработки массивов. (сдесь все есть для начинающих: http://ru.wikibooks.org/wiki/Ruby). Конец офф-топа.

Но не стану скромничать, год назад я сделал несколько нароботок для модуля длинной арифметики. Правда, он получился очень корявым и функции разработанны для 10сс, совсем без упора на ускорение.
Что касается времени, то у меня у самого выпадает пара дней в неделю для посещения данного форума. Да и занятся программированием (т.е. хобби) вобще.

P.S.> I'll be back... soon