Форум на Исходниках.RU

[Delphi] Длинная арифметика

tasman — Fri, 14 Jan 2011 05:28:49 +0000

tasman: возведение в степень можно реализовать методом последовательного возведения в квадрат алгоритм есть в книге Кормен Т., Лейзерсон Ч., Ривест Р. — Алгоритмы: построение и анализ, но там по модулю, можно подправить и будет работать. но для этого нужно перевести степень в бинарную систему. могу выложить алгоритм из книжки...

[Delphi] Длинная арифметика

ujhgj — Mon, 08 Nov 2010 14:01:50 +0000

ujhgj: Приветствую!
Вы делаете доброе дело. Я уже сбился с ног выискиваю путный модуль длинной арифметики.
У меня два вопроса:
1) модуль здесь только в виде исходный кодов, целиком скачать можно?
2) авторам известны другие реализации длинной арифметики? - какие, и как они в сравнении с этим модулем?

[Delphi] Длинная арифметика

Navi1982 — Wed, 07 Jul 2010 20:01:37 +0000

Navi1982: В делении сделал некоторые изменения:
1. обработка деления на ноль.
2. устранил ошибку, дающая в результяте деления 0 в случаях, когда делитель был больше 2^32-1 (т.е. в массиве занимал более 1-го разряда). (см. коментарий)
3. прокоментировал действия в делении.

Сожалею, что опубликовал деление не доконца протестив его. :blush:

[Delphi] Длинная арифметика

Navi1982 — Tue, 08 Jun 2010 20:19:18 +0000

Navi1982: Создал тему в которой выложил заготовку всего модуля... Вот ее ссылка

Только есть просьба - не пишите там коментарии... лучше их отписывайте сюды и почитайте правила темы. :thanks:

[Delphi] Длинная арифметика

Navi1982 — Thu, 03 Jun 2010 21:08:26 +0000

Navi1982: Ну, вот и написал деление... Правда по модулю. Так-же я знаю, сдесь есть несколько уязвимых мест и даже есть где оптимизировать, чтоб быстрей считало... Но пока на работе мучают - не могу сконцентрироватся как следует. То же самое и с умножением... Для быстрого умножения щас кучу методов придумали - самым быстрым на сегодня считается "Faster Integer Multiplication" от Мартина Фюрера. Кому интересно может почитать: FIM Martin Furer
Буду очень признателен, кто поможет его реализовать на дельфи.

Ну и ниже привожу свое деление по модулю...
Это вспомогательная функция:

{Функция сдвига разрядов в старшую сторону}

Function HIShl(const op:THugeInt; n:integer):THugeInt;

Var i,sg:integer;

begin

if n<0 then n:=0;

if op.flag<0 then sg:=-1 else sg:=1;

result.flag:=abs(op.flag)+n*sg;

SetLength(result.data,abs(result.flag));

for i:=0 to abs(op.flag)-1 do result.data[i+n]:=op.data[i];

end;

И само деление по модулю...

{Функция деления по модулю без остатка op1 DIV op2}

{разряд результата угадывается по методу дихотомии}

Function HIModDiv(const op1,op2:THugeInt):THugeInt;

Var

i,len1:integer;

r,t,y,rHI:THugeInt;

rk:longword;

base32,r64,x1,x2:Int64;

begin

//учтем деление на ноль!

t.flag:=1; SetLength(t.data,t.flag); // t=0;

t.data[t.flag-1]:=0;

if HICompare(t,op2)<>0 then //op2<>0 ? //иначе result=nil <=> бесконечность

begin

base32:=0000000; //2^32

len1:=abs(op1.flag); //"лишнее наследство" //вобщем: проход начнем со старших разрядов делимого,

i:=len1; //добавляя в промежуточное делимое по одному разряду справа...

r.flag:=0; SetLength(r.data,r.flag); // r=nil обнуляем часное

t.flag:=0; SetLength(t.data,t.flag); // t=nil обнуляем промежуточное делимое

while i>0 do //...пока не дойдем до последнего разряда из делимого!

begin

t:=HIShl(t,1); //Т.е. в промежуточном делимом сдвигаем разряды влево (умножаем на базу 2^32),

HICorrection(t); //убеждаемся что после такой процедуры неокажется "левых" нолей,

t.data[0]:=op1.data[i-1]; //и "прибавляем" разряд справа от делимого.

//gues r[k] - начинаем угадывание разряда в часном (макс.подх.знач.) по дихотомии...

x1:=0; x2:=base32; //...в отрезке 0..2^32

r64:=(x1+x2) div 2; //делим отрезок на две половины

rk:=Int64Rec(r64).Lo; //rk и есть текущий разряд в часном и = только что вычесленной середине отрезка.

rHI.flag:=1; SetLength(rHI.data,rHI.flag); //временная переменная THugeInt для rk

while x1<>rk do //будим разделять отрезки пока x1<>rk

begin

rHI.data[0]:=rk;

y:=HIModMul(rHI,op2);//rk*делитель

//теперь проверим в каком отрезке находится

//максимально подходящее значение для rk (текущего разряда часного)

if HICompare(t,y)>=0 then x1:=rk else x2:=rk; //If t>=y Then [значение в старшем отр.] else [младшем]

r64:=(x1+x2) div 2; //и выбраный отрезок снова на пополам

rk:=Int64Rec(r64).Lo; //rk=середина отрезка.

end;

rHI.data[0]:=rk; //Эта строка раньше отсувствовала: "баг подкрался незаметно" ;)

y:=HIModMul(rHI,op2); // y=[текущий разряд часного]*[делитель]

t:=HIModSub(t,y); // [промежуточное делимое]=[промежуточное делимое]-y

HICorrection(t); // убираем "левые" ноли, если имеются.

r:=HIShl(r,1); // фиксируем часное умножая его на базу

