ASCII Code

[Lul Thyme]

Originally posted by Kuciwalker


I mention it because one of my groupmates attempted exactly the implementation I described... not every language has a primality test like that built in, and not everyone knows that such a primality test exists (I only knew because I'd seen it in the Java API).

That's exactly my point. Different people will think of different things. I remember reading on the web some people trying to use method number 1.
There's no reason why number 1 and 2 are naive, and 3 and 4 are "not naive".

[padillah]

OK, let me first say - if I'm getting anoying just tell me and I'll stop. P vs. NP has always facinated me because it looks like a simple thing but the more you understand the more it "slips away".

Between the two of you, you mention "determanistic" and "polynomial-time".

I have always understood "deterministic" to mean "measurable"... or "able to determine". Is that even remotly correct?

And what the heck is "polynomial-time"? I just have never understood that phrase.

Again, I don't need these answers for anything other than my own curiosity. Feel free to be annoyed at my math-ignorance.

Tom P.

[padillah]

Oh, BTW there's tons of Miller-Rabin algorhythms all over the net if anyone wants to look.

Tom P.

[Lul Thyme]

Originally posted by padillah
OK, let me first say - if I'm getting anoying just tell me and I'll stop. P vs. NP has always facinated me because it looks like a simple thing but the more you understand the more it "slips away".

Between the two of you, you mention "determanistic" and "polynomial-time".

I have always understood "deterministic" to mean "measurable"... or "able to determine". Is that even remotly correct?

And what the heck is "polynomial-time"? I just have never understood that phrase.

Again, I don't need these answers for anything other than my own curiosity. Feel free to be annoyed at my math-ignorance.

Tom P.

a given problem is solvable in polynomial time if, more or less, there is a number "k" such that the time required to solve a "large" problem of size "n" is less than n^k.

[Solver]

Originally posted by Kuciwalker


Google does a cute, geeky ad that requires just a little bit of thought to complete (for the intended audience).

Later, EA does another geeky ad, except it's completely trivial - type that in and add printf and you have the answer. Meh. It's a copycat and a poor one. Thus, lame.

What's more, Google gave the real interesting tasks once you went to that site. So they actually ensured that those who got through both stages are probably fairly competent & can think outside the box.

[Solver]

And BTW, spigot algorithms are your friend for the problem itself .

[Lul Thyme]

Originally posted by Solver
And BTW, spigot algorithms are your friend for the problem itself .

As far as I can tell, using such an algorithm on the google problem would yield the solution SLOWER than using a std algorithm...

See :

http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf

end of first page, for example.

Spinot algorithms are not competitive with std algorithms for finding the first x digits of constants, in general.