Re: Large-numbers division way too slow -- what to do?

From: Carlos Moreno (moreno_at_mochima_dot_com_at_xx.xxx)
Date: 03/10/05 

Date: Thu, 10 Mar 2005 08:34:29 -0500

Francois Grieu wrote:

>>I recently started my own implementation of the internals of
>>the RSA system. I'm doing it for "didactical fun"
>
> From the rest of the post, it looks like yes, the division
> algorithm is now responsible for most of the slowness.

I was investigating a bit further (after posting this message)
and thought about the possibility that maybe the multiplication
could be at fault. I counted the number of operations for one
encryption and one decryption, and I get around 1500 divisions,
while I get 1.4 million multiplications!! (there are a lot of
multiplications done as part of a division, since my algorithm
"guesses" -- by binary search -- each digit of the result). I'm
wondering if it would also be a good idea to use an FFT-based
multiplication algorithm (I recently implemented a template-
based, meta-programming FFT algorithm trying to use the notion
of expression templates, and it looked pretty fast to me....
I wonder if I would have some interesting use for it here)

> It is hard to understand the code, notably because the
> the "mod" operator is not shown.

Yes, it is shown... Well, sort of... the mod is a quick/silly
wrapper function for the division (in the division function, I
pass an extra boolean parameter to the division, indicating if
I want to return the quotient or the remainder). But yes,
you're right, I didn't show the mod wrapper per se:

BigInt mod (const BigInt & n1, const BigInt & n2)
{
     const bool remainder = true;
     return division (n1,n2, remainder);
}

In the division function, at the very bottom, I placed:

     if (return_remainder) // this is the third parameter
     {
         return partial;
     }
     else
     {
         reverse (result.begin(), result.end());
         cleanup_zeros (result);
         return result;
     }
}

"partial" is what I keep adding digits to, and that after
processing the last digit becomes the remainder.

I wonder if this is precisely what I'm missing? Is it a
more efficient way to compute a remainder without doing
a complete division procedure?

The basic idea in my algorithm is that it follows this
structure:

    12345 | 678
          +-------
    1234 Q
    Q*678
    -----
    XXXX

At each step, I take one of the digits from 12345, and
attempt division (leading to one digit only). This digit
is "guessed" by binary search -- it requires computing
Qi*678 for each guessed value. Then, subtract Q*678 from
1234 to obtain XXXX, and add the digit 5 to attempt the
division XXXX5 divided by 678 (which will also lead to
a single-digit resul).

The range for the binary search is narrowed as much as
possible (as much as I could think of, at least), by
noticing that Qi is bounded by (in the example above):

1200/700 <= Qi <= 1300/600

And these two divisions can be done directly (discarding
the zeros, they're numbers that fit within an int value
in my program). I figured this could noticeably reduce
the amount of work for guessing each digit of the division.

Notice that my digits are numbers between 0 and base-1,
where base is arbitrary (I used a defined constant, and
in my currrent implementation I put base=32768)

Anyway, I'll check the pointers and ideas that you and
Tom give me before commenting more (I'm just quickly
reading your reply and answering a couple of the more
immediate issued).

Thanks!

Carlos 

--

Relevant Pages

  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • Re: Powers and logic
    ... quasi wrote: ... It is easy to give an algorithm which could be calculated ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ...
    (sci.math)
  • Re: continued fractions
    ... The "one bit at a time" algorithm is just a special case of the ... The dividend and divisor will be expressed as ... The crucial part here is the "guessing" of the digit. ... digit is 1, and the result of the subtraction is your new w; ...
    (comp.lang.forth)
  • Why are reals uncountable yet algorithms countable (long)?
    ... If you are going to say: construct a number from one digit ... you cannot enumerate the infinite digits.I have read that, unlike reals, ... one of these algorithms would also be an algorithm ... enumeration of algorithms cannot produce all reals? ...
    (sci.math)
  • Re: Need Algorithm for Persistence number
    ... efficient algorithm. ... One algorithm i applied ... Divide by 2 until there is a remainder. ... Also, the output can't have more than one digit of 2, otherwise you ...
    (sci.math)