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

*To*: "Paulo J. Matos" <pocm@rnl.ist.utl.pt>, <plt-scheme@fast.cs.utah.edu>, "John Clements" <clements@brinckerhoff.org>*Subject*: Re: [plt-scheme] Divisions*From*: Jens Axel Søgaard <jensaxel@soegaard.net>*Date*: Sat, 1 Jun 2002 16:00:43 +0200*References*: <873cw7j535.fsf@localhost.localdomain> <p05111701b91e6d6ee1a1@[10.0.1.5]>*Sender*: owner-plt-scheme@fast.cs.utah.edu

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

**Follow-Ups**:**Re: [plt-scheme] Divisions***From:*pocm@rnl.ist.utl.pt (Paulo J. Matos)

**References**:**[plt-scheme] Divisions***From:*pocm@rnl.ist.utl.pt (Paulo J. Matos)

**Re: [plt-scheme] Divisions***From:*John Clements <clements@brinckerhoff.org>

- Prev by Date:
**Re: [plt-scheme] Divisions** - Next by Date:
**Re: [plt-scheme] Divisions** - Prev by thread:
**Re: [plt-scheme] Divisions** - Next by thread:
**Re: [plt-scheme] Divisions** - Index(es):