[Navi1982]

Доброго времени суток!

Когда-то, уже давно (во времена Delphi 3), писал программу "калькулятор" для больших чисел... Реализовать удалось тока сложение, вычитание и умножение для 255 значных десятичных чисел (через String)... Кроме того, делалось это на школьном компе после уроков во время кружка не имея дома своего компа, следовательно - сохранить ничего неудалось...

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

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

На самом деле, голова забита реализацией другой программы, в которой возникла необходимость вычислений больших чисел. Времени мало, а еще предстоит решить многое. А потому обращаюсь к программистам, которые это отщелкают как орешки. добавил: Желательно с пояснениями алгоритмов.

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

Пожалуста, помогите.
Заранее благодарен!

[Admin]

Сообщение от Navi1982

Доброго времени суток!

Когда-то, уже давно (во времена Delphi 3), писал программу "калькулятор" для больших чисел... Реализовать удалось тока сложение, вычитание и умножение для 255 значных десятичных чисел (через String)... Кроме того, делалось это на школьном компе после уроков во время кружка не имея дома своего компа, следовательно - сохранить ничего неудалось...

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

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

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

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

Пожалуста, помогите.
Заранее благодарен!

- http://www.delphisources.ru/pages/so...alculator.html
- http://www.delphisources.ru/pages/so...alculator.html
- http://www.delphisources.ru/pages/so...unct_calc.html

[Navi1982]

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

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

[~ SaM ~]

to Navi1982

Насчет возведения числа в большую степень могу подсказать на мой взгляд вполне отличный метод. Сложность заключается в том, что при вычислениях реальных 512 и/или 1024, и/или N - значных чисел не возможно пользоваться встроенными арифметическими операциями языков программирования!

У меня была недавно лаба, связанная с шифрованием методом RSA. Так вот длина ключа(для шифрования/расшифрования) должна должна вычисляться с помощью квадратов чисел большой разрядности.

На первый взгляд может показаться, что это очень сложно, но это, ИМХО, наиболее быстро, удобно и надежно.

^ - этим знаком я буду обозначать возведение в степень!

В качестве примера: (432^678) mod 987.

Первым делом надо найти степени числа 432:

Код:

1 2 3 4 5 6 7 8 9

(432^2) mod 987 = (432^2) mod 987 = 81 (432^4) mod 987 = (81^2) mod 987 = 639 (432^8) mod  987 = (639^2) mod 987 = 690 (432^16) mod 987 = (690^2) mod 987 = 366 (432^32) mod 987 = (366^2) mod 987 = 711 (432^64) mod 987 = (711^2) mod 987 = 177 (432^128) mod 987 = (177^2) mod 987 = 732 (432^256) mod 987 = (732^2) mod 987 = 870 (432^512) mod 987 = (870^2) mod 987 = 858

Число 678 можно представить как

Код:

1	678=512+128+32+4+2

, то

Код:

1 2	(432^678) mod 987 = (432^512 ∙ 432^128 ∙ 432^32 ∙ 432^4 ∙ 432^2) mod 987 = (81∙639∙711∙732∙858) mod 987 = 204

В лабе по шифрованию RSA я РЕАЛЬНО использовал ключи, длиной не менее 2048 символов (такова была задача), и после реализации задачи таким методом, все работало на ура, но приходилось пользоваться методами против "залипания" клавиш во время работы программы!

[Navi1982]

Вобщем принялся сам реализовывать эти функции...

Для начала принял некоторые правила:
1. Операции делаю над десятичными числами.
2. Храню числа в динамическом массиве (элементы типа byte) - каждая цифра (0..9) занимает один элемент массива и по принцыпу: младший разряд по младшему адресу.
3. Последний элемент всегда хранит значение знака + или -. Реализовал через константы sgPlus, sgMinus.
4. Операции намерен делать столбиком. Проще пока не придумал. Пока есть тока функция ZAdd складывающая два массива без знака. Знак будет учитыватся в функции SZAdd где будет происходить коррекция и вызыватся ZAdd или ZSub.
5. Число получаю с переменной типа String. Реализовал через функции StrToZ и обратную ей ZToStr.

Ниже привожу код с пояснениями:
константы знаков в последнем элементе:

Код:

1 2 3

Const   sgPlus  = 100; //<=> +   sgMinus = 101; //<=> -

для уменьшения писанины и заморочек компилятора:

