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

Цитата Navi1982 @ 09.11.09, 13:15

ОК... Спасибо всем!
INS, отдельное спасибо тебе за ссылку на FGInt... Хоть я ее (библиотеку) не заюзал, но пришел к выводу, что будет легче перевести строку-10базы в строку-2базы (как там), а потом порциями по 32 бита закинуть в нужный мне массив... Однако, такой метод не совсем рационален - есть огромное ограничение в длине такого числа, т.е. максимально возможное число будет зависеть от колличества символов вмещаемое в бинарную строку - это 2^32 символов, что даст максимум 134'217'728 байт для массива (т.е. 128 MB). Численно это 2^1'073'741'824 - что уже не плохо! Но все-же хочется достич максимального предела 2^(2^32) или хотябы 2^(2^31)...

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

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

Интересно сколько процессорного времени займет выполнение одной операции умножения двух чисел (2^(2^15) - 1) ( т.е. состоящих из 2^(2^15) двоичных единиц ).
Если не ошибаюсь, то по двоичной математике это приведет к 2^(2^15) операциям сложения плюс учет переполнений ( переходов битов через байты ) и сдвигов.

Уже позабыл методику оценки точности результатов вычислений от промежуточных результатов, но насколько помню точность зависит не от величины промежуточного результата а от его точность.
Может быть все-таки достаточно промежуточные результаты иметь в BCD числах ( с какой-то более-менее реальной точностью, скажем 20 цифр ), хотя все зависит от алгоритма ( формулы ) вычислений.

Цитата Navi1982 @ 09.11.09, 17:47

Нуу, Romkin, самому то хоть не смешно что сказал?! Ладно, для наглядности привожу пример:

n=10
f=(n+100*n!)div(n^5) - это у нас будет функция

вычислим поэтапно:
(1) n! = 3628800 //раз промежуточный
(2) 100*(1) = 362880000 //два промежуточный
(3) n+(2) = 362880010 //и еще раз увеличился
(4) n^5 = 100000 //другой промежуточный
(5) (3)div(4) = 362880010 div 100000 = 3628 //бац! и уменьшился результат в разы!

Упрощений не видно? Совсем?
f = (1 + 100*(n-1)!) div n^4 - на порядок меньше уже
f = 1 div n^4 + 100*(n-1)! div n^4 - еще
f = 0 + int(100 * (9! / 10000))
f = 3628
А если подумать, и привлечь остатки, то можно еще уменьшить промежуточные результаты.

Добавлено 09.11.09, 19:28
f = 1 div n^4 + (n-1)! div (n^4 div 100) - так еще проще.

Romkin, чудной ты какой...
Я тебе для наглядности пример привел... На самом деле формула гораздо сложнее и подразумевает еще сумму всех результирующих значений. Неужели ты думаешь, что формулу оставили в первоначальном виде? Да, для ускорения подсчетов применяются упрощения и это уже реализованно до пределов исходя именно из тех соображений, что промежуточные вычисления очень велики! Но все ровно эти действия не спасают при наличии даже регистров xmm

Добавлено 09.11.09, 22:39
Кстати, недавно вычислил приблизительно максимальное значение в промежуточных вычислениях - это 134886 цыфр в 10-ой системе счисления. Правда я неуверен на сколько точно у меня получились эти вычисления. И так же хочу отметить, что в основной программе такие результаты будут лишь при минимальной сложности данных. Вот так вот

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

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

Кстати, недавно вычислил приблизительно максимальное значение в промежуточных вычислениях - это 134886 цыфр в 10-ой системе счисления

Что значит приблизительно? Может тебе вещественный тип чисел заюзать?

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

Да, для ускорения подсчетов применяются упрощения и это уже реализованно до пределов исходя именно из тех соображений, что промежуточные вычисления очень велики! Но все ровно эти действия не спасают при наличии даже регистров xmm

Но пример ты дал без упрощений. Что странно. И порядок выполнения действий "в лоб" тоже был выбран неоптимальный.
Применяется div? А тогда есть ли вычисление наибольшего общего делителя в алгоритме? Есть ли работа с остатками от деления?
Я бы советовал присмотреться к вычислениям, если бы все делали так, то и шифрование шло бы ооочень долго.
Наконец, можно подумать и о приближенных вычислениях.

Цитата Navi1982 @ 09.11.09, 17:55

Bug Hunter, тогда помоги найти такой алгоритм, например преобразование из n-base системы в m-base систему используя функции 10-base системы

