Making changes to a Racket package

[John Kemp]

Hi there,

I implemented an alternative to the modular-expt function in the math/number-theory package, that uses bit-shift (https://gist.github.com/frumioj/2dcc1364464508ec359075d5014d0157), as proposed by Bruce Scheier (pseudocode in https://en.wikipedia.org/wiki/Modular_exponentiation).

Although that’s how I ended up here, my actual problem came when I thought “oh, I could just add this to my local copy of the number-theory package, and test whether my implementation is faster or slower than modular-expt.”

First, I forked the github racket/math repo, and couldn’t see a way to build that independently of Racket. So then I checked out the racket repo itself, which uses raco to get me a copy of the math package collection. I was able to build with that, but it seems unconnected to the github racket/math repo.

I tried various raco incantations to see if it were possible to get a copy of my forked math package, but nothing seemed to work, and I am concerned I misunderstood the instructions in https://docs.racket-lang.org/racket-build-guide/index.html

Is there any document that describes how I should be able to both build and use a local math/number-theory package, and also be able to use my forked copy of that repo to commit my changes? Is it possible for me to *only* check out racket/math and build it for my local Racket installation?

Thank you,

- johnk

[Robby Findler]

I think you probably want to use "raco update --clone math" and you'll end up with a directory named "math": where you run that that is a clone of the racket/math github repo and the racket installation you ran "raco" from will now use that as the source. Then you can add a remote to it with your clone to work on a pull request. You should be able to do this with your own built version of racket (which you get by running "make" in the top level of a clone of racket/racket) or in a snapshot build or probably even in 8.0.

Does that help?

Robby

--
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+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/E30EA0E9-DC7F-498C-9F67-42554EBB757E%40gmail.com.

[John Kemp]

> On Feb 16, 2021, at 3:49 PM, Robby Findler <ro...@cs.northwestern.edu> wrote:
>
> I think you probably want to use "raco update --clone math" and you'll end up with a directory named "math": where you run that that is a clone of the racket/math github repo and the racket installation you ran "raco" from will now use that as the source. Then you can add a remote to it with your clone to work on a pull request. You should be able to do this with your own built version of racket (which you get by running "make" in the top level of a clone of racket/racket) or in a snapshot build or probably even in 8.0.
>
> Does that help?

Thanks Robby, that definitely helped (although I’m not finished getting this to work).

Checking the correct sequence:

0. cd ~/src
1. git clone https://github.com/racket/racket.git
2. cd racket && make PREFIX=/usr/local
3. cd .. && /usr/local/bin/raco pkg update —clone math (this worked FWIW and cloned the math collection to my ~/src directory)
4. cd racket && make PREFIX=/usr/local (to install the updated math package into this copy of racket)
5. /usr/local/bin/racket (to test changes in REPL)

In my case, I think part of my problem was a) two copies of Racket installed (so I needed to be more specific about which raco to use) and b) not understanding where raco is doing its work.

Cheers,

- johnk

[Robby Findler]

I would not do it quite that way. Here's the steps I recommend:

git clone https://github.com/racket/racket.git

cd racket

make # get some coffee here

mkdir extra-pkgs

cd extra-pkgs

# make sure `raco` in your path is the one you built just above

raco pkg update --clone math

.... now do git stuff / racket stuff.

The upside to avoiding the "PREFIX=..." is that the racket installation is now completely contained in that directory. Just throw it away when you're done with it and if you have more than one (perhaps you want to try out an older version or a released version or something) all you have to do is update your path. And if you want to update to get some bug fix or improvement, simply do a git pull and make in the top-level directory again. (That "make" really does include all of the steps, like it'll run configure and do all kinds of things so you don't have to worry about it.) And the "extra-pkgs" directory is just the convention some of us use.

Robby

[Sorawee Porncharoenwase]

Hi John,

A couple of questions:

Although that’s how I ended up here, my actual problem came when I thought “oh, I could just add this to my local copy of the number-theory package, and test whether my implementation is faster or slower than modular-expt.”

I don’t understand why you need to “add this to … local copy of the number-theory package”? If you want to compare your version with the math package’s version, you can do something like:

#lang racket

(require math/number-theory)

(define (my-modular-expt a n) ...)

(time (my-modular-expt ...)) ; test your version
(time (modular-expt ...)) ; test the `math` package's version

In fact, by modifying the math package, you will no longer have the math package’s version to compare to!

Slightly off-topic: do you find that the math package’s version is too slow? Why did you try to implement your own version in the first place?

Best,

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAL3TdONM%3DGm_t%3DO_X%3D%3DOcR1oj94yTXnSJ8zp3hU3OQ-qsFN2BA%40mail.gmail.com.

[John Kemp]

Hi Sorawee,

On Feb 17, 2021, at 3:20 PM, Sorawee Porncharoenwase <sorawe...@gmail.com> wrote:

Hi John,

A couple of questions:

Although that’s how I ended up here, my actual problem came when I thought “oh, I could just add this to my local copy of the number-theory package, and test whether my implementation is faster or slower than modular-expt.”

I don’t understand why you need to “add this to … local copy of the number-theory package”? If you want to compare your version with the math package’s version, you can do something like

Yes, I understand that (now). Originally, I used (time…) as you mentioned below, but for my function, I didn’t need to import anything (not even ‘loop’) so I noted that the (require …) would add time to the execution of modular-expt (it did). So for closest comparison, I wanted to put them in the same package. And, I wanted to put mine in github too, so forking racket/math made sense to me as good a place as any to put this.

#lang racket

(require math/number-theory)

(define (my-modular-expt a n) ...)

(time (my-modular-expt ...)) ; test your version
(time (modular-expt ...)) ; test the `math` package's version

In fact, by modifying the math package, you will no longer have the math package’s version to compare to!

Slightly off-topic: do you find that the math package’s version is too slow?

No I don’t. I was experimenting with modulo/expt, and I looked at modular-expt and saw that it was not using the bit-shift mechanism, so I decided to implement that. That’s all. 

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).

2. modular-expt uses the ‘loop’ syntax (taking an extra dependency that seems not needed for a bitwise shift to get equivalent performance).

I’m not suggesting that my implementation is better than what you’ve done already. I just followed my interest in learning how to implement what I did. 

- johnk

[Jens Axel Søgaard]

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