Snap! user discussion

jokebookservice1

^ well, finding prime numbers has always been a hard one, but in this post I'm going to outline an algorithm and then repeatedly improve it.

First of all, let's define what a prime number is.

A positive integer that has exactly two factors.

So, let's just check all the factors up to the number itself, starting with one.

set [factors v] to [0]
set [currently testing v] to [1]
repeat until <(currently testing) = (num #)>
if <((num #) mod (currently testing)) = (0)> then // divides it with remainder 0
change [factors v]  by [1]
end
change [currently testing v] by (1)
end
return <(factors) = (2)> ::control

…but that isn't very efficient, so, how can we improve this?

First of all, there's no need to actually check for 2 factors, we just need to make sure that it has no factors between 1 and the number itself (exclusive). We have to make sure it's a whole number, and that it's greater than one, but other than that we're fine.

Ok, so how would we do this?

set [currently testing v] to [2]
repeat ((num #) - (2))
if <((num #) mod (currently testing)) = (0)> then
return <(false::red)::operators>::control
end
change [currently testing v] by (1)
end
return <(true::#00ff00)::operators>::control

But here's something, let's list the factors of 18

1 2 3 6 9 18

and look at this, we can put them into pairs!

1 * 18 = 18
2 * 18 = 18
3 * 6  = 18

Note that from each pair, one of the pair is below the square root, and the other is above the square root. This is because if you start with

sqrt(18) * sqrt(18)

then if you increase the left side, then to make it still equal 18, you have to lower the right side, making what I just said about below/above true.

Note that some numbers have integer square roots, like 9, so we have to check its square root too.

set [currently testing v] to [2]
repeat until <(currently testing) > (sqrt(num #)::operators)>
if <((num #) mod (currently testing)) = (0)> then
return <(false::red)::operators>::control
end
change [currently testing v] by (1)
end
return <(true::#00ff00)::operators>::control

You might be thinking, “isn't finding the square root a little inefficient”, and while yes, it is, it's much more efficient than all of the needless checking you would do otherwise. You only really need it to the nearest integer (rounding up).

Now then, can we get any better than this? Yep! Let's check the definition of “even”.

A number with 2 as a factor.

So, that means every even number greater than two isn't prime, since it has 2 as a factor, as well as itself and 1, making at least three factors.

So, let's change “currently testing” by 2 each time, and start testing at 3 not 2. We'll need to check if it's even at the beggining, but then continue on with the odd numbers.

So, that brings us to our final code, that's pretty efficient (I'm sure there are some more efficient algorithms, but this is pretty good).

if <<((num #) mod (1)) > (0)> and <(num #) > (1)>> then // then # is whole and greater than one
if <(num #) = (2)> then
return <(true::#00ff00)::operators>::control
end
if <((num #) mod (2)) = (1)> then
set [currently testing v] to [3]
repeat until <(currently testing) > (sqrt(num #)::operators)>
if <((num #) mod (currently testing)) = (0)> then
return <(false::red)::operators>::control
end
change [currently testing v] by (2)
end
return <(true::#00ff00)::operators>::control
else
return <(false::red)::operators>::control

end
end
return <(false::red)::operators>::control

All the code is untested, and good luck!

bharvey

So here's how I'd do it.

First we need a little helper function that generates lists of consecutive integers:

which should really be in the Tools library. Meanwhile, here it is:

Now, what's a prime number? A prime number is a positive integer that has no factors other than itself and 1. Or, to say the same thing a little differently, it's not divisible by anything in the range [2, number-1].

So we have to be able to ask if one number is divisible by another:

Now we can just express the definition in code:

Doesn't that exactly say the definition? NUMBER is prime if the set of factors between 2 and NUMBER-1 is empty.

Of course this is horribly inefficient. If you ask whether 100 is prime, we make a list of length 98 whose first item is 2, we ask whether each of these numbers is a factor of 100 (even though 2 is a factor, and that's enough to prove 100 isn't prime). And, as it turns out, we really only need to check whether any prime numbers are factors, because if a composite number is a factor, so are its factors.

But, tada, we can actually have our cake and eat it too. We can keep this beautiful elegant program that concisely expresses what a prime is and make it efficient by using streams (also called lazy lists). But I'm falling asleep so we're not doing that this evening…

Last edited by bharvey (March 27, 2017 01:51:20)

Gabriel2900

Thank you all. Here's the finished game
http://snap.berkeley.edu/snapsource/snap.html#present:Username=gay%20lan&ProjectName=is%20number%20block

MichaelOlifant

I'm working on a generator project here.

ＴｈｅＣＡＰＩＴＡＬＢＯＹＳｗｉｌｌｐｒｏｔｅｃｔｍｅｆｒｏｍｋｕｍｑｕａｔｓ．

doloop

I need help getting a javascript block to work. I've made a block that computes a linear regression that works well. I tried to do the same with a javascript block (so I can compare speed) but I cannot get the javascript version to work. I can't post an image of it here because I am not a scratcher. I've shared my project here.

I think it may have something to do with conversion of javascript arrays back to snap lists, but I am not sure.

Any help is appreciated.

doloop

For some reason my link to my shared project (above) did not “stick”, so here it is again (I don't see any way to edit my post).

Javascript project: http://snap.berkeley.edu/snapsource/snap.html#present:Username=doloop&ProjectName=LinearRegression

THIS POST I CAN EDIT!?!?!? Weird.

Last edited by doloop (March 31, 2017 15:20:14)

docaiden

Anyone want The “First Version” of snap!
I have it

REPEAL THE DMCA!!!!!!

bharvey

doloop wrote:
I think it may have something to do with conversion of javascript arrays back to snap lists, but I am not sure.

Indeed. return new List(lr)

jokebookservice1

bharvey, your definition of “prime” implies that 1 is a prime number btw

bharvey

jokebookservice1 wrote:
bharvey, your definition of “prime” implies that 1 is a prime number btw

Yeah I was waiting for someone to point that out. And the code doesn't check if the input is a positive integer either. So really before my one-liner you have to check if the input is a number, if it's an integer, and if it's greater than one.

doloop

bharvey wrote:
doloop wrote:
I think it may have something to do with conversion of javascript arrays back to snap lists, but I am not sure.
Indeed. return new List(lr)

That was it, thanks!!

doloop

doloop wrote:
bharvey wrote:
doloop wrote:
I think it may have something to do with conversion of javascript arrays back to snap lists, but I am not sure.
Indeed. return new List(lr)

That was it, thanks!!

Hmm … my snap version of the linear regression is ever so slightly faster than the javascript version. (And much easier to program!) I did not expect that.

bharvey

doloop wrote:
Hmm … my snap version of the linear regression is ever so slightly faster than the javascript version. (And much easier to program!) I did not expect that.

The first version of Snap! out the door was pretty slow for certain things, although always fast for other things. A bunch of improvements have happened since then, including making all custom reporters implicitly warped.

But it must also be that there's some inefficiency in your Javascript algorithm, since your Snap! version is running in Javascript!

bloopperson

How do I make a sprite shoot projectiles in all four directions, up, down, left and right?

bharvey

bloopperson wrote:
How do I make a sprite shoot projectiles in all four directions, up, down, left and right?

Umm, you just do POINT IN DIRECTION four times and shoot each time!

doloop

I recently discovered a really good YouTube video of Prof. Terence Parr of the University of San Francisco entitled How to Build a Virtual Machine found here: https://www.youtube.com/watch?v=OjaAToVkoTw&t=1694s. In it he discusses how virtual machine interpreters work and he actually builds a simple one.

I thought it would be really fun to follow along and build the virtual machine interpreter described in that video using Snap! So I did.

In the video, Prof. Parr creates a simple instruction set, builds an interpreter for that instruction set, and then codes a function in that instruction set to compute the factorial of a number. He then runs the code in his interpreter, and voila, the answer appears. It was great fun to do this and quite educational. I highly recommend this project to anyone interested in Snap! and in how computers work.

I've shared my project TParr - VirtualMachineInterpreter here: http://snap.berkeley.edu/snapsource/snap.html#present:Username=doloop&ProjectName=TParr%20-%20VirtualMachineInterpeter

And, I've created a short YouTube video showing it in operation here: https://youtu.be/Hmf57VKx-*

Enjoy!

Last edited by doloop (April 10, 2017 19:27:10)

doloop

Something mangled the URL for my video. Here it is again: https://www.youtube.com/watch?v=Hmf57VKx-*&feature=youtu.be

Last edited by doloop (April 10, 2017 19:39:18)

doloop

I think some “bad words” routine is replacing the two letters in my URL with an asterix. The two letters are (1) the sixth letter of the alphabet capitalized and (2) the lower case 11th letter of the alphabet.

Snap! really needs to get its own discussion forum. ;-(

Last edited by doloop (April 10, 2017 19:43:10)

gdpr533f604550b2f20900645890

Here is the video : https://www.youtube.com/watch?v=OjaAToVkoTw I remember watching it a while back.

BookOwl

doloop wrote:
I recently discovered a really good YouTube video of Prof. Terence Parr of the University of San Francisco entitled How to Build a Virtual Machine found here: https://www.youtube.com/watch?v=OjaAToVkoTw&t=1694s. In it he discusses how virtual machine interpreters work and he actually builds a simple one.

I thought it would be really fun to follow along and build the virtual machine interpreter described in that video using Snap! So I did.

In the video, Prof. Parr creates a simple instruction set, builds an interpreter for that instruction set, and then codes a function in that instruction set to compute the factorial of a number. He then runs the code in his interpreter, and voila, the answer appears. It was great fun to do this and quite educational. I highly recommend this project to anyone interested in Snap! and in how computers work.

I've shared my project TParr - VirtualMachineInterpreter here: http://snap.berkeley.edu/snapsource/snap.html#present:Username=doloop&ProjectName=TParr%20-%20VirtualMachineInterpeter

And, I've created a short YouTube video showing it in operation here: https://youtu.be/Hmf57VKx-*

Enjoy!

Wow, that is a really good project! I'll have to watch the video myself.

who needs signatures

Discuss Scratch