As may be apparent from my previous posts, I am in a "If its worth doing, its worth overdoing" sort of competition with a friend of mine. Our goal is arbitrary precision integer arithmetic. I think I am close to getting the data storage working, but now I want to look at the complexity of my multiplication step. I already have it so that if the number is <MIN_MUL_NUM bytes in size then I use "Grade-School multiplication". When my number goes above that, but is still stored in an array (thus <8^sizeof(size_t) bytes) I use Toom-Cook (with k=5 if the other number would like to use Grade-School multiplication, but 3 otherwise). Once I switch over to file stored numbers I intend to implement a Schonhage-Strasse algorithm (I have yet to write it however). However I do have a relatively rapid means by which to determine if my number is far too large (using my header info I can search to see if I have >X files in use for storing the number). As such I would love to implement Furer's algorithm for true asymptotic optimality. However, search as I might I cannot find a description of it anywhere online. Is it just too complicated to use? Or is it protected by some kind of copyright? Where is it?!

Recommended Answers

All 2 Replies

It looks like the last one has what I need... This is going to be hard... Thank you!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.