extra large integer divison

[Geryon]

how can i divide 128-bit integers ?(idea is important than code)
i can't use Newtons divison method.

[Ratch]

Geryon,
     You need to be a little more specific.  Are the 128-bit numbers the dividend or divisor?  Is it integer or some floating point format?  If integer, is it signed or unsigned division.  Do you want to save the remainder?  Do you want to truncate or round?

     In reference to INTEL CPU's, divisors greater than 32-bits become a lot more complicated.  That is because a trial division has to be made using multiple precision techniques.  See the classic three volume set by Donald Knuth called The Art of Computer Programming to get an idea what's involved.  Ratch

[drhowarddrfine]

Ratch,

You do this a lot.  If you can't or won't answer the question, why reply? 

Geryon,

There are a few ways to do this but I just don't recall off the top of my head how since I haven't been programming lately.  I'm sure some here will get you the answer or a link soon.  Otherwise I'll look it up.

[russian]

Ratch,

You do this a lot.  If you can't or won't answer the question, why reply?

Geryon,

There are a few ways to do this but I just don't recall off the top of my head how since I haven't been programming lately.  I'm sure some here will get you the answer or a link soon.  Otherwise I'll look it up.

drhowarddrfine, can you feel the irony???

[drhowarddrfine]

No.  My reply was to Ratch.  I can't answer the question at this time and said so.  Otherwise I wouldn't have replied at all.

[Geryon]

@Ratch:
@drhowarddrfine:

thank you for interests

Are the 128-bit numbers the dividend or divisor? 

both of

Is it integer or some floating point format?  If integer, is it signed or unsigned division.  Do you want to save the remainder?  Do you want to truncate or round?

unsigned integer and i need remainder.

See the classic three volume set by Donald Knuth called The Art of Computer Programming to get an idea what's involved.

