The Daily WTF: Curious Perversions in Information Technology

2012-11-08 Reply Admin

Rodnas:
Before you star developers are all going to show us minor gods how it is done... i did what any sane programmer would do and searched the internet for an answer.
All i found was inefficient code. Well it is better than no code at all

If there was efficient code to do it, then any encryption based on the product of two large prime numbers would be easy to break.

2012-11-08 Reply Admin

Mark:
Phil:
What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

Ah, Boris was actually demonstrating his ability to do consulting in the real world. On the 3rd or 4th time upgrading this function, after much time billed and wasted, he would then give you something that worked. I bet Boris went far.

Do consultants actually give something that works eventually, or are you just saying that so we keep giving you another bite at the cherry?

2012-11-08 Reply Admin

of course you only check the prime numbers <= sqrt

2012-11-08 Reply Admin

Anoldhacker:
Phil:
If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

So, you check if Fermat's Little Theorem holds for the possible prime with a few candidates. If not, it fails. If so, then it starts to look like it might be prime.... http://en.wikipedia.org/wiki/Primality_test

In crypto, you are usually just looking for SOME prime number, not a definite statement about a particular number. In that case, a false negative usually not a problem.

In GENERATING crypto you are just looking for a Prime. In BREAKING Crypto you are looking for a prime which (coupled with another prime) gets you some number....of course (as someone else said) the issue is in being able to FACTORIZE the number - the primeness of the components is only important in so far as it narrows down the field to test from - but if the effort to determine primeness exceeds the saving, then you might as well just try to divide by every number, ignoring whether it's prime or not - you're kind of guaranteed that the result will be prime...

Simplified EG: need to factorize: 35 Work out primes: 2 (known) 3%2=1 => 3 4%2 =0 no good 5%2, 5%3 != 0 => good Test 35/2 no good. 35/3 no good. 35/5 - winner winner, chicken dinner

Alternative;y, forget primes.... 35/2 no good 35/3 no good 35/4 no good 35/5 Winner, Winner, chicken dinner.

Maybe (sometimes) working out if a number is prime is overkill

2012-11-08 Reply Admin

hikari:
neminem:
For the job I'm at, I had a similar experience - after the usual silly discussion questions, they gave me a couple really small programming questions, that I think I did a decent job of. Then they asked me a larger one - convert an int to its roman numeral expansion (or possibly the reverse, I forget, it was a while ago). That is the sort of problem domain I would not have had any reason to be an expert in before being asked to solve it, and my first response in a real scenario would clearly be visiting wikipedia for what the full rules of roman numerals even were. I had to ask a bunch of questions. So they said just go home, write it and email it. Interview ended at around 5 PM, I had it to them by 8 the next morning. It definitely would not have been nearly such a nice experience if I'd had to do the whole thing writing on a whiteboard with no internet.
Giving a whole week seems needlessly nice, though.

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Clocks use Roman Numerals? Well I'll be darned....

AFAIK most pedants consider IIII more correct (as in that's what Julius Scissors would have used), but the convention these days is IV.

2012-11-08 Reply Admin

Tim:
Well obviously he should have called out to a web service using XML. There must be one somewhere that can tell you if a given number is prime.
Just hope it isn't encrypted over https. Because in setting up the crypto you'll probably need some prime numbers! Recursion lurks wherever you look. If you don't see it at first, look closer.

The whole world is a fractal?

I'm off for some Almond Bread.

2012-11-08 Reply Admin

Caesar:
hikari:
Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.
Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

On the other hand we think about reuse....

If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII. Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

2012-11-08 Reply Admin

Mikey:
Caesar:
hikari:
Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.
Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".
On the other hand we think about reuse....
If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII. Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

Don't be ridiculous! You count gladiator victories by throwing another stick on the pile. Chiseling in stone is for constants, not variables.

havokk · 2012-11-08 Reply Admin

Caesar:
Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

As far as I understand it, roman numerals were invented by people carving notches into tally sticks. They are an ordinal representation. Carving 9 notches into the tally stick gives IIIIVIIII, which is then abreviated to VIIII (since a V implies four Is before it). Carving 19 notches is IIIIVIIIIXIIIIVIIII, abbreviated to XVIIII (since X implies IIIIVIIII before it).

2012-11-08 Reply Admin

TRWTF is how did the prime candidate ever graduate from electoral college?

And that test of integrity, that should be illegal.

2012-11-08 Reply Admin

What I found interesting about this article was that I had written up two of my own prime-testing programs, one a brute force checker (from 1 to sqrt(number)) and one that only checked a list of already found prime numbers, and added to the list if the number was found prime. I was quite proud of the last one, giving it the ability to "learn" what numbers needed to be checked, but it ended up taking ~45 times longer than the brute force method(2050 seconds, about 34 minutes, as compared to 45 seconds for the brute-force check) to calculate what numbers up to 1,000,000 were prime.

Oh Well.

(note: I'm not a professional (read: I'm a complete amateur) writing in Java))

