Программирование на Pascal. Функция MOD и TRUNC для типа данных extended

Hello Максим,

Sunday, February 27, 2005, 4:01:34 PM, you wrote:

А что значит, "очень больших"? Можно примерчик привести? Просто, я
как-то раз писал функцию сложения многоразрядных целых чисел (подойдет для
любого количества разрядов), где сами операнды (числа) имели строковое
представление. То есть, складывал, к примеру, не 123 с 456, а '123' c
'456'. Правда, не очень быстро оно считалось. Думаю, здесь тоже можно
что-то в этом роде сделать.

А криптосистема основана на каких криптоалгоритмах?

-----Original MessageFrom: Максим [mailto:labingr***@h*****.ru]
Sent: Sunday, February 27, 2005 4:02 PM
To: comp.soft.prog.prog (3778558)
extended

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



--
С уважением,
Максим mailto:labingr***@h*****.ru


Номер выпуска : 4069
Возраст листа : 526 (дней)
Количество подписчиков : 529
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/323932
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Номер выпуска : 4071
Возраст листа : 526 (дней)
Количество подписчиков : 529
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/324162
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Здравствуйте,
Моя криптосистема основана на алгоритме RSA. Возникла острая
необходимость в функции получения остатка от деления двух больших
чисел типа extended длиной не менее 64 бит. Встроенный mod не помогает
так как не расчитан на такой тип данных. Я пытался написать свою
функцию следующим образом: делил одно число на другое (здесь все
проходило гладко), затем с помощью функции trunc я брал целую часть
частного и умножал ее на делитель, после чего я вычитал это выражение
от делимого и получал остаток от деления. Все было хорошо пока
делитель не стал превышать предел real-a, функция переставала
работать. Моя криптосистема наполовину готова. Я реализовал генератор
случайных чисел, генератор ключей с помощью расширенного алгоритма
Евклида. Осталось сделать генератор простых чисел (алгоритм у меня
есть) и непосредственно функцию RSA, но все стало из-за остатка от
деления. Остальные детали программы к алгоритму шифрования отношения
не имеют, я думаю с ними будет проще. Помогите пожалуйста.

Hello Максим,

Monday, February 28, 2005, 7:52:36 PM, you wrote:

Штука в том, что mod "не расчитан" на тип extended - он же не
целочисленный. Тут даже говорить об остатке неверно чисто
математически. Но думаю, делу можно помочь, земенив деление сложением
и вычитанием. Рассмотрим такой алгоритм. Пусть есть делимое A и
делитель B. Возьмем число С, присвоим ему стартовое значение B и будем
увеличивать С на число B до тех пор, пока очередная порция С+B не
превзойдет А. Тогда А-С даст нужный остаток.

..................
var
a,b,c :Extended;
begin
.......................
c := b;
while c+b <= a do
c := c + b;

..............
Result := a - c; // "воображаемый" результат
end;

Здравствуйте, Вадим.

Вы писали 2 марта 2005 г., 18:52:16:

Большое спасибо за помощь, Вадим. У вас, да и у других, кто читал мои
письма наверное сложилось неверное
впечатление обо мне из-за небольшой моей неточности: я не собирался
применять функцию mod для нахождения остатка от деления нецелых чисел. Мне
необходимо оперировать с целыми аргументами, которые по длине
превышают все типы данных, и к extended они относятся лишь потому, что
входят в диапазон его допутимых значений, но они целые. Как я говорил
раньше, я проектирую криптосистему на основе RSA, а как известно,
криптостойкость RSA зависит от длины модуля и длины ключей, то есть
чем больше модуль, тем лучше будет криптосистема. И в дальнейшем, у меня
появится необходимиость оперировать с чилами, превышающими по длине
все типы данных в Паскале. Мне подсказали, что для этого необходимо
представлять эти числа в программе с помощью массивов. Не могли бы вы
подробнее рассказать об этом. Заранее спасибо.

Hello Максим,

Wednesday, March 2, 2005, 7:58:38 PM, you wrote:

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

Я же возвращаюсь к своему первому по этой теме письму - нельзя ли
хранить все эти числа в виде строк, например:
'13762890937893478956903896'
+
'6789478324798686'
Во-первых, это дает практически неограниченную "велечину" числа, а
во-вторых, к строкам можно применить алгоритм, описанный выше, немного
его доработав. Платой за это может быть лишь потери скорости
обработки.

Если Вам это не покажется бредом, могу привести полный алгоритм.
Пишите.

Может уже существующие big integers подойдут?

http://www.nl.freepascal.org/lists/fpc-announce/2001-August/000108.html
http://www.delphiforfun.org/Programs/Delphi_Techniques/big_integers.htm

Действительно. А теорию и примеры на C++ можно посмотреть здесь:
http://algolist.manual.ru/maths/longnum.php
Вообще, сайт хорош... Здесь же можно почитать статьи по криптографии,
тот же RSA. Кроме того, есть алгоритмы быстрого возведения в
степень, генерации больших простых чисел...

Еще можно посмотреть реализацию арифметики в исходниках c
www.pgp.com или www.gnupg.org, хотя там много на ассемблере.

бит.

