Sign in to follow this  
  • entries
    97
  • comments
    98
  • views
    50553

MAPM

Sign in to follow this  

84 views

I got bored today and decided that I should get an arbitrary precision math library up and running, just for fun. So of course I went to google and looked around.

What I found was MAPM. It was painless enough to make the library file using Dev-C++ and once I had that done, I linked it into a project and tried it out. The code to actually do something is pretty simple, but I kind of wish that they had overloaded the basic operators to make it a bit easier. I guess it's not that bad though.

What I thought was most interesting were the statistics that were given about the multiplication methods used.

For small numbers it uses the traditional multiplication method of O(N^2).

Next up is the divide-and-conquer method which is supposed to run at O(N^1.585).

Finally they have implemented a FFT (fast fourier transform) method for really big numbers that runs at O(N*Log2(N)).

To show a performance comparison of these methods the author of the site provides the following statistics about multiplying two 1,000,000 digit numbers together:

FFT Method : 40 seconds
Divide-and-Conquer : 1 hr, 50 min
Ordinary N2 : 23.9 days*

*projected!

I thought that that was simply amazing. I don't know what's involved in multiplying using the FFT method, but to know that you can get that performance is great.

I've setup a basic program to do math with the library and I doubt i'll need to worry about precision again.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now