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

Люди, кто знает как работает алгоритм функции StrToInt ?

Мне необходимо ее модифицировать так, чтобы она могла переваривать более длинные числа. Поможите разобратся, плииз.

Мне нужно перевести число записанное строкой -> в массив, как если бы это был один регистр, но не 32 бит, а стока скока будет иметь массив.

Например, 1234567890 должно быть записанно в итоге как 49 96 02 D2... А теперь представьте что нужно перевести число 12345678901234567890123456789012345678901234567890 в такую же форму как и предыдущее.

Прошу прощения, что изменил название темы. Но это название ей больше подходит!
Старое название "Какой алгоритм у функции StrToInt ?, Надо его модифицировать для более длинных чисел..."

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

Ну так он открыт в Delphi

procedure ConvertErrorFmt(ResString: PResStringRec; const Args: array of const); local;
begin
  raise EConvertError.CreateResFmt(ResString, Args);
end;
 
function StrToInt(const S: string): Integer;
var
  E: Integer;
begin
  Val(S, Result, E);
  if E <> 0 then ConvertErrorFmt(@SInvalidInteger, [S]);
end;

Вот вариант StrToInt на асме (автор leo)

function MyStrToInt(S:pChar):cardinal;register;
//eax = S
asm
  xor edx,edx
  xor ecx,ecx
@@loop:
  lea ecx,[ecx+ecx*4] //ecx:=ecx*5
  lea ecx,[edx+ecx*2] //ecx:=ecx*2+edx
  mov dl,[eax]
  inc eax
  sub dl,'0'
  jnc @@loop
  mov eax,ecx
end;

Цитата Navi1982 @ 24.10.09, 20:33

более длинные числа

int64 или числа, записанные строкой ?

Тип TBCD рулит для более длинных чисел...

В принцыпе я немного вопрос неправильно поставил... так-что наверное стоит переименовать тему...

Для BCD чисел у меня свои алгоритмы имеются... Мне нужно перевести число записанное строкой -> в массив, как если бы это был один регистр, но не 32 бит, а стока скока будет иметь массив.

Например, 1234567890 должно быть записанно в итоге как 49 96 02 D2... А теперь представьте что нужно перевести число 12345678901234567890123456789012345678901234567890 в такую же форму как и предыдущее.

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

ООФ
Navi1982 ждешь нового дефолта когда цены станут с множеством нулей и перестанут влазить в инт?

дело конечно не мое но все же интересно, зачем?

Frees, пишу программку для проверки одной теории... сразу отмечу - это не связанно с вычислениями числа ПИ или других констант... Но программка пригодилась бы и для этих целей.

Если любопытно узнать подробности, то милости прошу в скайп navi1982

а как ты храниш свои длинные числа? динамичесский массив или просто область в памяти?

видел эту демку
...Borland\BDS\4.0\Demos\DelphiWin32\VCLWin32\ComplexNumbers\Win32OperatorOverload.dpr

Поищи библиотеку FGInt, она решает эту и многие другие задачи

Цитата Lumen @ 24.10.09, 23:04

Вот вариант StrToInt на асме (автор leo)

function MyStrToInt(S:pChar):cardinal;register;
//eax = S
asm
  xor edx,edx
  xor ecx,ecx
@@loop:
  lea ecx,[ecx+ecx*4] //ecx:=ecx*5
  lea ecx,[edx+ecx*2] //ecx:=ecx*2+edx
  mov dl,[eax]
  inc eax
  sub dl,'0'
  jnc @@loop
  mov eax,ecx
end;

на отрицательных числах не заработает.

function S2Int2(S: PChar): Integer;
asm
        xchg     edx, eax
        xor      eax, eax
        test     edx, edx
        jz       @@exit
        xor      ecx, ecx
        mov      cl, [edx]
        inc      edx
        cmp      cl, '-'
        pushfd
        je       @@0
@@1:    cmp      cl, '+'
        jne      @@2
@@0:    mov      cl, [edx]
        inc      edx
@@2:    SUB      cl, '0'
        cmp      cl, '9'-'0'
        ja       @@fin
        lea      eax, [eax+eax*4] //
        lea      eax, [ecx+eax*2] //
        jmp      @@0
@@fin:  popfd
        jne      @@exit
        neg      eax
@@exit:
end;