Похоже под типом extended Вы понимаете именно тип Delphi,
а не нечто абстрактное; так не годится.
Тип extended это 80-битное вещественное, на мантиссу в нем
отведено 64 бита, так что при всем желании в него нельзя
загнать целое большей длины без потери точности
Так что у Вас только один вариант - массивы. Можно, конечно
и строки, но слишком большая и неоправданная потеря
производительности, а вычислений много.

Ну зачем же так категорично :)
В наборе команд 80x87 есть FPREM и FPREM1 для вычисления
"частичного остатка" вещественных чисел. Хотя насколько
это математическое понятие, не знаю...

Номер выпуска : 4105
Возраст листа : 529 (дней)
Количество подписчиков : 525
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/326449
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Как переместить четные числа в начало, а нечетные в конец не изменяя порядка

следования чисел с одинаковой четностью.
есть
12 7 9 6 -5 -6
4 6 -7 23 -24 9

надо
12 6 -6 7 9 -5
4 6 -24 -7 23 9

uses crt;
const n=9;
type mas=array[1..6] of integer;
var
f:file of mas;
i,x,min,max,num_of_max:integer;
a:mas;
begin
clrscr;
randomize;
assign(f,'000.000');
rewrite(f);
for i:=1 to n do
begin
for x:=1 to n do
begin
a[x]:=random(99);
write(a[x]:3);
end;
writeln;
write(f,a);
writeln;
end;
close(f);

Номер выпуска : 4112
Возраст листа : 530 (дней)
Количество подписчиков : 523
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/327405
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Hello Gift,

Friday, March 4, 2005, 4:59:01 PM, you wrote:

Короче говоря, массив нужно просматривать с конца (справо налево). Если текущий
элемент четен, то,
1. Запомнить его значение.
2. Все элементы слева от него сдвинуть вправо на один элемент.
3. Запомненное значение записать в первый элемент.

Здравствуйте, Вадим.

Вы писали 2 марта 2005 г., 22:24:35:

Криптография штука очень тяжелая, так что я тоже мало что понимаю в
ней. Да мне много и не надо, я стараюсь как можно тщательнее изучить
алгоритм шифрования RSA, который считается одним из самых надежных, во
всяком случае пока. И его основной "конек" работа с большими числами,
а точнее однонаправленные функции (one-way functions), обрабатывающие
эти числа. Обратные этим функциям очень сложны в выполнении. Например
оновной проблемой по взлому RSA является факторизация (разложение на
простые множители) модуля, длина которого при нормальной реализации
тысячи бит. Конечно же во время выполнения алгоритма для
криптостойкости необходимо оперировать с очень большими числами. Самый
простой пример-это вычисление модуля, который является произведением
двух простых чисел длиной не менее 512 бит. Впрочем, вопрос не в
криптографии. Если у вас будет возиожность и желание, то советую
почитать книгу Б. Шнайера "Основы криптографии", очень интересная
штука. Мне товарищ Grishka передал исходники для работы с длинными
числами, за что ему честь и хвала. Помогите пожалуйста с размещением
чисел в массивах и с операциями над ними.

Hello Максим,

Friday, March 4, 2005, 1:40:37 PM, you wrote:

Ну, во-первых, лично я ровным счетом ничего не знаю о том, что
находится в исходниках товарища Grishka. Во-вторых, мне бы конкретный
пример, поскольку все вышесказанное мне ни о чем не говорит.
В-третьих, для обсуждения этого вопроса с моим участием у нас осталось
времени до 16.00 5-го марта - уезжаю в длительную командировку.

Мне одно все-таки непонятно. Каким образом хранятся стартовые для
расчета данные? В качестве моей догадки:
Имеется числа, которые все-таки "впихиваются" в тип extended (иначе,
как бы это все работало - то, что у Вас уже работает?!). Потом над этими
операндами проводятся какие-то действия, результат которых, в
общем-то, уже не вмещается в этот тип. И Вам нужно продолжать
вычисления уже над такими "большими" числами? И еще одна мысль - если
мы имеем тип extended (то есть, например 1.23*10Е+12, если не ошибаюсь
в самом типе extended), то почему бы
такие числа не "разложить" по двум переменным - 1.23 и 12. Во-первых,
это на порядки облегчило бы арифметику задачи. Во-вторых, такое
представление облегчит вам жизнь, если доведется таки "разбрасывать"
число по массиву. Причем показатель степени при Е можно будет
вычислить еще ДО самого вычисления результата, а само вычисление будет
производиться над ЦЕЛЫМИ числами. Например, для деления 1.23Е+1251 на
3.758Е+364 результат будет выглядеть
(1.23/3.758)Е+(1251-364) = 1.23Е+887 / 3.758 = 123000(0000)Е+880 / 3758
- уже можно говорить о целочисленной арифметике.

Здравствуйте, Вадим.

Очень жаль, что Вы уезжаете в длительную командировку так как из Ваших
писем я смог извлечь много полезного. Гражданин Grishka прислал мне
исходники для работы с очень большими числами, а точнее функции и
процедуры для арифметичиских операций и некоторые функции вроде mod,
trunc etc.
Ниже ловите сорцы:
{==========================================================================}
unit LongMath;
{Автор Vit}

interface

Type TProgress = procedure(Done:real);

