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 <sorawe...@gmail.com>
> 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 racket-dev+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-dev/8ebb6ec0-5479-4b07-b862-07989ebb4ac9n%40googlegroups.com.
