Dear Bob,
My sense is that there are, perhaps, two questions: first, what's the advantage
of Racket when faced with a "prosaic computational task where ... my brain
defaults to writing in something like C"?; and second, how to advocate for
Racket when Python (appears to be) "quite a bit faster".
I’m interested in both of these because I am trying to understand where my
colleagues are coming from (and possibly changing their minds).
On the first question, this discussion has perhaps produced four different
versions of the prime-counting program:
1. Python (using a for-loop);
2. Racket (using accumulator-passing style);
3. Racket (using a for-loop);
4. Racket (using map/filter).
(Actually, I can’t find an example of (4) in the email chain, but there’s one
at the bottom of this email.)
It’s certainly been educational for me to see all four. On reflection, do you
still have the sense that (1) is the “most natural”?
On the second question, let me report some rough-and-ready timings on my
machine for counting the number of primes of the form 2^n + 3 for n < 1000 (the
code is at the end of the email):
Python: 265 ms
Racket (filter/map version): 760 ms
Racket (for loop version): 670 ms.
My own feeling is that /for this particular application/, there's just not that
much difference.
I strongly suspect that all of the difference comes from the implementation of
the primality testing functions. It turns out that, for sufficiently large
numbers, both sympy and math/number-theory actually check for pseudoprimality.
So there may be implementation-dependent details (which I don't understand)
that are different, such as the probability that a composite number is
incorrectly identified as a prime.
Indeed, maybe the answer to your second question is that, I rather suspect,
Racket is quite a bit faster than Python, so one could reasonably turn the
question around.
I implemented a cheap-and-cheerful, deterministic primality test (from
Wikipedia, code again at the end of the email). I’m pretty sure I’ve written
essentially identical code in Python and Racket: Python using `while` and
mutation; Racket using `for/and`. Here are the times I get for testing the
primality of 2^55 + 3 (which is in fact prime):
Python: 7 s
Racket: 0.8 s
Make of that what you will!
Best regards,
James
=== Python, count special primes ===
import timeit
import sympy
def count_special_primes(N):
count = 0
for n in range(N):
if sympy.isprime(2 ** n + 3):
count = count + 1
return count
print(timeit.timeit('count_special_primes(1000)', globals = globals(), number =
1))
=== Racket, count special primes ===
#lang racket
(require math/number-theory)
;; "filter/map" variation
;; Count primes of the form 2^n + 3 for n < N
(define (count-special-primes N)
(define (f n) (+ (expt 2 n) 3))
(length
(filter prime?
(map f (range N)))))
(time
(count-special-primes 1000))
;; “for-loop" variation
(define (count-special-primes/quicker N)
(define (f n) (+ (expt 2 n) 3))
(for/sum ([n (in-range N)])
(if (prime? (f n)) 1 0)))
(time
(count-special-primes/quicker 1000))
=== Python, primality test ===
Import timeit
import math
## Quick and dirty test for primality
## from https://en.wikipedia.org/wiki/Primality_test
def is_prime(n):
if n <= 3:
return (n > 1)
elif (n % 2 == 0) or (n % 3 == 0):
return False
else:
k = 5
k_max = int(math.sqrt(n)) + 1
while k < k_max:
if (n % k == 0) or (n % (k + 2) == 0):
return False
k = k + 6
return True
print(timeit.timeit('is_prime(2 ** 55 + 3)', globals = globals(), number = 1))
=== Racket, primality test ===
;; integer? -> integer?
;; Quick-and-dirty test for primality
;; from https://en.wikipedia.org/wiki/Primality_test
(define (prime/slow? n)
(if (<= n 3)
(> n 1)
(if (or (= (modulo n 2) 0)
(= (modulo n 3) 0))
#f
(prime-aux n))))
;; Test for primality assuming n > 3 and divisible by neither
;; 2 nor 3
(define (prime-aux n)
(let ([k-max (ceiling (sqrt n))])
(for/and ([k (in-range 5 n 6)]
#:break (> k k-max))
(not (or (= (modulo n k) 0)
(= (modulo n (+ k 2)) 0))))))
(time (prime/slow? (+ 3 (expt 2 55))))
> On 11 Jul 2019, at 02:36, Bob Heffernan <bob.heffer...@gmail.com> wrote:
>
> On 19-07-10 02:46, Maciek Godek wrote:
>> A while ago, I wrote a booklet which used almost the same problem to
>> introduce to, what you called nicely in the title of this thread, "thinking
>> in Scheme", so if you're interested, you may want to check out the first
>> chapter ("Introduction"):
>
> Maciek,
>
> Thank you for your reply.
>
> I skimmed through your booklet some time ago. (I too dislike the R
> language, although some attempts have been made in recent years to make
> it less awful). I read through the introduction again this morning and
> enjoyed it.
>
> The reason I like racket (and scheme-like languages in general) is that
> they encourage the style of programming you are advocating (I think)
> where the program is expressive and can be read and appreciated by
> humans. In theory, my favourite style of programming is one that is
> elegant and readable by humans.
>
> My original email had to do with the problem of when this comes into
> conflict with a prosaic computational task where my main aim is simply
> to get the job done efficiently and my brain defaults to writing the
> program in something like C.
>
> For instance, another way of writing something like my original program
> might be something like:
>
> (define (f n) (- (expt 2 n) 3))
> (define (good? n) (and (positive? n) (prime? n)))
> (length (filter good? (map f (range 1 100))))
>
> which is, I think, fairly expressive. It is still, however, relatively
> inefficient. A python programmer might write something like
>
> count = 0
> for n in range(1, 1000):
> if 2 ** n - 3 >= 0 and isprime(2 ** n - 3):
> count += 1
>
> print(count)
>
> and happily report that her program ran quite a bit faster than mine.
>
> I'm not sure how I'd advocate for Racket (or scheme) in a situation like this.
>
> Regards,
> Bob
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-users+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/racket-users/20190711013633.nm2jlznhzwibhsli%40bob-cit.
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/6E47B95D-D18B-4265-B6E6-AFA60CC2112E%40gmail.com.
For more options, visit https://groups.google.com/d/optout.
