Hi --

On Mon, 27 Jul 2009, Robert Klemme wrote:

> On 25.07.2009 12:14, David A. Black wrote:
>> Hi --
>> 
>> On Sat, 25 Jul 2009, Lloyd Linklater wrote:
>> 
>>> I am writing a little thing to find all the prime numbers to a million.
>>> I got it to work this way:
>>> 
>>> highestPrime = 1_000_000
>>> primes = Array.new(highestPrime, true)
>>> 
>>> currentNum = 3
>>> while currentNum < highestPrime do
>>>  (currentNum*currentNum).step(highestPrime, currentNum * 2) { |i|
>>> primes[i] = false }
>>>  currentNum += 2
>>>  while primes[currentNum] == false do
>>>    currentNum += 2
>>>  end
>>> end
>>> 
>>> I am unhappy with using currentNum += 2 twice.  I very much want to
>>> write something like this:
>>> 
>>> while currentNum < highestPrime do
>>>  (currentNum*currentNum).step(highestPrime, currentNum * 2) { |i|
>>> primes[i] = false }
>>>  currentNum += 2 until primes[currentNum] == true
>>> end
>>> 
>>> but that just hangs the program.  What am I missing?
>> 
>> When you do:
>>
>>    statement until condition
>> 
>> statement isn't executed at all unless condition is true. Since
>> primes[3] is false, the incrementation never takes place.

I garbled that because I was trying to answer the question and write
code that flipped the logic at the same time (see below for
clarification).

>> You can guarantee that the body of an until statement gets executed at
>> least once by doing it like this:
>>
>>    begin
>>      num +=2
>>    end while primes[num]
>
> Shouldn't that read
>
> begin
>  num += 2
> end until primes[num]
>
> ?  At least that would be a direct translation of the original
>
>  currentNum += 2
>  while primes[currentNum] == false do
>    currentNum += 2
>  end

This was a somewhat incomplete forward reference to my "flipped logic"
version (see below).

>> There's another issue here, though. Since the default value for
>> non-existent array values is nil, the test for truth will fail even if
>> num has gone over the maximum. So you might want to flip the logic:
>
> There's yet another issue: the limit highestPrime is not honored during the 
> incrementation of current_num which likely leads to the hanging which I 
> assume is in fact an endless loop.

The endless loop in the original is because currentNum never gets
incremented at all. Here's a skeletal version:

   x = 3
   array = [true, true, true, true]
   x += 2 until array[x] == true

x will still be 3 at the end. So the outer loop executes repeatedly,
not because the limit isn't honored but because there's no
incrementation.

Here's the version I cooked up the other day, which shows my flipped
logic in context:

max = 10
non_primes = Array.new(max)
num = 3

while num < max do
   (num * num).step(max, num * 2) { |i| non_primes[i] = true }
   begin
     num += 2
   end while non_primes[num]
end

Instead of setting an array to all true and then setting certain ones
to false, I prefer piggybacking on the fact that array values are nil
by default, and set them to true selectively.


David

-- 
David A. Black / Ruby Power and Light, LLC
Ruby/Rails consulting & training: http://www.rubypal.com
Now available: The Well-Grounded Rubyist (http://manning.com/black2)
Training! Intro to Ruby, with Black & Kastner, September 14-17
(More info: http://rubyurl.com/vmzN)