I want to manipulate really big numbers and I am trying to work with arrays. I have already implemented the multiplication operation, but now I want to implement the division operation.
I was wondering which algorithm(s) should I use? Is it possible to use the Newton–Raphson division algorithm or maybe should I use the algorithm that we learned in the school?
PS: I know that there are many libraries that work with big numbers, but I want to do this for practice.
These are my favorite algorithms I use:
Binary division
Look here: http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
This is what you should start with. It's not that slow and it is simple. Do not forget to properly test your +, -, <<, >> operations before you start. They should work flawlessly on any given input
Division by half the bits arithmetics
Look here: https://stackoverflow.com/a/19381045/2521214
With little tweaking you can adapt it to arrays. Uses +, -, *, /, %. If you code it properly should be much faster then Binary division.
approximation of division
Look here: https://stackoverflow.com/a/18398246/2521214
Or for some speed up of x^2, x*y here: Fast bignum square computation
This is more suited for floating/fixed point division. It's a little bit harder to understand, but the speed and accuracy is worth the while. Also, there are many other approximation algorithms out there, So google!
