Hi all....

can anyone tell me how to divide large integers..

e.g
N1 = 11112222333344445555666677778888h
N2 = 11111111222222223333333344444444h

Reminder = ?
Quotient = ?

How to reach to Remainder and Quotient in such case ???

regards
Posted on 2002-12-11 06:45:34 by processingspeed
what about thinking about an subtracting algorithm? if you have (demonstrated with small numbers)



eax=123
ebx=23


and you want to get eax/ebx and eax%ebx, do:



xor ecx,ecx
@@:
cmp eax,ebx
jl @f
sub eax,ebx
inc ecx
jmp @b
@@:


--> eax=reminder; ecx=quotient
Posted on 2002-12-11 13:10:00 by hartyl
Thanks hartyl...

But do you feel that this method is good enough for the division of very large integers.. Because in that case this method may take hell lot of time........ Which I want to avoid..

Actually right now I am checking for the speed & efficiency of this method....

regards
Posted on 2002-12-11 23:20:42 by processingspeed
Back in the "old days" many CPUs didn't have a hardware divide instruction. The 6502 is an example. If you wanted to divide, you had to do it yourself.

The fastest way is a subtract and shift loop. Here's a pretty good description I just dug up using Google:

http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

Have fun. :)
Posted on 2002-12-12 01:02:21 by S/390
The subtraction method is slow, since the number of iterations required is proportional to the quotient, and this can take a looong time if the divisor is small and the dividend is large.

'Subtract and shift' is just binary long division, and is the best solution if you are dealing with large unsigned integers. If that link is confusing then this might make more sense:

[size=12]*) let D = dividend, S = divisor, Q = quotient, R = remainder.

*) let dh = number of binary digits in D.
*) let sh = the number of binary digits in S.

1) if dh < sh, then R = D, and Q = 0. Exit.
2) shift sh bits of D into D2.
3) subtract S from D2 and check the carry flag.
4) if carry,
shift a 0 into Q.
go to step 6.
5) else if no carry,
shift a 1 into Q.
let D2 = D2-S.
go to step 6.
6) check if there are any bits left in D.
7) if no bits left, R = D2. Exit.
8) else shift next high bit of D into D2.
9) go to step 3.[/size]



To illustrate, pretend you're dividing 242 by 13:


[size=12]  D = 242 = 11110010b.

S = 13 = 1101b.
dh = 8
sh = 4


1111[color=grey]0010.[/color]
-1101
-----
100[color=grey]010.[/color] Q = [b]1[/b]
-1101
-----
[color=red]CF![/color] Q = 1[b]0[/b]
1000[color=grey]10.[/color]
-1101
-----
[color=red]CF![/color] Q = 10[b]0[/b]
10001[color=grey]0.[/color]
-1101
-----
1000[color=grey].[/color] Q = 100[b]1[/b]
-1101
-----
[color=red]CF![/color] Q = 1001[b]0[/b]
. R = [b]1000[/b][/size]


So the answer is 10010 R 1000, or 18 remainder 8.
The subtraction method would takes 18 loops, while binary long division takes 5 loops. Not a very big difference, but the benefit isn't all that apparent until you start using larger numbers.

Of course this can be further optimized but I'll leave that to you. ;)
Posted on 2002-12-12 01:14:24 by iblis
Thanks iblis..

but can we leave apart this binary method of doing division...

Can anyone suggest how to divide large integers ??? Please gimme some link or resource so that I can go through it ...




regards
Posted on 2002-12-12 03:15:51 by processingspeed
But this the way to deal with large numbers. I mentioned the 6502 because it was an 8 bit machine. But there were routines to do 32 or 64 or 128 bit divisions using the subtract/shift method. You just need to apply the same logic to the 32 bit x86. I'm sure you'll be able to find more info with Google or your fav search engine... :)
Posted on 2002-12-12 03:54:42 by S/390
processingspeed,

Binary long division is really your best option. Division is always a slow process and you won't find any miraculously fast way to divide large integers. However, there are always 'tricks' to do fast divs if you accept the limitations of the tricks. Here are just a few:

-You can use shifts to divide, but the restriction is that you can only divide by powers of two.

-If you are dividing a 64bit int by a 32bit int then you can do it in two divs, but it only works for that specific situation.

-If your numbers are within the range (-2???, +2???) then you can use the FPU to do precise division. Also, if you know the divisor beforehand you can store it as its reciprocal and use multiplication, which is always faster.


...but for really large numbers, binary long division is the best way I'm afraid. It's not as bad as it looks, though. Even in the worst cases, i.e. if your dividend was giga/megabytes in size and you were dividing by something small like 3, the division could take seconds or maybe minutes, whereas if you used the subtraction method, it could take literally a lifetime.
Posted on 2002-12-12 05:44:42 by iblis
The alternate way is to multiply by a reciprocal (1/divisor). Because multiply doesn't have the trial and adjust that division requires, it is faster if you are dividing several numbers by the same divisor. I believe some of the faster binary-to-(string)decimal routines use this method because 1/10 is the constant divisor.

