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

[Bug Hunter]

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

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

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

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

[leo]

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

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

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

[sCreator]

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

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

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

[Navi1982]

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

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

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

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

[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

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

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

[sCreator]

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

[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 бит) - но к сожалению ничего не вышло. Видать, с меня ассемблеровиц тоже не важный а пример брал из книжки.

Вобщем, вот сама функция. Использовал тип 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 столичный пригород) - с пешими прогулками и лазаньем по столбам, да и заморочками клиентов - сильно выматывает... а работы - непочатый край, а вознаграждение - рабское... ууу... это уже оффтоп... пора спать!

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

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

Сообщение отредактировано: Bug Hunter - 19.12.09, 21:58

[sCreator]

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

  TBigNum = record
    znak: boolean;
    data: array of longword;
  end;

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

TimeSta:=Time;
res:=HIAdd(num1,num2);
TimeFin:=Time;

[Navi1982]

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

Цитата BugHunter

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

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

Цитата sCreator

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

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

Цитата

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

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

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

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

[sCreator]

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

TBigNum = record
    znak: boolean;
    data: array of longword;
  end;

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

result.flag:=len;

А в начале

len:=length(op1.data);

[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 число значимых бит в числе. Или число значимых бит в последнем неполном двойном слове. Да мало ли еще чего можно придумать - резерв не помешает. Тем более, что ты своим булёном ничего не экономишь - размер струкруры все равно по умолчанию выводится на величину, кратную восьми, и я не вижу причин от этого отказываться - разьве что в сторону увеличения.

[Bug Hunter]

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

Цитата BugHunter

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

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

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

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

Цитата sCreator

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

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

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

[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 байт - это даже в хелпе написанно (где-то встречал).

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

Сообщение отредактировано: Navi1982 - 23.12.09, 19:46

[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;
  end;
  //учтем значение последнего переноса
  if t>$FFFFFFFF then begin
    lenmax:=lenmax+1;
    SetLength(result.data,lenmax);
    result.data[lenmax-1]:=cr[1];
  end;
  result.flag:=lenmax; //длина результата
end;

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