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

[sCreator]

Сперва немного в защиту моего формата: А почему именно определение на > 0.
Для выполнения основных операций достаточно знать что число не отрицательное:
При умножении, делении

res.znak := n1.znak xor n2.znak;

При сложении

if n1.znak xor n2.znak then // делаем вычитание массивов
else // делаем сложение

( Подробности в модуле с интерфейсным классом, где уже реализованы сложение, вычитание и умножение с учетом знака )
Не думаю что в Вашем варианте это проще - попробуйте прикинуть вариант реализации с THugeInt
А ноль можно хранить так

num.data = nil

( И почему у Вас num.flag = 0 если длинна равна 1 - ведь флаг хранит знак и длинну ? )

Хотя (-1, 0, 1) - хороший ход. ( но Boolean и nil помоему лучше - не люблю дублирования, можно получить трудноуловимую ошибку, достаточно не проследить в одном месте что число уже 0 или еще хуже когда оно уже не ноль, а в знаке осталось ).

Про размер массива больший значимого должно быть отдельное решение, потому, что в начале упоминались числа близкие к 2^(2^32) и при манипуляции с такими числами лишняя память может оказаться критичной.
Про мало ли на запас - в рекорде поля именованные и введение нового практически не скажется на старом коде. Хотя мое мнение прежнее - как лучший вариант скрыть хранение в приватных полях класса, но у Navi1982 с этим словом похоже плохие ассоциации.

Хранить в типизированном файле по моему не дальновидно. Про шутку Navi1982 с битом так и не понял - что между двумя мегабайтными числами на вашем ЖД не найдетcя нескольких байт ?

Как альтернативу могу предложить такой формат:

  TBigZnak = -1..1;
  TBigInt = record
    znak: TBigZnak; // хотя лучше все же Boolean
    len: cardinal;
    data: array of longword;
  end;

Не брать же каждый раз модуль для длинны.

Сообщение отредактировано: sCreator - 24.12.09, 08:53

[Navi1982]

Цитата

Не брать же каждый раз модуль для длинны.

Как вариант можно пользоватся операциями сдвига (3 такта).

//получить длину числа
len:=num.flag shl 1;
len:=len shr 1;
 
//тоже самое
asm
 mov len, num.flag
 shl len, 1
 shr len, 1
end;
 
//получить знак
sign:=num.flag shr 31
 
//тоже самое
asm
 mov sign, num.flag
 shr sign, 31
end;

Пожалуста, расскритикуйте - интересно знать ваше мнение.

[sCreator]

Раскритиковать, это я всегда пожалуйста .
Так зачем Вам хранить отдельно длинну массива? Вы будете задавать упреждающую размерность с большей вероятностью наткнуться на нехватку памяти?
Вы пытаетесь сэкономить на знаке, выделив ему вместо байта бит - вот Вам экономия в 3 байта: sizeOf(num.flag)=4 байта, sizeOf(num.znak)=1 байт.( если, конечно, выберите выравнивание полей по 1 байту, но даже лишние 8 байт в одном числе, как мне представляется, не будут главной причиной возможного переполнения памяти )
Операция чтения, записи на диск намного медленнее вычислений, поэтому формирование, например такой структуры для записи не скажется на самой скорости записи:

Цитата

4 Б - сигнатура файла ( для подтверждения что здесь записаны длинные числа, например строка 'BigI' )
[2 Б - версия]
4 Б - общий размер записи на одно число
[<контрольная сумма записи>]
1 Б - знак
4 Б - размер массива
<сам массив>
//Если общий размер больше
1 Б - код дополнительного поля ( например 1 - коментарий к числу)
4 Б - размер поля
<само поле>
//и так до конца общего размера записи

Про сдвиги на АСМе - а смысл, тогда переписывайте функцию заново, вставляя АСМ. Или вынесите в отдельные функции и посчитайте такты.
( и все ради того чтобы не выносить знак в отдельное поле? )

И посмотрите все таки мои модули с классами ( сообщение 63 ). Что Вы их так боитесь? Вы же с формами работаете?

type
  TForm1 = class(TForm)
  private
    { Private declarations }
  public
    { Public declarations }
  end;

Это тоже определение класса.
А методы - почти те-же функции. Поменяйте переменные и пользуйтесь. Тем более что там в отдельном модуле еще и АСМ функции - правда не так оптимизированные как функция преобразования из строки с АСМом ( сообщение 72 ), по подсказкам leo. Вы ее сами то пробовали хоть?

