Re: [plt-scheme] Divisions

[Jens Axel Søgaard <jensaxel@soegaard.net>]

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:

    http://www.swox.com/gmp/manual/Extended-GCD.html#Extended%20GCD

Yours,
--
Jens Axel Søgaard