last day (21 days later) » 

6:32 PM
1
A: How to generate list of prime pairs that can be concatenated to new prime?

RenzoYour function get-prime-pairs has several problems. Here is a working, non-tail recursive version: (define (get-prime-pairs lst) (define (find-all-prime-pairs prime lst) (if (null? lst) '() (if (prime? (list->number (append prime (car lst)))) (cons (list prime (...

 
Thanks a lot for your advice and help regarding the code. I was stuck on this and am grateful you have helped me out. Also thanks for leaving something as an exercise. :-) And indeed, 3367 should have been 3673.
Somehow your algorithm misses a lot of valid pairs (e.g., '((1 1) (3)); '((6 7 3) (3))); . My current suspicion is that the combinations where the second value is lower than the first are missed.
Suspicion was right. I did not know how to fix it in above code, so I added another method which loops over the list produced by your method, checks if the opposite is also a pair and if so adds it to a resulting list. It ain't pretty, but at least I have the full list now. Extra method can be found in comment below. I believe I do need an accumulator so I do not know how to not use an iterative/tail-recursive process.
(define (add-opposite-prime-pairs prime-pairs) (define (add-opposite-prime-pairs-iter lst acc) (cond ((null? lst) acc) ((prime? (list->number (append (cadar lst) (caar lst)))) (add-opposite-prime-pairs-iter (cdr lst) (cons (append (cdar lst) (list (caar lst))) acc))) (else (add-opposite-prime-pairs-iter (cdr lst) acc)))) (add-opposite-prime-pairs-iter prime-pairs prime-pairs))
 
You are right! I was missing half of the pairs! I (hope to) have corrected the algorithm.
There is also space for other optimizations, as well, in particular find-all-prime-pairs can be rewritten in tail-recursive way.
 
Hi Renzo, thanks :-). My method of looping over the whole list was way too slow for the particular problem I am solving. What is the advantage of using tail recursion? Is it quicker in time or only in space?
 
It is quicker both in time as well as in space. Since it is transformed in a loop, the stack is not used, and the recursive call becomes a loop. Another optimization should concern the test for primality, you should use the sieve not only to generate the list of primes, but also to test, instead of using prime?.
 
6:46 PM
Will converting your method to a tail recursive one create dramatic increase in performance (time)? I will need to create all pairs that come out of primes till 1.000.000. The current method can do up to ~1.000 quickly, 10.000 is already not halting quick enough. Is tail recursion an answer to this?

I already converted the prime check to one that performs better as per your suggestion.
I will take a break from this problem for a while. I will try to convert it to tail recursive and if that does not help I will check if the problem of the performance is due to the algorithm. It should be possible to generate the pairs up to 1.000.000 quickly (e.g., in less than a second).
The issue comes from Project Euler problem 60 by the way. projecteuler.net/problem=60.
 
7:52 PM
I think there are two points of possible optimization in your code. The first, is the redefinition of find-all-prime-pairs. Here is the tail recursive version:
    (defun find-all-prime-pairs (prime lst)
      (labels ((aux (lst acc)
	         (if (null lst)
		     acc
		     (if (is-prime? (list->number (append prime (car lst))))
		         (aux (cdr lst) (cons (list prime (car lst)) acc))
		         (aux (cdr lst) acc)))))
        (aux lst '())))
Sorry, I gave you the common-lisp version, not the scheme one. Here is the scheme version:
    (define (find-all-prime-pairs prime lst)
      (define (aux lst acc)
        (if (null? lst)
            acc
            (if (prime? (list->number (append prime (car lst))))
                (find-all-prime-pairs prime (cdr lst) (cons (list prime (car lst)) acc))
                (find-all-prime-pairs prime (cdr lst) acc))))
      (aux prime lst '()))
 
8:49 PM
If you have already changed the prime? function, then it costs only an access to a vector. I tried to compute the Sieve for 100 millions numbers, (using common-lisp, since I am more familiar with it that with scheme, as you probably have already understood !). And using a bit vector, this occupies 12.5MB of memory, and is calculated in 15 seconds on my machine. But...
with this we cannot calculate for instance the primeness of the combination of the numbers (1 0 0 9) and (1 0 0 0 7), since the result is 100910007 which is bigger than 100 millions. So the test can be performed only on numbers until 10000. And by the way this computation is quite fast, founding 159503 pairs in 0.14 seconds on my machine.
So a possibility is to compute a Sieve with one billion digits. I still didn't attempted it, but maybe I will try and let you know if I succeed...
 
9:10 PM
I think you mean:
(define (get-prime-pairs lst)
  (define (find-all-prime-pairs prime lst)
    (define (aux prime lst acc)
      (if (null? lst) acc
          (if (prime? (list->number (append prime (car lst))))
              (aux prime (cdr lst) (cons (list prime (car lst)) acc))
              (aux prime (cdr lst) acc))))
    (aux prime lst '()))
  (append-map (lambda (x) (find-all-prime-pairs x lst)) lst))
I know from some cheating (searching Google) that a sieve up to 1.000.000 max prime value is enough for this question.
Thanks again by the way :)
How do you know so much about Lisp/Scheme?
On my machine the get-prime-pairs method is too slow with input of primes up to ~10.000. Takes a minute already and has not stopped calculating.
 
1. Yes, I made a mistake in cutting and pasting the function, but note that you can omit the parameter prime inside the inner function aux, since it is already visibile to it (and does not change). So, this is the new definition:
(define (get-prime-pairs lst)
  (define (find-all-prime-pairs prime lst)
    (define (aux lst acc)
      (if (null? lst) acc
          (if (prime? (list->number (append prime (car lst))))
              (aux (cdr lst) (cons (list prime (car lst)) acc))
              (aux (cdr lst) acc))))
    (aux prime lst '()))
  (append-map (lambda (x) (find-all-prime-pairs x lst)) lst))
2. I started programming in Lisp (not common lisp) during the '70s... Then I abondoned it for so many years that when I started again programming in it two years ago I had to relearn many aspects of the language (that, by the way, is very different from the original lisp). But I was always interested in programming languages during my career.
3. For the speed. It is strange, since as I said, in my laptop. finding all the pairs with 10000 elements takes 0.14 seconds. You said you have redefined prime? Simply as a check for the truth of element of the sieve?
3. For the speed. It is strange, since as I said, in my laptop. finding all the pairs with 10000 elements takes 0.14 seconds. You said you have redefined prime? Simply as a check for the truth using the element as index in the sieve?
 
9:32 PM
1. The second line from under should also have the prime variable removed then. :) 2. Ah clear.

3. As follows:

(define primes-list (primes-up-to 1000))

(define (contains? lst item)
(if (empty? lst) #f
(or (equal? (car lst) item) (contains? (cdr lst) item))))

; Checks for primes upto the highest number in our primes-list generated by the sieve.
(define (prime? n)
(contains? primes-list n))
(define primes-list (primes-up-to 1000))

(define (contains? lst item)
(if (empty? lst) #f
(or (equal? (car lst) item) (contains? (cdr lst) item))))

; Checks for primes upto the highest number in our primes-list generated by the sieve.
(define (prime? n)
(contains? primes-list n))
 
I see, you still have to scan the list, and this is too slow.
I did the definition of the sieve in this way (common-lisp, sorry):
(defun make-sieve(n)
  (let ((sieve (make-array (1+ n) :element-type 'bit :initial-element 1)))
    (labels ((is-prime? (i) (aref sieve i))
	     (not-prime! (i) (setf (aref sieve i) 0))
	     (remove-mult (i step)
	       (loop for j from (+ i step) upto n by step do (not-prime! j)))
	     (test-prime (i)
	       (loop for j from i upto n
		  if (is-prime? j)
		  do (remove-mult j j))))
      (not-prime! 0)
      (not-prime! 1)
      (test-prime 2)
      sieve)))
And then is prime can be defined in this way:
(defun is-prime?(x)
  (= (aref sieve x) 1))
Where aref is simply the access to the element of the array with index x
and sieve is a global variabile that I have defined as:
 
I use a sieve definition in scheme in a similar manner (found on telegraphics.com.au/svn/puzzles/trunk/programming-in-scheme/…) .
 
(defvar sieve (make-sieve 1000000))
(and labels is the common-lisp way of defining one or more inner functions)
 
The sieve from the web looks like:


(define (primes-up-to n)
  (let
    ((sieve (make-vector (+ n 1) #t)))

    (define (test-prime i)
      (define (is-prime? idx)
        (vector-ref sieve idx))
      (define (not-prime! idx)
        (vector-set! sieve idx #f))
      (define (remove-multiples i step)
        (when (<= i n)
          (not-prime! i)
          (remove-multiples (+ i step) step)))
      (if (> i n)
          '()
          (if (is-prime? i)
              (begin
                (remove-multiples i i)
I have the problem that 1. I do not understand the vector-sets completely and 2. I cannot call the vector-set thing outside the primes-up-to n package.
When I use

(define (prime? x)
(vector-ref primes-list x))
I get:
vector-ref: contract violation
  expected: vector?
  given: (2 3 5 7 11 ......
 
This function build and return a list of primes. My function leave this as an array. This is the main difference, and this gives a big difference in performance.
 
9:43 PM
Aha clear.
 
Note that I have another function, to get a list of primes from the array.
so that I can build the list of 10000 primes to call the get-pairs function
Here is the function:
(it uses a loop, I'll try to rewrite as tail recursive):
(defun sieve-to-list (s upperlimit)
  (loop for bit across s
     for i from 0 upto upperlimit
     if (= bit 1)
     collect i))
So with this function I can "extract" the first upperlimit elements from the sieve.
 
Ah ok. And that can be used in the get-pairs function. And then for checking primality you can use a prime number and the fast array lookup of the sieve.
 
exactly
 
So I should rewrite the primes-up-to n to return the data type I do not have used before
Is the issue in the (cons i (test-prime (+ i 1)))) part?
 
yes, cons build a list, while you should return directly the vector
you can do this starting from my code
Ok, I have also rewritten the function sieve-to-list without iteration:
(defun sieve-to-list (s upperlimit)
  (labels ((aux(i acc)
	     (if (> i upperlimit)
		 (reverse acc)
		 (if (= (aref s i) 1)
		     (aux (1+ i) (cons i acc))
		     (aux (1+ i) acc)))))
    (aux 2 '())))
And now since here in Italy is quite late, I have to say goodbye to you for today.
 
9:59 PM
Thanks Renzo. Good night! I believe it is the same time in Holland, but I have to implement a sieve. :)
 

  last day (21 days later) »