On Sun, 14 Mar 2004, Philip Pemberton wrote:
>   I've attached some code I've been working on - a simple multiple-precision
> maths library written in C. I've got the add/subtract/multiply/divide stuff
> working, but I'm having a hard time finding some information on alternative
> multiplication and division routines.
>   At the moment, the code uses a brute-force (repeated subtraction) division
> routine and a very nasty multiplication routine. I'd like to get rid of the
> 16-bit multiply in the multiplication routine and find a faster division
> routine.

Brinch Hansen published a paper in "Software Practice and Experience"
where he described the few and poor examples of mulltiple word
division algorithms.  He gave references to the few that he had
been able to find in the literature and then gave a very careful
code example for division that was substantially faster and easier
to understand than the others.  There is a letter published by the
author a few months later, in the same journal, referring to his
paper I think it only included minor information and no corrections.

Google for
   +"brinch hansen" +division
and you will find references for it.

Hans Risel in his book "Prime Numbers and Computer Methods for
Factorization" in appendix 9 gives a Pascal coded example of a
complete multiple precision math package, but his division code is
one of those cited by Brinch Hansen.

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.