{Собственно экспортные функции}
Function ulFact(First:String):string;
Function ulSum(First, Second :string):string;
Function ulSub(First, Second :string):string;
Function ulMPL(First, Second :string):string;
Function ulPower(First, Second :string):string;
function UlDiv(First, Second:String; Precision:integer):String; {Precision
- не истинная точность а количество знаков учитываемых после запятой сверх тех
которые значимы. Все знаки уже существующие в делимом и делителе в любом случае
учитываются}

{Call back function for long operations}
var OnProgress: TProgress;

implementation

Uses SysUtils;

type TMathArray=array of integer;

Type TNumber=record
int, frac:TMathArray;
sign:boolean;
end;

var n1, n2:TNumber;

Procedure Str2Number(s:string; var n:TNumber);
var i, j, l:integer;
begin
if s='' then
begin
setlength(n.int , 0);
setlength(n.frac , 0);
exit;
end;
l:=length(s);
if s[1]='-' then
begin
s:=copy(s,2,l);
l:=l-1;
n.sign:=false;
end
else
n.sign:=true;
j:=pos('.', s);
if j>0 then
begin
setlength(n.int , j-1);
for i:=1 to j-1 do n.int[i-1]:=strtoint(s[j-i]);
setlength(n.frac , l-j);
for i:=1 to l-j do n.frac[i-1]:=strtoint(s[l-i+1]);
end
else
begin
setlength(n.int,l);
for i:=1 to l do n.int[i-1]:=strtoint(s[l-i+1]);
setlength(n.frac,0);
end;
end;

Function Num2Array(Var n:TNumber; var a:TMathArray):integer;
var i:integer;
begin
result:=length(n.frac);
setlength(a,length(n.int)+result);
for i:=0 to length(a)-1 do if i<result then a[i]:=n.frac[i] else a[i]:=n.int[i-result];

end;

Procedure MultiplyArray(var a1, a2, a:TMathArray);
var i, j:integer;
b:boolean;
begin
{checking for zero, 1}
for i:=length(a2)-1 downto 0 do
begin
for j:=length(a1)-1 downto 0 do
begin
a[j+i]:=a[j+i]+(a2[i]*a1[j]);
end;
end;
repeat
b:=true;
for i:=0 to length(a)-1 do
if a[i]>9 then
begin
b:=false;
try
a[i+1]:=a[i+1]+1;
except
setlength(a, length(a)+1);
a[i+1]:=a[i+1]+1;
end;
a[i]:=a[i]-10;
end;
until b;
end;

Procedure Array2Num(Var n:TNumber; var a:TMathArray; frac:integer; sign:boolean);

var i:integer;
begin
setlength(n.frac,frac);
setlength(n.int,length(a)-frac);
for i:=0 to length(a)-1 do
begin
if i<frac then n.frac[i]:=a[i] else n.int[i-frac]:=a[i];
end;
n.sign:=sign;
end;

Function Number2Str(var n:TNumber):string;
var i:integer;
s:string;
begin
result:='';
for i:=0 to high(n.int) do result:=inttostr(n.int[i])+result;
if length(n.frac)<>0 then
begin
for i:=0 to high(n.frac) do s:=inttostr(n.frac[i])+s;
result:=result+'.'+s;
end;
while (length(result)>1) and (result[1]='0') do delete(result,1,1);
if pos('.', result)>0 then while (length(result)>1) and (result[length(result)]='0')
do delete(result,length(result),1);
if not n.sign then result:='-'+result;
setlength(n.int,0);
setlength(n.frac,0);
end;

Procedure DisposeNumber(var n:TNumber);
begin
setlength(n.int,0);
setlength(n.frac,0);
end;

Function ulFact(First:String):string;
var n1, n2:TNumber;
i:integer;
a, a1, a2:TMathArray;
max:integer;
begin
Str2Number('1', n1);
Str2Number('1', n2);
Num2Array(n1, a1);
Num2Array(n2, a2);
max:=strtoint(First);
for i:=1 to strtoint(First) do
begin
if Assigned(OnProgress) then OnProgress((i/max)*100);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a1,0);
setlength(a2,0);
a1:=a;
Str2Number(inttostr(i), n2);
Num2Array(n2, a2);
end;
Array2Num(n1, a1, 0, true);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Function ulPower(First, Second :string):string;
var i, j, c:integer;
a, a1, a2:TMathArray;
var n1:TNumber;
max:integer;
begin
j:=strtoint(Second);
if j=0 then
begin
result:='1';
exit;
end
else
if j=1 then
begin
result:=First;
exit;
end;

max:=j-1;
Str2Number(First, n1);
c:=Num2Array(n1, a1);
setlength(a,0);
setlength(a2,0);
a2:=a1;
for i:=1 to j-1 do
begin
if Assigned(OnProgress) then OnProgress((i/max)*100);
setlength(a,0);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a2,0);
a2:=a;
end;
setlength(a1,0);
setlength(a2,0);
c:=c*j;
if n1.sign then
Array2Num(n1, a, c, true)
else
if odd(j) then Array2Num(n1, a, c, false) else Array2Num(n1, a, c, true);

