3

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.

Stefan
  • 109,145
  • 14
  • 143
  • 218
cabeto14
  • 43
  • 6
  • 10
    when it is for practice: implement both, then compare dev effort and performance. – H H Sep 13 '13 at 14:36

1 Answers1

2

These are my favorite algorithms I use:

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

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

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

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380