how can i divide 128-bit integers ?(idea is important than code)
i can't use Newtons divison method.
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
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.
Quote from: drhowarddrfine on January 03, 2005, 03:36:41 PM
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???
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.
@Ratch:
@drhowarddrfine:
thank you for interests
Quote from: Ratch on January 03, 2005, 02:23:14 PM
Are the 128-bit numbers the dividend or divisor?
both of
Quote from: Ratch on January 03, 2005, 02:23:14 PM
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.
Quote from: Ratch on January 03, 2005, 02:23:14 PM
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 :( :( :(
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.
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
drhowarddrfine ,
Quote
You do this a lot.
Thank you, I try to make sure I have the information needed to answer the question.
Quote
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
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.
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
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
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.
::)
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
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
Hugge,
Quote"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.
QuoteI'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.
QuoteOne 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
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
Hugge,
QuoteSecond, 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?
QuoteAnd 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
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
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
Quote from: Geryon on January 03, 2005, 11:04:42 AM
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
@Hugge:
@Randall Hyde:
thanks
Quote from: Scott on January 20, 2005, 05:39:55 PM
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]
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.
gluespill,
Can you post the VB code algo you have? I should have no problem translating it.
Scott
gluespill,
QuoteI 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
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]
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 ...
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.
Quote from: gluespill
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 ...
I was thinking you might be able to take off N bits at a time if you precompute a certain amount
you split up the source in pieces of K bits each (K ~= 2log(sqrt(N))). You precalculate for all possible bit patterns K can assume (2^K) which amount of divisor you can substract (positive number between 0 and 2^K preferred).
For each set of K bits in the source, shift your index right until you hit a 1, add the amount that can divide by the amount you can at least keep. Substract the amount you actually removed (precise calculation) and continue parsing. This modified method should run in order (sqrt(N) * 2^(sqrt(N))), which imho should be faster than most methods mentioned up to now. It's not memory efficient though, for K=4 (probable end solution) it's quite a memory hog with 16 precalculated values between 0 and 16 with each a precise multiple of the divisor (128-bit) attached. You can keep each in a separate array though, yet I doubt it'll be cache friendly.
HTH, Candy
Polizei,QuoteFactorial is just multiplying ...
I did not say
factorial, I said
factoring.
A factorial, like 3! is 3 * 2 * 1 and does indeed only involve multiplication.
Factoring, on the other hand, requires division.
I was trying to answer your post in which you asked:
QuoteWell guys, what's the idea of dividing 128bit values or dividing by 128bit bla-bla-bla...
I was just giving you an example of why I would want to divide by an extra larger integer.
I have other reasons if you're interested, or if you like, I could explain what factoring is.
And it would be difficult to appropriately answer your question without knowing whether you are asking
1) why someone would have any practical reason for dividing by 128 or more bits, or
2) why one would attempt to do so on a computer that can not hold numbers that large in a single register?
Or are you hinting that
3) 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?
Thanks for the insight on multiplying 64b*64b, and then dividing the 128b result by a 64b divisor. But my personal interests lie in dividing by up to 17 million bits with full precision.
Cheers.
Candy,
Your idea sounds similar to a method to which I have given considerable thought.
Is your first step critical, the one where you calculate the approximate value of K?
If so, how would you perform the square root without already having an algorithm capable of dividing large integers?
You are also performing a logarithm calculation in your initial step. Are you just looking up the log in a small lookup table?
When you refer to the 'Source', are you refering to the dividend or to the divisor?
I know it can be difficult to get an entire idea or concept into a single post, at least for me. But I must say your proposal looks interesting.
laytuhr
Quote from: gluespill on February 03, 2005, 12:14:31 AM
Your idea sounds similar to a method to which I have given considerable thought.
Is your first step critical, the one where you calculate the approximate value of K?
That one is the step that makes it differ from a simple linear approach (which would take about 128 steps). This one takes with K=4 16 (2^K) steps of calculation and 32 (128/K) steps of iteration.
Quote
If so, how would you perform the square root without already having an algorithm capable of dividing large integers?
You can decide the optimal value of K in advance. Only for codes with lots of binary zeroes at the start (IE, actually smaller integers) is using a smaller K useful. But then again, it wouldn't make much of a difference either, since this is about large integer division. I'm expecting him not to use it for small integers since he asked it explicitly.
Quote
You are also performing a logarithm calculation in your initial step. Are you just looking up the log in a small lookup table?
It's the initial step which you still take on paper, since you predecide the value of K for faster code. Especially since K=4 is optimal (more or less) for 64 and 128 bits, with K=4 possibly doing slightly more than K=5 on 256-bits values.
The running time of the algorithm is (with K=the value decided upon, N = the number of bits) 2^K * precalc time + N/K * division time. The concept of the algorithm is that by choosing a small K (explicitly small) you can cut the division time in half while not adding much precalc time. If you have a constant divisor you can optimize for it in a similar way to most encryption routines, you "key schedule" the divisor and then can feed any dividend to it to be divided in 1/K times the original time taken. Of course, if you are going to do lots (and I mean lots, like 2^12 or more) divisions on the same divisor, you can precalculate a larger K for quicker runs. Don't take K > 8 or it's going to outrun the other step quite probably in the foreseeable future.
Quote
When you refer to the 'Source', are you refering to the dividend or to the divisor?
You can replace source with dividend. I'm not naturally english so occasionally I pick the wrong word.
in an example:
first step:
a97093b7 /03a8238a987ac8b6e \ 4
2a5c24edc
----------
102613bbc7ac8b6e
second step:
a97093b7 /03a8238a987ac8b6e \ 58
2a5c24edc
----------
102613bbc7ac8b6e
0fe28dd928
----------
04385e29fac8b6e
Total completion:
a97093b7 /03a8238a987ac8b6e \ 58660494 leaving 0d5e49a2
2a5c24edc
----------
102613bbc7ac8b6e
0fe28dd928
----------
04385e29fac8b6e
03f8a3764a
----------
03fbab3b0c8b6e
02a5c24edc
----------
155e8ec308b6e
1484a1e329
----------
0d9ecdfdfb6e
0c935af695
----------
10b7307666e
0fe28dd928
----------
0d4a29d3ee
0c935af695
00b6cedd59 -> end of algorithm. See if there's a last fit
00a97093b7
----------
00d5e49a2
Table used for computing it:
0000000000 0 00
00a97093b7 1 01
01fc51bb25 3 02
02a5c24edc 4 03
03f8a3764a 6 04
04a2140a01 7 05
05f4f5316f 9 06
069e65c526 a 07
07f146ec94 c 08
089ab7804b d 09
09ed98a7b9 f 0a
0a97093b70 10 0b
0be9ea62de 12 0c
0c935af695 13 0d
0de63c1e03 15 0e
0e8facb1ba 16 0f
0fe28dd928 18 10
108bfe6cdf 19 11
11dedf944d 1b 12
1288502804 1c 13
13db314f72 1e 14
1484a1e329 1f 15
15d7830a97 21 16
1680f39e4e 22 17
17d3d4c5bc 24 18
...
In each step, it takes the first two nibbles from the previous result and looks up the value corresponding to it in the table (third value in the table). It substracts the first value in the table in that row from the previous result, shifted left to match up with the value, then shifts the resulting value left 4 bits and adds the second value in the table row to it. It does this until it cannot continue because the shift is 0. You can apply this algorithm to larger integers in the same way. If the quotient is low the algorithm is slightly slower than the substracting algorithm, yet if it's larger it's substantially faster.
The code used to generate the table (in C, sorry dudes) :
#include <stdio.h>
int main() {
int i, k=0;
long long t=0;
for (i=0; i<32; i++) {
while (((t + 0xA97093B7) >> 32 & 0x1F != i) {
t += 0xA97093B7;
k++;
}
printf("%02x%08x %02x %02x\n", (unsigned int)((t >> 32) & 0xFF), (unsigned int)(t & 0xFFFFFFFF), k, i);
}
}
Additional sidenotes:
The table for computation must be at least 2 * 2^K, because of edge cases and because it doesn't always decide the most optimal case but the quickest to decide upon. It might leave a 1 at the start of the next sequence.
It requires the divisor to start with a 1 in binary in the bit it uses for dividing. You can make it start at any bit so it is not a really big problem, but it might be.
I expect calculating the factors to take slightly longer than dividing it actually, since the factor-creation adds the divisor once or twice, while the other is a table lookup and a single substract. It's in time complexity 1.5*2^K*time(factor_create) + N / K * time(factor_substract)
Hope it's any good in actual use :)
Note, at the end because of the edge cases a single factor may still be left in. Please do check for it (the example also has it).
[edit] I can't do maths. Forgot to add an E somewhere :)[/edit]
[later edit] and I can't even do proper algorithm design. Made an off-by-8 error. [/later edit]
Hi guys...
I'm not following your discussion (don't have time to read it all), but here's a very good paper (pdf) describing a division algorithm. My implementation of it is many times faster than my multiplication algo (Karatsuba, divide and conquer).
Hugge
[attachment deleted by admin]
Quote from: Hugge on February 05, 2005, 12:35:07 PM
Hi guys...
I'm not following your discussion (don't have time to read it all), but here's a very good paper (pdf) describing a division algorithm. My implementation of it is many times faster than my multiplication algo (Karatsuba, divide and conquer).
Hugge
It's identical aside from two speedups in my algorithm:
1. You don't make an accurate estimate. Instead, you "guess" that you can fit a precomputed amount in the quotient, such that you reduce the first number that's non-0 to either 1 or 0. You then procede to the next number, which saves you from doing an incremental compare on that number (you don't increase your guess, you just live with an inaccurate guess). This also allows the algorithm to modify the quotient for up to 2 decimals, or more in case of overflow, upon being increased.
2. Since you don't have to do this, but calculate in K-bits at a time mode, you can also use any radix you like for it. However, you have to re-compute the precomputed table each time you switch divisor. If you switch with each division, it's unpractical. Since in most cases (except this particular factorization case) you want the remainder rather than the quotient, it's useful. Most cases in my point of view, which is mainly encryption and hashing for long numbers.
You can invert these two to make it faster for constantly switching quotients, should you find that precomputing the table is unpractical for any K>1. This would result in the algorithm itself as described in the paper.
I'm off implementing it in a C++ library for myself :)
How might modular division combined with Chinese Remainder Theorem perform?
Hi everyone,
A bit late to this post thread :tdown, but I have some assembly code that I found a while back that divides a 128bit number by a 64 bit number and leaves the results in the registers :dance:. The code is below, you'll have to do a little work to use it in masm.
The WinDog
PROCEDURE CpuDiv128
;In:
; edx:ecx:ebx:eax = 128-bit dividend
; edi:esi = 64-bit divisor
;Out:
; ebx:eax = quotient
; edx:ecx = remainder
;Modifies:
; edi,esi,ebp
mov ebp,64 ; 64 bits to process
CpuDiv128_l1:
add eax,eax ; shift left edx:ecx:ebx:eax 1 bit
adc ebx,ebx
adc ecx,ecx
adc edx,edx
inc eax
sub ecx,esi ; edx:ecx -= edi:esi
sbb edx,edi
jnb CpuDiv128_l2
dec eax
add ecx,esi ; edx:ecx += edi:esi (to restore)
adc edx,edi
CpuDiv128_l2:
dec ebp
jnz CpuDiv128_l1
ret
ENDPROCEDURE
Quote from: gluespill on February 02, 2005, 11:52:14 PM
Polizei,
But my personal interests lie in dividing by up to 17 million bits with full precision.
Are you prime-searching or cracking RSA? ( :wink )
AeroASM,
I am prime searching for the most part. How did you guess? You must be doing some yourself.
As for cracking RSA, no, I'm not tyring to. But a factoring algo that can factor say about 20,000 decimal digit (67,000 bit) numbers in a matter of hours or less would certainly put a hurt on some of the fairly recent encryption routines. I'm constantly trying to come up with better and faster ways of factoring. Right now it looks like parrallel processing on a very large scale is the only feasible way of factoring numbers greater than 1024 bits in any reasonable amount of time. Must be why the US govt requires that networks of this type be registered as 'supercompters.'
I like to solve, not crack. I'll leave the cracking to those with interest. And even though RSA will eventually melt under a good algo, there's already better encryption routines in use. I think the encryptors are always trying to stay a step ahead of the crackers.
Hi gluespill,
Noticed you lived in Grand Rapids, MI. That's just a stones through away from where I live, Holland, MI.
How long have you lived there?
Quote from: gluespill on February 26, 2005, 05:06:34 AM
AeroASM,
I am prime searching for the most part. How did you guess? You must be doing some yourself.
Nope, I had a fanatical ambition a few months ago (when I first got the hang of asm) to find the next Mersenne prime, then I realised it would probably blow my laptop out of this world.
About RSA, factoring 20000 decimal digits is hoping for a bit too much, especially in under a year. The really important world bank transactions only use 500 (i think). However the fastest algorithm to factor a random 100 digit number ran in 15 seconds on the CRAY.
Quote from: windog on March 01, 2005, 09:19:58 PM
That's just a stones through away from where I live, Holland, MI.
*waves* Greetings from Holland, Europe :)
I've been working on a factoring algorithm. I've been programming a modulus function for use with a GCD function and I'm trying to speed it up with P4 code.
I have a better idea for precalculating. You can simply use division in order to approximate a certain size multiplier. For instance, let's say you wish to divide really large numbers by each other using standard 32-bit division. You can start by finding the high 32-bits of the divisor, then take the high 64 or 63 bits of the dividend depending on whether or not the high dword of the dividend is larger than the high dword of the divisor. Then you increment the divisor 32-bits by 1 (and if zero, replace division with a 32-bit shift - this ensures that the multiplier times the divisor is less than the dividend). Then you divide the dividend 63/4 bits by the divisor 32-bits and the result is a 32-bit multiplier that you can use to save time by multiplying the full divisor before subtracting. The divisor should initially be virtually placed shifted so that the highest bit of the divisor is at the same location as the highest bit of the low dword of the 63/64 bit dividend. You can also align the dividend and divisor before any operations begin to avoid excessive shifting and can avoid shifting completely by simply taking the top two unaligned dwords of the dividend as the 63/4 bit dividend (removes the need for shifting entirely but only is efficient for the divisor bits approximation size divided by 2 (ie. 32/2 = 16 bits at a time on average)- the unshifted high dword must be less than the divisor to avoid a division exception). I'm trying to use P4 code and I'm trying to see if EP FP can do a full 64-bit division, as this would speed things up even more. Unfortunately I'm still looking for my CD with the intel help files on it in a stack of about 100 unlabeled CDs so I'm not sure if FP would be usable or not.
Why don't you post your code so we can help.
windog,
'Been here 10 years now. Didn't know you all had internet over in Holland, MI. :toothy
AeroASM,
I certainly know what you mean by fanatical ambition. I look at it more as maniacal. My guess is that most great achievements in math & algos were made by people that could sustain long periods of extreme focus. It feels like a vacation going to work to code database apps compared to researching and developing efficient algos at home.
glue spill: :U we sure do! Having a hell of a time finding hi speed connections though
candy: Our original dutch homland speaketh :wink, greetings to you to as well!! :8)