[leo]

Цитата Navi1982 @ 26.12.09, 12:43

Цитата sCreator @ 23.12.09, 21:20

Не брать же каждый раз модуль для длинны

Как вариант можно пользоватся операциями сдвига (3 такта).

Можно, но не нужно, т.к. проще через And:

len:=num.flag and MaxInt;

Хотя оперировать мегабайнтыми массивами и экономить 4 байта на знаке - это конечно нонсенс

[Navi1982]

Всех с наступившим Новым Годом! Желаю всем здоровья, успехов, счастья и исполнения желаний!

Почитал, подумал... убидили. Можно разделить процесс записи на диск от вычислений над массивами из длинных чисел. Но, некоторый нюансик все же есть... Что быстрее: хранить длину массива или в каждый раз ее спрашивать через функцию length(num.data) ?? Просто любопытно.

Сообщение отредактировано: Navi1982 - 02.01.10, 10:53

[Navi1982]

sCreator, порылся я в твоих исходниках, позаимствовал твой код из SubMem... но в результате какая-то ерунда получается... Из ниже следующего кода выдает какой-то непонятный результат... Вобщем саму свою функцию уже переписал с тем подходом, чтобы переменные хранились отдельно, т.е. в функции... и все ровно что-то не так - результат в каждый раз бывает разным! (точнее если получать несколько раз подряд результат, то он будет чередоватся с небольшим отклонением, но разным при каждом запуске программы)... могли бы вы мне подсказать что я делаю не так??

{Функция вычетания: result = op1 - op2; only if |op1| >= |op2|}
Function HIModSub(const op1,op2:THugeInt):THugeInt;
Var
  i,len:integer;
  P1,P2,res:THugeInt;
begin
  //проверка, если op1 больше или ровно op2!
  len:=length(op1.data);
  if len>=length(op2.data) then
  begin  //начинаем вычитане
   SetLength(res.data,len); res.flag:=len;
   SetLength(P1.data,len); P1.flag:=len;
   P1.data:=Copy(op1.data);
   SetLength(P2.data,len); P2.flag:=len;
   P2.data:=Copy(op2.data);
asm
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,P1.data
        MOV     EDI,res.data
        MOV     EDX,P2.data
        MOV     ECX,len
        CLD                  // <-- тут добавил я: направление
        CLC                  // <-- тут добавил я: перенос
        AND     ECX,ECX
        JLE     @exit
@@2:    LODSD
        SBB     EAX,EDX
        STOSD
        MOV     EDX,0
        JNC     @@1
        LOOP    @@2
        INC     EDX
        JMP     @exit
 
@@1:
        CLD
        REP     MOVSD
@exit:  MOV     EAX,EDX
        POP     EDI
        POP     ESI
end;
  end;
result.data:=Copy(res.data);
result.flag:=res.flag;
end;

[leo]

Цитата Navi1982 @ 11.01.10, 17:18

могли бы вы мне подсказать что я делаю не так??

Юзаешь какой-то левый левый кусок асм-кода, не имеющий никакого отношения к вычитанию result = op1 - op2

Добавлено 11.01.10, 17:53
Бред какой-то:

        MOV     EDX,P2.data  //в EDX УКАЗАТЕЛЬ на массив P2.data
        ...
@@2:    LODSD               //грузим в EAX дворд из массива P1.data
        SBB     EAX,EDX     //?!! вычитаем из него УКАЗАТЕЛЬ на P2.data
        STOSD               //сохраняем полученный мусор в res.data
        MOV     EDX,0       //?!! зануляем EDX
        JNC     @@1         //?!! выходим из цикла если не было переноса, т.е. либо случайно на 1-й итерации, либо 100% на 2-й
        LOOP    @@2

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

[sCreator]

Navi1982
Во-первых Вы не сравниваете op1 и op2? а сравниваете их длины. У Вас выполнится 10 - 16
Вот попробуйте функцию сравнения ( выдрал от туда же ).