Для этого нужно ни много ни мало реализовать длинную арифметику, причем не через эффективные 2^32 мегацифры, а посимвольно, так что вряд ли тебе это подойдет, да и не надо этого.

Цитата Navi1982 @ 09.11.09, 17:55

А если быть конкретнее, то подкинь пожалуста идею как преобразовать число 10-базы в число 2^32-базы (или 65536-базы, или 256-базы) используя при этом методы 10-базы учитывая возможности Delphi... Очень нужно... хотябы просто последовательностью общих мыслей. Спасибо.

Не надо использовать методы 10-базы! Метод сдвига и коррекции просто делит BCD число на 2, не используя операций деления, ничего страшного в этом нет.

Внутренний цикл этого процесса на Делфи выглядит примерно так:

  for i:=1 to dlen-1 do begin
    if odd(d[i]) then inc(d[i-1], 5); {5 = 8 - 3}
    d[i]:=d[i] shr 1;
    end;

и никаких сусликов!

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

Bug Hunter, спасибо за подсказку, я как раз щас занимаюсь этим модулем - длинной арифметики (копать ее раз так!)... Но все-же, почему ты думаешь что не следует реализовывать длиную арифметику через "эффективные 2^32 мегацифры" ? Например, у меня реализована часть модуля с приминением посимвольной 10-ой сс, но с той разницей, что храню цыфры в динамическом массиве array of byte... Т.е. получается что число занимает столько же сколько и тип String, но операции тикают чуточку быстрее. Однако есть очевидные недостатки такого исполнения: низкая скорость вычислений и высокий объем памяти. Мне почему-то казалось, что исполнение в 2^32 сс будет куда быстрее работать. Или я ошибаюсь? Кстати, какие недостатки в таком варианте исполнения? один я знаю - трудности и время перевода в читаемый вид. Но, в основной программе, числа будут использоватся в размерах кратные байту (в будущем кратные 2 и 4 байтам) и хранится в 2-ом формате. Т.о. я убиваю двух зайцев - это исключение преобразования и компактное хранение полученных данных. Кроме всего прочего, читаемый вид понадобится лишь в процессе дебагинга, что просто не принимается в счет.

Добавлено 10.11.09, 09:33
И еще вопросик... как эффективно обнулить значение последнего левого бита (из 32-х), если нужно использовать значение лишь в первых 31 битах ? Заметка, 32-й бит может иногда принимать значение 1.

Сообщение отредактировано: Navi1982 - 10.11.09, 09:35

в процессе написания этого поста, пост andriano почему-то удалили.
andriano и Romkin, вопрос по оптимизации формул покамись не обсуждается. То что я выше привел в примере совершенно не та формула, которая используется в действительности!!! Но и привести настоящую в пример я не имею права. Поэтому этот вопрос закрыт. А для справки скажу, формула и алгоритм ее расчета и так оптимизированы до предела с учетом часных случаев. Спасибо за участие.

На данный момент вопрос поставлен иначе: требуется реализация модуля длинной арифметики. В этом модуле необходимо реализовать функцию перевода из строки-10сс в массив-2^32cc. Ну и обратно для полноценности модуля.

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

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

Цитата Navi1982 @ 10.11.09, 10:34

в процессе написания этого поста, пост andriano почему-то удалили.
andriano и Romkin, вопрос по оптимизации формул покамись не обсуждается. То что я выше привел в примере совершенно не та формула, которая используется в действительности!!! Но и привести настоящую в пример я не имею права. Поэтому этот вопрос закрыт. А для справки скажу, формула и алгоритм ее расчета и так оптимизированы до предела с учетом часных случаев. Спасибо за участие.

На данный момент вопрос поставлен иначе: требуется реализация модуля длинной арифметики. В этом модуле необходимо реализовать функцию перевода из строки-10сс в массив-2^32cc. Ну и обратно для полноценности модуля.

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

1. Свой пост удалил я сам, т.к. писал его, не просмотрев до конца тему, а когда просмотрел, обнаружил, что ничего нового по сравнению с написанным он уже не содержит.
2. Вопрос оптимизации на самом деле очень важный. На словах ты утверждаешь, что здесь все в полном порядке, а приводимые тобой примеры говорят об обратном.
3. Форматное преобразование как бы пишется на основе реализованных в модуле арифметических операций. И, вообще говоря, является не частью модуля, а лишь надстройкой над ним, которая может быть, а може - не быть. Имея алгоритм форматного преобразования, написать его с использованием модуля, реализующего длинную арифметику, - пара пустяков. Не понимаю, в чем тут проблема.

