Arbitrary precision calculations

AI Thread Summary
The discussion centers on the challenges of implementing division in an arbitrary precision calculator, particularly when handling large numbers. While multiplication of thousand-digit numbers is efficient, achieving division with high precision (around 250 decimal places) is significantly slower, taking about 20 seconds. Participants suggest that optimizing algorithms for arbitrary precision can be complex, involving techniques like Fourier transforms and finite field math. A common approach discussed is calculating the inverse (1/x) and then multiplying, although this method has been noted to slow down exponentially with each decimal place. An alternative method proposed involves an iterative algorithm that starts with a rough estimate of the inverse and refines it to achieve higher precision quickly. This method doubles the precision with each iteration, allowing for efficient convergence to the desired result. Additionally, resources such as the Apfloat package and a VB-based package called XNUMBERS are recommended for further exploration and implementation guidance.
QuantumHop
Messages
68
Reaction score
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?
 
Technology news on Phys.org
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:
rcgldr said:
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: )
 
rcgldr said:
I'm not sure if division is done directly or if it's better to calculate the inverse (1/x) then multiply.

QuantumHop said:
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.
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »
Thread 'Project Documentation'

Thread 'Project Documentation'

Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
View full post »

Similar threads

Insights P vs. NP conjecture and what is a Turing Machine (TM)?
Replies
6
Views
3K
MHB Calculating Probabilities in Poker Hand: An Example
Replies
1
Views
2K
Program to list specific permutations of 5 digits
Replies
4
Views
3K
How does one convert a decimal float to binary using the multiply by 2 method?
Replies
4
Views
2K
Need more precision in the calculations....
Replies
6
Views
1K
MHB Answer: How Many Elementary Operations for Adding Two Numbers with $n$ Digits?
Replies
3
Views
2K
B Dimensional analysis peculiarity
Replies
6
Views
2K
Number of bits required for floating point representation
Replies
4
Views
2K
B How to handle significant digits of exact values?
Replies
12
Views
2K
Fortran Double precision computation time in fortran
Replies
15
Views
8K

Hot Threads

Recent Insights

Back
Top