[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:
http://www.swox.com/gmp/manual/Extended-GCD.html#Extended%20GCD
Yours,
--
Jens Axel Søgaard