Привет всем! Допустим, пользователь вводит в программу с клавиатуры пятиричное представление числа, имеющее до 12 знаков перед десятичной точкой и до 4 знаков дробной части. Число всегда положительное. Программа должна уметь складывать и умножать два таких введенных числа, не используя MUL, IMUL и команды процессора плавающей точки. Как можно хранить такое число в памяти? И как можно умножать два таких числа, используя операции сложения и сдвига?
Crash В какой бы системе счисления ни было введено число, его всегда можно преобразовать в другую, для которой тебе будет известно как складывать, умножать и делить. В чем конкретно проблема? Не умеешь преобразовывать строку в число (и обратно для вывода результата)? Не умеешь выполнять арифметические операции над числами? Тебе нужно готовое решение?
Мне нужно каким-то образом хранить числа из 48 бит в памяти. И уметь складывать и умножать их. Преобразовывать из строки в число и обратно я знаю, как.
Crash На четвертом курсе у универе перед тем как давать реализацию криптосистем нам давали задание реализовать сложение, вычитание, умножение, деление и нахождение остатка чисел любой разрядности Я полагаю у тебя что-то похожее Когда я делал свою реализацию я использовал двоичный формат big endian - младший байт самый левый Чтобы было проще можешь вводить числа как строку в шестнадатеричной системе счисления типа: 198756ACD76593B Такое число легко сконвертировать в двоичную форму берешь последовательно символы строки с конца и смотришь если цифра, то отнимаешь 48 если буква, то отнимаешь 55 ;Хотя наверное можно и лучше придумать Результат в Al Берешь втрой байт сконца Делаешь тоже самое результат в ah Сохраняешь получившийся байт в нужном месте в зависимости от выбранной спецификации Big Endian или Little Endian и так пока не дойдешь до начала строки ВСЕ Когда это сделаешь то складывать и вычитать такие числа можно с помощью замечательных команд adc и sbb Умножать числа можно как стобиком команда mul для этого замечательно подходит А вот хорошие алгоримы деления и нахождение остатка довольно сложные тебе лучше поискать статью в инете Такую информацию легко найти если искать, например, реализацию RSA
Crash Значит, имеем числа с фиксированной запятой: 12,4 Такие числа можно легко преобразовать в целые, умножением на 10000. Само умножение делать не надо, просто при конвертировании нужно "забыть" про запятую и добавить нужное кол-во нулей справа, если дробных знаков окажется меньше 4х. Результат прекрасно умещается в 64 бит. Далее можно складывать через add + adc и вычитать sub + sbb. Умножать и делить труднее, как уже заметил Miller Rabin, но тоже можно. Результат нужно будет разделить на 10000, т.е. сдвинуть запятую на 4 знака. Miller Rabin Да, по нику можно догадаться, что Вы увлекаетесь криптографией
Не знаю, поможет ли это кому, но на информатике такие числа мы раскладывали по следующему алгоритму: Допустим, есть большое число Код (Text): 30!= 265252859812191058636308480000000 Можно записать, как Код (Text): 30!=2*(10^4)^8+6525*(10^4)^7+2859 *(10^4)^6+8121 *(10^4)^5+ +9105 *(10^4)^4+8636 *(10^4)^3+3084 *(10^4)^2+8000*(10^4)^1+ +0000 *(10^4)^0 (если брать основу в 1000). В таком виде его можно записать в таблицу Код (Text): A[0] A[1] A[2] A[3] CH 0 0 0 0 1 2 0 0 2 1 26 0 0 6 1 265 0 0 5 1 2652 0 0 2 2 6525 2 0 5 2 5252 26 0 2 2 2528 265 0 8 ………………………………………. Вот и сам код для чтения числа в таблицу и его восстановление из нее Код (Text): Const maxDig=1000; osn=10; Type tlong=array[0..MaxDig] of integer; Var f:text; A,B:tlong; i,k: integer; Procedure Writelong; Var i:integer; l: string; begin Write(f,A[k]); If k>1 then begin While k-1>=1 do begin str(A[k-1],l); Write(f,l); k:=k-1; end; end; end; Procedure Readlong; Var ch:char; i,l,j,zn: integer; begin zn:=0; A[0]:=1; Read(f,ch); val(ch,A[1],j); zn:=1; While (not eof(f)) do begin REad(f,ch); Val(ch,l,j); A[1]:=a[1]*10+l; zn:=zn+1; For i:=1 to a[0] do begin If (i=a[0]) and(A[i]>=osn) then begin a[0]:=a[0]+1; zn:=0; end; If A[i]>=osn then begin A[i+1]:=a[i+1]*10+a[i] div osn; a[i]:=a[i]mod osn; end; end; end; end; begin k:=0; Assign(f,'Task.dat'); Reset(f); Readlong; Close(f); Assign(f,'Result.sol'); Rewrite(f); k:=A[0]; Writelong; Close(f); end. А вот процедура для сложения таких больших чисел Procedure Suma (a,b: tlong; Var c: tlong); Var i: integer; begin If a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0]; For i:=1 to c[0] do begin c[i]:=(a[i]+b[i]+c[i]) mod osn; c[i+1]:=(a[i]+b[i]+c[i]) div 1000; end; If c[c[0+1]]<>0 then c[0]:=c[0]+1; end; По-моему, этот код не корректно работает с нулями. Когда-то эту ошибку исправил, но сейчас лень разбираться