andriano, с п. 1 и 2 согласен полностью. На счет приводимых примеров я говорил выше. А вот п.3 мне не понятен, извини... Наверное уже в мозгу искрит. Вобщем приведу фрагмент кода реализации функции преобразования:

Кстати переделал немного. Для начала на форму скиньте 3 эдита, 1 лэйбл и 2 кнопки. Кнопки я переименовал в btFormat и btConvert (см. поле Name в свойствах). Да, и форма у меня называется Form3, так что и это можете переименовать, если не хотите копатся в коде.

используемые типы:

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;

...
Немного переменных для тестов:

var
  TestStr:string; // for tests
  TimeSta,TimeFin:TDateTime;

...
Ну и сами функции кидаем после implementation друг за другом:
Эта функция нужна для форматирования строки на выходе +100 или -45. Покамись понимает только целые числа:

{Форматирование числа в строке.
Сначала проверяет знак - если отсувствует, добавляет "+" по умолчанию.
Все остальные знаки считает цифрами, т.е принимает за "0".
Так-же удаляет все незначимые ноли в начале числа.}
Function FormatStr(s:string):String;
var
 num:String;
 i:Integer;
 rem0:boolean; //remove "0" while it's true
begin
 case s[1] of
 '-': begin num:='-'; i:=2; end;
 '+': begin num:='+'; i:=2; end;
 else begin num:='+'; i:=1; end;
 end;
 rem0:=true; //to remove not significant zeroes before number
 while i <= length(s) do
 begin
   case s[i] of
    '0': if rem0=false then num:=num+s[i];//to put or not to put? - that is question! :)
    '1'..'9': begin rem0:=false; num:=num+s[i]; end;
   else
    if rem0=false then num:=num+'0';//put if significant!
   end;
   i:=i+1;
 end;
 if length(num)=1 then num:=num+'0'; //спасибо BugHunter'у что заметил!
FormatStr:=num;
end;

Эта функция преобразует форматированную строку в число в 2^16cc (т.е. элементы массива типа Word); позже переделаю на тип Cardinal. Наконец-то правильно переводит, но много лишьнего в ней, да и не эстетично записана...

{Функция преобразования строки-10сс в массив-2^16сс}
Function FStrToBigNum(src:string):TBigNum;
Var i,j,len,lon,d,m:Cardinal;
    n,base:Int64;
    num:TBigNum;
    s,rs:string;
  //automatisation
    maxbase:Word;
Function TakeMinDividend(s:string; base, index:Int64; Var lon:Cardinal):Int64;
Var i,len:Cardinal;
    n:Int64;
begin
 len:=length(s);
 i:=index; if not(s[1] in ['0'..'9']) then i:=index+1;
 n:=0; lon:=0;
 repeat
  n:=n*10 + (Ord(s[i])-48);
  i:=i+1; lon:=lon+1;
 until (n>=base)or(i>len);
Result:=n;
end;
begin
//do automatisations
 base:=High(maxbase)+1; //get base in function of array type in TBigNum
num.flag:=0;
rs:=src;
repeat
 s:=rs; len:=length(s);
 n:=TakeMinDividend(s,base,1,lon);
 rs:='';
 i:=1; if not(s[1] in ['0'..'9']) then i:=2;
 i:=i+lon;
while (i<=len) do
begin;
 d:=n div base;
 rs:=rs+IntToStr(d); //store result here
 m:=n mod base;
 if m>0 then begin
  n:=m*10 + (Ord(s[i])-48);
  i:=i+1;
 end else
 begin
  n:=TakeMinDividend(s,base,i-1,lon);
  for j:=1 to lon-1 do rs:=rs+'0';
  i:=i+lon;
 end;
end;
  d:=n div base;
  rs:=rs+IntToStr(d); //store result here
  m:=n mod base;
 num.flag:=num.flag+1;
 SetLength(num.int,num.flag);
 num.int[num.flag-1]:=m;
until TakeMinDividend(rs,base,1,lon)<base;
n:=StrToInt64(rs);
if n>0 then begin
 num.flag:=num.flag+1;
 SetLength(num.int,num.flag);
 num.int[num.flag-1]:=n;
end;
Result:=num;
num.int:=nil;
end;