// HIModCompare(const op1,op2:THugeInt): Integer;
// -1 : op1 < op2
//  0 : op1 = op2
//  1 : op1 > op2
function HIModCompare(const op1, op2: THugeInt): Integer;
 
  function CompareMemDown(P1, P2: Pointer; Length: Integer): Integer; assembler;
  asm
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,P1
        MOV     EDI,P2
 
        LEA     ESI,[ESI+ECX-4] { point ESI to last dword of source     }
        LEA     EDI,[EDI+ECX-4] { point EDI to last dword of dest       }
        STD
 
        MOV     EDX,ECX
        XOR     EAX,EAX
        AND     EDX,3
        SAR     ECX,2
        JS      @@1     // Negative Length implies identity.
 
        REPE    CMPSD
        JNE     @@2
        MOV     ECX,EDX
 
        ADD     ESI,4-1         { point to last byte of rest    }
        ADD     EDI,4-1
 
        REPE    CMPSB
        JE      @@1
        MOVZX   EAX,BYTE PTR [ESI+1]
        MOVZX   EDX,BYTE PTR [EDI+1]
        JMP     @@3
 
@@2:    MOV     EAX,[ESI+4]
        MOV     EDX,[EDI+4]
 
@@3:    SUB     EAX,EDX
        MOV     EAX,1
        JNC     @@1
        NEG     EAX
 
@@1:    CLD
        POP     EDI
        POP     ESI
  end;
begin
  Result := CompareValue(length(op1.data), length(op2.data));
  if Result = 0 then
  begin
    Result := CompareMemDown(op1.data, op2.data, length(op1.data) * 4);
  end;
end;

[Navi1982]

Цитата sCreator

Во-первых Вы не сравниваете op1 и op2? а сравниваете их длины.

да... я забыл сказать, что так оно и есть, но это скоростное сравнение... Дополнительно надо будет дописать код поправки. Но на такие вот значения op1 и op2 это не влияет:
op1 = $012C (300)
op2 = $00C8 (200)
leo, спасибо тебе за анализ... Я действительно и сам понял что там бред какой-то, вот и поинтересовался у sCreator'а...
Но и такой код тоже не канает - взял из книжки (асм).

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

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

[sCreator]

Navi1982
Во вторых: после этого

P1.data := Copy(op1.data);

length(P1.data) = length(op1.data)

Аналогично для P2 в результате вы вычитаете мусор памяти
( у Вас Range checking и Overflow checking у компилятора выставлены? )

Добавлено 11.01.10, 18:29
Вот попробуйте такую ( выдрал из своего кода )

function HIModMinus(const op1, op2: THugeInt): THugeInt;
var
  res: THugeInt;
  v: longword;
  len1, len2, i: Integer;
begin
  if HIModCompare(op1, op2) < 1 then
  begin // при op1 <= op2 возвращаем 0
    Result.data := nil;
    Result.flag := 0;
    Exit
  end;
 
  len1 := length(op1.data);
  len2 := length(op2.data);
  SetLength(Result.data,len1);
  v := SubMem(op1.data[0], op2.data[0], Result.data[0], len2);
  if len1 > len2 then
    v := SubMemDWord(op1.data[len2], v, Result.data[len2], len1 - len2);
 
  if v <> 0 then
    raise Exception.Create('illegal param in HIModMinus(const op1, op2: THugeInt)');
 
  i := len1 - 1;
  while (Result.data[i] = 0) and (i >= 0) do
    Dec(i);
  Inc(i);
  if i < len1 then
    SetLength(Result.data,i);
  Result.flag := i;
end;

В ней используются асм функции

function SubMemDWord(const P1; P2: Cardinal;var Res; Length: Integer): Cardinal; assembler;
asm
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,P1
        MOV     EDI,Res
        MOV     EDX,P2
        MOV     ECX,Length
        AND     ECX,ECX
        JLE     @exit
@@2:    LODSD
        SBB     EAX,EDX
        STOSD
        MOV     EDX,0
        JNC     @@1
        LOOP    @@2
        INC     EDX
        JMP     @exit
 
@@1:
        CLD
        REP     MOVSD
@exit:  MOV     EAX,EDX
        POP     EDI
        POP     ESI
end;
 
function SubMem(const P1, P2;var Res; Length: Integer): Cardinal; assembler;
asm
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,P1
        MOV     EDI,Res
        MOV     EDX,P2
        MOV     ECX,Length
        AND     ECX,ECX
        JLE     @@1