Frees, я собираюсь хранить конвертированное число в динамическом массиве array of cardinal; ... Хотя принцыпиальной разницы перевода не вижу в этом, ведь динамический массив можно расширять как только это понадобится. Но даже если приведешь пояснения для статического массива, то буду очень признателен! И кстати, что за демка? Откуда можно посмотреть?

Ins, я первый раз слышу о библиотеке FGInt... где искать то ?

Antonn, извини, но я не очень понял ассемблеровский код - расшифровать можешь? Т.е. на словах объясни что там делается?

спасибо

Цитата Navi1982 @ 03.11.09, 22:30

Ins, я первый раз слышу о библиотеке FGInt... где искать то ?

В гугле, вестимо

Navi1982 я прокоментировал лишь тот код, мой просто преобразует строку в integer

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

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

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

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

Это что считаешь-то?

Цитата Romkin @ 09.11.09, 13:20

Это что считаешь-то?

Не иначе как расстояния между скоплениями галактик в попугаях

Цитата Romkin @ 09.11.09, 13:20

Это что считаешь-то?

Это не так важно, но в общих чертах - это нечто вроде отпечатков некоторых структур которые комбинируются между собой... А для упрощения расчетов пришли к способу который расчитывается легко по формуле, но промежуточные значения очень велики, следовательно нужно написать модуль который умеет работать с длинной арифметикой... Т.е. нужны следующие функции: +, -, *, /, ^ ну и перевод из строки в численный-массив и обратно... Последнее нужно для проверок. Первые 3 операции над числами реализовать не трудно, а вот в реализации остальных есть необходимость в помощи. Т.е. для меня не сложно все это сделать и самому, но ищу более оптимальные решения.

Navi1982

Цитата

Следовательно буду ждать других идей и предложений.

Почему бы не использовать уже готовые решения в мат.пакетах типа Maple, Mathematica? Есть уверенность в том, что по скорости вычислений наверняка не сможешь обойти тамошние алгоритмы хранения и оперирования над хранимыми данными и т.д.

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

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

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

NetVir, ух ты! А можно ссылочку? И хотябы в двух словах объяснить какие функции мне оттуда нужны? Но, в любом случае спасибо.

Romkin, а что подозрительного тебе тут кажется? Обыкновенная математика и ничего более, разве что числа громадные.

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

Цитата Navi1982 @ 24.10.09, 20:33

Люди, кто знает как работает алгоритм функции StrToInt?

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

Bug Hunter, ты меня послал в google и я вернулся с другой задачей... Нарыл там такой сайт gmplib.org
вобщем я так понял, что там есть все необходимые мне функции... Единственное что я не понял, так это как эту либу прикрутить в дельфи?

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

Romkin, а что подозрительного тебе тут кажется? Обыкновенная математика и ничего более, разве что числа громадные.

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

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

Bug Hunter, ты меня послал в google и я вернулся с другой задачей... Нарыл там такой сайт gmplib.org
вобщем я так понял, что там есть все необходимые мне функции... Единственное что я не понял, так это как эту либу прикрутить в дельфи?

Я имел в виду найти описание алгоритма и реализовать его самостоятельно - там делов то...

Нуу, 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 //бац! и уменьшился результат в разы!

Подозрения еще остались?! Помоги если есть мысли, а раз мыслей нет, то пиши когда будут, ок?

Int64: -2^63...2^63-1 ?????

Даже integer хватает для твоего примера.

Сообщение отредактировано: osmiy74 - 09.11.09, 17:56

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

Система исчисления

Navi1982

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

NetVir, ух ты! А можно ссылочку? И хотябы в двух словах объяснить какие функции мне оттуда нужны? Но, в любом случае спасибо.

Все гуглится
http://www.wolfram.com/products/mathematica/index.html
http://ru.wikipedia.org/wiki/Mathematica
http://www.maplesoft.com/
http://ru.wikipedia.org/wiki/Maple

Добавлено 09.11.09, 18:13
Добавлю, что и в первом и во втором пакетах есть исключительная и полностью исчерпывающая справочная система. Все твои задачи, думаю, можно будет переписать в пару тройку строк кода. Хотя...

Цитата 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. Вобщем смотрите сами и подкиньте пожалуста идею как можно оптимизировать деление? Потому-что мне кажется что там явно не аккуратно я написал (но я и не профи).

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

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

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

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

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

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

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

uint64

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

