Arbitrary precision calculations

  • Thread starter QuantumHop
  • Start date
  • #1
68
0

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
rcgldr
Homework Helper
8,682
520
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:
  • #3
68
0
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 :biggrin: )
 
  • #4
rcgldr
Homework Helper
8,682
520
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.
 
  • #5
hotvette
Homework Helper
996
5

Related Threads on Arbitrary precision calculations

Replies
2
Views
563
Replies
0
Views
2K
Replies
6
Views
768
  • Last Post
Replies
5
Views
26K
Replies
2
Views
3K
Replies
4
Views
377
  • Last Post
Replies
7
Views
2K
Replies
4
Views
488
Replies
4
Views
3K
Replies
3
Views
673
Top