Prev: Computer nostalgia song
Next: If you don't immediately see your CLAX post...
From: Branimir Maksimovic on 12 Apr 2010 16:03

Starting point is:
http://www.x86asm.net/articles/working-with-big-numbers-using-x86-instructions/

So case when one of numbers fits in register is trivial.
Multiplications (karatzuba variant)
y1 = x1*2^32 + n1
y2 = x2*2^32 + n2

y1*y2 = (x1*2^32 + n1) * (x2*2^32+n2)
= x1*2^32*x2*2^32 + x1*n2*2^32 + x2*n1*2^32 + n1*n2

= x1*x2 * 2^32 * 2^32 + (x1*n2+x2*n1)*2^32 + n1*n2

x1*n2 (trivial) x2*n1 (trivial) n1*n2 (trivial)

So this is easy. x1, x2 are big n1,n2 < 2^32
recurse until x1 or x2 <2^32
exponentiation is easy as it is shifting.

Problem is how to do integer division.
I have found newton-rafson method of interpolation,
so you can aproximate division of x1/x2 to x1*1/x2
but that requires floating / fixed point math.
Do someone knows method for fast big integer division
which does not requires floating / fixed point math?
Obvioux method is just to count how many times
x2 fits x1 but that's n^2 and is slow
for really big ints.

Thanks

--
http://maxa.homedns.org/

Sometimes online sometimes not




From: Nathan Baker on 12 Apr 2010 16:16
"Branimir Maksimovic" <bmaxa(a)nospicedham.hotmail.com> wrote in message
news:20100412220303.02038de7(a)maxa...
>
> Starting point is:
> http://www.x86asm.net/articles/working-with-big-numbers-using-x86-instructions/
>
> So case when one of numbers fits in register is trivial.
> Multiplications (karatzuba variant)
> y1 = x1*2^32 + n1
> y2 = x2*2^32 + n2
>
> y1*y2 = (x1*2^32 + n1) * (x2*2^32+n2)
> = x1*2^32*x2*2^32 + x1*n2*2^32 + x2*n1*2^32 + n1*n2
>
> = x1*x2 * 2^32 * 2^32 + (x1*n2+x2*n1)*2^32 + n1*n2
>
> x1*n2 (trivial) x2*n1 (trivial) n1*n2 (trivial)
>
> So this is easy. x1, x2 are big n1,n2 < 2^32
> recurse until x1 or x2 <2^32
> exponentiation is easy as it is shifting.
>
> Problem is how to do integer division.
> I have found newton-rafson method of interpolation,
> so you can aproximate division of x1/x2 to x1*1/x2
> but that requires floating / fixed point math.
> Do someone knows method for fast big integer division
> which does not requires floating / fixed point math?
> Obvioux method is just to count how many times
> x2 fits x1 but that's n^2 and is slow
> for really big ints.
>
> Thanks
>

In "The Art of Assembly Language Programming," Randall devoted an entire
chapter to Multiprecision Arithmetic:

http://homepage.mac.com/randyhyde/webster.cs.ucr.edu/www.artofasm.com/Windows/HTML/AdvancedArithmetic.html#998265

Nathan.


From: H. Peter Anvin on 12 Apr 2010 22:15
On 04/12/2010 01:03 PM, Branimir Maksimovic wrote:
> Do someone knows method for fast big integer division
> which does not requires floating / fixed point math?

Fixed-point is just integer arithmetic with the binary point in a
different place.

-hpa
From: Robert Redelmeier on 12 Apr 2010 23:26
In alt.lang.asm Branimir Maksimovic <bmaxa(a)nospicedham.hotmail.com> wrote in part:
> Problem is how to do integer division.

Of course it is. The difficulty of factoring large number
is the basis of public key crypto.

> I have found newton-rafson method of interpolation, so you can
> aproximate division of x1/x2 to x1*1/x2 but that requires floating
> / fixed point math. Do someone knows method for fast big integer
> division which does not requires floating / fixed point math?
> Obvioux method is just to count how many times x2 fits x1 but
> that's n^2 and is slow for really big ints.

There is always the method of long division -- shift, compare
& subtract. About n^1.7

-- Robert

From: vic on 13 Apr 2010 00:04
Branimir Maksimovic wrote:
> Starting point is:
> http://www.x86asm.net/articles/working-with-big-numbers-using-x86-instructions/

> Problem is how to do integer division.
> I have found newton-rafson method of interpolation,
> so you can aproximate division of x1/x2 to x1*1/x2
> but that requires floating / fixed point math.
> Do someone knows method for fast big integer division
> which does not requires floating / fixed point math?
> Obvioux method is just to count how many times
> x2 fits x1 but that's n^2 and is slow
> for really big ints.
> Thanks




Use Newton's method - this comparison says it is actually faster than
the common "schoolboy math" method:

http://www.treskal.com/kalle/exjobb/original-report.pdf

Here is the idea: compute not 1/n, but (2^k)/n for some large k

Let x = (2^k)/n + e, where e is a small error term.

Then n*x2 = (2^2k)/n + (2^(k+1))*e + n*e2

and (2^(k+1))*x - n*x2 = 2^(2k)/n - n*e2

Dividing by 2^k (which is very easy if we choose k to be a multiple of
32) gives :

2x - (n*x2)/(2^k)

approximates (2^k)/n with a smaller error than x does. Iterate until
convergence, which will be rapid if your first estimate for (2^k)/n is
accurate (if 2^m is the largest power of 2 less than or equal to n, then
use 2^(k-m) as a first estimate).

Then p/n = p * (2^k/n) / (2^k)

Vic

 |  Next  |  Last
Pages: 1 2 3
Prev: Computer nostalgia song
Next: If you don't immediately see your CLAX post...