I don't have the details for this technique. The first detail is how to calculate the reciprocal. The second detail is where to assume the binary point. I also don't know what the accuracy of this method is.
Posted on 2002-12-12 15:59:22 by tenkey

Can anyone suggest how to divide large integers ??? Please gimme some link or resource so that I can go through it...
http://www.swox.com/gmp/manual/Division-Algorithms.html#Division%20Algorithms
Posted on 2002-12-12 17:01:56 by bitRAKE
Wow!
That's a really great site (though I've only managed to look through it very roughly) and a piece of good mathematical work.
Posted on 2002-12-13 04:48:52 by Ender
Hi processingspeed,
Have you looked at Donald Knuth's The Art of Computer Programming, V2. Seminumerical Algorithms. He goes into detail about computing numbers. Ratch
Posted on 2002-12-14 00:34:19 by Ratch
There are many quick ways, you should NOT focus on the programming part, but on the
MATH part. Once you understand that there are quick ways to do a division by hand,
you will see that programming htis method is easy. At least that's what I learned facing this same problem.

For some new and old suggestions go to URL and type Division f.e.


http://mathforum.org/library/drmath/mathgrepform.html

Also interested a Prime related problem? See my note on thread
Posted on 2002-12-17 06:59:50 by davidsimple
I still have yet to see a method for dividing arbitrary bignums that's better than 'subtract and shift'. I'd like to see one though.
Posted on 2002-12-17 08:12:33 by iblis
(I do not think there is a quicker way to travel from here to the moon, than with the space shuttle until I see it.)

It all depends on the subtraction or division- members.

Let's say you want to do : 2^123456 / 2^9

I know since a couple of weeks that a^b / a^c = a^(b-c) therefore the answer is 2^(123456-9).

Can you do quicker?
Posted on 2002-12-17 08:30:19 by davidsimple
Can I do quicker? Well you're dividing by 2^9, so just shift the dividend right by 9. No need to subtract exponents and recalculate and it also lifts the restriction that the dividend be a power of two.

Sure it's fast and it works for powers of two, but I'm talking about dividing any two arbitrary numbers. For an all-purpose bignum divide I have yet to see anything better than binary long division.
Posted on 2002-12-17 09:27:34 by iblis
Why is your shift quicker, if you have to make the 2^123456 in memory, binary or not, creating the number takes time. Shifting takes time. This takes 2^123456 BITS in memory, is this all time-less?

Calculating 123456-9 can be done on 1 line. I do not see how an actual division (shifted or not) can be quicker than a subtraction of 2 bytes (rounded).
Posted on 2002-12-17 09:36:30 by davidsimple
The focus of this thread is not in dividing numbers in the form 2^x. As suggested by the first post, the dividend and divisor are represented precisely bit for bit.

If the numbers were stored literally as just a base and an exponent, then yes it's faster to just subtract, but that's not what most of us need. What most people need is an all-purpose algorithm for dividing any two literal numbers of random value and size, producing both quotient and remainder if possible.

A smart algo would see the request to divide by 2^9 and noticing it to be a power of two, it would shift the dividend down 9 bits.

A smarter algo would see that the dividend is a power of two and that it would only need to move 1 bit.

If the algo used your method, it would have to see that both numbers are powers of the same base and subtract the exponents, and then it would have to use that to reconstruct the quotient. Not as fast.
Posted on 2002-12-17 10:03:04 by iblis
I notice that what you wrote sounds beautifull, but seems to me somewhat virtual.

I am currently in the progress of writing some solutions to the same problem, how can one divide and multiply the fastest ?

Earlier attempts like shifts and other nice methods are much too universal. There is also the difference in what you wrote and what I mean to write. The focus should not be on solving a global problem when you want to have the fastest solution.

If you want to build the fastest car for On or Off the road there are some huge differences.

What I am trying to say is, there is always a faster way to invent than the common or global solution.
You can find this method by focussing on the specific problem and solve this in a specific way.

For instance, I am looking for the fastest way to do the Lucas Lehmer test and found out that the fastest
way lies in the math part (making a formula and method that is the fastest) and not ONLY in the speed of the
programmed-routine. In 2 weeks Math I made the division of the LL-test about 3 times faster, without touching the keyboard. Of course I could have bought a faster computer to run the existing routines, but
that ends when there is no budget ;)

(Sorry for any bad grammar)
Posted on 2002-12-18 09:25:08 by davidsimple
Of course the best solution depends on the problem at hand, but that is beyond the scope of what was asked here. Processingspeed plainly wanted to know how to divide large integers. He didn't give any hint to what he needs it for, nor the conditions of the divide, thus it makes the most sense to address a general purpose algorithm.
Posted on 2002-12-18 12:10:46 by iblis