Re: Dividing long numbers

Carlos Moreno <moreno_at_mochima_dot_com@xxxxxxxxxxxxxx> (06-03-01 10:20:39):

A while ago, I was trying to have some fun (didactic fun) implementing
my own RSA. The division (required to calculate something modulo
something else) seemed to be the big bottleneck. I was trying the
standard division algorithm we're all taught as kids, except that
base 2^32 instead of base-10. From the answers I got here, it seemed
to me like I was using the right approach, only that my algorithm was
grossly unoptimized.

You might, as an alternative, use GMP. Then you don't have to reinvent
the wheel. Libtommath is nice, too. But personally I don't like the
convention that the destination is the last function argument, and GMP
is faster.

If you really want to do everything yourself, then read the GMP manual.
It explains every algorithm.


Regards.
.

Relevant Pages

  • Re: Public domain algorithm for arbitrary-precision fast division?
    ... David N. Williams wrote: ... >> I'm looking for an algorithm for doing arbitrary-precision ... the fastest method uses fast multiplication by two steps. ... I've never used it, but I must say that from the outside, GMP ...
    (sci.math.num-analysis)
  • Re: Public domain algorithm for arbitrary-precision fast division?
    ... >> I'm looking for an algorithm for doing arbitrary-precision ... the fastest method uses fast multiplication by two steps. ... on some machines it is faster ... I've never used it, but I must say that from the outside, GMP ...
    (sci.math.num-analysis)
  • Re: "Humans Do It Now" Criteria (was: Definition Challenge)
    ... signals, there may be OTHER SIGNALS in the data, that some OTHER ... identify the ET-archelogy. ... bottleneck. ... I think your algorithm is not useful. ...
    (talk.origins)
  • Re: Binqry Tree sort
    ... > root node to the other half of the tree. ... > having to pass through, making it the bottleneck, and restricting your ... First I think the order of the algorithm will be Logn becasue when we ...
    (comp.programming)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... >> about he needs the kind of stuff that they use in gmp. ... Notice that the ADD-3 to TENS suddenly is ... i.e. a register long enough to hold the value. ... It's a nice algorithm and you have a good writeup, ...
    (comp.programming)
Quantcast