extra large integer divison

[Ratch]

Hugge,

"Subtracting the divisor from the dividend until the dividend is smaller than the divisor..." is a teqnuiqe with horrible complexity

     Actually it is one of the most simple techniques.  It just takes a hellacious amount of time if the divisor is small compared with the dividend.  I pointed out in my previous post that this method would only be fast if the divisor was comparable with the dividend.

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.

     You would do well to read Knuth as referenced in my previous post.

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.

     You are describing an operation called "scaling".  That does not help you in this case.  You cannot right shift all the least significant bits and discard them.  You will lose all the precision those bit represent.  If you save them, you still have the same problem of dividing a large number of bits.  The biggest problem is dividing with a divisor that too large to fit into a register.  Then the multi-register arithmetic is really complex.  Ratch

[Hugge]

Ratch,

First of all, I'm not talking about complexity the way you seem to think about. As you have meantioned, it really is an easy algorithm to understand and to implement, but it's complexity when talking in terms of computer science is something like O(2^n). Algorithms with this complexity is a big no-no when programming. :naughty:

Second, I think you are misunderstanding the algorithm I was describing. To clear things out, here is an example:

Let's divide 153 by 6, which is 25.5. We start by dividing 153 by 2, which gives us 76. That's one step. Then we do this again, and divide 76 by 2, and we get 38 which is still larger than 6. (That was the second step). Now we continue doing this, and after the fifth step, we get 4, which is less than 6.

The result so far is 2^(steps-1) which is 2^4 = 16.

Now subtracting 6*16=96 from 153 gives us 57. And we do the same procedure one more time, starting at 57 instead...
57/2 => 28/2 => 14/2 => 7/2 => 3

That's four steps, which gives us 2^3=8. Add this to 16 and we have 24. 153 - 24 * 6 = 9, and we have to do the procedure one last time starting at 9:
9/2 => 4 (one step).

Finally we get 2^0 = 1, and adding this to 24 gives us our correct answer, which is 25. :U

So what was that about precision?

And why are you talking about registers? You'll have to store these large numbers in memory of course, and write your own shifting routines as well.

/ Hugge

[Ratch]

Hugge,

Second, I think you are misunderstanding the algorithm I was describing. To clear things out, here is an example:

     Thanks for the example.  I understand your algo now.

     OK, you have to ask yourself.  Is the DIV instruction quicker than your method?  Everyone knows that DIV is one of the slowest ALU instructions, but can your method divide an arbitrary 32-bit number into a 64-bit number as quickly as DIV can?  And receive a remainder besides?  Now KNUTH, who I mentioned earlier, goes into a method called "modular arithmetic".  He shows how to group a binary number into a series of "modules" dependent on the size of the CPU data word.  For the INTEL CPU it will be either 16-bits or 32-bits depending on whether you are running protected mode or not.  Anyway, he shows how to add, subtract, multiply, and divide large multi-word numbers with what could be a 32-bit gulp for the INTEL CPU.  Taking advantage of the large DWORD size has got to be faster than iterative division by 2 and the accompanying "housekeeping" necessary, don't you agree?

And why are you talking about registers? You'll have to store these large numbers in memory of course, and write your own shifting routines as well.

     Registers are necessary for the DIV, IDIV instructions.  Ratch

[Hugge]

Well... The algorithm isn't faster than the div-instruction, but that was not the issue from the beginning of this thread either, or was it? I was just giving that guy Geryon an answer, and I hope it helped him.

But what do I know? I didn't even realize that this forum was made for assembler programmers until now... I just answered the question. :)

I am programming in C++ myself anyway... Well, that's all I had to say.

Happy coding!

/ Hugge

[sbrown]

Hugge,

You got my attention. Can you post a short example of dividing an unsigned 64-bit number by an unsigned 32-bit number?


Scott

[Randall Hyde]

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

Check out the chapters on "Extended Precision Arithmetic" in "The Art of Assembly Language" at http://webster.cs.ucr.edu. Not only does it explain the principles behind extended precision division, it also gives an example of a 128/128 division.

You might also look at the extended precision arithmetic routine in the HLA Standard Library (callable from MASM). There's a 128/128 division in that library. Also found on Webster.
Cheers,
Randy Hyde

[Geryon]

@Hugge:
@Randall Hyde:
thanks

[Hugge]

Hugge,

You got my attention. Can you post a short example of dividing an unsigned 64-bit number by an unsigned 32-bit number?