setlength(a,0);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Procedure MultiplyNumbers(var n1, n2 :TNumber);
var i:integer;
a, a1, a2:TMathArray;
begin
i:=Num2Array(n1, a1)+Num2Array(n2, a2);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a1,0);
setlength(a2,0);
Array2Num(n1, a, i, n1.sign=n2.sign);
DisposeNumber(n2);
setlength(a,0);
end;

Function ulMPL(First, Second :string):string;
var n1, n2:TNumber;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
MultiplyNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Procedure AlignNumbers(var n1, n2:TNumber);
var i1, i2, i:integer;
begin
i1:=length(n1.int);
i2:=length(n2.int);
if i1>i2 then setlength(n2.int, i1);
if i2>i1 then setlength(n1.int, i2);

i1:=length(n1.frac);
i2:=length(n2.frac);

if i1>i2 then
begin
setlength(n2.frac, i1);
for i:=i1-1 downto 0 do
begin
if i-(i1-i2)>0 then n2.frac[i]:=n2.frac[i-(i1-i2)] else n2.frac[i]:=0;

end;
end;
if i2>i1 then
begin
setlength(n1.frac, i2);
for i:=i2-1 downto 0 do
begin
if i-(i2-i1)>0 then n1.frac[i]:=n1.frac[i-(i2-i1)] else n1.frac[i]:=0;

end;
end;
end;

Function SubInteger(a1,a2:TMathArray):integer;
var i:integer;
b:boolean;
begin
result:=0;
if length(a1)=0 then exit;
for i:=0 to length(a1)-1 do a1[i]:=a1[i]-a2[i];
repeat
b:=true;
for i:=0 to length(a1)-1 do
if a1[i]<0 then
begin
b:=false;
if i=length(a1)-1 then
begin
result:=-1;
a1[i]:=a1[i]+10;
b:=true;
end
else
begin
a1[i+1]:=a1[i+1]-1;
a1[i]:=a1[i]+10;
end;
end;
until b;
end;

Procedure AssignNumber(out n1:TNumber; const n2:TNumber);
var i:integer;
begin
Setlength(n1.int, length(n2.int));
for i:=0 to length(n2.int)-1 do n1.int[i]:=n2.int[i];
Setlength(n1.frac, length(n2.frac));
for i:=0 to length(n2.frac)-1 do n1.frac[i]:=n2.frac[i];
n1.sign:=n2.sign;
end;

Procedure SubNumber(var n1, n2 : TNumber);
var i:integer;
n:TNumber;
begin
AlignNumbers(n1, n2);
i:=subInteger(n1.frac, n2.frac);
n1.int[0]:=n1.int[0]+i;
DisposeNumber(n);
AssignNumber(n, n1);
i:=subInteger(n1.int, n2.int);
if i<0 then
begin
subInteger(n2.int, n.int);
AssignNumber(n1, n2);
end
else
begin
DisposeNumber(n2);
end;
end;

Function SumInteger(a1,a2:TMathArray):integer;
var i:integer;
b:boolean;
begin
result:=0;
if length(a1)=0 then exit;
for i:=0 to length(a1)-1 do a1[i]:=a1[i]+a2[i];
repeat
b:=true;
for i:=0 to length(a1)-1 do
if a1[i]>9 then
begin
b:=false;
if i=length(a1)-1 then
begin
result:=1;
a1[i]:=a1[i]-10;
b:=true;
end
else
begin
a1[i+1]:=a1[i+1]+1;
a1[i]:=a1[i]-10;
end;
end;
until b;
end;

Procedure SumNumber(var n1, n2:TNumber);
var i:integer;
begin
AlignNumbers(n1, n2);
i:=sumInteger(n1.frac, n2.frac);
n1.int[0]:=n1.int[0]+i;
i:=sumInteger(n1.int, n2.int);
if i>0 then
begin
setlength(n1.int, length(n1.int)+1);
n1.int[length(n1.int)-1]:=i;
end;
DisposeNumber(n2);
end;

Procedure SumNumbers(var n1, n2:TNumber);
begin
if n1.sign and n2.sign then
begin
SumNumber(n1, n2);
n1.sign:=true;
end
else
if (not n1.sign) and (not n2.sign) then
begin
SumNumber(n1, n2);
n1.sign:=False;
end
else
if (not n1.sign) and n2.sign then
begin
SubNumber(n2, n1);
AssignNumber(n1, n2);
end
else
begin
SubNumber(n1, n2);
end;
end;

Function ulSum(First, Second :string):string;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
SumNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Function ulSub(First, Second :string):string;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
n2.sign:=not n2.sign;
SumNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

function DupChr(const X:Char;Count:Integer):AnsiString;
begin
if Count>0 then begin
SetLength(Result,Count);
if Length(Result)=Count then FillChar(Result[1],Count,X);
end;
end;

function StrCmp(X,Y:AnsiString):Integer;
var
I,J:Integer;
begin
I:=Length(X);
J:=Length(Y);
if I=0 then begin
Result:=J;
Exit;
end;
if J=0 then begin
Result:=I;
Exit;
end;
if X[1]=#45 then begin
if Y[1]=#45 then begin
X:=Copy(X,2,I);
Y:=Copy(Y,2,J);
end else begin
Result:=-1;
Exit;
end;
end else if Y[1]=#45 then begin
Result:=1;
Exit;
end;
Result:=I-J;
if Result=0 then Result:=CompareStr(X,Y);
end;

