Arbitrary precision calculations

[QuantumHop]

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?

 

[rcgldr]

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.

 

[QuantumHop]

I'm not sure if division is done directly or if it's better to calculate the inverse (1/x) then multiply.

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 )

 

[rcgldr]

I'm not sure if division is done directly or if it's better to calculate the inverse (1/x) then multiply.

I was hoping there was some clever trick that would solve the problem.

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.

 

[hotvette]

You might want to check out a VB based arbitrary precision package called XNUMBERS:

http://digilander.libero.it/foxes/SoftwareDownload.htm

Source is included that could give you some hints about division.