mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   New Code (https://www.mersenneforum.org/showthread.php?t=15999)

JohnFullspeed 2011-08-31 09:45

New Code
 
I work on the Goldback conjecture and the authors
of the verify explain that they compute the list of the prime

Why in their method they need this list?

N even number
repeat
for i:=1 to 100
M:=N-Primes(i)
If IsPrime(M) then N:=n+2;
until N > ?????
John

Christenson 2011-09-01 00:48

That bit of programming is a simple verification of Goldbach's conjecture:

"Every even number can be expressed as the sum of two primes."

The program (if you add the correct braces) searches for small counterexamples. It needs some editing, since it needs to make output when it finds a counterexample, and a number of limits have been omitted.

They use the list of primes as a way to avoid repeatedly testing numbers for primality. Undoubtedly, the function IsPrime() also uses the list.

JohnFullspeed 2011-09-01 07:26

Thanks
 
To don't answer to the question

Many people use the list but why here?
What is the algo use?

(Sorry to use my bad english but i don't found traducer for your dialect)

John

N could have 1000 digits it is not a problem

Christenson 2011-09-01 12:52

Hint: I can read french, and your english translation makes things worse.
Hint: complete the program, and, for given N, tell me how many times I actually need to execute the inner loop, assuming a counterexample exists. Give me numbers with N=50.

JohnFullspeed 2011-09-01 19:03

Goldback
 
[CODE]
Procedure Veri_GoldBack(L:Qword);
Var I,J,W:integer;
M,N,R: Qword;
e2: double;
Label LN;
begin
I:=0;
HH:=0; // Le nombre - le NP
N:=Primes[200]+1; /// for testing Not 0 1223
a1 := GetTickCount; //timer
Offset:=0; // sortie
repeat
LN:
N:= N+2;
If N>200000 then Break;// stop here
j:=1;
repeat
HH:=N-Primes[j]; // test des divisions
if not Is_Div(HH) then Goto LN;
J:=J+1;
until J> 20;
I:=I+1; // not found
until i>1000;
a1 := GetTickCount-a1;
[/CODE]


IsPrime:
[CODE]

Function Is_Div(A: QWord):boolean;
var i,R,S: Cardinal;
E5:extended;
begin
Result:=True;
E5:=A;
R:= Round(Sqrt(E5));
i:=2;
repeat
If A mod Primes[i]=0 then exit;
I:=I+1;
until Primes[i] > r;
Result:=False;
end;
[/CODE]

Like you can see ,I verify since
N=1223+1 even. The step is 2 (even) and I stop at 200 000
So I do 99 383 verifs


And now like Jasonp,axn,Five,silver,Bssquare... you stop to answer because your times are not in the same range that me, and you thinks that I most better that you You stop to answer.
I m not better than other but it's my job.


With the bad test of division I need 0,8 ... seconds
Perhaps I can learn to you if you want
The code is not magic

The time is on my RISC for a CISC the code will be other

PS can you give me the time for
for i:=1 to 100000 do
a=isprime(i);
They all say No.

bsquared 2011-09-01 21:03

[QUOTE=JohnFullspeed;270587] [CODE]
Procedure Veri_GoldBack(L:Qword);
Var I,J,W:integer;
M,N,R: Qword;
e2: double;
Label LN;
begin
I:=0;
HH:=0; // Le nombre - le NP
N:=Primes[200]+1; /// for testing Not 0 1223
a1 := GetTickCount; //timer
Offset:=0; // sortie
[B][COLOR=red]repeat[/COLOR][/B]
LN:
N:= N+2;
If N>200000 then Break;// stop here
j:=1;
repeat
HH:=N-Primes[j]; // test des divisions
if not Is_Div(HH) then Goto LN;
J:=J+1;
until J> 20;
[B][COLOR=red] I:=I+1; // not found[/COLOR][/B]
[B][COLOR=red] until i>1000;[/COLOR][/B]
a1 := GetTickCount-a1;
[/CODE]



Like you can see ,I verify since
N=1223+1 even. The step is 2 (even) and I stop at 200 000
So I do 99 383 verifs
[/QUOTE]

I won't bother debunking the inner loop, but how can you claim to verify up to 200000 if you only run 1000 iterations of a loop that increments N by 2?

Christenson 2011-09-01 22:20

John, slow down a bit...what language is this?:pancakebunny::coffee:
Since our hardware runs at very different speeds, depending on what else is going on on the computer, and the computer itself, we count operations, rather than clock time.

And re-read carefully what I asked...we need to begin with code which is correct, and do some small counting exercises before we start trying to time things. I can compute anything faster than you if it doesn't have to be right!!!

What you have there is called a mess...and a classic example of what I was talking about in terms of giving people the wrong idea about you.

In particular, suppose Goldbach's conjecture is false for N=50. How long will the program run, and how would we know if Goldbach's conjecture is false from looking at the output of the code?

I suggest you re-start from the original fragment you copied into this thread.

LaurV 2011-09-02 03:31

[CODE]
begin
N:=Primes[200]+[B][COLOR=Red]3[/COLOR][/B]; /// for testing Not 0 1223 [COLOR=Red]{you better do postincrement of it[/COLOR]}
a1 := GetTickCount; //timer
repeat
j:=0; [COLOR=Red]{here preincrement works better, to exit the loop when is found}
[/COLOR] repeat
J:=J+1;
until (J>[B][COLOR=Red]200)[/COLOR][/B] or not Is_Div(N-Primes[j]); [COLOR=Red] {not 20, as in your program}[/COLOR]
N:=N+2;
until N>20000; [COLOR=Red]{not 1000!}[/COLOR]
a1 := GetTickCount-a1;
[COLOR=Red]{printing stuff}[/COLOR]
end;
[/CODE]I think you just wanna start flame wars. Your program is bullshit, and I believe you just typed it in some "random" fashion, and you never ran it in a computer, first of all because "comments" (in all Pascal versions I know) are given between braces {} and not by // like in C-style. Beside of the fact that your program is full of shit variables you never use (did you claim you can actually.... optimize any program???), it only checked 1001 even numbers between 1226 and 3226, and for each of these numbers only tried if it can be written as a sum of two primes "a+b", with "a" being one of the first 20 primes. Please see my comment in red.

That is, the 20th prime is 71. [COLOR=Red][B]Your program was checking if an even number in the interval 1226..3226 (in Pascal notation) can be written as a sum of a prime smaller then 72 and another prime.[/B][/COLOR] That's all. You could check that much easier and faster in Pascal using "set" operators (Pascal can do a lot of stuff with sets of objects).

See how much time do you need if you give the right values for limits, like I modified above in your code, and anyhow this won't be enough correct to verify Goldbach, if you want to go to N=200000 then you have to store the primes to 100000, just in case you run in some number which is a sum of two primes of about the same size (try playing on some superior limit of a very large prime gap). But for the solely purpose of timing, you should use the right number of iterations....

Tip: If you just copy the codesnap from above, be careful how you set the compiler's behaviour of evaluating boolean expressions, otherwise you could get an "array out of bounds" when you evaluate Primes[201] for j=201 at the most inner loop.

JohnFullspeed 2011-09-02 12:14

The original question is:

Why Zimmerman need to compute the primelist to verify Golback
In a Brute force method like thyis(I never say thatt I use it, that it is speederr orr anything like this

Christenson answer that the Brute force method is bad but don't give a method using prime list

To prove that the brute force method is false He say me try the sample withs N=50 maxi

I understand that he want to see how many time the brute force needs to verif that all even numbers <52 can be write like a sum
I write a little code to find
I do'nt say that I use It but I compute the time


For those that think that they are better than bullshiit I add a vector with the 25 sums. Before to give lessons on Pascal open a book


[url]http://en.wikipedia.org/wiki/Turbo_Pascal[/url]
Historically, Pascal comments are indicated { like this }, or (* like this *), and these can span any number of lines. Later versions of Borland Pascal [COLOR=Red]also supported C++-style comments // like this, which finish at the end of the line.
[/COLOR]
You forget to give the name of your Pascal compiler that you use to try the code

You see Christenson : no code publish, no times and more simple I never Use pascal
But when I ask how many time you need no answer: just bullshit

You are speeder than me : show me .
You give the math problem:


Choose an hard problem for the computer
or a classic suject: twin search,Aliquot,factorisation
You can use all the library you want the langage you want

To give me a handicap I make a version on windows 32.

or

You know that my job is to make YOUR code better for the computer
without change the math

So write a code
publish it
An every one can optimize it

I take the challenge to go 2 time speeder than you only because I know well the computer
I said 2 but I thinks 5...

Before to say that I m bullshit try: I wait your code

And don't forget it's the computer which make tiime not the coder


In this version N <50 but the chrono doesn't move
I set N to 10000 to have a small time 0,050 second
But it's easy to make many more faster without bullshit

Procedure Veri_GoldBack(L:Qword);
Var I,J,W:integer;
M,N,R: Qword;
Label LN;
begin
HH:=0;
N:=0; // Begin with N=0
a1 := GetTickCount; //timer
repeat
LN:
N:= N+2;
If N> 50 then Break;// stop when N > 50
j:=1;
repeat
HH:=N-Primes[j]; // test des divisions
if odd(hh) then // speeder for mod 2 and mod 5
if not Is_Div(HH) then
begin
Q[N-1]:= N;// the sum
Q[N]:= hh;// a prime
Goto LN;
end;
J:=J+1;// No limit to J
until Primes[j] > N; // overflow N<0
I:=I+1; // not found
NotFound[i] :=N; //if the Goldbak is false you arrive here and can stop
until false; // infinity loop
a1 := GetTickCount-a1;
end;

Christenson 2011-09-02 14:15

[QUOTE=Christenson;270566]Hint: I can read french, and your english translation makes things worse.
Hint: complete the program, and, for given N, tell me how many times I actually need to execute the inner loop, assuming a counterexample exists. Give me numbers with N=50.[/QUOTE]

Notes:
@Laurv: The first program could work, if the braces in the original (or the begin/end pairs) had been preserved, and the code that would execute if Goldbach's conjecture were to prove false were included.
John has completely lost it with the second program...it's hopeless and not even worth debugging.

@John
1) I haven't said brute-force is good or bad....it's just one more tool.....we all work in terms of properties of the programs. (If you think I think brute force is bad, you have to ask why I have a high rank at TF, which is a brute-force method...)
2) I wanted you to give the original program...I promise you that what you posted wasn't it. This way we can CHECK your analysis.
3) I wanted you to analyse the original program, in terms of what would happen if, say, 50 was a counterexample to Goldbach's conjecture. How many loops would be required?
4) Talk about the program, not the people. Improve the program....get it right FIRST AND FOREMOST.