function StrDiv(X,Y:AnsiString):AnsiString;
var
I,J:Integer;
S,V:Boolean;
T1,T2:AnsiString;
R:string;
max:integer;

begin
Result:=#48;
R:=#48;
I:=Length(X);
J:=Length(Y);
S:=False;
V:=False;
if I=0 then Exit;
if (J=0) OR (Y[1]=#48) then begin
Result:='';
R:='';
Exit;
end;
if X[1]=#45 then begin
Dec(I);
V:=True;
X:=Copy(X,2,I);
if Y[1]=#45 then begin
Dec(J);
Y:=Copy(Y,2,J)
end else S:=True;
end else if Y[1]=#45 then begin
Dec(J);
Y:=Copy(Y,2,J);
S:=True;
end;
Dec(I,J);
if I<0 then begin
R:=X;
Exit;
end;
T2:=DupChr(#48,I);
T1:=Y+T2;
T2:=#49+T2;
max:= Length(T1);
while Length(T1)>=J do begin
while StrCmp(X,T1)>=0 do begin
X:=UlSub(X,T1);
Result:=UlSum(Result,T2);
end;
SetLength(T1,Length(T1)-1);
SetLength(T2,Length(T2)-1);
if Assigned(OnProgress) then OnProgress(100-(Length(T1)/max)*100);
end;
R:=X;
if S then if Result[1]<>#48 then Result:=#45+Result;
if V then if R[1]<>#48 then R:=#45+R;
end;

Function Mul10(First:string; Second:integer):string;
var s:string;
i, j:integer;
begin
if pos('.',First)=0 then
begin
s:='';
For i:=0 to Second-1 do s:=s+'0';
Result:=First+s;
end
else
begin
s:='';
j:=length(First)-pos('.',First);
if (second-j)>0 then For i:=0 to Second-j-1 do s:=s+'0';
First:=First+s;
j:=pos('.',First);
First:=StringReplace(First,'.','',[]);
insert('.',First,j+second);
while (length(First)>0) and (First[length(First)]='0') do delete(First,length(First),1);

while (length(First)>0) and (First[length(First)]='.') do delete(First,length(First),1);

Result:=First;
end;
end;

Function Div10(First:string; Second:integer):string;
var s:string;
i:integer;
begin
s:='';
For i:=0 to Second do s:=s+'0';
s:=s+First;
Insert('.', s, length(s)-Second+1);
while (length(s)>0) and (s[1]='0') do delete(s,1,1);
if pos('.',s)>0 then
while (length(s)>0) and (s[length(s)]='0') do delete(s,length(s),1);
if (length(s)>0) and (s[length(s)]='.') then delete(s,length(s),1);
Result:=s;
end;

function UlDiv(First, Second:String; Precision:integer):String;
begin
First:=Mul10(First, Precision);
result:=Div10(StrDiv(First, Second), Precision);
end;

end.

{==========================================================================}

Желаю удачно съездить.

Привет Максим,

Нужно:
C:=A mod B;

Попробуй так:
C:=A - Int(A/B);

Кстати в книге написано про Trunc
"Если полученный результат лежит вне пределов, определенных для типа
Int64, то функция Trunc вырабатывает исключение EInvalidOp"

Афоризм напоследок: По статистике на одного злого гения приходится около 100000
добрых бездарностей.
Winamp глаголит: М.Круг - Чифирнуть бы ништяк
28 февраля 2005 г. 20:55:22

Просто студент
Eugene mailto:rav***@o*****.ru

Номер выпуска : 4072
Возраст листа : 526 (дней)
Количество подписчиков : 529
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/324383
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Привет!!!

Может это поможет...

{==========================================================================}
unit LongMath;
{Автор Vit}

interface

Type TProgress = procedure(Done:real);

{Собственно экспортные функции}
Function ulFact(First:String):string;
Function ulSum(First, Second :string):string;
Function ulSub(First, Second :string):string;
Function ulMPL(First, Second :string):string;
Function ulPower(First, Second :string):string;
function UlDiv(First, Second:String; Precision:integer):String; {Precision
- не истинная точность а количество знаков учитываемых после запятой сверх тех
которые значимы. Все знаки уже существующие в делимом и делителе в любом случае
учитываются}

{Call back function for long operations}
var OnProgress: TProgress;

implementation

Uses SysUtils;

type TMathArray=array of integer;

Type TNumber=record
int, frac:TMathArray;
sign:boolean;
end;

var n1, n2:TNumber;

Procedure Str2Number(s:string; var n:TNumber);
var i, j, l:integer;
begin
if s='' then
begin
setlength(n.int , 0);
setlength(n.frac , 0);
exit;
end;
l:=length(s);
if s[1]='-' then
begin
s:=copy(s,2,l);
l:=l-1;
n.sign:=false;
end
else
n.sign:=true;
j:=pos('.', s);
if j>0 then
begin
setlength(n.int , j-1);
for i:=1 to j-1 do n.int[i-1]:=strtoint(s[j-i]);
setlength(n.frac , l-j);
for i:=1 to l-j do n.frac[i-1]:=strtoint(s[l-i+1]);
end
else
begin
setlength(n.int,l);
for i:=1 to l do n.int[i-1]:=strtoint(s[l-i+1]);
setlength(n.frac,0);
end;
end;

Function Num2Array(Var n:TNumber; var a:TMathArray):integer;
var i:integer;
begin
result:=length(n.frac);
setlength(a,length(n.int)+result);
for i:=0 to length(a)-1 do if i<result then a[i]:=n.frac[i] else a[i]:=n.int[i-result];

end;

Procedure MultiplyArray(var a1, a2, a:TMathArray);
var i, j:integer;
b:boolean;
begin
{checking for zero, 1}
for i:=length(a2)-1 downto 0 do
begin
for j:=length(a1)-1 downto 0 do
begin
a[j+i]:=a[j+i]+(a2[i]*a1[j]);
end;
end;
repeat
b:=true;
for i:=0 to length(a)-1 do
if a[i]>9 then
begin
b:=false;
try
a[i+1]:=a[i+1]+1;
except
setlength(a, length(a)+1);
a[i+1]:=a[i+1]+1;
end;
a[i]:=a[i]-10;
end;
until b;
end;

Procedure Array2Num(Var n:TNumber; var a:TMathArray; frac:integer; sign:boolean);

var i:integer;
begin
setlength(n.frac,frac);
setlength(n.int,length(a)-frac);
for i:=0 to length(a)-1 do
begin
if i<frac then n.frac[i]:=a[i] else n.int[i-frac]:=a[i];
end;
n.sign:=sign;
end;

Function Number2Str(var n:TNumber):string;
var i:integer;
s:string;
begin
result:='';
for i:=0 to high(n.int) do result:=inttostr(n.int[i])+result;
if length(n.frac)<>0 then
begin
for i:=0 to high(n.frac) do s:=inttostr(n.frac[i])+s;
result:=result+'.'+s;
end;
while (length(result)>1) and (result[1]='0') do delete(result,1,1);
if pos('.', result)>0 then while (length(result)>1) and (result[length(result)]='0')
do delete(result,length(result),1);
if not n.sign then result:='-'+result;
setlength(n.int,0);
setlength(n.frac,0);
end;

Procedure DisposeNumber(var n:TNumber);
begin
setlength(n.int,0);
setlength(n.frac,0);
end;

Function ulFact(First:String):string;
var n1, n2:TNumber;
i:integer;
a, a1, a2:TMathArray;
max:integer;
begin
Str2Number('1', n1);
Str2Number('1', n2);
Num2Array(n1, a1);
Num2Array(n2, a2);
max:=strtoint(First);
for i:=1 to strtoint(First) do
begin
if Assigned(OnProgress) then OnProgress((i/max)*100);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a1,0);
setlength(a2,0);
a1:=a;
Str2Number(inttostr(i), n2);
Num2Array(n2, a2);
end;
Array2Num(n1, a1, 0, true);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Function ulPower(First, Second :string):string;
var i, j, c:integer;
a, a1, a2:TMathArray;
var n1:TNumber;
max:integer;
begin
j:=strtoint(Second);
if j=0 then
begin
result:='1';
exit;
end
else
if j=1 then
begin
result:=First;
exit;
end;

max:=j-1;
Str2Number(First, n1);
c:=Num2Array(n1, a1);
setlength(a,0);
setlength(a2,0);
a2:=a1;
for i:=1 to j-1 do
begin
if Assigned(OnProgress) then OnProgress((i/max)*100);
setlength(a,0);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a2,0);
a2:=a;
end;
setlength(a1,0);
setlength(a2,0);
c:=c*j;
if n1.sign then
Array2Num(n1, a, c, true)
else
if odd(j) then Array2Num(n1, a, c, false) else Array2Num(n1, a, c, true);

