Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Arbitrary precision calculations

  1. Aug 19, 2012 #1
    I decided to write an arbitrary precision calculator but I'm having problems with division.

    It will multiply a thousand digit number by another thousand digit number in about a second but to get a division result to about 250 decimal places is taking around 20 seconds, I cannot figure out how it should be done.

    Anybody have any ideas?
  2. jcsd
  3. Aug 20, 2012 #2


    User Avatar
    Homework Helper

    The optimizing algorithms for arbitrary precision can get complex, involving a combination of fourier transforms and modulo (finite field) math. Apfloat (do a web search) is a package that you can get for free and includes source and some documentation on the algorithms. I'm not sure if division is done directly or if it's better to calculate the inverse (1/x) then multiply.
    Last edited: Aug 20, 2012
  4. Aug 20, 2012 #3
    This is exactly the method I have used, it works but its very slow and the time taken to calculate the next decimal place increases exponentially. I was hoping there was some clever trick that would solve the problem, I've searched for solutions but haven't found one I can use in VB2010. ( yeah I know , learn a real language :biggrin: )
  5. Aug 20, 2012 #4


    User Avatar
    Homework Helper

    If you have a relatively fast multiply you can try this algorithm that converges to the result quadratically:

    z ~= 1/x (use actual division for initial 16 bit estimate of 1/x).

    then iterate this process using extended multiply algorithm.

    z = z (2 - x z)

    If you start off with a 16 bit estimated quotient, then the precision doubles to 32 bits after 1st step, 64 bits after second step, ... So if you need 64 bits, you would iterate twice, then do a test multiply t = x z, and adjust z +/- 1 bit for the final correction.
  6. Aug 21, 2012 #5


    User Avatar
    Homework Helper

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook