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?

···

--
Posted via http://www.ruby-forum.com/.

Hi,

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

···

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

--
Bertram Scharpf
Stuttgart, Deutschland/Germany
http://www.bertram-scharpf.de

Modify it to show u what ur problem is

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

···

On Jul 24, 2009, at 4:27 PM, Lloyd Linklater <lloyd@2live4.com> 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?
--
Posted via http://www.ruby-forum.com/.

Hi --

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.

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 Sat, 25 Jul 2009, Lloyd Linklater wrote:

--
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)

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

···

At 2009-07-24 04:27PM, "Lloyd Linklater" wrote:

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

--
Glenn Jackman
    Write a wise saying and your name will live forever. -- Anonymous

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

···

--
Posted via http://www.ruby-forum.com/.

Hi --

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.

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

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.

Kind regards

  robert

···

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

On Sat, 25 Jul 2009, Lloyd Linklater wrote:

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

Hi --

Hi --

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

···

On Mon, 27 Jul 2009, Robert Klemme wrote:

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

On Sat, 25 Jul 2009, Lloyd Linklater wrote:

--
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)

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

···

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

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

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:

···

--
Posted via http://www.ruby-forum.com/.

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:
--
Posted via http://www.ruby-forum.com/.

i = Time.now.to_f + 0.001; begin print('.') end until

Time.now.to_f > i
.....................................................................................................= > nil

i = Time.now.to_f - 0.001; begin print('.') end until

Time.now.to_f > i
.=> nil

i = Time.now.to_f - 0.001; print('.') until

Time.now.to_f > i
=> nil

i = Time.now.to_f - 0.001; print('.') while

Time.now.to_f < i
=> nil

i = Time.now.to_f - 0.001; begin print('.') end while

Time.now.to_f < i
.=> nil

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 Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

···

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

Hi --

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)

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 Fri, 31 Jul 2009, Lloyd Linklater wrote:

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

Rob Biedenharn 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:

···

--
Posted via http://www.ruby-forum.com/.

Hi --

···

On Fri, 31 Jul 2009, Rob Biedenharn wrote:

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

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:

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

--
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 Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

···

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

Hi --

On Fri, 31 Jul 2009, Lloyd Linklater wrote:

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)

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

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

Hi --

Hi --

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)

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

--
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.

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

···

On Fri, 31 Jul 2009, Rob Biedenharn wrote:

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

On Fri, 31 Jul 2009, Lloyd Linklater wrote:

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

Hi --

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.

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.)

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

···

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

On Fri, 31 Jul 2009, Rob Biedenharn wrote:

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