setlength(a,0);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Procedure MultiplyNumbers(var n1, n2 :TNumber);
var i:integer;
a, a1, a2:TMathArray;
begin
i:=Num2Array(n1, a1)+Num2Array(n2, a2);
setlength(a,length(a1)+length(a2)+1);
MultiplyArray(a1, a2, a);
setlength(a1,0);
setlength(a2,0);
Array2Num(n1, a, i, n1.sign=n2.sign);
DisposeNumber(n2);
setlength(a,0);
end;

Function ulMPL(First, Second :string):string;
var n1, n2:TNumber;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
MultiplyNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Procedure AlignNumbers(var n1, n2:TNumber);
var i1, i2, i:integer;
begin
i1:=length(n1.int);
i2:=length(n2.int);
if i1>i2 then setlength(n2.int, i1);
if i2>i1 then setlength(n1.int, i2);

i1:=length(n1.frac);
i2:=length(n2.frac);

if i1>i2 then
begin
setlength(n2.frac, i1);
for i:=i1-1 downto 0 do
begin
if i-(i1-i2)>0 then n2.frac[i]:=n2.frac[i-(i1-i2)] else n2.frac[i]:=0;

end;
end;
if i2>i1 then
begin
setlength(n1.frac, i2);
for i:=i2-1 downto 0 do
begin
if i-(i2-i1)>0 then n1.frac[i]:=n1.frac[i-(i2-i1)] else n1.frac[i]:=0;

end;
end;
end;

