On Wednesday, February 17, 2021 at 9:38:09 PM UTC+1 John K wrote:
> Hi Sorawee,
>
> On Feb 17, 2021, at 3:20 PM, Sorawee Porncharoenwase <[email protected]>
> wrote:
>
>
> Why did you try to implement your own version in the first place?
>
> Just as a learning exercise…
>
> I didn’t see any obvious performance difference, but I guess if I compare
> the two implementations, I would say:
>
> 1. modular-expt uses infix operators (which looked strange to me in Racket
> context FWIW but is clearly just my personal taste).
>
I think, Neil liked (a . < . b) over (< a b). For consistency, I prefer (<
a b).
> 2. modular-expt uses the ‘loop’ syntax (taking an extra dependency that
> seems not needed for a bitwise shift to get equivalent performance).
>
I was curious, so I looked up the code:
(: modular-expt* (Positive-Integer Integer Integer -> Natural))
;; Exponentiate by repeated modular multiplication and squaring
(define (modular-expt* n a b)
(cond
[(b . < . 0) (raise-argument-error 'modular-expt "Natural" 1 a b
n)]
[(b . = . 0) (if (n . = . 1) 0 1)]
[else
(let ([a (modulo a n)])
(let loop ([b b])
(cond [(b . = . 1) a]
[(even? b) (define c (loop (quotient b 2)))
(modulo (* c c) n)]
[else (modulo (* a (loop (sub1 b))) n)])))]))
I expect that (quotient b 2) is implemented as a bitshift. That would
explain why you don't see any difference.
The loop syntax is called "named let", and is just a convenience.
/Jens Axel
--
You received this message because you are subscribed to the Google Groups
"Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-dev/8ebb6ec0-5479-4b07-b862-07989ebb4ac9n%40googlegroups.com.