r.data[0]:=rk; // и "прибавим" только что вычеслиный разряд

dec(i); // опускаем следующий разряд делимого справа к промежуточному

end;

HICorrection(r); // в результате могут оказаться ноли и мы их почистим кроме значемого

end else //if op2=0 => r=nil ! or infinite (см. в начало)

begin

r.flag:=0; SetLength(r.data,r.flag); // r=nil

end;

result:=r;

end;

А это уже с учетом знака (по аналогии умножения со знаком - см. посты выше):

{Функция деления op1 DIV op2 со знаком}

Function HIDiv(const op1,op2:THugeInt):THugeInt;

Var f1,f2,m:integer;

begin

f1:=op1.flag;

f2:=op2.flag;

m:=0;

if (f1>0)and(f2>0) then m:=1 else

if (f1<0)and(f2<0) then m:=1 else

if (f1>0)and(f2<0) then m:=-1 else

if (f1<0)and(f2>0) then m:=-1;

result:=HIModDiv(op1,op2);

result.flag:=result.flag*m;

end;

[Delphi] Длинная арифметика

Navi1982 — Sat, 29 May 2010 14:09:22 +0000

Navi1982: Тра-та-та-та, та-та! :whistle:
Всем привет!!! :victory: Сколько лет сколько зим меня носило по командировкам... Но я так сказать: с корабля - на бал. Неуспел вернутся из командировки, так уже запрегли на реконструкцию старой ТВ-сети в соседнем городке. Вот, уже 2 недели как отпахал с утра до темна... еще месяц осталось. :hang: Да что я все о себе да и о себе?!... Я главное хотел сказать - продвигаюсь дальше по программированию модуля... Вот за вчера и сегодня напрогал функции умножения по модулю и со знаком. :blush:

Предаю вашему вниманию и вашей критике:
это у меня умножение по модулю:

{Функция умножения по модулю}

Function HIModMul(const op1,op2:THugeInt):THugeInt;

Var

i,j,len1,len2:integer;

t:Int64;

cr:array [0..1] of cardinal absolute t;

rp,r:THugeInt; //rp - is precedent result of multiply

begin

len1:=abs(op1.flag);

len2:=abs(op2.flag);

//begin rp:=0;

rp.flag:=1; SetLength(rp.data,rp.flag);

rp.data[rp.flag-1]:=0; //end rp:=0;

j:=0;

while j<len2 do

begin

i:=0; t:=0;

//begin r:=0;

SetLength(r.data,0);

SetLength(r.data,len1+j+1); //size of op1.data + shift + 1 elem of .data

//end r:=0;

r.flag:=0+j;

while i<len1 do

begin

t:=int64(op2.data[j])*int64(op1.data[i])+t;

inc(r.flag); //SetLength(r.data,r.flag);

r.data[r.flag-1]:=cr[0];

t:=int64(cr[1]);

inc(i);

end;

inc(r.flag);

r.data[r.flag-1]:=t;

//Add r with rp

r:=HIModAdd(r,rp);

//begin rp:=r;

rp.flag:=r.flag; SetLength(rp.data,rp.flag);

rp.data:=Copy(r.data); //end rp:=r;

inc(j);

end;

HICorrection(rp); // убирает незначемые нулевые элементы из массива числа, если присувствуют

result:=rp;

end;

А это умножение с учетом знака:

{Функция умножения со знаком}

Function HIMul(const op1,op2:THugeInt):THugeInt;

Var f1,f2,m:integer;

begin

f1:=op1.flag;

f2:=op2.flag;

m:=0;

if (f1>0)and(f2>0) then m:=1 else

if (f1<0)and(f2<0) then m:=1 else

if (f1>0)and(f2<0) then m:=-1 else

if (f1<0)and(f2>0) then m:=-1;

result:=HIModMul(op1,op2);

result.flag:=result.flag*m;

end;

А еще мечтаю написать деление, но быстрое... допустимо раза в 3 медленее умножения. А то если вспоминать мою старую String'овую версию деления, то там если поделить xxx...xxx длинное число на, скажем 2, то ждать приходится оооущень долга. :wacko:

[Delphi] Длинная арифметика

Navi1982 — Mon, 08 Feb 2010 12:53:31 +0000

Navi1982: Всем здрасти! :writer: Я пропал, потому что в командировку уехал. Щас пишу от знакомого. Программированием щас нет возможности занятся. Скоро вернусь. :hunter:

[Delphi] Длинная арифметика

AndNot — Tue, 26 Jan 2010 03:12:32 +0000

AndNot: Navi1982, меня тоже когда то терзали такие сомнения. После множества тестов остановился на простом варианте: числа хранятся "как есть", то есть в маш. представлении, но всегда беззнаковые:

struc LONG

max dd ? ; макс. количество ячеек (Cell)

sign dd ? ; знак числа

dot dd ? ; положение точки

len dd ? ; использовано ячеек

; здесь начинается число

ends

Упрощенно говоря число хранится точно так же как и четыре байта в DWORD, только здесь размер ячеек 32-х битный. Знак числа и его длина вынесены в отдельные флаги по одной причине: реализация умножения, деления, извлечения корня и возведения в степень, для чисел без знака, на несколько порядков проще и быстрее реализации для чисел в доп. коде, не говоря уж о сложении, вычитании и командах сравнения чисел. Значительно проще. Например умножение будет выглядеть так:

; esi - умножаемое

; edi - множитель

; ebx - результат

@@cycle:

xor ebp, ebp ; ebx - index, для проходов по массивам

@@loop:

mov eax, [esi+ebp*4]

mul [dword edi]

