OpenEuphoria

1. primes.e documentation error? and function error

• Posted by Lnettnay Dec 04, 2013
• 1934 views

According to the documentation for primes.e the prime_list function is supposed to give us a list of primes

8.29.1.3 prime_list

include std/primes.e 
namespace primes 
public function prime_list(integer top_prime_p = 0) 

Returns a list of prime numbers. Parameters:

top_prime_p : The list will end with the prime less than or equal to this value. If top_prime_p is zero, the current list of calculated primes is returned.

Returns:

A sequence, a list of prime numbers from 2 to <= top_prime_p

Example 1:

sequence pList = prime_list(1000) 
-- pList will now contain all the primes from 2 up to the largest less than or 
--    equal to 1000, which is 997. 

---

While working on Problem 37 from Project Euler, I was experimenting with the prime_list function to see how high I could go before I ran out of memory. I have 6 gigs so I thought I could go up a ways. So I used the following program:

include std/primes.e 
atom n = 10 
atom time_start = time() 
sequence list = prime_list(n) 
? list[$] 
? length(list) 
? time()  - time_start 

multiplying n by 10 until I ran out of memory. At least that was the plan. When n hit 10_000_000 I got the following error:

c:\Euphoria\include\std\primes.e:242 in function prime_list()  
subscript value 546253 is out of bounds, reading from a sequence of length 546252  
    top_prime_p = 10000000 
    index_ = 546253 
 
... called from C:\Users\Lonny\Programming\Euler\nnprimes.ex:4  
 

What was curious to me is that when I ran the program multiple times the index_ would change. It would always be in the same general area 500_000 < index_ < 550_000 but it wouldn't be the exact same number every time.

As the saying goes "WTF!". So I copied primes.e to my current directory, added the above program, minus the include, to the end of it and ran it again. Same thing.

I put a

with trace 
trace(1) 

at the top of the program to see if I could figure out what was happening. The error happened with index_ = 5 reading from sequence of length 4. After investigating further I figured out that the following lines are causing the problem:

	if list_of_primes[$] < top_prime_p then 
		list_of_primes = calc_primes(top_prime_p, 5) 
	end if 
	 
	index_ = search:binary_search(top_prime_p, list_of_primes) 
	if index_ < 0 then 
		index_ = - index_ 
	end if 
	if list_of_primes[index_] > top_prime_p then 
		index_ -= 1 
	end if 
	 

prime_list(n) calls calc_primes with a time limit of 5 seconds. On my machine I get a top prime of around 8_000_000 or so, YMMV.

If n > 8_000_000 then the calc_primes function may return a list with the largest prime < n. The following lines:

	index_ = search:binary_search(top_prime_p, list_of_primes) 
	if index_ < 0 then 
		index_ = - index_ 
	end if 

will give us an index_ of 1 larger than length(list_of_primes) because the binary_search function either returns the position in the list or the position where the number belongs (as a negative number). The following lines will then attempt to use that index_ value:

	if list_of_primes[index_] > top_prime_p then 
		index_ -= 1 
	end if 

causing the error.

If the line

list_of_primes = calc_primes(top_prime_p, 5) 

is changed to

list_of_primes = calc_primes(top_prime_p, -1) 

Then the error goes away because the last value is always >= top_prime_p.

This also enables the code to be changed as follows: remove

	index_ = search:binary_search(top_prime_p, list_of_primes) 
	if index_ < 0 then 
		index_ = - index_ 
	end if 

and add

	index_= length(list_of_primes) 
	if list_of_primes[$] > top_prime_p then 
		index_ -= 1 
	end if 

If the changes above are made then the max prime I can get on my machine is around 900_000_000 depending on what else is running.

If we want to keep the time limit then the documentation should be changed. Also, the above changes, without the calc_primes line will prevent the error.

Sorry such a long post. And I know I should submit a ticket. I just thought it would be easier this way.

Lonny

list_of_primes = calc_primes(top_prime_p, 5) 

list_of_primes = calc_primes(top_prime_p, -1) 

public function prime_list(integer top_prime_p = 0, atom time_limit_p = -1) 
   ... 
        list_of_primes = calc_primes(top_prime_p, time_limit_p)