uint64

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

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

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

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

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

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

Еще несколько вопросов-предложений:
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;

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

Небольшой примерчик:
Входные выходные 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

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

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

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

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

Цитата

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

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

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

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

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

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

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;

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

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

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

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

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

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

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

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

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

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

Сообщение отредактировано: sCreator - 15.11.09, 05:47

Прикреплённый файлLongMath.zip (7.29 Кбайт, скачиваний: 232)

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

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

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

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

Однако!

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

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

Вообще-то основная моя идея была в том, что бы сперва разработать операции длинной арифметики и на их основе уже преобразовывать строку в длинное число.
А старые знания асма немного попользовал для убыстрения (хотя врядли он оптимальный ) . Работа с 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 $80000000
  else
    result.flag := cardinal(i);
end;

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

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

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

Сообщение отредактировано: imgavario - 25.11.09, 02:48

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

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

Прикреплённый файлMax_Intermediate_Value.zip (59.47 Кбайт, скачиваний: 220)

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

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

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

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

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

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

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

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 $80000000
  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 $80000000
  else
    result.flag := cardinal(sDw);
end;

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

Сообщение отредактировано: sCreator - 25.11.09, 20:30

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

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

Сообщение отредактировано: leo - 25.11.09, 11:15

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

Цитата sCreator

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

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

Цитата sCreator

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цитата BugHunter

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

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

Цитата sCreator

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

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

Цитата

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

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

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

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

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

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

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

result.flag:=len;

А в начале

len:=length(op1.data);

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

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

Цитата BugHunter

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

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

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

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

Цитата sCreator

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

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

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

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

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

{Функция сложения}
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

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

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

При сложении

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

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

num.data = nil

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

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

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

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

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

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

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

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

Цитата

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

Как вариант можно пользоватся операциями сдвига (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;

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

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

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

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

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

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

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

len:=num.flag and MaxInt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цитата sCreator

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{Процедура коррекции числа:
 убирает незначемые нулевые элементы с конца .data}
Procedure HICorrection(op:THugeInt);
Var i,sg:integer;
Begin
 if op.flag<0 then sg:=-1 else sg:=1;
 i:=length(op.data)-1;
 while (i>0)and(op.data[i]=0) do Dec(i); //пока не первый и равен нулю
 SetLength(op.data,i+1);
 op.flag:=length(op.data)*sg;
End;

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

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

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

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

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

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

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

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

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

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

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

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

Можно еще сэкономить на 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

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

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

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

Да, я согласен с тем что моя функция не претендует на идеал, но если я не ошибаюсь, то делал замечание на то, что сначала пробовал именно как подсказал 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 ?

первое.

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

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

Navi1982

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

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

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

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

Вот! Зацените...

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;
  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;
  end;
result:=r;
End;

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

{Функция сложения по модулю}
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;
  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;
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;
end;

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

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

Сообщение отредактировано: leo - 13.01.10, 09:04

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

Цитата

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

и где?

{функция сравнения с учетом знака}
{возвращает: 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 !

где же оно

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

Сообщение отредактировано: sCreator - 14.01.10, 16:32

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

Сообщение отредактировано: Navi1982 - 14.01.10, 21:05

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

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

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

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

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

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

Ну, вот... Дождался ответа 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;
  end;

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

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

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

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

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

в этом есть несколько приимуществ:

• избавляемся от заморочек со знаками заменяя на другие заморочки, а ля инвертирование числа при отрицательных знаках (наверное можно реализовать "на лету" в цыкле вычисления);
• за-то, вычетание делается сложением, без предварительной проверки на Больше или Меньше, но тогда еще придется добавить алгоритм, который бы расширял разрядную сетку в случаях переполнения;
• знак не придется хранить отдельным полем.

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

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

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: кусок кода выдрал из макроса, так что не ручаюсь за его полную работоспособность.

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

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

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

{Функция умножения по модулю}
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, то ждать приходится оооущень долга.

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

Ну, вот и написал деление... Правда по модулю. Так-же я знаю, сдесь есть несколько уязвимых мест и даже есть где оптимизировать, чтоб быстрей считало... Но пока на работе мучают - не могу сконцентрироватся как следует. То же самое и с умножением... Для быстрого умножения щас кучу методов придумали - самым быстрым на сегодня считается "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:=$100000000; //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;

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

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

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

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

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

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

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

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