```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]
>
>
> 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