add [ebx+ebp*4], eax ; inc(dst[index], eax

adc [ebx+ebp*4+4], edx ; adc(dst[index+1], edx)

lea edx, [ebp*4+8] ; edx = index+2

@@carry:

jnc @@next

adc [dword ebx+edx], 0

lea edx, [edx+4] ; edx = edx+4 /флаг переполнения изменять нельзя!/

jmp @@carry

@@next:

add ebp, 1

cmp ebp, [esi-4] ; if (ebp < len) then

jb @@loop ; повторяем

add edi, 4

add ebx, 4

dec ecx

jnz @@cycle

Коротко и ясно. А попробуй ка сделать эмуляцию знакового умножения - проще повеситься :)
К сожалению код привести не могу, там все на интелектуальных макросах (т.е. генерируемый код зависит от операндов, типа как компиляторы ЯВУ оптимизируют).

ps: кусок кода выдрал из макроса, так что не ручаюсь за его полную работоспособность.

[Delphi] Длинная арифметика

Navi1982 — Mon, 25 Jan 2010 21:32:39 +0000

Navi1982: хммм... долго думал... и не как не решил... а может это я все зря пишу? в смысле - дублирования функций: по модулю и со знаком... начал читать одну статейку (курсовую) про кодирование чисел см. главу "Прямой, обратный и дополнительный коды" и далее.
...и вдруг призадумался... может хранить числа и оперировать над ними так как это делается в процессорах??!

в этом есть несколько приимуществ:
Или же оставить прямое кодирование так как оно уже есть?!...

P.S.> Интересно ваше мнение... А то у меня почему-то возникают сомнения в выйгрыше по скорости, используя машинный способ кодирования числа...

[Delphi] Длинная арифметика

sCreator — Mon, 18 Jan 2010 19:54:46 +0000

sCreator:

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

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

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

[Delphi] Длинная арифметика

Navi1982 — Mon, 18 Jan 2010 15:16:18 +0000

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;

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

[Delphi] Длинная арифметика

sCreator — Fri, 15 Jan 2010 08:44:30 +0000

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

[Delphi] Длинная арифметика

Navi1982 — Thu, 14 Jan 2010 21:10:47 +0000

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

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

[Delphi] Длинная арифметика

sCreator — Thu, 14 Jan 2010 21:06:42 +0000

sCreator:

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

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

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

[Delphi] Длинная арифметика

Navi1982 — Thu, 14 Jan 2010 20:59:32 +0000

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.

[Delphi] Длинная арифметика

sCreator — Thu, 14 Jan 2010 15:55:53 +0000

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

Цитата

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

и где?

{функция сравнения с учетом знака}

{возвращает: 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 ! :D

где же оно

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;

[Delphi] Длинная арифметика

leo — Wed, 13 Jan 2010 09:03:45 +0000

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, но более туманно и двусмысленно

[Delphi] Длинная арифметика

Navi1982 — Tue, 12 Jan 2010 22:23:13 +0000

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;

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;

result:=r;

End;

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

{Функция сложения по модулю}

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;

//учтем значение последнего переноса

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;

- Кстати, переделал слегка. Однако, есть трабла... Когда делаю так (см. коментарии в 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;

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

[Delphi] Длинная арифметика

sCreator — Tue, 12 Jan 2010 17:12:46 +0000

sCreator: Navi1982

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

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

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

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

[Delphi] Длинная арифметика

leo — Tue, 12 Jan 2010 17:07:14 +0000

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 имеют разную длину

[Delphi] Длинная арифметика

Navi1982 — Tue, 12 Jan 2010 16:39:04 +0000

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 ?

первое.

[Delphi] Длинная арифметика

sCreator — Tue, 12 Jan 2010 10:17:58 +0000

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

[Delphi] Длинная арифметика

leo — Tue, 12 Jan 2010 09:55:28 +0000

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));

[Delphi] Длинная арифметика

sCreator — Tue, 12 Jan 2010 08:53:41 +0000

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

[Delphi] Длинная арифметика

leo — Tue, 12 Jan 2010 07:02:12 +0000

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;

[Delphi] Длинная арифметика

Navi1982 — Mon, 11 Jan 2010 22:37:09 +0000

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;

HiCorrection(P1);

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

result.flag:=P1.flag;

P1.data:=nil;

P2.data:=nil;

end;

[Delphi] Длинная арифметика

Navi1982 — Mon, 11 Jan 2010 20:14:21 +0000

Navi1982:

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

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

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

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

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

result.flag:=res.flag;

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

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

result.flag:=P1.flag;

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

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

[Delphi] Длинная арифметика

sCreator — Mon, 11 Jan 2010 20:11:09 +0000

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

[Delphi] Длинная арифметика

Navi1982 — Mon, 11 Jan 2010 20:02:38 +0000

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

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

[Delphi] Длинная арифметика

sCreator — Mon, 11 Jan 2010 18:10:25 +0000

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;

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

[Delphi] Длинная арифметика

Navi1982 — Mon, 11 Jan 2010 18:01:37 +0000

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;

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

result.flag:=res.flag;

end;

[Delphi] Длинная арифметика

sCreator — Mon, 11 Jan 2010 18:00:49 +0000

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;

[Delphi] Длинная арифметика

leo — Mon, 11 Jan 2010 17:45:17 +0000

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

[Delphi] Длинная арифметика

Navi1982 — Mon, 11 Jan 2010 17:18:27 +0000

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;

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

result.flag:=res.flag;

end;

[Delphi] Длинная арифметика

Navi1982 — Sat, 02 Jan 2010 10:53:31 +0000

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

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

[Delphi] Длинная арифметика

leo — Sat, 26 Dec 2009 15:41:32 +0000

leo:

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

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

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

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

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

len:=num.flag and MaxInt;

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

[Delphi] Длинная арифметика

sCreator — Sat, 26 Dec 2009 13:54:59 +0000

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. Вы ее сами то пробовали хоть?

[Delphi] Длинная арифметика

Navi1982 — Sat, 26 Dec 2009 12:43:45 +0000

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;

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