hikari · 2012-11-08 Reply Admin

Mikey:
Caesar:
hikari:
Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.
Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".
On the other hand we think about reuse....
If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII. Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

For things of a transitory nature Romans used wax tablets. For things that needed to be permanently recorded, they wrote them down on papyrus, parchment, or vellum. Romans highly respected and prized the ability to write.

2012-11-08 Reply Admin

Anon:
What I found interesting about this article was that I had written up two of my own prime-testing programs, one a brute force checker (from 1 to sqrt(number)) and one that only checked a list of already found prime numbers, and added to the list if the number was found prime. I was quite proud of the last one, giving it the ability to "learn" what numbers needed to be checked, but it ended up taking ~45 times longer than the brute force method(2050 seconds, about 34 minutes, as compared to 45 seconds for the brute-force check) to calculate what numbers up to 1,000,000 were prime.
Oh Well.

(note: I'm not a professional (read: I'm a complete amateur) writing in Java))

Not 10 seconds after I hit "submit" I realised a way to drastically reduce the amount of time required for the second method. It now takes just under 3 times as long (174073 milliseconds as opposed to 62551 milliseconds. And yes I'm using real-time clocks, as I didn't need any big-O notation to realise it used to be crazy innefficient).

herby · 2012-11-08 Reply Admin

jay:
When I was in high school, we once had a programming contest where the problem was to write a program that would produce a list of all the prime numbers less than 100. Entries were to be judged based on accuracy, conciseness and efficiency. Namely, any programs that produced incorrect results failed. Working programs were then scored by multiplying the number of lines of code (excluding comments) by the run-time, and low score wins. (Which, by the way, I think is an excellent scoring system.)
A friend of mine submitted a program that looked basically like this (I don't have the original listing, but this was the basic idea):

10 PRINT "2,3,5,7,11,13,17,19,23,29,31,37,41,43,47" 20 PRINT "53,59,61,67,71,73,79,83,89,97"

His entry had the fewest lines of code and the fastest run-time, so under the rules, he should have won. He also commented that he thought the algorithm was very easy to understand and so the program was highly maintainable. But the teachers disqualified him.

Many years ago, there were always students posting to various language groups on usenet. On comp.lang.c this problem came up quite often in the beginning of the school year. While the number of primes was usually those less than 1000, the given answer was always the same for the "can you give me a program" question. Yes, just a bunch of print statements with the numbers included.

Most likely the student realized:

Yes, the answer WAS correct as it did print the correct numbers.
The answer was likely to get a failing grade since it did now show an algorithm.
A little research was in order (before Google!).

This falls into the category of answering questions with the word "or" in them with "yes" (eg: Are you male or female?).

2012-11-08 Reply Admin

PedanticCurmudgeon:
So TRWTF was left out of the article entirely. How typical.

Hey, don't knock it. Obfuscated WTFs are way more fun to figure out. :)

2012-11-08 Reply Admin

Wrong Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved

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

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

2012-11-08 Reply Admin

Matthew:
Wrong Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved
http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

It blows my mind that you can determine that a number is prime without knowing any of its factors. I need to brush up on my number theory.

I'm almost just as surprised that JRebel has found a pig large enough so that a single strip of bacon from it can completely encircle a Ferrari.

Man, everything is impressive today.

2012-11-08 Reply Admin

No wonder he was nervous...

-Harrow.

2012-11-08 Reply Admin

Matthew:
Wrong Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved
http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

Well...IMHO (which is probably worth less than all you cleveries out there) the problem is that the security of RSA relies on the unpredictability of primes. Once primes are shown to follow a pattern (which as I understand it is one of the corollaries to the Japanese Mathematician's paper) then RSA becomes considerably less secure, because we suddenly have a quick way to verify the factorization that we are doing is really involving primes...

That said, IIRC (and it's a long time since I did anything involving RSA - and only ever in a school environment) the RSA problem is about taking two primes p,q and then multiplying (p-1)(q-1) rather than pq (pq is used, but I don't think known). What this means is that the problem is not quite as straight forward as factoring into primes.... eg: p=7, q=11 (p-1)(q-1) = 6*10 = 60 (2,3,4,5,6,10,12,15,20,30) all divide that. Of course, it's still rather advantageous to be able to know which numbers are prime, so that we can test prime-1.....

And I could be totally wrong....I'm no mathamagician.

Coyne · 2012-11-09 Reply Admin

Anonymous:
Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Another simple hack can cut it to by another third to 2667 numbers: Alternately increment by 2 and 4, starting with 5. That not only skips evens, but also numbers divisible by 3.

Addendum (2012-11-09 01:00): Oh, and alternating the inc: inc = 6-inc

Steve The Cynic · 2012-11-09 Reply Admin

jMerliN:
It blows my mind that you can determine that a number is prime without knowing any of its factors. I need to brush up on my number theory.

If N is a prime, I (by definition) know all its factors: 1 and N. A prime has no other factors but 1 and itself. Go back and check your sources again...

Cbuttius · 2012-11-09 Reply Admin

My "difference of squares" rule is what I use to calculate if numbers are prime in my head. With regards to mental arithmetic, I find squaring fairly simple and working out if a number is square fairly simple too.

Of course if you were using a computer program to do this you would be able to store a table of squares.

That mine had 19 as the first prime factor made it perhaps less efficient for this particular formula. It is generally more efficient when the number actually is prime, and when the prime factors are higher.

Take as another example 2773. Yes, I picked this number on purpose this time.

You go through your early checks but when you see the square root is just under 53, and work out that 53 is a valid "top" number to try for it, you will immediately arrive at the fact that 53 squared is 2809 which is 36 more than the target number, which means 2773 is 47 * 59.

Addendum (2012-11-09 04:49):

2773 is 5 mod 8, 1 mod 9, 3 mod 5, 1 mod 7. We're looking for numbers that are odd, 1 or 8 mod 9, 2 or 3 mod 5 and 1, 3, 4 or 6 mod 7.

53 satisfies all of those. Note the mod 9 rule eliminates more than any of the others here. 73 would have been the next eligible target, followed by 127.

2012-11-09 Reply Admin

Meh,

This is pretty typical of what I expect from developers really. Mainly ignorant and egotistical.

There are very few good developers.

2012-11-09 Reply Admin

verisimilidude:
if (($Number > 0) AND ($Number < 1)) { return (FALSE) } else { return (TRUE) }
I see his level of expertise right there. If he can't do

return ($Number > 0) AND ($Number < 1)

then his code it too wordy for consideration.

A lot of less-experienced devs seem to have a blind spot for the fact that you can put a boolean calculation directly into a return statement or a function argument, even if the same people have no trouble writing "return a * b + c" for a numeric type.

Can you still blame BASIC for this nowadays? :-)

JimLahey · 2012-11-09 Reply Admin

I was going to say something along those lines. Judging by his efforts he should be writing best practice guidelines for www.php.net

2012-11-09 Reply Admin

Mike:
So judge the code, not the algorithm.
Only if the code is good should you even consider looking at if the algorithm is good.

Dammit! All my code contains algorithms!

ASheridan · 2012-11-09 Reply Admin

chubertdev:
below the fold.

This is TRWTF. The fold is for print, not for web. Anyone who says otherwise is stupid and/or delusional.

2012-11-09 Reply Admin

Primes is in P jackass. Look it up.

2012-11-09 Reply Admin

StupidTheKid:
Hum, you realize that making an efficient prime number detector for all possible values is currently impossible. The difficulty of finding prime numbers is what makes RSA secure after all...

Wrong. What makes RSA secure is the difficulty of finding the factors of the product of two large primes. If it was hard to find large primes, then RSA wouldn't work at all, because you need to find two large random primes to create the keys.

2012-11-09 Reply Admin

ASheridan:
chubertdev:
below the fold.
This is TRWTF. The fold is for print, not for web. Anyone who says otherwise is stupid and/or delusional.

Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

Just one simple example: Bolt http://dictionary.reference.com/browse/bolt?s=t

ASheridan · 2012-11-09 Reply Admin

Chris:
Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

I realise that the word is being used to mean something else, but it's really not applicable. The fold doesn't exist on a screen where a huge mix of resolutions means you can't ever know where it is. So sure, morph the word all you want, it's still wrong.

chubertdev · 2012-11-09 Reply Admin

ASheridan:
Chris:
Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

I realise that the word is being used to mean something else, but it's really not applicable. The fold doesn't exist on a screen where a huge mix of resolutions means you can't ever know where it is. So sure, morph the word all you want, it's still wrong.

What word would you use? Google is failing me when it comes to finding a better one.

ASheridan · 2012-11-09 Reply Admin

chubertdev:
What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

2012-11-09 Reply Admin

da Doctah:
(1) Test last digit for even/odd. (2) Test last digit to determine whether divisible by 5. (3) Starting with 3, test for divisibility by numbers ending in 3, 7, 9, or 1.
I just knocked about another 20% off your execution time. You're welcome.

Nice try, but no.

Is it faster for the computer to extract the last digit and then test that for even/odd or divisible by 5, rather than testing the number as a whole? How are you going to extract the last digit? If you say, "Convert the number to a decimal string, then convert the string to a character array, then examine the last digit", big time fail. That would require multiple divisions by 10, creating new objects, etc etc. No ways that's going to be faster than just dividing by 2. Even if you think a little harder and say, okay, all we need to do to get the last digit is to take the number mod 10 ... well, how is

lastdigit = number mod 10
if lastdigit mod 2 = 0 then ...

going to be faster than

if number mod 2 = 0 then ...

You're doing two mods instead of one. I don't see how that helps.

Similarly, "only try numbers that end in 3, 7, 9, or 1". How do you find those numbers? You seem to think that

lastdigit = x mod 10
if lastdigit mod 2 = 0 then return false
if lastdigit mod 5 = 0 then return false
for n = 3 to sqrt(x)
  lastdigit = n mod 10
  if lastdigit = 3
    or lastdigit = 7 
    or lastdigit = 9
    or lastdigit = 1 then
      if x mod n = 0 then return false
return true

will be faster than

for n = 2 to sqrt(x) step 2
  if x mod n = 0 then return false
return true

Moving two of the tests outside of the loop does nothing for run time. You still have to do the compares. No performance gain there. Plus it takes more code.

As to the rest, do you really think that doing 2 mods and 5 compares is faster than 1 mod and 1 compare? Why would that be true?

The lesson to be learned here is: Just because a shortcut works for a human being looking at decimal representations doesn't mean that it will be helpful for a computer looking at binary.

2012-11-09 Reply Admin

ASheridan:
chubertdev:
What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

And furthermore, no concept from the print industry can or ever will be a valid analogy for a similar concept on the web?

That being the case, what word would you use for web content that is not immediately visible (ie without scrolling) after page load?

Not because the concept of "page load" has any meaning whatsoever in the print industry, obviously. Just curious.

2012-11-09 Reply Admin

MightyM:
Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.
Actually you only need to iterate to the squareroot of $val.

And you don't have to compute the square root in order to do that. You can just square $i and compare to $val. Additionally you can check divisibility by two outside of the loop and only check odd numbers in the loop. I think this is the fastest you can do before it starts getting complicated:

function isPrime($val) {
	if ($val < 3) return $val == 2;
	if ($val % 2 == 0) return false;
	for ($i = 3; $i*$i <= $val; $i+=2) {
		if( $val % $i == 0 ) {
			return false;
		}
	}
	return true;	
}

The part about skipping even numbers can be generalized. But by the time you generalize that, you no longer need equal steps between the candidates for your divisor, and then it starts getting complicated.

Skipping even numbers is simple and saves you 1/2 of the execution time. Skipping numbers divisible by three only saves 1/3 of the remaining execution time. The payoff decreases with every prime you avoid this way, and complexity increases.

If you for example consider the primes up to 7, you get a cycle of length 210 of which you have to test 48 of them. You can precompute such a cycle of what length you prefer. I think by the time the length of the cycle would exceed the square root of the largest candidate to consider it no longer pays off. That means the length of the cycle needs to be less than the square root of the square root of the number. If the numbers are 64 bits, you'd reach the limit already when you have multiplied 2, 3, 5, 7, 11, and 13. Multiplying by 17 as well would give you a number which is larger than sqr(sqr(2^64)). I don't think the theoretical 16% savings from including 11 and 13 would be enough for me to bother implementing this algorithm.

chubertdev · 2012-11-09 Reply Admin

ASheridan:
chubertdev:
What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

2012-11-10 Reply Admin

This is a prime comment http://thedailywtf.com/Comments/AddComment.aspx?ArticleId=7437

2012-11-11 Reply Admin

I was under the impression that factorizing prime numbers is exceedingly simple.

2012-11-11 Reply Admin

Brent:
Remy Porter:
If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

That's a very important thing to do. I have a friend that when asked to do the Fibonacci Sequence, proceeded to quickly work out the closed form expression and coded that. This confused the interviewers to no end.

The closed form implementation is not equivalent in practice to the recursive implementation. Did your friend know that?

2012-11-11 Reply Admin

k:
I was under the impression that factorizing prime numbers is exceedingly simple.

Yes, if you know they're prime.

Coyne · 2012-11-11 Reply Admin

Some Guy:
A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

When you test a variable using the == operator, it evaluates the type of the lvalue to find the correctly-typed internal value of the rvalue to compare against the lvalue.

When you test a variable using the === operator, it evaluates the type of the lvalue against the type of the rvalue, and if that matches, it then evaluates the value of the lvalue against the value of the rvalue.

The reason your third checkInteger fails is because it coerces the type of the lvalue. When you cast (int)$num, it's creating a copy of $num, but setting its type to int. Then you're comparing type-for-type against an uncoerced $num. If $num is anything but an int already, this implementation of checkInteger will fail.

A correctly idiot-proofed PHP function should always treat "1" the same as 1. If a PHP-hack-claiming-to-be-a-dev called checkInteger("1"), it should work correctly and return true.

But wait! There's another WTF buried here. Since the (int)$num takes the internal integer representation from $num and makes it the "real" value of that instance of $num, then compares it to the original $num's internal integer instance, this function effectively proves nothing but identity.

Think of PHP variables as a struct:
struct PHPVar {
  int typeEnum;
  int intVar;
  float floatVar;
  string stringVar;
  bool boolVar;
  object objectVar;
  int* refVar;
}
[---snip---]

Oversimplified just a bit. Yes, a PHP variable is a struct, but one member of the struct is a union (the item called "value", here).

Casting can't work that way exactly, because if you change the type, the content of "value" would also have to change, since these variables are overlaid and not separate primitives.

So if the types of two elements of an "==" compare are not of the same type then a cast would have to occur (explicit) or implicit and so your example at the end would happen more like this:

If you have one that's set up like so:

PHPVar1 {
  union {
    lval;  // doesn't exist
    dval;  // doesn't exist
    str = "1";
    *Ht;   // doesn't exist
    obj;   // doesn't exist
  }
  type = 's';   // string type
}

When you cast it to an int, you get this:

PHPVar1 {
  union {
    lval = 1;     // integer value
    dval;  // doesn't exist
    str;   // doesn't exist
    *Ht;   // doesn't exist
    obj;   // doesn't exist
  }
  type = 'l';   // string type
}

So a cast can't simply just change the type; it also has to set the correct member of the union, in order to ensure that the structure is correct for the new type.

I've done a little PHP, and I'm not sure it is a WTF in whole (though it certainly contains it's fair share of RWTF's, which isn't surprising given its history).

ASheridan · 2012-11-12 Reply Admin

What content is that? Is that content viewed on a laptop screen, a large widescreen, a TV, a standard circa 90s 4:3 monitor? Just giving that unknown quantity of hidden content a name that means something different in the print industry does not make the issue of not knowing how much content is actually shown/hidden go away.

ASheridan · 2012-11-12 Reply Admin

chubertdev:
If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

Cbuttius · 2012-11-12 Reply Admin

If your target number is 1 mod 4 then you can also test if it is the sum of two squares.

If it is not the sum of two squares it is definitely NOT prime. However if it is, that is not a proof that it is prime.

e.g.

13, 17, 29, 37 and 41 are all the sum of two squares, but 21 and 33 are not.

(13=4+9, 17=1+16, 29=4+25, 37=1+36, 41=16+25)

25 is itself square as well as being 9+16 and 45 is 9+36, so as I said, being the sum of two squares is not a proof of primeness, but failing to be such is a clear test of non-primeness.

Assuming you have a table of squares less than your number you can thus eliminate some numbers without any divisions at all.

Note that if the number is 3 mod 4 it will never be the sum of two primes.

chubertdev · 2012-11-12 Reply Admin

ASheridan:
chubertdev:
If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

A comment is more important just because it happens to be #52 instead of #48? :headscratch:

ASheridan · 2012-11-12 Reply Admin

chubertdev:
A comment is more important just because it happens to be #52 instead of #48? :headscratch:

Now you're just being deliberately stupid.

2012-11-12 Reply Admin

chubertdev:
ASheridan:
chubertdev:
If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.
Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.
A comment is more important just because it happens to be #52 instead of #48? :headscratch:

I'll "fold"... Where do I go to change the count for comment pagination on this site?

2012-11-12 Reply Admin

Fast naive solution in python

def is_prime(n): return n >= 2 and all(map(lambda d: n % d, range(2, int(n ** 0.5) + 1)))

def primes(n): i = 2 while i < n: if is_prime(i): yield i i += 1

2012-11-13 Reply Admin

JC:
"Hum, you realize that making an efficient prime number detector for all possible values is currently impossible."
No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

"Prime Factorization" is finding which prime numbers multiply together to make the original number.

Factoring can be done trivially in time equal to the square root of the number to be factored. The factors are efficient, it's just that numbers can be arbitrarily large.

The Prime Candidate

Leave a comment on “The Prime Candidate”