честно говоря, уже самому трудно разобратся что я в ней написал (100 раз переделывал). Но в кратце: функция TakeMinDividend набирает минимальное делимое из текущего делимого. Дальше обычное деление в столбик: делимое делим на базу, а остаток пишем в массив; затем полученный результат снова делим на базу и записываем остаток и так до тех пор пока результат не станет меньше базы. Последний результат тоже в массив.
...
и два обработчика кнопок... тут время обработки считается и выносится в лэйбл:

procedure TForm3.btConvertClick(Sender: TObject);
Var i:Cardinal;
    num:TBigNum;
    t,TestStr:String;
begin
TestStr:=FormatStr(form3.Edit1.Text);
form3.Edit2.Text:=IntToStr(length(TestStr)-1);
num:=FStrToBigNum(TestStr);
t:='';
for i:=num.flag-1 downto 0 do
begin
 t:=t+IntToHex(num.int[i],4);
end;
form3.Edit3.Text:=t;
end;
 
procedure TForm3.btFormatClick(Sender: TObject);
Var TestStr:String;
begin
TestStr:=FormatStr(form3.Edit1.Text);
form3.Edit2.Text:=IntToStr(length(TestStr)-1);
form3.Edit3.Text:=TestStr;
end;

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

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

Navi1982, начинать решение задачи нужно со словесной формулировки условия.
Для того, чтобы заменить неправильную конструкцию (я так понимаю "n>base") на правильную, нужно знать, что именно является правильным.
Кстати, правильно сформулированный вопрос - половина ответа. Поэтому с вероятностью около 50% после того как ты сформулируешь условие словами, ты САМ найдешь правильное решение.

andriano, я полностью с тобой согласен... щас выходил на улицу и немного проветрился... но, согласись и с тем, что перелопатив груду страиц в интернете для поиска способов реализации функции преобразования из строки-10сс в массив-2^32сс уже голова перестанет соображать если ей не сделать перерыв... А на все про все у меня еще пара дней - я на больничном отпуске и решил занятся программированием в свободное от работы время. А если учесть и то, что прошлый отпуск был аж в январе, соответственно данной проблемой занимался имено тогда, то мне приходилось день разбирать ранние наработки. Хотя, 4 дня болел в августе, но тогда только просматривал свой труд чтобы не забыть вовсе.

Что касается последнего кода, то решил делать преобразование числа-строки методом деления на базу - в коде база =65536 (2 байта), но потом переделать надо на 2^32. Т.е. грубо говоря делаю деление столбиком.

Сначала из s набираю в ss количество цыферок покамись получившиеся число не станет >=base.
Потом делю ss div base чтобы получть целое, т.е. первую цыфру результата. Затем нужно посмотреть если остаток < base но и если есть возможность занять следуищее число из s. И так покамись неостанется цыфр в числе s.

Затем получившийся остаток записываю в массив num.int[0]:=остаток. И начинаю результат снова делить на базу. И так покамись результат не станет меньше базы.

Никак не могу решить эту задачу... поможите люди добрые!

Сообщение отредактировано: Navi1982 - 10.11.09, 15:28

Цитата Navi1982 @ 10.11.09, 09:04

Но все-же, почему ты думаешь что не следует реализовывать длиную арифметику через "эффективные 2^32 мегацифры" ?

Вообще-то, я говорил о том, что не следует реализовывать длинную арифметику через 10-based технологию. И где ты увидел в моем сообщении ковычки - про эффективные 2^32 я не шутил, я считаю, что это правильный подход.

Цитата Navi1982 @ 10.11.09, 09:04

И еще вопросик... как эффективно обнулить значение последнего левого бита (из 32-х), если нужно использовать значение лишь в первых 31 битах ? Заметка, 32-й бит может иногда принимать значение 1.

  cardval := cadrval and $7FFFFFFF;

Bug Hunter, примного благодарен! Что касается кавычек, то я тебя цитировал, но видать не так понял твою мысль, за что глубоко сорриусь. Хотя если перечитаешь свой пост, то поймешь в чем дело

Как на счет алгоритма деления в столбик на дельфи?

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

Ура!!! Наконец-таки сделал рабочую функцию преобразования см. пост выше, я его изменил.

Но там как-то коряво все получилось, и хочу еще доделать перевод на 2^32. Вобщем смотрите сами и подкиньте пожалуста идею как можно оптимизировать деление? Потому-что мне кажется что там явно не аккуратно я написал (но я и не профи).