Arbitrary precision calculations

  • Thread starter QuantumHop
  • Start date
  • #1
68
0
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,756
555
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,756
555
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
638
Replies
0
Views
2K
Replies
6
Views
857
  • Last Post
Replies
5
Views
27K
Replies
2
Views
3K
  • Last Post
Replies
7
Views
2K
Replies
4
Views
506
Replies
3
Views
801
Replies
4
Views
627
Replies
15
Views
7K
Top