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

[sCreator]

Можно еще сэкономить на P если использовать вместо него op2 (сперва увеличить длинну потом восстановить )
И хочу обратить внимание Navi1982 что leo сказал "как-то так:" - он показывает Вам принцип, костяк, который надо отработать.
В часности
- вопрос с вычитанием 200 - 300 не решен функция выдаст FFFFFF9C = 4294967196 ( т.е. дополнительный вид числа )
- Если SetLength() увеличивает длинну массива то согласно справки Delphi новые элементы имеют неопределенное значения ( т.е. не обязательно = 0 )

И так и не понял формат нуля:
- он data=nil, flag=0
- или data=(0), flag=1 ?

Я когда выдирал function HIModMinus(const op1, op2: THugeInt): THugeInt;
из выложенных ранее классовых методов не включил в нее работу со знаками и полную обработку если op1 меньше, потому, что так и не понял, какое у Вас теперь представление знака и у меня там это решалось комплексно в методах

    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 ModPlus(const Val: IBigInt):IBigInt; overload;
    function ModPlus(const Val: TElemTyp):IBigInt; overload; // надеюсь немного быстрее
    // вычитает не смотря на знаки
    function ModMinus(const Val: IBigInt):IBigInt; overload;
    function ModMinus(const Val: TElemTyp):IBigInt; overload;

Экономия у меня не только в памяти но и в том, что я сперва вычитаю массивы на длинну меньшего, а вовтором асме просто учитывается знак переполнения.
Т.е. при вычитании из числа размерностью в 100000 элементов числа размерностью 100 эл. у меня в лучшем случае дело ограничится циклом до 100

[leo]

Цитата sCreator @ 12.01.10, 08:53

Можно еще сэкономить на P если использовать вместо него op2 (сперва увеличить длинну потом восстановить )

Тогда придется передавать op2 как var-параметр, да и суть экономии не очень понятна, т.к. во-первых, в любом сл.нужно выделять новый массив под result и соотв-но изменение длины op2 приведет к лишнему расходу памяти, во-вторых, увеличение длины массива op2 без его перелокации по новому адресу не гарантировано, а перелокация влечет за собой копирование старых данных на новое место и следовательно выигрыша по скорости тоже не будет - поэтому лучше и проще сразу скопировать op2 в result (= P)

Цитата sCreator @ 12.01.10, 08:53

Если SetLength() увеличивает длинну массива то согласно справки Delphi новые элементы имеют неопределенное значения ( т.е. не обязательно = 0 )

Согласно справке - да, а согласно исходнику system.DynArraySetLength в дельфи 7 новые элементы зануляются независимо от их типа

  // Set the new memory to all zero bits
  FillChar((PChar(p) + elSize * oldLength)^, elSize * (newLength - oldLength), 0);

и маловероятно, что это поведение было\будет изменено в последующих версиях

Добавлено 12.01.10, 10:00
PS: В моем "как-то так" варианте для копирования op2 в P вместо Copy + SetLength видимо лучше юзать

SetLength(P,len);
Move(op2.data[0],P.data[0],length(op2)*SizeOf(integer));

Сообщение отредактировано: leo - 12.01.10, 10:00

[sCreator]

Согласен.
Про system.DynArraySetLength взял на заметку ( вот так и верь справке ) и проверил - в 2010 тоже самое.

[Navi1982]

Да, я согласен с тем что моя функция не претендует на идеал, но если я не ошибаюсь, то делал замечание на то, что сначала пробовал именно как подсказал leo, а потом даже перераспределил переменные с тем, чтобы убедится что нет ошибки... А вопрос ошибки так и не решился... Т.е. я все про ту же передачу данных массива... При возвращении из процедуры HICorrection данные искажаются! Причем, не всегда!!! Я пробовал и со словом VAR (что по ходу воспринимается по умолчанию) Кароче тупизм какой-то... попробывал предложение leo, коректировать прямо в функции HIModSub - та же ерунда... Результат выдает правильно только в первом элементе (4 байта) а во втором происходит отрицание и даже с вариацией... Но такой результат не всегда происходит - иногда правильно показывает результат, а иногда нет... Я просто в шоке!
Вот какие числа складываются: 99999999999999999999 - 200 = правильно / и неправильно с отклонениями через 1-2 раза. Череда между правильно и неправильно тоже вариирует, но только после функции HIModAdd (см.выше по теме).