Function SubInteger(a1,a2:TMathArray):integer;
var i:integer;
b:boolean;
begin
result:=0;
if length(a1)=0 then exit;
for i:=0 to length(a1)-1 do a1[i]:=a1[i]-a2[i];
repeat
b:=true;
for i:=0 to length(a1)-1 do
if a1[i]<0 then
begin
b:=false;
if i=length(a1)-1 then
begin
result:=-1;
a1[i]:=a1[i]+10;
b:=true;
end
else
begin
a1[i+1]:=a1[i+1]-1;
a1[i]:=a1[i]+10;
end;
end;
until b;
end;

Procedure AssignNumber(out n1:TNumber; const n2:TNumber);
var i:integer;
begin
Setlength(n1.int, length(n2.int));
for i:=0 to length(n2.int)-1 do n1.int[i]:=n2.int[i];
Setlength(n1.frac, length(n2.frac));
for i:=0 to length(n2.frac)-1 do n1.frac[i]:=n2.frac[i];
n1.sign:=n2.sign;
end;

Procedure SubNumber(var n1, n2 : TNumber);
var i:integer;
n:TNumber;
begin
AlignNumbers(n1, n2);
i:=subInteger(n1.frac, n2.frac);
n1.int[0]:=n1.int[0]+i;
DisposeNumber(n);
AssignNumber(n, n1);
i:=subInteger(n1.int, n2.int);
if i<0 then
begin
subInteger(n2.int, n.int);
AssignNumber(n1, n2);
end
else
begin
DisposeNumber(n2);
end;
end;

Function SumInteger(a1,a2:TMathArray):integer;
var i:integer;
b:boolean;
begin
result:=0;
if length(a1)=0 then exit;
for i:=0 to length(a1)-1 do a1[i]:=a1[i]+a2[i];
repeat
b:=true;
for i:=0 to length(a1)-1 do
if a1[i]>9 then
begin
b:=false;
if i=length(a1)-1 then
begin
result:=1;
a1[i]:=a1[i]-10;
b:=true;
end
else
begin
a1[i+1]:=a1[i+1]+1;
a1[i]:=a1[i]-10;
end;
end;
until b;
end;

Procedure SumNumber(var n1, n2:TNumber);
var i:integer;
begin
AlignNumbers(n1, n2);
i:=sumInteger(n1.frac, n2.frac);
n1.int[0]:=n1.int[0]+i;
i:=sumInteger(n1.int, n2.int);
if i>0 then
begin
setlength(n1.int, length(n1.int)+1);
n1.int[length(n1.int)-1]:=i;
end;
DisposeNumber(n2);
end;

Procedure SumNumbers(var n1, n2:TNumber);
begin
if n1.sign and n2.sign then
begin
SumNumber(n1, n2);
n1.sign:=true;
end
else
if (not n1.sign) and (not n2.sign) then
begin
SumNumber(n1, n2);
n1.sign:=False;
end
else
if (not n1.sign) and n2.sign then
begin
SubNumber(n2, n1);
AssignNumber(n1, n2);
end
else
begin
SubNumber(n1, n2);
end;
end;

Function ulSum(First, Second :string):string;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
SumNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

Function ulSub(First, Second :string):string;
begin
Str2Number(First, n1);
Str2Number(Second, n2);
n2.sign:=not n2.sign;
SumNumbers(n1, n2);
result:=Number2Str(n1);
DisposeNumber(n1);
end;

function DupChr(const X:Char;Count:Integer):AnsiString;
begin
if Count>0 then begin
SetLength(Result,Count);
if Length(Result)=Count then FillChar(Result[1],Count,X);
end;
end;

function StrCmp(X,Y:AnsiString):Integer;
var
I,J:Integer;
begin
I:=Length(X);
J:=Length(Y);
if I=0 then begin
Result:=J;
Exit;
end;
if J=0 then begin
Result:=I;
Exit;
end;
if X[1]=#45 then begin
if Y[1]=#45 then begin
X:=Copy(X,2,I);
Y:=Copy(Y,2,J);
end else begin
Result:=-1;
Exit;
end;
end else if Y[1]=#45 then begin
Result:=1;
Exit;
end;
Result:=I-J;
if Result=0 then Result:=CompareStr(X,Y);
end;

function StrDiv(X,Y:AnsiString):AnsiString;
var
I,J:Integer;
S,V:Boolean;
T1,T2:AnsiString;
R:string;
max:integer;