JohnFullspeed 2011-09-02 17:28

Word...
 
Where is your code ? I don't search juge but idea
But you are not an 'intlectual '
You need concret (French expression not insult)

I verify the conjecture with
[COLOR=Red] 0 < N < 1 223 193 544 (( 10^ 9) I need 1' 32 [/COLOR]
(I can give all the sums: no need of verify)
It's slow? You are far? How many works before joint the WC of the forum

PS Don't say it to Christensen : the code use only 6 lines
In the version I use prime list: I found a use( not the use of Zimmer)

I wait code...

Christenson 2011-09-03 02:18

[QUOTE=JohnFullspeed;270455]I work on the Goldback conjecture and the authors
of the verify explain that they compute the list of the prime

Why in their method they need this list?

N even number
repeat
for i:=1 to 100
M:=N-Primes(i)
If IsPrime(M) then N:=n+2;
until N > ?????
John[/QUOTE]
John:

I say your code is bad because it is unreadable, and therefore the probability of its being correct is asymptotically zero. I was surprised that LaurV actually bothered to analyze it at all...it reads like a bad example out of "A manual of programming style" by Kernighan and Plaugher.

You want code??? Here's a complete example of Zimmer's algorithm in C. You probably won't want to run this with ULONG_MAX being the limit as it may take your computer a year or ten....but I imagine it could run in an hour or two if the limit was 2^32-1 instead.

Please focus on what happens at the iteration where N is 50. At that iteration lies the answer to your original question, "Why did Zimmer use Primes(i) [Primelist] function?".

Ignore, for the time being, the cost of initializing the external functions such as Primes(i) and IsPrime(i).

[CODE]
// Search for a (likely nonexistant) counterexample to Goldbach's conjecture:
// Every even number can be expressed as the sum of two odd prime numbers.
//
#define bool char //create boolean type; makes code much more readable
#define TRUE 1
#define FALSE 0
#include <limits.h> // for ULONG_MAX, check doc to see it's in fact 2^64-1
#include <stdio.h> // for printf, fprintf....
extern bool IsPrime(unsigned long P);
extern unsigned long Primes(unsigned long Rank); // Note: Primes(1)=2;
extern void Initialize_Primes(unsigned long SieveMax);

int main(int argc, char *argv[])
{
bool counterexample;
unsigned long N; // The even number being tested to see if it is a counterexample
unsigned long i;
Initialize_Primes(ULONG_MAX);
for (N=6; N< ULONG_MAX; N+=2)
{ counterexample = TRUE;
for (i=2; Primes(i) <= N/2; i++)
{ if (IsPrime(N-Primes(i))
{ counterexample = FALSE;
break;
}
}
if (counterexample)
{ printf("Counterexample to GC: %lu!\n", N);
return (1);
}
if (N%(1UL<<16) == 0)
fprintf(stderr, ".");
}
printf("No Counterexample Found to GC to %lu.\n", N-2);
return 0;
}
[/CODE]

JohnFullspeed 2011-09-03 05:38

Code
 
One time more the code IS NOT my cocde;: Ot's a sample
Sorrryu if you don't koow the difference. I explaint to you

Zimmer'man use a method with the list? ›hyu?:
I givve a samle of a logic to verify Golback to explain thhe generrrral wayy I use without the ;list Is't an argument not a final profiuct

But of course you doesn't answer, like LaureV
[QUOTE]Where is your code ? I don't search juge but idea
But you are not an 'intlectual '
You need concret (French expression not insult)

I verify the conjecture with
[COLOR=Red] 0 < N < 1 223 193 544 (( 10^ 9) I need 1' 32 [/COLOR]
(I can give all the sums: no need of verify)
It's slow? You are far? How many works before joint the WC of the forum[/QUOTE]



I wait code...

JohnFullspeed 2011-09-03 06:12

Learn...
 
Try to understand before to speak...

Let Primes be the prime iist
(as usual thhe list have 200 000 000 of values)


var
Bons: array [0..223192870] of byte;
Primes :array [0..210000000] of dWord;

procedure Load_Primes;
var i,J, size: dword; OutFile: file;
begin
AssignFile(OutFile, 'NPM.bin');
Reset(OutFile, 1);
try
Blockread(OutFile, Primes[1], 813120892);
finally
Nb_Np := (813120892 div 4);
CloseFile(OutFile);
end;
end;
Procedure Verif_GoldBack(L:Qword);
Var I,J:integer;
begin
Load_Primes:
Repeat
M:=Primes[i];
for j:=1 to 300 do
Bons[M+Primes[j]]:=1;
I:=I+1;
until M> 223092870-500;
end

I use this code for (FreePAscal)

[COLOR=Red]0 < N < 1 223 193 544 (( 10^ 9) I need 1' 32

[/COLOR]
Since I optimize and ti is many more faster
If you wannt I also can use a second Core bbut it will be more difficult for you.

Christenson 2011-09-03 09:47

John:
Notice the difference between my *sample* code, which is ready for both humans to read and gcc or other "C" compiler, and yours. Si vous suiviez mes instructions, vous comprendiez pourquoi Zimmerman a utilize le liste de nombres primes. Hopefully, LaurV will be back and let me know if I missed anything when I checked my program.

Without indentation, (hint: use the [ CODE ] and [ /CODE ] tags, and leave out the spaces to make them active), your code might be legible to the compiler but is undreadable by human beings.

Hit the "advanced" button to preview your post.

Other hints on readability:
Also, in this font, I find variables I and J to be very easy to confuse.....use X and Y if you need to.
A file you are reading from should not be called "outfile" -- it's not output at this point.
You have at least 4 arbitrary constants shown. What are they? Why aren't they symbols with meaningful names? Did you even notice that one of them looks mis-typed?(Hint: ULONG_MAX is a pre-defined constant in C giving the largest value that will fit in an unsigned long.)
How would I or anyone know if your program proves Goldbach's conjecture is false? It has no apparent output.

Finally, we aren't discussing how you might create the list of primes Primes[i]. Including it distracts from the main point of the discussion.
:never again:

JohnFullspeed 2011-09-03 19:45

Blabla
 
vous etes exactement comme les autres vous avez peur d'etre ridicule
Je vais vous faire une confidence: vous l'etes encore plus en ne repondant pas
Vous etes tous aussi grande geule les uns que les autrres Pas in de vouys ne sait se servvir d'un ordinnateur. Je retourne aux calculateurs : la u moans les mathématiciens sont bons.

Mais voous avez peir de qui.? Qu'n pauvre con de Français aille plus vite que Maathématica: Votre attitude bornée n'y change rien..
Je vous rassure vous je repards sans rien avoir appris: il n'y a que la médiocrité a apprendre et la encore desolé il y a mieux que vous
Gardez vottre code si exeptionnel et allez vous faire voir

Meerci de ne pas repondre :rien ne saurait justifier votre meduiocriyé
Fin du Débat

firejuggler 2011-09-03 20:54

*translator hat**Be warned, offensive language*

You are exactly like the other, you are afraid to be ridiculous.
Let me tell you : you are even more when you do not reply.
You are all as big mouthed as each other. Not one of you can properly use a computer. I'm going back to the calculator([I]??[/I]) :At least, there, mathematician are good.


Who are you afraid off? That a french cunt could go faster than mathemathica : Your narrow minded attitude change nothing...
Let me reassure you, i'm going back having learned nothing : There is only mediocrity to learn , and, there again, there are better people than you.
Keep your so called exceptionnal code, and fuck off.

Thanks for not answering : Nothing would justify your medicrity.
End of the debate.

------------------------------------

Now if you made less typo, it would have been easier to translate.

fivemack 2011-09-03 21:00

Mr Fullspeed will not be bothering us for a moderate period.

M. Fullspeed ne nous bruterons plus pendant quelques semaines.

science_man_88 2011-09-03 21:47

[QUOTE=firejuggler;270765]*translator hat**Be warned, offensive language*

You are exactly like the other, you are afraid to be ridiculous.
Let me tell you : you are even more when you do not reply.
You are all as big mouthed as each other. Not one of you can properly use a computer. I'm going back to the calculator([I]??[/I]) :At least, there, mathematician are good.


Who are you afraid off? That a french cunt could go faster than mathemathica : Your narrow minded attitude change nothing...
Let me reassure you, i'm going back having learned nothing : There is only mediocrity to learn , and, there again, there are better people than you.
Keep your so called exceptionnal code, and fuck off.

Thanks for not answering : Nothing would justify your medicrity.
End of the debate.

------------------------------------

Now if you made less typo, it would have been easier to translate.[/QUOTE]

yeah I had to do a lot of editing to try and find one that made some sense as well (Google translate doesn't help much some days).

science_man_88 2011-09-04 00:42

[QUOTE=JohnFullspeed;270587][CODE]
Procedure Veri_GoldBack(L:Qword);
Var I,J,W:integer;
M,N,R: Qword;
e2: double;
Label LN;
begin
I:=0;
HH:=0; // Le nombre - le NP
N:=Primes[200]+1; /// for testing Not 0 1223
a1 := GetTickCount; //timer
Offset:=0; // sortie
repeat
LN:
N:= N+2;
If N>200000 then Break;// stop here
j:=1;
repeat
HH:=N-Primes[j]; // test des divisions
if not Is_Div(HH) then Goto LN;
J:=J+1;
until J> 20;
I:=I+1; // not found
until i>1000;
a1 := GetTickCount-a1;
[/CODE]


IsPrime:
[CODE]

Function Is_Div(A: QWord):boolean;
var i,R,S: Cardinal;
E5:extended;
begin
Result:=True;
E5:=A;
R:= Round(Sqrt(E5));
i:=2;
repeat
If A mod Primes[i]=0 then exit;
I:=I+1;
until Primes[i] > r;
Result:=False;
end;
[/CODE]

Like you can see ,I verify since
N=1223+1 even. The step is 2 (even) and I stop at 200 000
So I do 99 383 verifs


And now like Jasonp,axn,Five,silver,Bssquare... you stop to answer because your times are not in the same range that me, and you thinks that I most better that you You stop to answer.
I m not better than other but it's my job.


With the bad test of division I need 0,8 ... seconds
Perhaps I can learn to you if you want
The code is not magic

The time is on my RISC for a CISC the code will be other

PS can you give me the time for
for i:=1 to 100000 do
a=isprime(i);
They all say No.[/QUOTE]

assuming you every get to come back:

[CODE]for(i=0,10,print("X\n"i);forstep(N=prime(2)+1,20,2,print("\t"N);for(J=1,20,HH=N-prime(J);print("\t\t"J);if(isprime(HH),break()));if(N==20,break()));print())[/CODE]

is a gp.exe code just like yours as far as I can tell; the main differences are I use isprime(), have set the limits lower, and have a print out of the variables values as it goes. this way you can see if anyone hits the limit ( if it does your code ( as pointed out by others) will print nothing to alert us to that fact, so it a finder but not a notification of finding code if it works at all).

Christenson 2011-09-04 04:28

[QUOTE=firejuggler;270765]*translator hat**Be warned, offensive language*

You are exactly like the other, you are afraid to be ridiculous.
Let me tell you : you are even more when you do not reply.
You are all as big mouthed as each other. Not one of you can properly use a computer. I'm going back to the calculator([I]??[/I]) :At least, there, mathematician are good.


Who are you afraid off? That a french cunt could go faster than mathemathica : Your narrow minded attitude change nothing...
Let me reassure you, i'm going back having learned nothing : There is only mediocrity to learn , and, there again, there are better people than you.
Keep your so called exceptionnal code, and fuck off.

Thanks for not answering : Nothing would justify your medicrity.
End of the debate.

------------------------------------

Now if you made less typo, it would have been easier to translate.[/QUOTE]

Thank you, and thank you Mr Xilman.

The code I posted is unexceptional; it is the product of an hour or two's work. It is only a simple brute-force search, and by no means the last word on exhaustively searching for counterexamples to Goldbach's conjecture quickly. I'm still waiting for Mr Fullspeed to analyze it and find the answer to his original question about why Mr Zimmerman used the list of primes, but by no means "holding my breath". I hope others find it reasonably workmanlike and easily understood, and that I put correctness first.


All times are UTC. The time now is 09:49.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.