[Delphi] Длинная арифметика

sCreator — Wed, 23 Dec 2009 21:20:41 +0000

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;

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

[Delphi] Длинная арифметика

Navi1982 — Wed, 23 Dec 2009 19:39:07 +0000

Navi1982: мда... действительно... вы оба правы... у меня не учитывается длина меньшего числа. А как лучше (и быстрее) сделать? Дублировать меньшее число в памяти с учетом длины большего числа или переделать цыкл?... например вот так:

{Функция сложения}

Function HIAdd(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;

//учтем значение последнего переноса

if t>$FFFFFFFF then begin

lenmax:=lenmax+1;

SetLength(result.data,lenmax);

result.data[lenmax-1]:=cr[1];

end;

result.flag:=lenmax; //длина результата

end;

[Delphi] Длинная арифметика

Navi1982 — Wed, 23 Dec 2009 18:21:33 +0000

Navi1982: sCreator, по поводу вами предложенного формата... Я сперва тоже так хотел сделать. Но при сохранении на ЖД этот бит всеровно придется куда-нибудь "клеить"... Или же придется выделять минимум 1 байт для его хранения раздельно. Для чего я сделал поле flag? А для того чтобы в нем хранить как размер, так и знак числа. Но, ты возможно возразишь и скажешь: "функция length(*.data) возвращает размер числа". Но представим себе, что мы записываем на ЖД рекорд с полем дата... Причем несколько подряд... Поидее, сначала записывается (в твоем варианте) поле znak (1 байт), затем поле data (n_elem*4=№ байт)... потом следующий рекорд и т.д. ... может я не прав?... но, обращаю внимание на то, что записывается лишь содержимое массива data, который не содержит "нулевого" элемента (как в String) содержащего информацию о длине.

Но что происходит, когда мы начинаем читать эти рекорды? первый байт прочитается без проблем, т.к. он имеет шаблон (размерность)... Но тип data не имеет размерности, пока не задаш ее длину функцией SetLength... Но на каком основании задать эту длину?... Вот тут то я и придумал переменную flag. Да и функцию length можно с этим учетом вызывать резже... Хотя BugHunter правильно сделал, когда переменную falg типизировал как integer (32bit) вместо моего варианта Cardinal, где бы приходилось писать лишний код для установления и проверки знака (сразу не додумался).

Конечно я не отрицаю и тот момент, что упаковывать знак и длину можно прямо перед самой записью, т.е. вызвать length и добавить знак в последний бит, тем самым обозначить в четырех байтах знак и длину считывания в поле data.

А в коде можно пользоватся и конфигурацией с полем znak... Хотя если заглянуть в память программы, то для znak будет выделено 1 байт - это даже в хелпе написанно (где-то встречал).

Нусь, это сугубо мое мнение...

[Delphi] Длинная арифметика

Bug Hunter — Wed, 23 Dec 2009 17:38:55 +0000

Bug Hunter:

Цитата Navi1982 @ 22.12.09, 17:49

Цитата BugHunter

Т.е. сложение по твоим замерам работает вообще мгновенно!

Вот и я об этом же... Любопытно, от чего так происходит?

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

Цитата Navi1982 @ 22.12.09, 17:49

Цитата sCreator

Функция не будет правильно складывать числа разной длины ...

Это еще почему? Покамись складываются нормально...

Потому, что для меньшего числа у тебя будет происходить выход за границу динамического массива с непредсказуемыми последствиями. А нормально у тебя складывается пока потому, что фишка так легла, что за границей находятся нули, но в общем случае так не будет.

[Delphi] Длинная арифметика

Bug Hunter — Wed, 23 Dec 2009 17:27:10 +0000

Bug Hunter:

Цитата sCreator @ 23.12.09, 06:14

Bug Hunter - интересно Ваше мнение по поводу предложенного мной формата хранения длинного числа:

TBigNum = record

znak: boolean;

data: array of longword;

end;

Ну, смотри: в моем формате проверка числа на то, что оно = 0, делается так:

if num.flag = 0 then ...

а на то, что оно > 0, так

if num.flag > 0 then ...

А у тебя соответственно так:

if (not num.znak) and (length(num.data)=1) and (num.data[0]=0) then ...

и так:

if (not num.znak) and (not ((length(num.data)=1) and (num.data[0]=0))) then ...

Улавливаешь разницу?

Цитата sCreator @ 23.12.09, 06:14

Зачем хранить длину массива в отдельном поле?

Ну, для удобства сравнения достаточно в flag хранить только знак числа (-1, 0 или +1}, но мало ли что понадобиться...

Например, возможно, для того, чтобы не войдохать лишний раз динамическую память, может оказаться полезным хранить числа так, чтобы число значимых двойных слов было меньше размера data. Или можно хранить в flag число значимых бит в числе. Или число значимых бит в последнем неполном двойном слове. Да мало ли еще чего можно придумать - резерв не помешает. Тем более, что ты своим булёном ничего не экономишь - размер струкруры все равно по умолчанию выводится на величину, кратную восьми, и я не вижу причин от этого отказываться - разьве что в сторону увеличения.

[Delphi] Длинная арифметика

sCreator — Wed, 23 Dec 2009 06:14:49 +0000

sCreator: Bug Hunter - интересно Ваше мнение по поводу предложенного мной формата хранения длинного числа:

TBigNum = record

znak: boolean;

data: array of longword;

end;

Зачем хранить длину массива в отдельном поле ? если, например у Navi1982 в функции сложения в конце пишется

result.flag:=len;

А в начале

len:=length(op1.data);

[Delphi] Длинная арифметика

Navi1982 — Tue, 22 Dec 2009 17:49:41 +0000

Navi1982: :blush: Ой... Глубоко сожалею, что неправильно вас понял на счет авторства... совсем запутался... И поскольку вы между собой договорились - я уже это обстоятельство принимаю на веру. Однако, важность авторства должна будет сохранится... и вот почему...
...BugHunter и sCreator, загляните в приват, там следующий фрагмент этого поста...
...

Цитата BugHunter

Т.е. сложение по твоим замерам работает вообще мгновенно!

Вот и я об этом же... Любопытно, от чего так происходит?

Цитата sCreator

Функция не будет правильно складывать числа разной длины ...

Это еще почему? Покамись складываются нормально...

Цитата

...и не учитывает знак.

Да - это так и есть. А разве я этого не отмечал?! :blush:

Вобщем жду ваших мнений...

P.S.>На приват отвечаем приватом :)

