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?!

5 Years
Discussion Span
Last Post by Labdabeta

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

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.