|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Операции с большими числами...
Доброго времени суток!
Когда-то, уже давно (во времена Delphi 3), писал программу "калькулятор" для больших чисел... Реализовать удалось тока сложение, вычитание и умножение для 255 значных десятичных чисел (через String)... Кроме того, делалось это на школьном компе после уроков во время кружка не имея дома своего компа, следовательно - сохранить ничего неудалось... Теперь возникла такая необходимость: написать программу (точнее модуль) которая умела бы сумировать, вычитать, умножать, делить и возводить в степень числа любой (почти бесконечной) разрядности... Например, используя динамический массив (dynamic array). Для упрощения задачи - требуется только целочисленные вычисления, но с запятой тоже не помешает. На самом деле, голова забита реализацией другой программы, в которой возникла необходимость вычислений больших чисел. Времени мало, а еще предстоит решить многое. А потому обращаюсь к программистам, которые это отщелкают как орешки. добавил: Желательно с пояснениями алгоритмов. К тому-же, если выложить исходники тут, то будет прекрасная возможность для других пользоватся такой прелестью. Пожалуста, помогите. Заранее благодарен! Последний раз редактировалось Navi1982, 28.01.2008 в 16:18. |
#2
|
||||
|
||||
Цитата:
- http://www.delphisources.ru/pages/so...alculator.html - http://www.delphisources.ru/pages/so...unct_calc.html |
#3
|
|||
|
|||
так быстро ответ пришел Спасибо... Тока там ничего не понять - мало коментариев... И вытащить чего-то функционального от туда тоже не удается без пояснений. И модулей/классов тоже не хватает, чтобы полноценно оценить проги и сами исходники... У меня делфи 6
первые две ссылки прошли, последняя не открывается... Да и с самого сайта в раздел "исходники" попасть не могу - открывает пустую страницу |
#4
|
|||
|
|||
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 символов (такова была задача), и после реализации задачи таким методом, все работало на ура, но приходилось пользоваться методами против "залипания" клавиш во время работы программы! |
#5
|
|||
|
|||
Вобщем принялся сам реализовывать эти функции...
Для начала принял некоторые правила: 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; Код:
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; помагите реализовать функцию вычитания. Лучше в столбик, чтобы понятней было. А раз столбиком, то я понимаю, что надо отнимать меньшее значение от большего. Допустим, я напишу функцию сравнения... А дальше как? Алгоритм пожалуста. Код уже сам напишу или свой дайте. Заранее благодарен! Последний раз редактировалось Navi1982, 06.03.2008 в 00:52. |
#6
|
|||
|
|||
всем здраствуйте!!
Помогите плиз, очень срочно нужна информация о методах быстрых вычислений чисел большой разрядности. Может можете порекомендовать хотя бы какую литературу искать. |
#7
|
|||
|
|||
Насчет литературы не скажу, а сам составил для себя модуль для поддержки больших чисел реализовано через String (писал сам, это не алгоритмы которые кочуют по форумам). Если очень надо могу скинуть, только зачем тебе это?
|
#8
|
|||
|
|||
А тебе Int64 не хватает?
Еще можно через SSE оперировать аж со 128-расзрядными числами, но придется писать на асемблере, благо, это не сложно. Ну а если тебе нужны ОЧЕНЬ БОЛЬШИЕ числа, то тогда нужно будет искать алгоритмы работы с ними. |
#9
|
|||
|
|||
Код:
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 hty007 |