[Delphi] Длинная арифметика

sCreator — Sun, 20 Dec 2009 07:34:23 +0000

sCreator: Присоединяюсь к критике.
THugeInt предложил Bug Hunter. Мое предложение было в использовании интерфейсного объекта. Если выделить из него в виде record то выглядит так:

TBigNum = record

znak: boolean;

data: array of longword;

end;

Не вижу смысла хранить длину если Length() от динамического массива просто считывает ее по отрицательным адресам.
Функция не будет правильно складывать числа разной длины и не учитывает знак.
Для оценки времени ее выполнения достаточно в батонклике переместить две строчки:

TimeSta:=Time;

res:=HIAdd(num1,num2);

TimeFin:=Time;

[Delphi] Длинная арифметика

Bug Hunter — Sat, 19 Dec 2009 21:58:06 +0000

Bug Hunter:

Цитата Navi1982 @ 18.12.09, 19:53

Выглядит она сырова-то, но за-то работает...

Хм... Глядя на исходник, я бы не сказал, что функция твоя правильно работает для чисел с разной длинной data.

Попробуй потестировать с волшебной строчкой

{$R+}

Цитата Navi1982 @ 18.12.09, 19:53

на конвертирование числа из 100000 цыфр (10сс) уходит примерно 0,8 секунд (включая: форматроване ~0,032сек; конвертирование ~0,768сек), то на сложение двух чисел по 100000 уходит примерно 1,6 сек!!! (т.е. форматирование + конвертирование 1-го числа, затем 2-го, и затем само сложение)... Незнаю почему так получается

И что тут странного? Если у тебя на форматирование и конвертирование ОДНОГО числа уходит 0.8 сек, то на то же для ДВУХ чисел аккурат должно уходить 1.6 сек. Т.е. сложение по твоим замерам работает вообще мгновенно!

Цитата Navi1982 @ 18.12.09, 19:53

Использовал тип THugeInt, предложенного sCreator'ом.

Лучше все таки ты бы посмотрел повнимательнее на тип THugeInt, предложенный мной. У меня используется знаковый flag, поэтому проверка знака числа производится проверкой знака flag, без громоздкой проверки старшего бита, а длина data дается выражением abs(flag) без, опять же, громоздкого выделения старших бит.

Число ноль в моем типе THugeInt хранится так:

*.data:=nil;

*.flag:=0;

ИМХО, так удобнее.

[Delphi] Длинная арифметика

Navi1982 — Fri, 18 Dec 2009 19:53:20 +0000

Navi1982: Спустя 10 дней, с перебоями приступая к программированию, убийственно уставшим от работы, наконец-таки написал функцию сложения... Выглядит она сырова-то, но за-то работает... И я бы сказал не так уж и медленно! Если, на конвертирование числа из 100000 цыфр (10сс) уходит примерно 0,8 секунд (включая: форматроване ~0,032сек; конвертирование ~0,768сек), то на сложение двух чисел по 100000 уходит примерно 1,6 сек!!! (т.е. форматирование + конвертирование 1-го числа, затем 2-го, и затем само сложение)... Незнаю почему так получается, но думаю что в результате кэширования комманд и данных самим процессором, значительно уменьшается время выполнения процедур форматирования+конвертирования, а затем и самого сложения. (у меня CPU: DualCore Intel Pentium E2200, 2200 MHz (11 x 200), L2 1MB, L1 32kb code / 32kb data)... В любом случае результат приемлим, особенно если его попытатся оптимизировать под ассемблеровскую вставку используя инструкции SSE# и регистры xmm0..xmm7 (128bit). Кстати, пробовал это делать с обычными инструкциями и регистрами (32 бит) - но к сожалению ничего не вышло. Видать, с меня ассемблеровиц тоже не важный :blush: а пример брал из книжки.

Вобщем, вот сама функция. Использовал тип THugeInt, предложенного sCreator'ом.

Function HIAdd(const op1,op2:THugeInt):THugeInt;

Var

i,len:integer;

t:Int64;

cr:array [0..1] of cardinal absolute t;

begin

//определим размер результата

len:=length(op1.data);

SetLength(result.data,len);

if len<length(op2.data) then

begin

len:=length(op2.data);

SetLength(result.data,len);

end;

//начинаем сложение с младших элементов

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;

//учтем значение последнего переноса

if t>$FFFFFFFF then begin

len:=len+1;

SetLength(result.data,len);

result.data[len-1]:=cr[1];

end;

result.flag:=len; //длина результата

end;

Ну и если добавить кнопку на форму, то в ее обработчике у меня следующий код:

procedure TForm3.btAddClick(Sender: TObject);

Var i:Cardinal;

num1,num2,res:THugeInt;

t:String;

begin

LongTimeFormat:='hh:nn:ss:zzz';

TimeSta:=Time;

TestStr:=FormatStr(form3.Edit1.Text);

form3.Edit1.Text:=TestStr;

num1:=StrToHugeInt(TestStr);

TestStr:=FormatStr(form3.Edit2.Text);

form3.Edit2.Text:=TestStr;

num2:=StrToHugeInt(TestStr);

res:=HIAdd(num1,num2);

