Операции с большими числами...

Navi1982 · #1 28.01.2008, 15:12

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

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

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

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

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

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

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

Admin · #2 28.01.2008, 15:19

Цитата:

Сообщение от 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 · #3 28.01.2008, 16:12

так быстро ответ пришел

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

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

~ SaM ~ · #4 28.01.2008, 19:26

to Navi1982

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

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

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

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

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

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

Код:

(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 можно представить как

Код:

678=512+128+32+4+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 · #5 06.03.2008, 00:49

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

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

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

Код:

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

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

Код:

type
  TZ = array of byte;

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

Код:

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;

Код:

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 массивов под максимальное количество знаков путём добавления нулей:

Код:

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;

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

Код:

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;

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

Код:

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 · #6 01.12.2008, 22:11

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

zerg · #7 04.02.2009, 18:08

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

lmikle · #8 04.02.2009, 18:48

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

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

hty007 · #9 06.02.2009, 23:15

Код:

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

Опции темы	Поиск в этой теме
Версия для печати Отправить на Email	Поиск в этой теме: Расширенный поиск
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

	Сайт	Форум	FAQ	RSS лента	Прочее
	Новости Исходники Компоненты Статьи Добавить исходник Поиск	Правила Поиск Сообщения за сегодня Пользователи Кто на форуме?	Delphi FAQ - 5000 статей DRKB - 4500 статей (ZIP-архив) Справочник функций и процедур Delphi Delphi Programming Guide Indy in Depth. Глубины Indy	Новости сайта Новости форума	Ссылки и Баннеры Donate О сайте Реклама Контакты