@@2:    LODSD
        SBB     EAX,[EDX]
        STOSD
        LEA     EDX,[EDX+4]
        LOOP    @@2
@@1:    MOV     EAX,0
        JNC     @exit
        INC     EAX
 
@exit:
        POP     EDI
        POP     ESI
end;

Кстати нашел интересную ссылку: Огромные числа

Сообщение отредактировано: sCreator - 11.01.10, 18:48

[Navi1982]

Ага, видел эту статейку... она в DRBK записана и взята с http://delphiworld.narod.ru/
Но я позно ее заметил, да к тому-же там функция перевода, мне так кажется (еще не пробовал), не так оптимальна как выработанная в этой теме

sCreator, Range и Owerflow Checking не выставлены. А должны быть?

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

[sCreator]

Для отладки надо выставлять Range и Owerflow Checking.
Тогда при попытки выйти за пределы массива сразу будет ошибка.
После отладки их снимают, чтобы побыстрее работало

[Navi1982]

Цитата от_себя

Но и такой код тоже не канает - взял из книжки (асм).

нашел прокол... теперь работает.. и код вышел проще чем у sCreator'а... Хотя у sCreator'а есть приемущество - экономичный расход памяти, но я не въехал каким образом у него происходит вычетание...

а вот и место ошибки (в конце функции):

result.data:=Copy(res.data);
result.flag:=res.flag;

а надо было так:

result.data:=Copy(P1.data);
result.flag:=P1.flag;

всем спасибо за помощь!!!

P.S.: Перехожу на корректировку знаков и скоро выложу код.

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

[Navi1982]

А почему после процедуры коррекции в P1 меняются данные? (см. функцию HIModSub в конце) Такое ощущение, буд-то меняются ссылки на этот массив... или остаются старыми? Тогда как правильно получить массив?

{Процедура коррекции числа:
 убирает незначемые нулевые элементы с конца .data}
Procedure HICorrection(op:THugeInt);
Var i,sg:integer;
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;

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

[leo]

Цитата Navi1982 @ 11.01.10, 22:37

Тогда как правильно получить массив?

Procedure HICorrection(var op:THugeInt); //!!! VAR

Цитата Navi1982 @ 11.01.10, 20:14

и код вышел проще чем у sCreator'а... Хотя у sCreator'а есть приемущество - экономичный расход памяти

Преимущество не только в расходе памяти, но и в быстродействии, т.к. нет ненужных копирований массивов. А твой вариант - это просто чудо "антиоптимизации" Вопросы на засыпку:
1) зачем создавать полную копию массива op1, если можно читать данные непосредственно из op1 ?
2) зачем для result создавать отдельную копию массива P1, если можно выдать сам массив P1.data ?
3) зачем в цикле юзать юзать совершенно ненужные дополнительные операции записи и чтения [EDI]:

Цитата Navi1982 @ 11.01.10, 22:37

  SBB     [EDI],EAX
  MOV     EAX,[EDI]

если можно просто поменять массивы местами или вобще отказаться от LODS\STOS ?
К тому же ты упорно игнорируешь замечание sCreator'а о том, что длину массива нужно задавать не перед Copy, а после, т.к. Copy изменяет длину массива.
С учетом сказанного, если уж использовать выравнивание длин массивов для упрощения вычитания, то как-то так:

{Функция вычетания: result = op1 - op2; only if |op1| >= |op2|}
function HIModSub(const op1,op2:THugeInt):THugeInt;
Var
  len,i:integer;
  P:THugeInt;
begin
  Result.data:=nil;
  Result.flag:=0;
  //проверка, если op1 больше или ровно op2!
  len:=length(op1.data);
  if (len = 0) or (len < length(op2.data)) then Exit;
  P.data:=Copy(op2.data);  
  SetLength(P.data,len);
  //вычитане
  asm
    push esi
    push edi
    mov esi,op1.data
    mov edi,P.data
    mov ecx,len
    test ecx,ecx //очистка CF вместо CLD
@@1:
    lodsd
    sbb eax,[edi]
    stosd
    dec ecx
    jnz @@1
    pop edi
    pop esi
  end;
  //HiCorrection
  for i:=len-1 downto 0 do
  begin
    if P.data[i] <> 0 then Break;
    dec(len);
  end;
  if len < length(P.data) then SetLength(P.data,len);
  result.data:=P.data;
  result.flag:=len;
end;

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