t:='';

for i:=res.flag-1 downto 0 do

begin

t:=t+IntToHex(res.data[i],8);

end;

form3.Edit3.Text:=t;

TimeFin:=Time;

form3.Label1.Caption:=TimeToStr(TimeFin-TimeSta);

end;

Какие будут идеи по функции вычитания? Т.е. как эффективнее учитывать перенос и определить длину результата? У меня есть пример из книжки по ассемблеру для вычитания, тока пример оттуда-же для сложения, как я писал выше, увенчался неудачей - ну не понимает дельфя все то что понимает TASM/MASM.

На следующей недельке постараюсь написать вычитание. У нас снег выпал, а работа ремонтника+монтажника кабельной сети в частных секторах (1 городок и 1 столичный пригород) - с пешими прогулками и лазаньем по столбам, да и заморочками клиентов - сильно выматывает... а работы - непочатый край, а вознаграждение - рабское... ууу... это уже оффтоп... пора спать! :jokingly:

[Delphi] Длинная арифметика

sCreator — Wed, 09 Dec 2009 08:35:46 +0000

sCreator: Navi1982 - не забудь здесь упомянуть созданную тему, а то могу пропустить.

[Delphi] Длинная арифметика

Bug Hunter — Tue, 08 Dec 2009 21:58:22 +0000

Bug Hunter:

Цитата Navi1982 @ 08.12.09, 20:55

пробовал сам разобратся в скоростном варианте от BugHunter'а предложенного sCreator'ом (вариант с THugeInt) - немного стал улавливать идею... Однако, хотелось бы от авторов узнать теоритическую часть данного перевода. Если, незатруднит, пожалуста приведите на словах общие шаги преобразования? Думаю так легче будет понять суть кода.

Суть там простая - схема Горнера. Ускорение получается за счет того, что в 2^32 цифрах умножение на 10 и на 10^9 по трудоемкости одинаковые операции. Плюс само умножение на цифру пре переходе с 2^16 на 2^32 стало в четыре раза быстрее.

Цитата Navi1982 @ 08.12.09, 20:55

И надо не забыть про функцию обратного перевода из 2^XXcc -> в 10сс (т.е. HugeIntToStr)- а поскольку, исходя из выше приведенных мной примеров, с меня "переводчик" не ах-ти какой, то полностью рассчитываю на вашу помощь

Идея обратного перевода точно такая же - делим на 10^9, получившийся остаток переводим в строку стандартной функцией преобразования, не забывая дополнять при необходимости нулями слева для непоследнего фрагмента, фрагменты стыкуем в выходную строку функцией insert.

Цитата Navi1982 @ 08.12.09, 20:55

А вот с делением у меня плохо

У меня тоже - как-то не было необходимости с этим разбираться. Но если надыбаешь описание алгоритма и/или пример, думаю смогу разобраться.

[Delphi] Длинная арифметика

Navi1982 — Tue, 08 Dec 2009 20:55:56 +0000

Navi1982: Всем, привет!
Ну, вот я вернулся из коммандировки и мне не терпелось вновь взятся за начатое... Посидел пару часиков чтобы вспомнить на чем остановились... Немного отстал мыслями на счет методов перевода, пробовал сам разобратся в скоростном варианте от BugHunter'а предложенного sCreator'ом (вариант с THugeInt) - немного стал улавливать идею... Однако, хотелось бы от авторов узнать теоритическую часть данного перевода. Если, незатруднит, пожалуста приведите на словах общие шаги преобразования? Думаю так легче будет понять суть кода.

В остальном - можно уже переходить на операции сложения, вычетания, умножения (эти я сам скоро приведу в пример), деления и возведения в степень. И надо не забыть про функцию обратного перевода из 2^XXcc -> в 10сс (т.е. HugeIntToStr)- а поскольку, исходя из выше приведенных мной примеров, с меня "переводчик" не ах-ти какой, то полностью рассчитываю на вашу помощь (и в часности на BugHunter'а и sCreator'а).

Что касается первых двух (+ и -), то я просмотрел кое-какую литературу по применению инструкций из набора SSE2, так-что пишу уже с использованием регистров 128-бит (xmm0..xmm7). Умножение в принцыпе тоже можно реализовать с приминением 2 регистров по 128-бит для хранения промежуточного результата (но, еще обдумаю). А вот с делением у меня плохо - за-то BugHunter и sCreator в этом здорого соображают. На счет возведения в степень, мысль примерно такая - использовать сдвиги.

Скоро создам новую темку с готовыми исходниками наработанных вещей.

[Delphi] Длинная арифметика

sCreator — Sat, 28 Nov 2009 07:15:52 +0000

sCreator:

Цитата leo @ 26.11.09, 10:10

Мануалы по оптимизации на оф.сайтах Intel и AMD (... Оptimization Manual) + труды А.Фога

Спасибо. ( про АПИ читаем в MSDN, а при асме про Intel не подумал ) .

[Delphi] Длинная арифметика

leo — Thu, 26 Nov 2009 10:10:11 +0000

leo:

Цитата sCreator @ 25.11.09, 17:32

про оптимизацию под современные процессоры ничего толком не нашел.

Все толковое - на аглицком ;)
Мануалы по оптимизации на оф.сайтах Intel и AMD (... Оptimization Manual) + труды А.Фога

[Delphi] Длинная арифметика

Bug Hunter — Wed, 25 Nov 2009 22:16:25 +0000

Bug Hunter:

Цитата Navi1982 @ 24.11.09, 20:23

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

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

И поиграться с обратным преобразованием BIN->DEC - тоже.

[Delphi] Длинная арифметика

Navi1982 — Wed, 25 Nov 2009 21:04:23 +0000

Navi1982:

Цитата sCreator

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

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

Цитата sCreator

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

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

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

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

[Delphi] Длинная арифметика

