TB with and without O2 - Goldbach's conjecture as a test.

[RobbeK]

Still unproven the conjecture states that every even number > 2 can be written as the sum of two primes.

4=2+2
6=3+3
8=5+3
10 = 5+5 , 7+3
etc....

A benchmark test TB only and TB + O2 looking for the Goldbach partition of even numbers , input is the upper limit.

(O2 does not have the IsPrime() , so a boolean matrix has to be set up first ... )

The program outputs only the number that needed the deepest search.

best, Rob (serious difference in speed, not ?)

We can speed it up by skipping the number 2 as a prime and start with 6 :
- the only partition containing the number 2 is 4, because n-2 from an even number is even and can't be prime , so : goldbachA0no4.tbasic (running thru the odd numbers only )

[RobbeK]

Tried some other basic programming languages too (attached).

The results - limit = 1,000,000

TB = 100
Liberty basic (no LBB booster) = 750 (I used Just Basic - a stripped down version)
Same with LBB booster = 150
Freebasic with Firefly RAD = 20
FNX basic = 16 (a p-code compiler ! by Marco Waterman)
GFA compiler = 9
TB with O2 = 0.9 !!!!!!!!!!

best Rob

[mike lobanovsky]

Hi Rob,

FBSL doesn't have IsPrime() either so I've used your verbatim O2 source for my BASIC and its equivalent C, for my DynC.

My results are: thinBasic = 11328 msec, O2 = 94 msec, FBSL = 3640 msec, DynC = 32 msec.

[RobbeK]

WOW Mike -- (In the meantime I started with FBSL -- congrats for Electra !!)
Computers became really fast, not ? -- testing the Goldbach Conj. holds for 500,000 numbers is not nothing and done in no time.

-- well, ok ;-) http://www.isgtw.org/feature/researchers-edge-closer-solving-270-year-old-math-problem-thanks-grid-computing
they are up to 4 X 10^18 (but solving is a big word here, verification should be better imho).

Looking at your results the main difference in speed is between TB and FBSL probably ? and probably O2 an DynC about similar ? (just wondering)

(I may ask you things about FBSL in the future, is there an active forum ? )


best Rob

[mike lobanovsky]

Hi Rob,

Yeah, "verification" is more appropriate in this case IMO. They should probably offer a $$$ award for finding a solution... :)

My primary interest was to compare pure TB and FBSL results while O2 and DynC were added later on just as another vote in favor of JIT's against bytecode compilers. And yes, O2 and DynC should yield approximately similar results for such a short run as this. The difference is due to your measuring Oxygen's total execution time including matrix setup while DynC measures the search loops only. As I said earlier, there isn't much sense in measuring JIT's one against another as they all run in native albeit unoptimized code.

Here's an answer (http://www.fbsl.net/phpbb2/index.php) to your last question. You can address me with any further questions in a PM here or publicly there. Let's try and keep threads clean... :)

[RobbeK]

Hi Mike ,

... They should probably offer a $$$ ...
yes, they did 1,000,000 $ , but it expired in 2002 ... we're too late ;-)

About the linked document , as there are an infinite numbers of even numbers and primes, even if you examine 10^10^10^10 numbers, you will have done exactly "zero" % of them. Maybe they find patterns - but may be very doubtful.
(maybe they try to reach the lower limit of the Vinogradov Theorem - http://en.wikipedia.org/wiki/Vinogradov%27s_theorem
but that's something as e^3200 iirc )

Attached something with a more visual presentation -- probably the string manipulations make it very slow , it gives the partitions of a number and a frequency diagram. (max 10,000 is still workable imo).

Certainly the number of partitions grow and grow , but it proves nothing of course.

Thanks for link c u soon then
Rob

[jack]

hello RobbeK
what are the specs on your computer?
the timings on my computer were much slower than the times you posted, also would you post the FreeBasic source code?
I would like to try different compiler switches and see what impact if any they would have on the timing.
just run GoldbachFB and the times varied from 200 to 600 mSec, don't know why.

my virtual windows 7 machine runs on a Mac pro 2 x 2.66 GHz 6-Core Intel Xeon.

[RobbeK]

Hi Jack,

I'm running an old (recycled) computer -- the specs are in the attached file under Winaudit.jpg
Also included the source (Firefly RAD for FreeBasic) , the code is at the bottom of ....FORM.inc
Emergence Basic is very fast (also included) , it has been freeware during a very short time before it became IBasic and then IWbasic (iirc),
I have a copy if you like to have one (it has 2D and 3D capabilities and can compile into DLL's ).
(here the "gadgets" are not tuned, but it is easy to give them an XP look in case)
No idea about the fluctuations (if that's the correct English word )

best Rob

(forgot to mention : the red dots or lines in the frequence diagram are solutions of the "Weak Goldbach conj." of the numbers which have 2 partitions - it is easy to prove they are all of the form 2+prime and consequently they number is infinite and grows logaritmic )...

[mike lobanovsky]

Hello again Rob,

Concatenating strings in a loop is in fact a very bad idea. Apart from being painfully slow, such a program would also fragment its memory a lot. This may often lead to low memory resources in string-intesive applications such as e.g. text editors, RAD's, etc.

I have three timed scripts attached below. The timings are printed at the bottom of your text output box in every script. The first one is your original script unmodified and the second one is an almost vain attempt to improve it while keeping the notorious string concatenation in place.

The last one eliminates looped string concatenation completely. It uses formated output of results into a fixed-length string buffer based on the sprintf() function in the msvcrt.dll system library. The code is a little longer but calculation runs about 6 times faster. The only thing I'm not sure about off the top of my head is how to pre-calculate the length of resultant buffer that's goint to be streamed into the text box. My 32MB is a pure guess valid for an upper limit of at least 180,000.

The rest of the lag is evidently attributed to canvas drawing.

Regards,

[jack]

Hi RobbeK,
thank you for the code, it turns out that in FreeBasic the Timer function returns a double, changing the variable t to double fixed the time variation problem, FreeBasic time is now 120 mSec, if you take out the string functions the time goes down to 5 mSec.

[RobbeK]

Hi Jack, I've been too hasty then switching between those basics :-c thanks !

Hi Mike, perfect -- just what I needed !
Predicting the size of the string is something else ... as usual with prime numbers , when you open a door you find a new closed one ;-)

I mean, I can think of a system to calculate their size , but ...

(the idea is next)

Using the Gauss Legendre pi(x) function which gives an estimation of the number of primes below an upperlimit.
For the Goldbach numbers below N , you take first the ones composed with 3 then 5 , 7 .... then we get
Sum=pi(N-3) + pi(N-5) + ... pi(N-p) + .... + pi(N/2) where p=is prime and < N/2

(and pi(x)=x/ln(x) )

so , once again we need primes to calculate something about primes.

I was hoping to find something by setting up an X-axis not by the natural numbers but by just the prime numbers ---
(in the attached program the green is the Gauss-Legendre pi(x) - by morphing the X axis it became linear now )

best Rob