leo, я не игнорирую рекомендации sCreator'a задавать длину после Copy, но просто в моих случаях там гарантированно не выходит за пределы.

sCreator, не 200-300, а на оборот 300-200... Такие числа гарантирую покамись я.
На счет документации дельфи про SetLength - проверял опытным путем, под наблюдением Watches... Хотя, кто знает как оно себя поведет потом... Возможно уже так себя и ведет.

Вобщем бьюсь и пробую пока ваши варианты...

Добавлено 12.01.10, 16:49

Цитата sCreator

И так и не понял формат нуля:
- он data=nil, flag=0
- или data=(0), flag=1 ?

первое.

[leo]

Цитата Navi1982 @ 12.01.10, 16:39

я не игнорирую рекомендации sCreator'a задавать длину после Copy, но просто в моих случаях там гарантированно не выходит за пределы

За какие пределы ? Твои слова:

Цитата Navi1982 @ 12.01.10, 16:39

Вот какие числа складываются: 99999999999999999999 - 200

т.е. длина первого числа = 3, а второго = 1, и соотв-но при P2.data:=Copy(op2.data) длина массива P2 становится равной 1, а не 3, и соотв-но в старших 2-х элементах содержится какой-то случайный мусор и поэтому

Цитата Navi1982 @ 12.01.10, 16:39

Результат выдает правильно только в первом элементе (4 байта) а во втором происходит отрицание и даже с вариацией... Но такой результат не всегда происходит - иногда правильно показывает результат, а иногда нет...

т.е. "искажение" происходит не при HICorrection, а раньше - при вычитании, т.к. массивы P1 и P2 имеют разную длину

Сообщение отредактировано: leo - 12.01.10, 17:10

[sCreator]

Navi1982

Цитата Navi1982 @ 12.01.10, 16:39

На счет документации дельфи про SetLength - проверял опытным путем, под наблюдением Watches... Хотя, кто знает как оно себя поведет потом... Возможно уже так себя и ведет.

Прочитайте внимательно посты leo и мои - уже разобрались - новые элементы зануляются ( проверено в 7 и 2010 ).
Procedure HICorrection(op:THugeInt); не выполняет условие нуля ( data=nil, flag=0 )

и какая у Вас теперь функция ( смотрите замечания leo по асму своей ) ? ( а лучше возьмите его, если не нужны мои дополнения )

[Navi1982]

Вот! Зацените...

type
  THugeInt = record //"HugeInt" <=> "HI"
    flag: longint;
    data: array of longword;
    end;

...

{Процедура коррекции числа:
 убирает незначемые нулевые элементы с конца .data}
Procedure HICorrection(Var op:THugeInt);
Var i,sg:integer;
Begin
 if op.data <> nil then //or op.flag<>0
 begin
   if op.flag<0 then sg:=-1 else sg:=1;
   i:=length(op.data)-1;
   while (i>0)and(op.data[i]=0) do Dec(i); //пока не первый и равен нулю
   SetLength(op.data,i+1);
   op.flag:=length(op.data)*sg;
 end;
End;

{функция сравнения по модулю, нужна для некоторых операций}
{возвращает: 1 if |op1|>|op2|; 0 if |op1|=|op2|; -1 if |op1|<|op2|}
{!!!доработать если операнды=nil}
Function HIModCompare(Const op1, op2:THugeInt):integer;
Var i,r:integer;
Begin
  if abs(op1.flag)>abs(op2.flag) then r:=1;
  if abs(op1.flag)<abs(op2.flag) then r:=-1;
  if abs(op1.flag)=abs(op2.flag) then
  begin
    i:=abs(op1.flag)-1;
    while (i>=0)and(op1.data[i]=op2.data[i]) do Dec(i);
    if i<0 then r:=0 else
    begin
     if op1.data[i]>op2.data[i] then r:=1;
     if op1.data[i]<op2.data[i] then r:=-1;
    end;
  end;
result:=r;
End;

{функция сравнения с учетом знака}
{возвращает: 1 if op1>op2; 0 if op1=op2; -1 if op1<op2}
{!!!доработать если операнды=nil}
Function HICompare(Const op1, op2:THugeInt):integer;
Var i,r:integer;
Begin
  if op1.flag>op2.flag then r:=1;
  if op1.flag<op2.flag then r:=-1;
  if op1.flag=op2.flag then
  begin
    i:=abs(op1.flag)-1;
    while (i>=0)and(op1.data[i]=op2.data[i]) do Dec(i);
    if i<0 then r:=0 else
    begin
     if op1.data[i]>op2.data[i] then r:=1;
     if op1.data[i]<op2.data[i] then r:=-1;
    end;
  end;
result:=r;
End;

- вот истинное удобство поля .flag !

{Функция сложения по модулю}
Function HIModAdd(const op1,op2:THugeInt):THugeInt;
Var
  i,len,lenmax:integer;
  t:Int64;
  cr:array [0..1] of cardinal absolute t;
begin
  //возьмем число за основу
  if abs(op1.flag)<abs(op2.flag) then
  begin
    len:=abs(op1.flag); lenmax:=abs(op2.flag);
    SetLength(result.data,lenmax); //определим размер результата
    //начинаем сложение с младших элементов до минимальной длины
    t:=0; //<=> cr[0..1]:=0;
    for i:=0 to len-1 do begin
      t:=int64(op1.data[i])+int64(op2.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
    //далее прибавляем 0 с переносами до конца
    for i:=len to lenmax-1 do begin
      t:=int64(op2.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
  end else //abs(op1.flag)>=abs(op2.flag)
  begin
    len:=abs(op2.flag); lenmax:=abs(op1.flag);
    SetLength(result.data,lenmax); //определим размер результата
    //начинаем сложение с младших элементов до минимальной длины
    t:=0; //<=> cr[0..1]:=0;
    for i:=0 to len-1 do begin
      t:=int64(op1.data[i])+int64(op2.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
    //далее прибавляем 0 с переносами до конца
    for i:=len to lenmax-1 do begin
      t:=int64(op1.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
  end;
  //учтем значение последнего переноса
  if t>$FFFFFFFF then begin
    lenmax:=lenmax+1;
    SetLength(result.data,lenmax);
    result.data[lenmax-1]:=cr[1];
  end;
  result.flag:=lenmax; //длина результата
end;

{Функция вычетания по модулю}
{result = op1 - op2; only if |op1| >= |op2|}
Function HIModSub(const op1,op2:THugeInt):THugeInt;
Var
  i,len,rif:integer;
  P1,P2:THugeInt;
begin
  result.data:=nil;
  result.flag:=0;
  //проверка, если |op1| >= |op2|
  rif:=HIModCompare(op1,op2);
  if rif>=0 then
  begin
   len:=length(op1.data);
   P1.data:=Copy(op1.data);
   SetLength(P1.data,len); P1.flag:=len;
   P2.data:=Copy(op2.data);
   SetLength(P2.data,len); P2.flag:=len;
//начинаем вычитане
asm
        PUSH    EAX
        PUSH    EDI
        PUSH    ESI
        PUSH    ECX
        MOV     EDI,P2.data[0]
        MOV     ESI,P1.data
 
        MOV     ECX,len
        CLD
        CLC
@@1:    LODSD
        SBB     EAX,[EDI]
        STOSD
        LOOP    @@1
        POP     ECX
        POP     ESI
        POP     EDI
        POP     EAX
end;
HICorrection(P2);
result.data:=Copy(P2.data);
result.flag:=P2.flag;
end;
end;

- Кстати, переделал слегка. Однако, есть трабла... Когда делаю так (см. коментарии в ASM блоке):

{Функция вычетания по модулю}
{result = op1 - op2; only if |op1| >= |op2|}
Function HIModSub(const op1,op2:THugeInt):THugeInt;
Var
  i,len,rif:integer;
  P2:THugeInt;
begin
  result.data:=nil;
  result.flag:=0;
  //проверка, если |op1| >= |op2|
  rif:=HIModCompare(op1,op2);
  if rif>=0 then
  begin
   len:=length(op1.data);
   P2.data:=Copy(op2.data);
   SetLength(P2.data,len); P2.flag:=len;
//начинаем вычитане
asm
        PUSH    EAX
        PUSH    EDI
        PUSH    ESI
        PUSH    ECX
        MOV     EDI,P2.data[0]
        MOV     ESI,op1.data //<- то ESI принимает значение 1
        MOV     ECX,len
        CLD
        CLC
@@1:    LODSD                //<- в результате происходит ошибка чтения
        SBB     EAX,[EDI]
        STOSD
        LOOP    @@1
        POP     ECX
        POP     ESI
        POP     EDI
        POP     EAX
end;
HICorrection(P2);
result.data:=Copy(P2.data);
result.flag:=P2.flag;
end;
end;

Способ исправления - либо используем P2, либо op1 должен быть Var! А может и как-то иначе можно разрешить вопрос?!

[leo]

Цитата Navi1982 @ 12.01.10, 22:23

        MOV     ESI,op1.data //<- то ESI принимает значение 1

Способ исправления - либо используем P2, либо op1 должен быть Var! А может и как-то иначе можно разрешить вопрос?!

Ах, да - ведь op1 передается как const, т.е. по указателю, а не по значению, поэтому непосредственно мувить op1.data нельзя (только странно почему дельфи это проглатывает и вместо ошибки выдает фиг знает что)
Варианты решения: либо просто передавать op1 по значению (убрать const из объявления параметров), либо оставить const и слегка изменить асм-код:

  mov esi,op1  //загружаем в esi указатель на op1
  mov esi,[esi+THugeInt.data] //загружаем в esi указатель на op1.data

При const можно также и промежуточный P2 использовать, но только не копировать весь массив через Copy, а просто присвоить ссылку на data:

  P2.data:=op1.data;
  asm
    ...
    mov esi,P2.data
    ...

Цитата Navi1982 @ 12.01.10, 22:23

MOV EDI,P2.data[0]

Здесь никакие [0] не нужны, т.к. в асме квадратные скобки имеют совсем другой смысл. В данном случае запись P2.data[0] является эквивалентом pChar(P2.data)+0, т.е. это тоже самое что и просто P2.data, но более туманно и двусмысленно

Сообщение отредактировано: leo - 13.01.10, 09:04

[sCreator]

leo прошелся по асму, пройдусь по другому
Navi1982

Цитата

- вот истинное удобство поля .flag !

и где?

{функция сравнения с учетом знака}
{возвращает: 1 if op1>op2; 0 if op1=op2; -1 if op1<op2}
{!!!доработать если операнды=nil}
Function HICompare(Const op1, op2:THugeInt):integer;
Var i,r:integer;
Begin
  if op1.flag>op2.flag then r:=1;
  if op1.flag<op2.flag then r:=-1;
  if op1.flag=op2.flag then
  begin
    i:=abs(op1.flag)-1;
    while (i>=0)and(op1.data[i]=op2.data[i]) do Dec(i);
    if i<0 then r:=0 else
    begin
     if op1.data[i]>op2.data[i] then r:=1;
     if op1.data[i]<op2.data[i] then r:=-1;

Последние две строки правильно работают на отрицательных числах ?

Как Вам такой вариант суммы ( нелюблю повторов ):

{Функция сложения по модулю}
Function HIModAdd(const op1,op2:THugeInt):THugeInt;
Var
  i,len,lenmax:integer;
  t:Int64;
  cr:array [0..1] of cardinal absolute t;
  pMax: THugeInt;
begin
  //возьмем число за основу
  if abs(op1.flag)<abs(op2.flag) then
  begin
    len:=abs(op1.flag); lenmax:=abs(op2.flag);
    pMax.data := op2.data;
  end else //abs(op1.flag)>=abs(op2.flag)
  begin
    len:=abs(op2.flag); lenmax:=abs(op1.flag);
    pMax.data := op1.data;
  end;
 
    SetLength(result.data,lenmax); //определим размер результата
    //начинаем сложение с младших элементов до минимальной длины
    t:=0; //<=> cr[0..1]:=0;
    for i:=0 to len-1 do begin
      t:=int64(op1.data[i])+int64(op2.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
    //далее прибавляем 0 с переносами до конца
    for i:=len to lenmax-1 do begin
      t:=int64(pMax.data[i])+int64(cr[1]);
      result.data[i]:=cr[0];
    end;
  //учтем значение последнего переноса
  if cr[1] > 0 then begin
    lenmax:=lenmax+1;
    SetLength(result.data,lenmax);
    result.data[lenmax-1]:=cr[1];
  end;
  result.flag:=lenmax; //длина результата
end;

Procedure HICorrection(Var op:THugeInt);

Т.е. нулевое число у Вас может иметь два представления: или (op.flag=-1;op.data=(0)) или (op.flag=1;op.data=(0)) ?

немного отредактировал одну цитату ( нету взял ) и хотел добавить про

Цитата

- вот истинное удобство поля .flag !

где же оно

Function HICompare(Const op1, op2:THugeInt):integer;
Begin
  Result := IfThen(op1.znak, -1, 1);
  if not (op1.znak xor op2.znak) then
    Result := Result * HIModCompare(op1, op2);
End;

function HIModCompare(const op1, op2: THugeInt): integer;
var
  i: integer;
begin
  Result := CompareValue(length(op1.data), length(op1.data));
  if Result = 0 then
  begin
    i := length(op1.data) - 1;
    while (i >= 0) and (op1.data[i] = op2.data[i]) do
      Dec(i);
    if i < 0 then
      Result := 0
    else
      Result := CompareValue((op1.data[i], op2.data[i]));
  end;
end;

Сообщение отредактировано: sCreator - 14.01.10, 16:32

[Navi1982]

Цитата sCreator

Последние две строки правильно работают на отрицательных числах ?

sCreator, спасибо - вы правы, как всегда! Я действительно недоглядел этот момент... Однако, это решается просто - добавлением вот такой строчки:

...
if i<0 then r:=0 else
    begin
     if op1.data[i]>op2.data[i] then r:=1;
     if op1.data[i]<op2.data[i] then r:=-1;
     if op1.flag<0 then r:=r*-1; //<= вот эта строчка: спасибо sCreator'у что заметил!
...

исправлений выше делать не буду, поскольку хочу скоро открыть новую тему, где будут выкладыватся комплексные решения, но сдесь хочу продолжить обсуждать этот модуль.

На счет нулевого значения... хммм... - получается, что число может иметь как "-0", так и "+0"... а это может как-то критично обернутся в будущем?! А что предлагаете вы?

Добавлено 14.01.10, 21:03
Кстати, ваше замечание меня навело на мысль и эта мысль помогла мне обнаружить, что у меня возникают проблемы при обработке нолей! Еще точнее - это происходит в функции StrToHugeInt.

Сообщение отредактировано: Navi1982 - 14.01.10, 21:05

[sCreator]

Цитата Navi1982 @ 14.01.10, 20:59

На счет нулевого значения... хммм... - получается, что число может иметь как "-0", так и "+0"... а это может как-то критично обернутся в будущем?! А что предлагаете вы?

Пока ничего не предлагаю кроме как подумать над этим и подставить в функции сравнения -0 и +0
они не выдадут что нули равны - надо это как то учесть

[Navi1982]

Ха-ха значит мы заметили это одновременно!

Добавлено 14.01.10, 21:45
А вот и ссылка той самой функции StrToHugeInt.

[sCreator]

Если бы еще знать на каком варианте функции StrToHugeInt Вы остановились - а то у меня их штук 5

[Navi1982]

Ну, вот... Дождался ответа BugHunter'а и он мне напомнил, что в его функции значение "0" задается .data=nil и .flag=0. И я принял решение подправить его функцию таким вот образом (см. в конце):

//Создана BugHunter'ом по мотивам sCreator'а
{Функция преобразования форматированой строки-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;
 
    //я тут добавил для обработки нолей.
    if (result.data=nil)and(result.flag=0) then
    begin
     SetLength(result.data,1);
     result.data[0]:=0;
     result.flag:=1;
    end;
  end;

sCreator, я таким образом решил и вопрос со сравнением -0 и +0

[sCreator]

Цитата Navi1982 @ 14.01.10, 21:10

Ха-ха значит мы заметили это одновременно!

Может и одновременно, только "это" у нас разное.