Using until

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?

Hi,

Am Samstag, 25. Jul 2009, 05:27:07 +0900 schrieb Lloyd L.:

I am writing a little thing to find all the prime numbers to a million.

Here is one that works:

def sieve max
a = Array.new max do |i| i end
a.shift
a.shift
i = 0
while (t = c = a[i]) do
yield c if block_given?
while (t += c) <= max do a.delete t end
i += 1
end
a
end

And this one is fast enough:

def sieve max
if block_given? then
h = {}
2.upto max do |c|
unless h[ c] then
yield c
t = c
while (t += c) <= max do h[ t] = true end
end
c += 1
end
else
a = []
sieve max do |p| a.push p end
end
end

Bertram

Nice but I still wonder what is wrong with my until statement. Any
thoughts?

Modify it to show u what ur problem is

until primes[currentNum]
p currentNum
p primes[currentNum]
currentNum += 2
end

Hi –

On Sat, 25 Jul 2009, Lloyd L. wrote:

currentNum += 2
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.

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]

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:

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

David

On 25.07.2009 12:14, David A. Black wrote:

currentNum = 3
write something like this:

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

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 whole looping construction looks suspicious though: there is an
outer loop and two inner loops of which I am not sure they align
properly. Lloyd, I believe you should reevaluate your logic. This
reminds me of Eratosthenes’ Sieve but your code is different.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Kind regards

robert

At 2009-07-24 04:27PM, “Lloyd L.” wrote:

I am writing a little thing to find all the prime numbers to a million.

You’ve gotten lots of good advice. You might want to peruse how others
have coded prime number generators at
http://rosettacode.org/wiki/Category:Prime_Numbers

Hi –

On Mon, 27 Jul 2009, Robert K. wrote:

I am unhappy with using currentNum += 2 twice. I very much want to
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).

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

On 27.07.2009 00:32, David A. Black wrote:

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

Ah, thanks for the clarification!

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.

Absolutely. I would consider though to use a different type of
container because the sequence of prime numbers becomes sparse as soon
as you reach reasonable large numbers. So using a bit set (either
directly or by using Integers) or a Hash seems more appropriate.

Kind regards

robert

I have the answer. fyi, it is that

doSomething until condition

does not work at all like

begin doSomething end until condition

In the first case, the condition is checked BEFORE the doSomething is
run. In the second case, the condition is checked AFTER the doSomething
is run. I am not sure just why this is or how I could have figured it
out intuitively. It seems to me that it would be better to have
something like this (to mimic pascal)

doSomething while condition #check condition before

doSomething until condition #check condition after

Thanks for all your input everyone! I finally got there. :slight_smile:

On Jul 30, 2009, at 11:15 AM, Lloyd L. wrote:

doSomething
Posted via http://www.ruby-forum.com/.
irb> i = Time.now.to_f + 0.001; begin print(’.’) end until
Time.now.to_f > i
…=
nil
irb> i = Time.now.to_f - 0.001; begin print(’.’) end until
Time.now.to_f > i
.=> nil
irb> i = Time.now.to_f - 0.001; print(’.’) until
Time.now.to_f > i
=> nil
irb> i = Time.now.to_f - 0.001; print(’.’) while
Time.now.to_f < i
=> nil
irb> i = Time.now.to_f - 0.001; begin print(’.’) end while
Time.now.to_f < i
.=> nil
irb> i = Time.now.to_f + 0.001; print(’.’) while
Time.now.to_f < i
…=
nil

Well, I didn’t believe you until I tried it myself. Seems that both
until and while behave similarly when applied to a block rather than a
simple expression.

$ ruby -v
ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0]

I get the same results with ruby -e “…” as I do with irb so it’s not
just an irb oddity.

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

Rob B. wrote:

Well, I didn’t believe you until I tried it myself. Seems that both
until and while behave similarly when applied to a block rather than a
simple expression.

I get the same results with ruby -e “…” as I do with irb so it’s not
just an irb oddity.

excellent! I always like it when things are proven. With this working
consistently that means it is a quirk and not a bug as such, though I
still wish that Matz would change this behavior.

Thanks again for checking. :slight_smile:

Hi –

On Fri, 31 Jul 2009, Rob B. wrote:

In the first case, the condition is checked BEFORE the doSomething is

Well, I didn’t believe you until I tried it myself. Seems that both until and
while behave similarly when applied to a block rather than a simple
expression.

I don’t think you’d want it otherwise, though. “until” really just
means “while not”. So the two should always behave the same as each
other in any given construct.

David

Hi –

On Fri, 31 Jul 2009, Lloyd L. wrote:

is run. I am not sure just why this is or how I could have figured it
out intuitively. It seems to me that it would be better to have
something like this (to mimic pascal)

You didn’t have to figure it out intuitively; I told you on Saturday
:slight_smile: (Though I garbled my example a bit.)

doSomething while condition #check condition before

doSomething until condition #check condition after

I suspect Ruby got the idiom from Perl, and/or from the way similar
language would be used in English. I’m not sure about the above in
Pascal (a quick look at several sources doesn’t show either of those
constructs), but I don’t think you’d want the while/until difference
to make the difference between the order of execution like that. The
difference should only be whether condition is being checked for truth
or falsehood. In other word:

statement while condition

and

statement until (not condition)

should always be the same.

David

On Jul 30, 2009, at 2:16 PM, David A. Black wrote:

begin doSomething end until condition
:slight_smile: (Though I garbled my example a bit.)
difference should only be whether condition is being checked for truth

David


David A. Black / Ruby Power and Light, LLC / http://www.rubypal.com
Q: What’s the best way to get a really solid knowledge of Ruby?
A: Come to our Ruby training in Edison, New Jersey, September 14-17!
Instructors: David A. Black and Erik Kastner
More info and registration: http://rubyurl.com/vmzN

But David, should the behavior of:

statement while condition

be different from:

begin statement end while condition

which is what the issue boils down to. When the statement is enclosed
in a block, it is evaluated once before the condition is checked.
This is what I intended to show very explicitly in my response to Lloyd.

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

Hi –

On Fri, 31 Jul 2009, Rob B. wrote:

or falsehood. In other word:
David

statement while condition

be different from:

begin statement end while condition

which is what the issue boils down to. When the statement is enclosed in a
block, it is evaluated once before the condition is checked. This is what I
intended to show very explicitly in my response to Lloyd.

I wasn’t sure which issue was the focus (see my response to Lloyd
about the Pascal thing). I personally don’t have any problem with the
above difference. I think they exist for different reasons: the
begin/end one specifically as a way of forcing at least one execution
of statement (as opposed to while conditions; statement; end), and the
one-line modifier form just as a convenience.

I don’t have an air-tight technical argument, though. (There probably
isn’t one.)

David

Hi –

On Fri, 31 Jul 2009, David A. Black wrote:

which is what the issue boils down to. When the statement is enclosed in a
I don’t have an air-tight technical argument, though. (There probably
isn’t one.)

This discussion got me curious about something I remembered from days
gone by: namely, that if you add a “rescue” to a
begin/end/(while|until) construct, it ceased to do the one execution
of the block.

It’s mainly of historical interest, since it was changed by Ruby
1.8.6. But it’s just so much fun showing how ruby-versions.net works
that I can’t resist! :slight_smile:

$ ruby160 -e ‘begin; puts “hi”; rescue; end until true’
$ ruby171 -e ‘begin; puts “hi”; rescue; end until true’
$ ruby186 -e ‘begin; puts “hi”; rescue; end until true’
hi

David

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs