mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-04-24, 18:04   #34
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

An array of ints would probably be faster, if you were willing to use 4 times the memory. Of course going above the 2-4 GB watermark might cause things to slow down; I'm not sure.

A bitarray might actually be faster than an array of bytes, and it's easy to use in C#: System.Collections.BitArray. This would probably reduce memory use below 500 MB.
CRGreathouse is offline   Reply With Quote
Old 2009-04-25, 09:20   #35
Joshua2
 
Joshua2's Avatar
 
Sep 2004

21516 Posts
Default

I was wondering if you did something like that to get my source. I will trim it up a bit and post it tomorrow I guess on the website. I am not just storing a 0 or 1, I am storing a 0-255, to signify which part of the space the collision is in. Just because a^x + b^y mod n1 and mod n2 are both in the hashtable isn't a real solution unless they are both equal to the same c^z (even then it still wouldn't have to be, because they are only equal mod n1 & n2).

I tried using a int array, but it was slower. I would think that on a 64 bit computer long would be the fastest, but it wasn't. Maybe I wasn't doing it right. I should try a BitArray collections as an additional presieve that is smaller and might be faster.

Last fiddled with by Joshua2 on 2009-04-25 at 09:21
Joshua2 is offline   Reply With Quote
Old 2009-04-25, 19:03   #36
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts
Default

A "very" close hit:
(9^4280+7639^1052)/2471^1204 = 0.9999999999946931842701194196
R. Gerbicz is offline   Reply With Quote
Old 2009-04-25, 20:04   #37
Joshua2
 
Joshua2's Avatar
 
Sep 2004

21516 Posts
Default

How did you come up with that? That would be in a range that hasn't been searched before. It isn't likely to find a solution with such big exponents, thats why I'm concentrating on the smaller ones first.
Joshua2 is offline   Reply With Quote
Old 2009-04-25, 21:02   #38
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32×179 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
How did you come up with that? That would be in a range that hasn't been searched before. It isn't likely to find a solution with such big exponents, thats why I'm concentrating on the smaller ones first.
See http://robert.gerbicz.googlepages.com/beal.c

This is using a new idea: sort the powers in increasing order (store only their logarithms) and use that if a^x+b^y=c^z, then 1/2*c^z<=b^y<c^z (if we assume that a^x<=b^y), if we fix c^z then there is not too much cases for b^y and then it is a simple math to get the logarithm of a^x. This is faster then the old mod tricks. By the built-in eps=1e-10 the code is good up to bound=10^4. I haven't checked this, only started, then stopped, it would take about a day. It prints the close values to ki.txt file in a,x,b,y,c,z order one number in each line (consecutive sets are sepearted by a blank line). Not tested too much.

Note that i'm checking only gcd(a,b)=1, so it is possible that i'm printing a close hit for that gcd(a,c)>1 or gcd(b,c)>1 (obviously for a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1). And I excluded a,b,c=1 values (it is proven that those are not giving solutions, see Catalan's conjecture/theorem), because that are generating lots of errors in the code.

// needs about 1.5 GB Ram for n=10000

Last fiddled with by R. Gerbicz on 2009-04-25 at 21:03
R. Gerbicz is offline   Reply With Quote
Old 2009-04-26, 22:49   #39
Joshua2
 
Joshua2's Avatar
 
Sep 2004

53310 Posts
Default

Nice. How long does it take to check all numbers a,b,c,x,y,z up to 1000? My program takes about an hour on my computer. When you talk about bound, is that checking all variables exactly up to the bound?

BTW this isn't a senior project, its a sophmore project for my AA at a community college. I think I get why a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1, but I read it works for a,c or b,c as well. It seems these two are the same case, but I wasn't exactly sure how this would be proved, and I wanted to double check.
Joshua2 is offline   Reply With Quote
Old 2009-04-26, 23:05   #40
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32×179 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
Nice. How long does it take to check all numbers a,b,c,x,y,z up to 1000? My program takes about an hour on my computer. When you talk about bound, is that checking all variables exactly up to the bound?

BTW this isn't a senior project, its a sophmore project for my AA at a community college. I think I get why a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1, but I read it works for a,c or b,c as well. It seems these two are the same case, but I wasn't exactly sure how this would be proved, and I wanted to double check.
Yes, if you give bound then code is checking all 6 variables up to bound. For bound=1000 it takes about 1 minute on my Amd triple core, (it is using only one core). As I remember if you remove the gcd(a,b)==1 checking then you will get all false solutions also (for that gcd(a,b,c)>1), possibly multiple times, because the built-in log(1/2) value is only an approximation.
R. Gerbicz is offline   Reply With Quote
Old 2009-05-02, 03:58   #41
Joshua2
 
Joshua2's Avatar
 
Sep 2004

21516 Posts
Default

I got it to compile w/ Visual Studio 2008 c++, just had to make a (double) conversion explicit. So I don't really know c++; where does your program spend most of its time? Could you provide me a slightly more detailed explanation of what it does, because I would like to implement it in C#.
Joshua2 is offline   Reply With Quote
Old 2009-07-15, 01:24   #42
spkarra
 
"Sastry Karra"
Jul 2009
Bridgewater, NJ (USA)

33 Posts
Default

Quote:
Originally Posted by T.Rex View Post
?? Java ?? When you want a very efficient program for Math, you use either C or/and assembler, I think. Not Java... Strange idea...
Hi,
I am tackling to get a counterexample in two ways. I wrote a JAVA program that gathers the data. Right now, I am gathering data upto 9999 integers on my laptop. Once its done, then I will run another JAVA code to review the data and find if there is atleast one set of numbers as a counter example.

-Sastry Karra
spkarra is offline   Reply With Quote
Old 2009-07-16, 19:12   #43
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3×311 Posts
Default C vS Java

Quote:
Originally Posted by spkarra View Post
Hi,
I am tackling to get a counterexample in two ways. I wrote a JAVA program that gathers the data....
Hummm Since I know quite well both C and Java, since I wrote hundreds of thousands lines of code in C and Java, and since I knew very well how a Java Machine works, I'm sure the fastest language is C. However, using Java for managing the algorithms and C for coding them is fine. Just need to write JNI code.
T.
T.Rex is offline   Reply With Quote
Old 2009-10-18, 00:09   #44
Joshua2
 
Joshua2's Avatar
 
Sep 2004

10000101012 Posts
Default

http://jjoshua2.googlepages.com/beal

I published the C# source code there towards the bottom of the page.
Joshua2 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Beal Conjecture Proof Arxenar Miscellaneous Math 1 2013-09-07 09:59
Distributed NFS postprocessing poily Msieve 6 2012-12-05 12:45
New Beal Conjecture Search Joshua2 Open Projects 0 2009-04-20 06:58
distributed.net completes OGR-25 ixfd64 Lounge 4 2008-11-22 01:59
distributed proofreading adpowers Lounge 10 2004-11-05 01:54

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


Fri Feb 3 09:36:26 UTC 2023 up 169 days, 7:05, 1 user, load averages: 0.54, 0.75, 0.79

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