newlispfanclub.alh.net

Posted: **Wed Apr 06, 2005 4:30 pm**

Lutz,

I was talking to you earlier about the performance of two versions of the same algorithm. Intuitively the most recent version I have written should be much faster, but that is not the case. I cannot figure out why the introduction of mapping and filters should cause the program to degrade time-wise so rapidly. The following are the two versions.

Code: Select all


(set 'prime_list '(2 3))

(define (list-map op p lst)
	(map (lambda (x) (op p x)) lst)
)

(define (true? x)
	(if x true nil)
)

(define (mods? x)
	(if (= x 0) true nil)
)

(define (n_is_prime? number)
	(set 'largest_prime (first (sort prime_list '>)))
	(set 'flag true)
	(set 'contained (list-map = number prime_list))
	
	(if (filter true? contained)
		number
		(begin
			(if (= (mod number 2) 0)
				nil
				
				(begin
					(if (filter mods? (list-map mod number prime_list))
						(begin												(set 'flag nil)
							nil
						)
						(begin
							(if flag
								(begin
									(push number prime_list)
									number
								)
							)
						)
					)
				)
			)
		)
	)		
)

(define (n_prime_factor number)
	
	(set 'number_lst (sequence 3 number 2))
	(push '2 number_lst)
		
	(set 'prime_seq (filter true? (map n_is_prime? number_lst)))
	(set 'prime_factors (filter (fn (x) (= (mod number x) 0)) prime_seq))
		
)

The preceding block is the code I thought would run faster. The next block of code is the first version, that seems to be running quite well.

Code: Select all

(define (l_is_prime? number)
	(set 'divisor (- number 1))
	(set 'return 'true)
	
	(until (= divisor 1)
		(if (= (mod number divisor) 0)
			(set 'return nil)
		)
		(set 'divisor (- divisor 1))
	)
	
	return
)

(set 'prime_factors '())	

(define (l_prime_factor number)
	(set 'csr '2)
	(until (= csr number)
		(if (= (mod number csr) 0)
			(if (l_is_prime? csr)
				(push csr prime_factors)
			)
		)	
		(set 'csr (+ csr 1))
	)
)

Notice that the second version goes through every number and tests, and it does not keep track of each prime number like the first version. Theoretically if you have a list of primes and you only check them to see if they are factors, you avoid testing the rest of the numbers and your execution time should speed up. There is probably an error in my lisp-code that isn't exactly following what i am thinking, but I can't find it.

Any thoughts?

Posted: **Wed Apr 06, 2005 8:04 pm**

It appears that the problem is when you run n_is_prime? for every single number. If I change my

Code: Select all

(define (n_prime_factor number)

to the following there is a dramatic speedup.

Code: Select all

(define (n_prime_factor number)
	
	(set 'number_lst (sequence 3 (/ number 2) 2))
	(push '2 number_lst)
	
	(set 'prime_seq '())
	(until (not number_lst)
		(set 'tst_num (pop number_lst))
		(if (= (mod number tst_num) 0)
			(if (n_is_prime? tst_num)
				(push tst_num prime_factors)
			)
		)
	)
	
	prime_factors

The reason this is so much faster is because n_is_prime?() is only being called when factor of the number is found. Check out the following benchmarks.

Code: Select all

> (time (l_prime_factor 1001))
3
> (time (n_prime_factor 1001))
1
> (time (l_prime_factor 10001))
23
> (time (n_prime_factor 10001))
5
> (time (l_prime_factor 100001))
236
> (time (n_prime_factor 100001))
52
> (time (l_prime_factor 1000001))
1514
> (time (n_prime_factor 1000001))
472
> (time (l_prime_factor 10000001))
15395
> (time (n_prime_factor 10000001))
3429
> (time (l_prime_factor 100000001))
147949
> (time (n_prime_factor 100000001))
42249

Now I just need to figure out how to speed up n_is_prime?

Posted: **Thu Apr 07, 2005 5:26 am**

You may get a further, though small speedup changing

(until (not number_lst)
....

to

(while number_lst
...

'while' is the same as 'until not', just like 'while not' is like 'until'

Lutz

ps: In Atlanta in a hotel, missed the flight to Ft. Lauderdale ... good night

newlispfanclub.alh.net

Benchmarks

Benchmarks

Ineficciency discovered