Division Algorithm
-
Hi all. I am David and I am writing "big integer" class. In my class I use "long long Number[_NUMBER]" ( in C++) and I need algorithm of division, it is not problem if this algorithm will use bit set and not "long long" type, I need that it was fast. In other words I need algorithm that divides one vector onto another this vector can be vector of bits ( Ex: [1, 1, 1, 0, 0, 1, 0, 1, 0, 1] ) or vector of number ( Ex: [1258, 16546, 54646846, 54685, 088946, 555468, 8864, 11213, 1] ) Thanks for any help.
Hi, I can't help specifically with c++ code to do long division .. but I wrote code in vb to do arbitrary precision floating point math. The division method that I used turned out to be suprisingly fast and much easier to implement than addition or subtraction with signed floating point numbers. The method is called the Newton-Raphson method or just Newton's method. I won't go into it here, just search for it, you'll find numerous examples. I don't know how well it would would with integers only since the method uses multiplication, addition and subtraction iteratively but principal is sound anyway. The guts of the divide method I wrote is this: Do While Compare <> Guess Compare = Guess Guess = Left(Multiply(Subtract("2", Multiply(y, Guess)), Guess), Precision) Loop If your multiply, add and subtract methods can handle large numbers (this one uses strings) and you provide code to prevent the length of the result with each iteration from getting too long then sometime like may work. Each iteration will double the accuracy. With another 50 or so lines of code this method can divide numbers thousands of digits long in milliseconds. I also read somewhere where the Newton method is the fastest for divison.
-
Hi, I was playing around with a BigInteger class recently and so have come across the same problem. The fastest way I could think of is below, if you say x / y = z (with remainder = r). 1. Find the leading 64 bits of your big number (x) 2. Find the leading 32 bits of your divisor (y). 3. Divide (1) by (2) to give you the leading 32 bits of z. 4. Multiply (3) by y and take this number from x Continually applying steps 1-4 reduces the size of x until you are within +/- 1 of the correct value of z. This is fast because all operations are O(n) or less if you code them properly! Hope this is of some use & good luck! Russ
thanks: https://movied.org
-
Hi, I can't help specifically with c++ code to do long division .. but I wrote code in vb to do arbitrary precision floating point math. The division method that I used turned out to be suprisingly fast and much easier to implement than addition or subtraction with signed floating point numbers. The method is called the Newton-Raphson method or just Newton's method. I won't go into it here, just search for it, you'll find numerous examples. I don't know how well it would would with integers only since the method uses multiplication, addition and subtraction iteratively but principal is sound anyway. The guts of the divide method I wrote is this: Do While Compare <> Guess Compare = Guess Guess = Left(Multiply(Subtract("2", Multiply(y, Guess)), Guess), Precision) Loop If your multiply, add and subtract methods can handle large numbers (this one uses strings) and you provide code to prevent the length of the result with each iteration from getting too long then sometime like may work. Each iteration will double the accuracy. With another 50 or so lines of code this method can divide numbers thousands of digits long in milliseconds. I also read somewhere where the Newton method is the fastest for divison.
thanks: https://movied.org
-
I'll apply the above to my class and I'll email you my source or I'll email you a link to it.
Class Diagram::LongMathAddition Add(sourceA As String, sourceB As String) As String Subtraction Subtract(sourceA As String, sourceB As String) As String Multiplication Multiply(sourceA As String, sourceB As String) As String Division Divide(divisor As String, dividend As String) As StringThis may take me a few days with the holidays here and all.thanks: https://movied.org
-
"Interested?" Yes I am. About your problem: Use integer division for your non integer Number. Ex: 121/11 = 11 if 1.21/11 = (121/11)*0.01 or 14/3 = 4+2/3 = 4+(20/3)*0.1 = 4+(6+2/3)*0.1 = 4+(6+(20/3)*0.1)*0.1= =...=4+0.6+0.06+0.006+0.0006+..... it is idea and math.I hope you like this.:) Can you send my division algorithm?
thanks: https://movied.org
-
I've posted my source code to my LongMath dll. link to my profile where I've posted it.[^] After re-reading your prior post I'm not sure if this is what your looking for. If not, I'm sorry.:-O
thanks: https://movied.org
-
I apologize. I missed the fact that you already posted this in the Math-Forum. Thats what you get when you usually only read the VC-forums.
thanks: https://movied.org
-
I'm working on a similar class LongMath. Have you had any luck with division? I've completed add, subtract and multiplication of negative/position whole and non-whole numbers but have been stuck on the division. I can divide negative/positive numbers but only whole numbers and I'd like to compare notes. Interested?
thanks: https://movied.org
-
Hi all. I am David and I am writing "big integer" class. In my class I use "long long Number[_NUMBER]" ( in C++) and I need algorithm of division, it is not problem if this algorithm will use bit set and not "long long" type, I need that it was fast. In other words I need algorithm that divides one vector onto another this vector can be vector of bits ( Ex: [1, 1, 1, 0, 0, 1, 0, 1, 0, 1] ) or vector of number ( Ex: [1258, 16546, 54646846, 54685, 088946, 555468, 8864, 11213, 1] ) Thanks for any help.
thanks: https://movied.org
-
You could check out libGMP (GNU Multiple Precision Library), which is Open Source (zlib-licensed, IIRC) and does the same thing. Alternatively, you could model the thing by re-implementing what you would do when you divide one number by another. Just do some divisions and model those steps. That, however, probably is not the best way to do divisions. You should check the "Math"-Forum for better algorithms.
thanks: https://movied.org