[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [plt-scheme] Divisions

John Clements wrote:
>> I'm implementing extended euclidean algorithm, I wish it
>> to be fast and I need a way to compute the integer
>> division of a by b and the division remainder. Is there
>> a way to do it without 2 divisions... (I'm counting that
>> remainder function performs a division).
>> Any ideas?
> Well, if you subtract the quotient times the divisor from
> the ... divisee(?),

Dividend, see http://mathworld.wolfram.com/Division.html
for more info (I had no idea that / is called solidus).

> you get the remainder without
> performing an additional division.  That is:
> (lambda (a b)
>    (let ([quotient (div a b)]
>          [remainder (- a (* quotient b))])
>       ... do what you want with the result ...))
> Not rocket science, certainly, but the desired effect is
> what you get. Only one division.

I predict that the next question from Paulo is how to get rid of the extra
multiplication. :-)

Since mzscheme uses the GMP library one could use

    void mpz_tdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
    Divide n by d, forming a quotient q and/or remainder r.

which calculates the quotient and the remainder at the same time, to
implement a quotient-remainder function.

    (let-values ([(q r) (quotient-remainder 42 5)]))

The file to hack must be "mzscheme/src/numarith.c".

If anyone has the energy (Paulo, Matthew?) one could add the extended gcd
algorithm at the same time:


Jens Axel Søgaard