sCreator — Wed, 25 Nov 2009 17:32:12 +0000

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

[Delphi] Длинная арифметика

leo — Wed, 25 Nov 2009 11:12:48 +0000

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

Цитата 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 ;))

[Delphi] Длинная арифметика

sCreator — Wed, 25 Nov 2009 09:57:26 +0000

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

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 000000

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 000000

else

result.flag := cardinal(sDw);

end;

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

[Delphi] Длинная арифметика

sCreator — Wed, 25 Nov 2009 05:15:00 +0000

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

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

[Delphi] Длинная арифметика

Navi1982 — Tue, 24 Nov 2009 20:23:06 +0000

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

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

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

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

[Delphi] Длинная арифметика

Navi1982 — Tue, 24 Nov 2009 20:09:01 +0000

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

[Delphi] Длинная арифметика

imgavario — Sat, 21 Nov 2009 03:33:35 +0000

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

[Delphi] Длинная арифметика

Navi1982 — Wed, 18 Nov 2009 16:25:01 +0000

Navi1982: Извиняюсь что пропал... Сегодня попробывал функцию 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 сек

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

[Delphi] Длинная арифметика

sCreator — Wed, 18 Nov 2009 14:51:10 +0000

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 000000

else

result.flag := cardinal(i);

end;

[Delphi] Длинная арифметика

Bug Hunter — Tue, 17 Nov 2009 21:13:13 +0000

Bug Hunter:

Цитата 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, ++ за идею :yes:

[Delphi] Длинная арифметика

Bug Hunter — Mon, 16 Nov 2009 20:48:43 +0000

Bug Hunter:

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

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

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

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

Однако! :yes:

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

[Delphi] Длинная арифметика

sCreator — Sat, 14 Nov 2009 22:15:43 +0000

sCreator: По просьбе 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 пробовать не стал.

[Delphi] Длинная арифметика

Bug Hunter — Fri, 13 Nov 2009 21:35:45 +0000

Bug Hunter:

Цитата 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
Гы - для восьмерок получается периодическое повторение девяток слов :)

[Delphi] Длинная арифметика

Navi1982 — Thu, 12 Nov 2009 20:26:52 +0000

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

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

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

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

[Delphi] Длинная арифметика

Bug Hunter — Thu, 12 Nov 2009 18:45:36 +0000

Bug Hunter:

Цитата Navi1982 @ 12.11.09, 13:03

Но, исходя из уже проведенных тестов функции перевода, обнаружил, что компилятор не хранит массивы длинее 16Кбайт

Че за бред? Даже Турбо Паскаль позволяет использовать структуры данных размером до 64k.

Цитата Navi1982 @ 12.11.09, 13:03

Давно еще, знал как это ограничение снимается, только не помню как? Подскажите, пожалуста.

Ограничиние в 16k было для локальных (автоматических) массивов в Турбо Паскале при стандартных установках - лечилось увиличением размера сегмента стека, но память для динамического массива выделяется в куче и такого ограничения быть не должно <_<

Цитата Navi1982 @ 12.11.09, 17:39

Что касается ошибок с памятью, то у меня не выдает ошибки, просто какбы получается память размером 16Кб забивается нормально, а все байты что свыше адресса 16Кб принимают значение FF. Непонятно почему?!...

Мне вот тоже непонятно, что я делаю не так:

program Project4;

{$APPTYPE CONSOLE}

uses

SysUtils;

var

a: array of integer;

i: integer;

begin

setlength(a, 1000000);

for i:=0 to 1000000-1 do

a[i]:=i;

for i:=1000000-10 to 1000000-1 do

writeln(a[i]);

finalize(a);

readln;

end.

999990

999991

999992

999993

999994

999995

999996

999997

999998

999999

Массивчик под 4 метра - и полет нормальный.

Ты как свой массив смотришь то?

[Delphi] Длинная арифметика

Bug Hunter — Thu, 12 Nov 2009 18:04:01 +0000

Bug Hunter: А вот и мой вариант перевода через деление в столбик без использования делений и умножений:

type

TBigNum = record // 2^31-1 = 2147483647 elements!!!

flag: cardinal; // 31 - sign:0=+ 1=-, 0..30 - length of array

int: array of word; //integer part of number

end;

...

{Функция преобразования форматированой строки-10сс в массив-2^16сс}

{ Функция ожидает строку, содержащую корректную запись целого числа, }

{ форматированую в соответствии со спецификацией: строка должна }

{ содержать только цифры и возможно знак '+', '-' или один лидирующий }

{ пробел вместо знака '+'. Для входящей строки, не соответствующей }

{ спецификации, результат работы функции непредсказуем. }

Function FStrToBigNum(const s: string): TBigNum;

Var

d: array of byte; dlen: integer;

i, j, k: integer;

a: longword; {accomulator}

aw: array[0..1] of word absolute a;

ab: array[0..3] of byte absolute a;

begin

if (s[1] in ['+','-',' ']) then j:=2 else j:=1;

dlen:=length(s)-(j-1);

setlength(d, dlen);

for i:=0 to dlen-1 do d[i]:=ord(s[i+j])-ord('0');

setlength(result.int, 1);

k:=0;

while true do begin

i:=0;

a:=d[0];

j:=1;

while (j<dlen) do begin

a:=(((a shl 2) + a) shl 1)+d[j]; inc(j);

if (ab[2]>0) then begin

d[i]:=ab[2]; inc(i);

ab[2]:=0;

end

else

if (i>0) then begin

d[i]:=0; inc(i);

end;

result.int[k]:=aw[0];

if (i>0) then begin

dlen:=i;

setlength(result.int, k+2);

inc(k);

end

else

break;

end;

if (s[1]='-') then

result.flag:=cardinal(k+1) or 000000

else

result.flag:=cardinal(k+1);

