using until

L

Lloyd Linklater

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 = 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 = false }
currentNum += 2 until primes[currentNum] == true
end

but that just hangs the program. What am I missing?
 
B

Bertram Scharpf

Hi,

Am Samstag, 25. Jul 2009, 05:27:07 +0900 schrieb Lloyd Linklater:
I am writing a little thing to find all the prime numbers to a million.
Click to expand...

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

Lloyd Linklater

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

List.rb

Modify it to show u what ur problem is

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

David A. Black

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 = 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 = false }
currentNum += 2 until primes[currentNum] == true
end

but that just hangs the program. What am I missing?
Click to expand...


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 = true }
begin
num += 2
end while non_primes[num]
end


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

Robert Klemme

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 = 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 = false }
currentNum += 2 until primes[currentNum] == true
end

but that just hangs the program. What am I missing?
Click to expand...


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]
Click to expand...


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:
Click to expand...

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
 
D

David A. Black

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 = 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 = false }
currentNum += 2 until primes[currentNum] == true
end

but that just hangs the program. What am I missing?
Click to expand...


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.
Click to expand...
Click to expand...


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]
Click to expand...

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
Click to expand...

This was a somewhat incomplete forward reference to my "flipped logic"
version (see below).
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.
Click to expand...

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

Robert Klemme

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

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.
Click to expand...

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
 
L

Lloyd Linklater

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

Rob Biedenharn

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. :)
Click to expand...

irb> i = Time.now.to_f + 0.001; begin print('.') end until
Time.now.to_f > i
.....................................................................................................=
nil
Click to expand...
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
Click to expand...

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
(e-mail address removed)
 
L

Lloyd Linklater

Rob said:
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.
Click to expand...

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

David A. Black

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)
Click to expand...

You didn't have to figure it out intuitively; I told you on Saturday
:) (Though I garbled my example a bit.)
doSomething while condition #check condition before

doSomething until condition #check condition after
Click to expand...

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
 
D

David A. Black

Hi --

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.
Click to expand...

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
 
R

Rob Biedenharn

Hi --



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


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
Click to expand...


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
(e-mail address removed)
 
D

David A. Black

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.
Click to expand...

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

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

David A. Black

Hi --

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.)
Click to expand...

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

$ 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

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Java 8 Streams and Eratosthenes 22
How do I estimate how long it will take a calculation to complete? 8
Enumerable#to_a can run forever 3
Peculiar Behavior for a Newby to Undertstand 12
Prime number generator 11
i'm sure this must be trivial, remember i'm learning ... program included 11
Can I improve my code? 0
mathn.rb is unacceptably slow (proposed replacements) 5

Members online

No members online now.
Total: 36 (members: 0, guests: 36)
Robots: 395

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,070
Latest member
BiogenixGummies

Latest Threads

Top