Код:

1 2	type   TZ = array of byte;

функции конвертирования из текста в число и обратно:

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Function StrToZ(s:string):TZ; {Ссначала проверяет наличие знака. Если отсувствует, значит добавляет "+" по умолчанию. Все остальные знаки считает цифрами. Другие знаки принимает за "0"} var  num:TZ;  i,j,len:Integer; begin  case s[1] of  '-': begin len:=length(s); SetLength(num,len); num[len-1]:=sgMinus; end;  '+': begin len:=length(s); SetLength(num,len); num[len-1]:=sgPlus; end;  else begin len:=length(s)+1; SetLength(num,len); num[len-1]:=sgPlus; end;  end;  i:=2-(len-length(s)); j:=len-2;  while i <= length(s) do  begin    case s[i] of     '0': num[j]:=0;     '1': num[j]:=1;     '2': num[j]:=2;     '3': num[j]:=3;     '4': num[j]:=4;     '5': num[j]:=5;     '6': num[j]:=6;     '7': num[j]:=7;     '8': num[j]:=8;     '9': num[j]:=9;    else     num[j]:=0;    end;    i:=i+1; j:=j-1;  end; StrToZ:=num; end;

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Function ZToStr(num:TZ):String; var  s:String;  j,len:Integer; begin  s:='';  len:=length(num);  j:=len-1;  while j >= 0 do  begin    case num[j] of     0: s:=s+'0';     1: s:=s+'1';     2: s:=s+'2';     3: s:=s+'3';     4: s:=s+'4';     5: s:=s+'5';     6: s:=s+'6';     7: s:=s+'7';     8: s:=s+'8';     9: s:=s+'9';     sgMinus: s:=s+'-';     sgPlus : s:=s+''; //s:=s+'+';    end;    j:=j-1;  end; ZToStr:=s; end;

Для выравнивания 2 массивов под максимальное количество знаков путём добавления нулей:

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Procedure AdjustZ(n1,n2:TZ); Var  sign1,sign2:byte;  i,len1,len2:Integer; begin  len1:=length(n1);  sign1:=n1[len1-1];  len2:=length(n2);  sign2:=n2[len2-1];  if len1<len2 then  begin   SetLength(n1,len2);   n1[len2-1]:=sign1; //return sign back  end;  if len2<len1 then  begin   SetLength(n2,len1);   n2[len1-1]:=sign2; //return sign back  end; end;

Для удаления лишних нулей:

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Function SimplifyZ(num:TZ):TZ; Var  sign:byte;  i,len:Integer; begin  len:=length(num);  sign:=num[len-1];  i:=len-2;  while num[i]=0 do  begin   i:=i-1;  end;  len:=i+2;  SetLength(num,len);  num[len-1]:=sign; SimplifyZ:=num; end;

Функция сложения двух массивов, результат помещаем в третий, т.е. возращается функцией... Знак здесь не учитывается!

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Function ZAdd(n1,n2:TZ):TZ; Var  r:TZ;  t1,t2,t,mem:Shortint;  i,len:integer; begin  AdjustZ(n1,n2);  len:=length(n1);  SetLength(r,len);  i:=0; mem:=0;  while i <= len-2 do  begin   t1:=n1[i]; t2:=n2[i];   t:=t1+t2+mem;   r[i]:=t mod 10;   mem:=t div 10;   i:=i+1;  end;  while mem>0 do  begin   SetLength(r,len+1);   t:=mem;   r[i]:=t mod 10;   mem:=t div 10;   i:=i+1;  end;  r[high(r)]:=sgPlus; ZAdd:=r; end;

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

Заранее благодарен!

[Gera]

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

[zerg]

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

[lmikle]

А тебе Int64 не хватает?
Еще можно через SSE оперировать аж со 128-расзрядными числами, но придется писать на асемблере, благо, это не сложно.

Ну а если тебе нужны ОЧЕНЬ БОЛЬШИЕ числа, то тогда нужно будет искать алгоритмы работы с ними.

[hty007]

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