finalize(d);

end;

[Delphi] Длинная арифметика

Navi1982 — Thu, 12 Nov 2009 17:39:51 +0000

Navi1982: sCreator, еще не запускал программу... Что касается ошибок с памятью, то у меня не выдает ошибки, просто какбы получается память размером 16Кб забивается нормально, а все байты что свыше адресса 16Кб принимают значение FF. Непонятно почему?!... Виновата в этом то ли опция в компиляторе, то ли это система WindowsXP 32bit не позволяет разбазаривать память... :-?

Касательно расположения байт, то при записи на диск они останутся в таком виде как записанны в массиве и считывание будет происходить также... Единственное что может помешать - это совместимость старых данных с новыми версиями программы. Так что на этот счет вы всеже правы, придется разворачивать массив и записывать число подрят. Чтобы можно было считать более новыми версиями где элемент массива будет например 32бита. Но при чтении нужно будет учесть кратность байт к элементам массива вот и все. :)

[Delphi] Длинная арифметика

sCreator — Thu, 12 Nov 2009 14:58:09 +0000

sCreator:

Цитата

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

На диск записывать можно в любом придуманном формате - например записываете в 8 байт длину массива в байтах, а делее этот массив ( он в памяти непрерывно храниться ).
обратно считываете 8 байт, устанавливаете длинну массива (выделяется память ) и считываете туда записанные данные (хранение в памяти и в файле разные вещи. Тем более, что в самой записи ( record )
храняться только статические массивы, а на динамические только ссылки.

Цитата

функция предназначена гарантировать содержание исключительно чисел в строке для упрщения функции перевода.

Лучше сразу заменить

else

if rem0=false then num:=num+'0';

На

else ;

А то случайно наберете в эдите пробел и у Вас появится лишний ноль ( во втором варианте он пропустится )

Цитата

компилятор не хранит массивы длинее 16Кбайт

В Delphi 7 похоже такой проблеммы нет ( попробовал SetLength(2000000) ошибки не дало.
Переходите на семерку - с Апдейтами, по моему, самая стабильная - интерфейс ( насколько помню 6 ) практически идентичен.

Удалось ли запустить мою наработку?

Я там использовал для BigNum интерфейсы.
Обьекты в Delphi необходимо отслеживать и уничтожать, во избежании утечек памяти, а при вычислениях формул постоянно создаются временные промежуточные результаты, что не проблема при простых типах данных.
Интерфейсы же в месте с интерфейсными объектами сами следят за своим использованием и сами уничтожаются при обнулении ссылок.
Для контроля утечек и подключал FastMM4 - бесплатная библиотека легко находится и скачивается из интернета.

Добавлено 12.11.09, 15:36

Цитата

Если в array хранить элементы в обратном порядке ( также как в word, например, сперва идет старший байт ), с выравнивание по 64 бита, то тогда через указатели можно получать к такому массиву доступ в каждом случае наиболее эффективный ( хоть UInt64, хоть word ).

Прошу прощения, но кажется я ОШИБСЯ - сейчас проверил байты в word храняться в прямом порядке.
И это значит что при прямом порядке хранения элементов массива к ним через указатели можно обращатся по разному. :blush:

[Delphi] Длинная арифметика

Navi1982 — Thu, 12 Nov 2009 13:03:12 +0000

Navi1982:

Цитата sCreator

TBigNum - зачем во флаге хранить длину array - всегда можно получить ее функцией Length().

Цитата sCreator

FormatStr - может символы отличные от цифр не переводить в нули ( даже не понял для чего это сделано ...

Я не хотел заморачиватся нештатными ситуациями. Кроме того, функция предназначена гарантировать содержание исключительно чисел в строке для упрщения функции перевода. Ее все ровно придется переделывать, но позже. И вобще, функции перевода понадобятся лишь для тестов. Поэтому, если понадобится удобное чтение, то напишу другую функцию GroupNumStr которая просто вставит апострофы или пробелы в нужных местах.

Цитата sCreator

Если в array хранить элементы в обратном порядке ( также как в word, например, сперва идет старший байт )...

Чесно говоря, я давно не помню как распологаются в памяти переменные. Ваша идея принята к сведению - Спасибо!

Цитата sCreator

Интересный вопрос - выделит ли система на один массив больше 2^31 БАЙТ и выделит ли на всю программу больше 2^32 БАЙТ на 32 битной архитектуре?

Интересный вопрос, конечно... Но, исходя из уже проведенных тестов функции перевода, обнаружил, что компилятор не хранит массивы длинее 16Кбайт :( Давно еще, знал как это ограничение снимается, только не помню как? Подскажите, пожалуста. :blush:

Цитата sCreator

Немного о длинной арифметике ...
...( ведь результат, как Вы говорили вполне приемлем, то есть укладывается в Int64? )

Начну с ответа на вопрос из скобок... Максимальный результат не вместится в Int64 это однозначно и наверное даже в 128 бит - но его расчеты в процессе. Однако, он будет много меньше чем ранее указанное колличество знаков в промежуточном результате (134886 знаков в 10сс).

Цитата sCreator

Не лучше ли разработать

Нет - не лучше! Нужны не примерные результаты, а точные.

Люди, подскажите как воспользоватся регистрами XMM (128бит) из дельфи6 ?

[Delphi] Длинная арифметика

Bug Hunter — Thu, 12 Nov 2009 11:16:01 +0000

Bug Hunter:

Цитата Navi1982 @ 12.11.09, 00:22

Shaggy, а действительно - с какой версии? Я в 6-ой.

Тип uint64 упоминается в 7-й версии как IDL тип, но он не работает: переменную типа uint64 описать можно, но арифметические выражения с ним даже не транслируются. И есть сведения, что в Delphi 2006 тип uint64 еще полноценно не работает. Так что используй мегацифры типа word и не парься.