Re: Assembly Language - Mathematics WITHOUT maths coprocessor

On Sun, 09 Oct 2005 08:13:42 GMT, "Richard Cooper"
<spamandviruses@xxxxxx> wrote:
>On Sun, 09 Oct 2005 02:21:43 -0400, ¬a\/b <al@xxx> wrote:
>> 14.20 Algorithm Multiple-precision division
>> INPUT: positive integers x = (xn, ... x1,x0)b, y = (yt,... y1,y0)b
>> with n >= t >= 1, yt != 0.
>> OUTPUT: the quotient q = (qn-t, ... q1,q0)b and remainder r = (rt,...
>> r1r0)b such that
>> x = qy + r, 0 <= r < y.
>> 1. For j from 0 to (n - t) do: qj 0.
>> 2. While (x  ybn-t) do the following: qn-t qn-t + 1, x x - ybn-t.
>> 3. For i from n down to (t + 1) do the following:
>>
>> 3.1 If xi = yt then set qi-t-1 b - 1; otherwise set qi-t-1 b(xib +
>> xi-1)=yt)c.
>>
>>
>> #######################
>> 3.2 While (q[i-t-1](y_tb +y_t-1) > x_ib^2 +x_i-1b + x_i-2)
>> do: q[i-t-1]= q[i-t-1] -1.
>> #######################
>>
>> 3.3 x = x - q[i-t-1]yb^(i-t-1).
>>
>>
>> #######################
>> 3.4 If x < 0 then set x=x + yb^(i-t-1) and q[i-t-1]= q[i-t-1] - 1.
>> #######################
>> 4. r x.
>> 5. Return(q,r).
>
>And that's why I don't like those cryptography people. They encrypt
>everything they write.

if you want understand
it is in chapter 14 of book "Handbook of Applied Cryptography by A.
Menezes, P. van Oorschot and S. Vanstone" that is possible to find in
internet (it is find if you google it)
i have not implemented that version but i think it could be ok and
fast.
anyway i think i'm not smart enough for speak of divisions
it is 3-4 year that i think on it and last week i found another error
in my implementation ... but it seems: i like find errors more than to
program :)

if i have +-*/ for signed number
and i have defined "<<" and ">>" shift operators for unsigned one

for fixed point numbers i see the thing very easy

fixed point numbers "fnum" has the same data representation of
"snum"==signed numbers that has a digits array
that has the same data representation of "num" unsigned numbers
(change only the name)

if "a" is an fnum than "a.sn" is the signed number in it
a.sn.sn is the unsigned number in it
so i define +-/* for "fixed point numbers"

fnum a, b;

a+b = a.sn+b.sn;
a-b = a.sn-b.sn;
a*b =(a.sn*b.sn).sn>>(32*precision)
a/b =(a.sn.sn<<(2*32*precision))/b.sn;

where precision == 1 means 32 bit of fractional part
precision == 2 means 64 bit of fractional part
etc

for see it in 10 base
12.9/3.4 = 3.7[94]
1290/34 = 37.[94]
12.9*3.4 = 43.8[6]
129 *34 = 4386

Do you see some error?

it should be ok but i don't know how to find the position of "."
in the translation base2^32 --> base10
and base10 --> base2^32
that serve for read-write the fixed point number in input output.
Has someone some idea on how it is possible find that position?
Thanks
.