Well... As you can see in my last post, I'm programming in C++, and I'm programming a large integer class that can manage integers of any size. It won't be the fastest code, but it will be sufficient for my purposes. If you want some code in assembly, then what CPU are we talking about? The only CPU I know anything about is the Intel Pentium family, and it was a long time ago I practiced assembly programming, so I'm not sure that I can give you what you want.

But if you use the MMX instruction set, it can't be that hard to implement...? I've attached an old document that I wrote years ago. It's a summary of the MMX instruction set, in case anyone finds it useful.

Hugge

[attachment deleted by admin]

[gluespill]

Repetetive subtraction is a very feasible method of large integer division.  In my post where I referred to repetetive subtraction, I mentioned that there are optimizations that can be used if the divisor is smaller than the dividend. 

<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.>

This was in reply to an inquiry about 128/128 bit division.  Then in a subsequent reply I referred to aaustin's post as being very similar to the optimization that I use for repetetive subtraction for large integer division.  It seems that new posts to this topic do not have access to the referenced post, or the poster would know that the algo in question does not use 2^n subtraction iterations.  In vb.net, a very inefficient language compared to assembly, I can divide a 33 million bit number by any other number less than or equal to the dividend in under one minute.  The 120 bit number referenced by Hugge can be divided by any other sub 120 bit number in an eyeblink using this algorithm.

I have experimented with variations of the divide and conquer method posted by Hugge and found it to be much much much much slower.  I let an optimized version run for over an hour on a 1 million bit dividend using a 512 bit divisor with very dissapointing results, as the algorithm was very elegant.

I am taking Geryon's advice and looking at Knuth before I continue converting my algos to Assembler.  I've written (practically copied) some algos for modular reduction of large integer expressions.  Very simple algos that return an answer on very large integer expressions almost instantly.  I'm hoping Knuth is the answer.

[sbrown]

gluespill,

Can you post the VB code algo you have? I should have no problem translating it.


Scott

[Ratch]

gluespill,

I am taking Geryon's advice and looking at Knuth before I continue converting my algos to Assembler.

     Not that it matters much, but it was I, and only I that recommended within this thread that you read Knuth.  Ratch

[gluespill]

Scott,
I'm not sure posting vb code would be appropriate here,
but maybe I can get away with attaching it to this post.

Ratch,
Sorry about the Knuth reference Ratch, and thanks for
the pointers in that direction.

[attachment deleted by admin]

[Polizei]

Well guys, what's the idea of dividing 128bit values or dividing by 128bit bla-bla-bla... You processors can't use decimals larger than 32bits (64bit respectively in 64bit processors), or 64bit values using the FPU. They are so-called useless. But if somebody wants to divide 128bit values, i offer him to wait some YearZ (10-15 maybe :-) for the 128bit machines :>
Regards ...

[gluespill]

Polizei,
Are you asking why someone would have any practical reason for dividing by 128 or more bits, or are you asking why one would attempt to do so on a computer that can not hold numbers that large in a single register?

Factoring is one reason.  To factor a number larger than 1024 bits in any reasonable amount of time is not possible with today's computers and algorithms.  By refining or developing better algorithms we may some day be able to factor even larger numbers.

Just because today's processor's cannot typically hold more than 128 bits that does not mean that the processor cannot divide by numbers larger than 128 bits.  A well written algorithm can utilize the processor to break a large division problem down into smaller problems, and then solve each of the smaller problems individually, then finally combining the results to yield a final answer.  I believe that the human brain starts to become very inefficient in cases where it tries to hold in short term memory a number larger than 7 decimal digits in length.  That's only 24 bits at maximum.  But a human being can divide by numbers much larger than 7 decimal digits by using paper and pencil and an algorithm.

Algorithms are considered to be technology.  I would like to see the development of this technology continue rather than have it wait until a processor with larger registers is developed.  Before the advent of machines that do arithmetic for us, should they have just waited for a computer to be invented before performing  division operations at all?  If they had, we would not have computers today. 

Typical encryption in the United States over the internet utilizes 128 bits, and our 32 bit processors are quite proficient at decrypting the messages.  The computer can handle as many bits as the programmer is capable of directing it to handle, regardless of the size of the registers.

Do you know of some method that can be employed to divide large numbers without using a CPU, or perhaps a method that does not involve division but can arrive at the same answer as a division operation?  I would be most eager to see it.

[Polizei]

Factoring is one reason...

Nice, but the topic was extra large integer divison :(
Factorial is just multiplying ...
And, btW, the 64b Windowses must have 64bit function equal to the MulDiv!KERNEL32. So you'll can easily multiply 64b*64b, and then divide the 128b result by 64b divisor. Hope so :)
Regards ...