program LongSum;{$APPTYPE CONSOLE}uses SysUtils; { Программа предназначина дла складывания чисел в пределах  +-10^30000 с учётом знака. } type    TByte = -9..9;    TLongExt = Record       sign: boolean;(*Положительность false - "-" true - "+" *)       (* Mantissa *)       UnitM :Array of TByte; {Целая мантисса}       CountU:Integer;{Кол-во разрядов цел}       FracM :Array of TByte; {Дробная мантисса}       CountF:Integer;{Кол-во разрядов дроб}    end; Var A, B,{Входные данные} C{Выходные данные}:TLongExt; q:integer; (* =-=-=- Процедуры -=-=-= *) procedure ReadEXT(var A:TLongExt);    var       i:integer;       S:String;    begin       Readln(s);A.sign:=(s[1]='+');       delete(s,1,1);i:=1;       While not((s[i]='.')or(s[i]=',')) do inc(i);       Setlength(A.UnitM,i-1);{-2}       A.CountU:=i-1;{-2}       For i:=0 to A.CountU-1 do          A.UnitM[i]:=StrToInt(s[A.CountU-i]);       delete(s,1,A.CountU+1);       A.CountF:=Length(S);       SetLength(A.FracM,A.CountF);       For i:=0 to A.CountF-1 do          A.FracM[i]:=StrToInt(S[i+1]);    end; procedure WriteEXT(var A:TLongExt);    var q:Integer;    begin       if A.sign then Write('+')else Write('-');       for q:=A.CountU-1 downto 0 do          Write(A.UnitM[q]);       Write('.');       for q:=0 to A.CountF-1 do Write(A.FracM[q]);       WriteLN;    end; procedure Align(var A, B:TLongExt);    begin       If A.CountF<>B.CountF then if A.CountF>B.CountF then          begin             B.CountF:=A.CountF;             setlength(B.FracM,B.CountF);          end       else begin             A.CountF:=B.CountF;             setlength(A.FracM,A.CountF);          end;       If A.CountU<>B.CountU then if A.CountU>B.CountU then          begin             B.CountU:=A.CountU;             setlength(B.UnitM,B.CountU);          end       else begin             A.CountU:=B.CountU;             setlength(A.UnitM,A.CountU);          end;    end; {=====  Собственно сумма =====} procedure Summ(var A, B, C:TLongExt);    Var q:integer; // Какая-то рабочая переменная       Oct:TByte;  // Остаток, без него хоть тресни    function RF(const A:TLongExt; Index:Integer):integer;       begin // Выдает разряд Index с нужным знаком       If A.sign then Result:=A.FracM[Index]          else Result:=A.FracM[Index]*(-1);       end;    function RU(const A:TLongExt; Index:Integer):integer;       begin       If A.sign then Result:=A.UnitM[Index]          else Result:=A.UnitM[Index]*(-1);       end;    begin // Начало сумма       C.sign:=true;// По умолчанию пусть будет "+"       Align(A,B);   // Выравнивание       SetLength(C.FracM,A.CountF);       C.CountF:=A.CountF; Oct:=0; // Первичные установки       for q:= C.CountF-1 downto 0 do          begin // Суммирование мантиссы дробной части          Oct:=Oct+RF(A,q)+RF(B,q);          if oct<0 then begin                C.FracM[q]:= (Oct mod 10)*(-1);                C.sign:=False;                end             else C.FracM[q]:= Oct mod 10;          Oct:= Oct div 10;          end;       C.CountU:=A.CountU;       SetLength(C.UnitM,C.CountU);       for q:= 0 to C.CountU-1 do          begin // Суммирование мантиссы целой части          Oct:=Oct+RU(A,q)+RU(B,q);          if oct<0 then             begin //Остаток отрицательный в одном случае когда всё число отрицательно                C.UnitM[q]:= (Oct mod 10)*(-1);                C.sign:=False;             end             else C.UnitM[q]:= Oct mod 10;          Oct:= Oct div 10;          end;    end;// Конец сумма begin AssignFile(Input,'LongSum.in');Reset(Input);    {Считываем данные}    ReadEXT(A);    ReadEXT(B);    CloseFile(Input);//Нас учили уберать за собой    Summ(A,B,C);    AssignFile(Output,'LongSum.out'); Rewrite(Output);    WriteEXT(C);    CloseFile(Output);//Нас учили уберать за собой end.

Если честно то это не очень то и сложно, если умеешь складывать отрицательные числа, то это и есть разность.
Надеюсь организовать произведение сам сможешь. Если нет почитай Меньшикова, он извращался и не так. Я про Олимпиадные задачи.

Ф.Меньшиков-Оллимпиадные задачи по программирыванию

hty007