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

[Bug Hunter]

Цитата Navi1982 @ 11.11.09, 09:16

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

1) Неправильно обрабатывается число ноль, причем еще на этапе форматирования: строки '00000', '-0' и 'qwerty' должны форматироваться в '+0', а у тебя что?

2) Забываешь установить знаковый бит в num.flag.

[Bug Hunter]

Цитата Navi1982 @ 11.11.09, 09:16

и хочу еще доделать перевод на 2^32

Я бы не советовал тебе это делать ввиду отсутствия беззнакового 64-х разрядного типа. Ведь далее, при реализации длинного умножения, тебе прийдется перемножать cardinal мегацифры, а результат этой операции в общем случае не влезает корректно в знаковый int64!

Цитата Navi1982 @ 11.11.09, 09:16

В общем смотрите сами и подкиньте пожалуста идею как можно оптимизировать деление?

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

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

И умножение на 10, кстати, можно заменить сдвигами и сложением:

  d : cardinal;
 
  d := ((d shl 2) + d) shl 1; { <=> d := d * 10; )

[Shaggy]

Цитата Bug Hunter @ 11.11.09, 14:47

ввиду отсутствия беззнакового 64-х разрядного типа.

uint64

[Bug Hunter]

Цитата Shaggy @ 11.11.09, 16:56

uint64

Упс... С какой версии это появилось?

[sCreator]

Такое начало длинной целочисленной арифметики пойдет?
Прикреплённый файлLongMath.zip (3.64 Кбайт, скачиваний: 303)

[Navi1982]

BugHunter, спасибо что заметил на счет нолей... Исправил добавлением строчки в конце:

 if length(num)=1 then num:=num+'0';

Что касается флага, то это не проблема... покамись реализованна функция преобразования и не решена проблема перевода 2^32... Кстати, потому и не решился делать сразу так, поскольку незнал как потом делать умножение, хотя где-то читал, что из дельфи6 можно использовать регистры XMM (128bit), но незнаю как?!?!

На счет деления - огромное спасибо за подсказку, завтра займусь переделкой.

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

sCreator, я не могу разобратся без тестов... Во-первых, при открытии пишет что не находит файл ресурсов "...LongMathTest.res" Но, потом пишет что он Recreated непонятно где. А во-вторых при компиляции пишет что не находит файл "FastMM4.dcu"... Не мог бы ты скинуть полный комплект?

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

[sCreator]

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

...
sCreator, я не могу разобратся без тестов... Во-первых, при открытии пишет что не находит файл ресурсов "...LongMathTest.res" Но, потом пишет что он Recreated непонятно где. А во-вторых при компиляции пишет что не находит файл "FastMM4.dcu"... Не мог бы ты скинуть полный комплект?

Когда спросит Recreated - согласитесь и он создастся по вашей версией Delphi ( я использовал 7 ), там где обычно у Вас создается ( по умолчанию в папке с проектом )
В dpr закоментируйте FastMM4 в uses ( это замена стандартному менеджеру памяти, если его закоментить, то подключится стандартный ).

[sCreator]

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

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

Если в array хранить элементы в обратном порядке ( также как в word, например, сперва идет старший байт ), с выравнивание по 64 бита, то тогда через указатели можно получать к такому массиву доступ в каждом случае наиболее эффективный ( хоть UInt64, хоть word ).
Интересный вопрос - выделит ли система на один массив больше 2^31 БАЙТ и выделит ли на всю программу больше 2^32 БАЙТ на 32 битной архитектуре?

Немного о длинной арифметике и целочисленной в частности.

При работе с целыми числами есть такой нюанс:

123456789 div 1000 * 1000 = 123456000
в то время как
123456789 * 1000 div 1000 = 123456789

Вероятно из-за этого и очень большие числа в промежуточных результатах.
Но нужна ли точность в 2^(2^32) знака?

Чтобы сумма 2^(2^30) + 2 оказала влияние на результат необходимо ее повторить около 2^(2^30 - 2^6) раз - т.к. в последствии на такое число будут производиться деления ( ведь результат, как Вы говорили вполне приемлем, то есть укладывается в Int64? ) и младшие цифры будут отброшены.

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

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

TBigNum = record        
    exponenta : Integer;        
    mantisa :array[0..1023] of word; //включает знак с обратным порядком байт и отрицательными числами в дополнительной форме
  end;

Думаю длинная математика с такими числами будет более быстрой и скорее всего даст не худший результат

[sCreator]

Небольшой примерчик:
Входные выходные 3 значные ( остальные промежуточные результаты)
целочисленная арифметика:

567 * 123456789 = 69999999363
 
69999999363 + 987654321 = 70987653684
 
70987653684 * 7777777 = 552126140107380468
 
552126140107380468 + 800000000000000 = 552926140107380468
 
552926140107380468 div 1000000000000000 = 552

( наиболее опасны div )


длинная арифметика ( промежуточные результаты с 6 значной мантисой ):

567 * (123456*10^3) = (699995*10^5)
 
(699995*10^5) + (987654*10^3) = (709871*10^5)
 
(709871*10^5) * (777777*10) = (552121*10^12)
 
(552121*10^12) + (800000*10^9) = (552921*10^12)
 
(552921*10^12) / (100000*10^10) = (552921*10^-3) =~ 553

[Bug Hunter]

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

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

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

[Navi1982]

Цитата sCreator

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

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

Цитата sCreator

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

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

Цитата sCreator

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

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

Цитата sCreator

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

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

Цитата sCreator

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

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

Цитата sCreator

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

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

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

[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 храняться в прямом порядке.
И это значит что при прямом порядке хранения элементов массива к ним через указатели можно обращатся по разному.

[Navi1982]

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

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

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

[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;
        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 $80000000
    else
      result.flag:=cardinal(k+1);
 
    finalize(d);
  end;

Ловкость рук - и никакого мошенства! ©

[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 метра - и полет нормальный.

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