i can't buy this book in my country
i have to buy it from amazon.com :( :( :(

[MichaelW]

Vague questions cannot be answered efficiently. A good, complete answer must cover all possible interpretations of the question, when it's likely that the person asking the question was focused on only a small subset of all possible interpretations.

[Ratch]

Geryon,
     I was going to copy the snippet from Knuth for you to read, but it is too long and contains too many funky symbols and flowcharts that I cannot reporduce here.  Instead I will post some links you might find interesting.  Ratch

The following program is written in FORTRAN.
http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/libkern/qdivrem.c.html

http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00688-6/S0025-5718-96-00688-6.pdf

http://fox.wikis.com/wc.dll?Wiki~MultiprecisionDivision~VFP

[Ratch]

drhowarddrfine ,

You do this a lot.

     Thank you, I try to make sure I have the information needed to answer the question.

  If you can't or won't answer the question, why reply?

     Who says I cannot answer it.  I just needed to know more about the problem.  Ratch

[gluespill]

This is the simplest way I can think of to divide two 128bit unsigned integers and obtain the quotient and the remainder.
Subtract the divisor from the dividend until the dividend is smaller than the divisor, but not less than zero.
The count of the subtraction iterations is the quotient.
The left over dividend is the remainder.

Example in 8 bits:

dividend / divisor  = quotient, remainder
10101010 / 01010010 = ????????, ????????

            divisor is larger than dividend,
            so subtract divisor from dividend

10101010   dividend
-01010010   subtract divisor
--------   --------
01011000   new dividend, count of subtractions = 00000001
            divisor is still larger than dividend,
            so subtract again

01011000   dividend
-01010010   subtract divisor
--------   --------
00000110   new dividend, count of subtractions = 00000010

00000110   dividend is now smaller than divisor, so stop

            quotient  = 00000010 (count of subtractions)
            remainder = 00000110 (left over dividend)

In decimal:

170 / 82 = 2 remainder 6

The quotient variable or memory space needs to be 128bits wide, as well as your dividend and divisor.
The divisor variable or memory space will hold the remainder, so a separate remainder resource is not required unless you need to preserve the dividend.

If the divisor has less than 128 significant digits, there are optimizations that can be employed to reduce the actual subtraction iterations without loss of data integrity.

This is just the idea.  Obviously, we don't have any 128 bit registers, so the subtracts will need to be done 32 or 64 bits at a time. 
I know this is over-simplified, but hope it's of some use.

[Ratch]

gluespill,
    Division by subtracton is one of the "classical" methods available.  It is probably about the only way available if the CPU does not have a DIV or MUL instruction.  Unfortunately it is one of the slowest algos for large numbers.  If you try to chip away by multiprecision subtraction, a large multiword dividend with a small divisor, you could be executing a long time even with a fast CPU.  Ratch

[aaustin]

I described a general purpose method for reducing the subtraction algorithm to a log n complexity in the old forum.
http://www.old.masmforum.com/viewtopic.php?t=4755

[gluespill]

Ratch,

The classical method would be the fastest if both the dividend and the divisor have 128 significant bits.
In the case of 128 (significant) bits/128 (significant) bits there can only be one of two quotients: either
0 or 1 with a remainder equal to either the dividend (where the divisor is larger than the dividend) or the
difference between the dividend and the divisor (where the dividend is larger than the divisor).
Overall, this would require only a few instructions.  First a compare. Then if dividend is larger than divisor
perform necessary instructions to subtract two 128 bit integers. The result of this subtraction being the
remainder.  I haven't seen anything faster than this anywhere for this scenario.

For all other scenarios; if you'll take note of the next to the last paragraph in my example, I did state:
<If the divisor has less than 128 significant digits (bits), there are optimizations that
can be employed to reduce the actual subtraction iterations without loss of data integrity.>
The method I use in this case is very similar to the post made by aaustin in the old forum, and is reasonably
fast for dividing 10 million bit integers by 5 million bit  integers in VB.NET.  If it works reasonably in VB.NET, I can
just imagine how well it will work in Asm, and how well it should certainly work for mere 128 bit integer division.

I believe that the worst case scenario using the method similar to aaustin's would be where the width of the
divisor's significant bits is half the width of the dividend's, and not when dividing by a small (or even large) integer.

If someone knows of a faster method for dividing very large non-constant integers, I would certainly be interested in
seeing it as I do this type of division routinely in my prime number search routines.  I'm not talking about tricks to make
this 'classical' method work faster, but an entirely different method that can handle integers of any size limited only by
memory.  I know the fpu can be employed, and the newer larger registers in the AMD 64bit processors can also help
speed things up.  Also, under some circumstances finding the reciporical of the divisor and then multiplying
can be faster even with non-constant divisors.  But I'll be darned if I can find any example in any book or web page that
can do this type of arithmetic without using some form of optimized repetitive subtraction when the entire divisor will
not fit in a register.
::)

[Ratch]

gluespill,
     I apologize for not answering sooner.  Have you evaluated Donald Knuth's method of obtaining a trial divisor?  After the partial division, the quotient is then checked to be sure it is correct.  That method is explained in his three book series The Art of Computer Programming, within the chapter on seminumerical algorithms.  Naturally if the divisor is close the the value of the dividend, then subtraction will be faster.  Thanks for the information and insight.  Ratch

[Hugge]

Geryon (and all you other guys),

"Subtracting the divisor from the dividend until the dividend is smaller than the divisor..." is a teqnuiqe with horrible complexity.
Let's divide 2^120 - 1 (which is an odd number, could be a prime as well) by 2, for instance. That would result in about 2^119 iterations, which will take about 10^19 years on a 4+ GHz computer, which is about a billion times longer than the age of the universe. That's plain stupid if you ask me. :tdown

I'm searching for information about integer division myself, which is the reason I got into this discussion. But I already have a good idea of how to do it, and I just want to see if there is someone else having an even better way of doing it.

If you are writing code for large integer arithmetic I suppose that you've already written routines for addition, subtraction, multiplication and comparison. If you have, life will be a lot easier.

I'm not familiar with Newton's method, so I'm not sure if that's the one I'm describing here...?

One way to go is to divide the dividend (well, a copy of it since you have to keep the original) by 2 (just shift all bits one step to the right), until the dividend is smaller than the divisor. This is in worst case done in 128 iterations. Count the number of steps (iterations) required. At this point, we've probably gone one step too far, depending on how we implement it in the code. Now the result from the division is at least 2^(steps-1) (same as 1 shifted left "steps-1" times).

Subtract this value from the original dividend, and repeat the procedure if it's still larger than the divisor. Add this new result to the old one, and you'll finally end up with the correct result.

To get the remainder, just multiply the result with the divisor, and subtract this product from the dividend.

/ Hugge