begin
Result:=#48;
R:=#48;
I:=Length(X);
J:=Length(Y);
S:=False;
V:=False;
if I=0 then Exit;
if (J=0) OR (Y[1]=#48) then begin
Result:='';
R:='';
Exit;
end;
if X[1]=#45 then begin
Dec(I);
V:=True;
X:=Copy(X,2,I);
if Y[1]=#45 then begin
Dec(J);
Y:=Copy(Y,2,J)
end else S:=True;
end else if Y[1]=#45 then begin
Dec(J);
Y:=Copy(Y,2,J);
S:=True;
end;
Dec(I,J);
if I<0 then begin
R:=X;
Exit;
end;
T2:=DupChr(#48,I);
T1:=Y+T2;
T2:=#49+T2;
max:= Length(T1);
while Length(T1)>=J do begin
while StrCmp(X,T1)>=0 do begin
X:=UlSub(X,T1);
Result:=UlSum(Result,T2);
end;
SetLength(T1,Length(T1)-1);
SetLength(T2,Length(T2)-1);
if Assigned(OnProgress) then OnProgress(100-(Length(T1)/max)*100);
end;
R:=X;
if S then if Result[1]<>#48 then Result:=#45+Result;
if V then if R[1]<>#48 then R:=#45+R;
end;

Function Mul10(First:string; Second:integer):string;
var s:string;
i, j:integer;
begin
if pos('.',First)=0 then
begin
s:='';
For i:=0 to Second-1 do s:=s+'0';
Result:=First+s;
end
else
begin
s:='';
j:=length(First)-pos('.',First);
if (second-j)>0 then For i:=0 to Second-j-1 do s:=s+'0';
First:=First+s;
j:=pos('.',First);
First:=StringReplace(First,'.','',[]);
insert('.',First,j+second);
while (length(First)>0) and (First[length(First)]='0') do delete(First,length(First),1);

while (length(First)>0) and (First[length(First)]='.') do delete(First,length(First),1);

Result:=First;
end;
end;

Function Div10(First:string; Second:integer):string;
var s:string;
i:integer;
begin
s:='';
For i:=0 to Second do s:=s+'0';
s:=s+First;
Insert('.', s, length(s)-Second+1);
while (length(s)>0) and (s[1]='0') do delete(s,1,1);
if pos('.',s)>0 then
while (length(s)>0) and (s[length(s)]='0') do delete(s,length(s),1);
if (length(s)>0) and (s[length(s)]='.') then delete(s,length(s),1);
Result:=s;
end;

function UlDiv(First, Second:String; Precision:integer):String;
begin
First:=Mul10(First, Precision);
result:=Div10(StrDiv(First, Second), Precision);
end;

end.

{==========================================================================}

Здравствуйте, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

Остаток от деления не вычисляется для чисел с плавающей точкой. Это
операция над четырьмя целыми числами: делимое (64 бита), делитель (32
бита), частное (32 бита) и остаток (32 бита).
Неужели стандартные функции DIV и MOD недостаточны?
Если так, то надо делать составные целые.
Вспомните, как делится число в столбик.
Сделайте массив целых и делите его на массив целых, где большие по
индексу элементы - старшие разряды.

ВрЕМеЧк0 д0бРеНьк0е, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

год - два назад в универе решали задачи по "длинной арифметике" -
выполнение простейших операций (+,-,*,>,<), в т.ч. нахождение целой
части и остатка от деления. Если надо могу послать, исходники...
числа представляются массивом.

например, считает: 30!=265252859812191058636308480000000 может
кто-нить проверит правильно или нет.

Здравствуйте,
ОГРОМНОЕ спасибо за советы. У меня просьба к Samurai: если не трудно
вышлите мне пожалуйста исходники с функциями для работы с большими
числами (для "длинной арифметики"), особенно trunc и mod. Буду очень
признателен. Мой адрес:labingr***@h*****.ru. Расскажите пожалуста
подробнее о представлении чисел массивами. Заранее очень благодарен.
Спасибо за советы Andrey Yakushev. Я прекрасно знаю, что остаток от
деления не вычисляется для чисел с плавающей точкой, впрочем, я и не
собирался этого делать. Если вам известна схема RSA, то вполне ясно,
что встроенные mod или div не решат проблемы.

Если результат trunc'a не влазит в longint, то появляется ошибка.

Для работы с большими числами побробуй тип comp, но скорее всего он не
подойдет для криптования.

вероятно тебе нужно описать собственный типработы с т.н.
"длинной арифметикой".

Номер выпуска : 4079
Возраст листа : 528 (дней)
Количество подписчиков : 529
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/325369
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Здравствуйте, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

Остаток от деления не вычисляется для чисел с плавающей точкой. Это
операция над четырьмя целыми числами: делимое (64 бита), делитель (32
бита), частное (32 бита) и остаток (32 бита).
Неужели стандартные функции DIV и MOD недостаточны?
Если так, то надо делать составные целые.
Вспомните, как делится число в столбик.
Сделайте массив целых и делите его на массив целых, где большие по
индексу элементы - старшие разряды.

ВрЕМеЧк0 д0бРеНьк0е, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

год - два назад в универе решали задачи по "длинной арифметике" -
выполнение простейших операций (+,-,*,>,<), в т.ч. нахождение целой
части и остатка от деления. Если надо могу послать исходники...
числа представляются массивом.

например, считает: 30!=265252859812191058636308480000000 может
кто-нить проверит правильно или нет.

ВрЕМеЧк0 д0бРеНьк0е, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

год - два назад в универе решали задачи по "длинной арифметике" -
выполнение простейших операций (+,-,*,>,<), в т.ч. нахождение целой
части и остатка от деления. Если надо могу послать, исходники...
числа представляются массивом.

например, считает: 30!=265252859812191058636308480000000 может
кто-нить проверит правильно или нет.

ВрЕМеЧк0 д0бРеНьк0е, Максим.

Вы писали 27 февраля 2005 г., 17:01:34:

это был калькулятор для длинных чисел, если что не понятно
обращайся...