Posts by Ethian
log in
1) Message boards : Science : Question about the client algoritm... (Message 11658)
Posted 2515 days ago by Profile Ethian
That has already been suggested (by me, and others), but since it cannot keep track of the amount of steps, it might be less beneficial to mathematicians ;)
(however, it does speed up calculations, since you only have to check up to current n, if the number drops below that, it has already been checked. Also, (repeated) division by 2 is incredibly easy in binary, simply slash all trailing zeroes, and there you go.
Multiplying by 3 and adding one can be done by shuffling your bits around and 1 addition, too
(11011 * 3 + 1 =

0110111 (times 2 + 1, aka add a 1 in the last place)
0011011 (original number)
--------+
1010010 (per definition a 0 on last spot, so it can be removed straight away if you feel like it)

Hmmm, maybe you can even build a checker in Minecraft if you feel like it :D
2) Message boards : Number crunching : Tasks not running on linux x86_64 ati (Message 11077)
Posted 2556 days ago by Profile Ethian
Probably a stupid question, but did you enable the use of the GPU? (Advanced, Preferences, Use GPU while computer is in use) That, or another ticbox might be unchecked... Same on this site, under My Account, Collatz Conjecture preferences, where you have to manually tick the GPU-box... and uncheck the CPU one, unless you like wasting power ;)
3) Message boards : News : Deer Amber Alert (Message 10411)
Posted 2618 days ago by Profile Ethian
Or, ofcourse the reasoning of someone who doesn't see the difference between a dog and a deer :) I'm quite certain both would taste delicious, but imagine the public outcry if i shoot a deer...

<- one of those nasty vegetarians :P
4) Message boards : Science : The Collatz Conjecture (Message 10410)
Posted 2618 days ago by Profile Ethian
Since no one can store all results (number + number of steps to reach 1),
I wonder why we calculate the number of steps at all !?

For a given starting number 'a' we could stop counting the steps as soon as
the current value 'x' is lower than 'a'. We know each number below 'a' already
has been proven to reach 1.

pseudo code without optimisations (well, a bit C related):
x=a;
do {
if (x&1)
x=x*3+1; // odd
else
x=x/2; // even
} while (x>a);

Of course, we just have to detect a 'running away' and a 'loop' scenario.
'Best Of' data could be taken from the number of iterations.
We just need to calculate odd numbers from the WU ranges.
Optimisations should almost be the same as for the current implementation.

At least on 3 years old 2.2 GHz CPU, a current WU takes about 16 hours to calculate. The above code (without optimizations) is about 10 times faster...

What do you think ?

I've been toying with that idea as well, and have put your script to C#, where it's doing quite OK. However, it's definately slower than a full WU... 1G numbers takes about 20 seconds here (Q6600, 2.8Ghz, 1 core). Slicker claims about 600M numbers checked per second, at a higher N too (which shouldn't matter much for this method). So let's say it's still a tiny weeny bit slower. I can't find how many numbers there are in 1 WU, but I'm sure Slicker or Gipsel can tell you :)

The routine in question :
public static int Collatz (int n)
{
int m,counter=0;
m = n - 1;
while(n > m)
{
if(n % 2 == 0)
n = n/2;
else
n = 1+n*3;
counter++;
}
return counter;
}
Throw a nice loop around it ( for(int n=5;n<huuuugenumber;n++) {}, you know the drill :P ) and go for it, but in order to speed things up, you might need assembler magic :)

On the other hand, i'm currently looking at the binary representation of numbers, and so far it seems the amount of "1"s can only decrease... whereas the number of zeroes (which are lovely, since division by 2 in binary is only too easy) goes everywhere... Probably nothing, but hey :)
5) Message boards : Science : Largest number checked? (Message 8541)
Posted 2766 days ago by Profile Ethian
ty ;)
I know this is not 'proof', but it's the best we can do. If it can't be proven wrong, i simply assume it is correct. Checking all numbers would be silly, but collecting data on the progress would be nice, since i assume (again) that the amount of steps to reach 1 and the size of the number are correlated in a somewhat linear way. Why? Since there is no way to determine whether this number or the next will have a longer path to 1, chances are that the numbers higher up are coming to a random number as well. Adding all those chances should mean the average down-to-1-time is doubled when number size doubles.Checking is easy, the WU-time should simply keep up with the size of the numbers on test ;)
6) Message boards : Science : Largest number checked? (Message 8430)
Posted 2774 days ago by Profile Ethian
I know that he won't even try to keep a database with how long the numbers take to get to 0, but you can't even know which one takes longest to 0, only which one takes longest to get below the original value. Depending on that number, it may or may not take ages to get to the 4-2-1-cycle.
@Don : it's a nice script, and indeed, depending on your desires, it does the job. However since i'm (personally) most interested in proving (by trial) that the theorem is correct, simply rushing through all the numbers as fast as possible will do. That means assembly magic if possible, and else a nice and quick C(++) or Fortran routine does the job. I think your script could be done in Fortran just as easy ;)

pseudocode :
integer n
do n=5,10000
if(n.eq. 4) then
write(iwr,*)reached 4 for n=',n
enddo
endif
if(n=odd) n=n*3+1 ! *
else n=n/2
endif
enddo

* This bit is trickiest, and the limiting step. Doing it bitwise would make this a hell of a lot easier (last bit zero = delete last bit, else multiply by 3, last bit = 0 and the next bit +1).However... I have no idea how to handle that, so I trust Slicker that he found the faster way ;)
7) Message boards : Science : Largest number checked? (Message 8331)
Posted 2780 days ago by Profile Ethian
This too counts completely back to 1.
I think there's 2 simplifications that can be made, if you only care about checking the conjecture.
a. Stop counting when the number reaches a value below starting level. Say we test 17, which goes to 52, 26, 13, and since we started at 0, 13 was already tested, and confirmed not to be an exception. Therefore, you can stop right there, instead of calculating the other steps.
b. Skip all the even numbers, since they're going down below starting value in their first step.
The drawback is that you loose the records, so you don't know how long exactly it took to get to 1.
8) Message boards : Number crunching : Optimized Applications (Message 7102)
Posted 2841 days ago by Profile Ethian
As said, a GF 9100 only has a measly 8 stream processors (the things doing the actual crunching), whereas even a 4650 has a sweet 320 of those things, making it a lot faster. Your 9100 may have a higher number (which means completely nothing, be aware!), but it is the absolute light-edition, baked on a chipset, only good for displaying a nice background in Windows. If you want to make the computer fly, add a nice GPU, a 5770 (or 4770, for even less money, and OCable like mad), and go for it. Don't be tempted to take an NVidia unless you know damned well why (and even then, don't) ;)

A CPU will on this project loose against a GPU, so i suggest using your CPU-power on another project.
Just for good measurement, the optimized apps do give a big boost, but are generally downloaded automagically, so you might already have one (when running Windows).

As a sidenote to Gipsel and the other devvers : Linux 64-bit : 1 WU takes 1500 seconds, whereas those same WUs (ok, actually different ones, but the same series) under WinXP 32bit run in 1100 seconds...
9) Message boards : Number crunching : What's your bet for GTX470/480 performance at Collatz? (Message 6768)
Posted 2857 days ago by Profile Ethian
Well, the GTX4X0 might come close to the 58X0-cards, but for the double power consumption, i think it's still not a good choice. 300 Watt for a single GPU is too much in my opinion, especially if i want to run 24/7 apps on it (pushing my power bill through the roof). But let's first see if we can actually get one, for a decent price. ATi has some margin (smaller chips), so i'll wait for the price war to begin. Whoever looses, we win :D
10) Message boards : Science : Largest number checked? (Message 6589)
Posted 2866 days ago by Profile Ethian
Probably some home-testing from Slicker & Co, to cover the gap between the 3x+1@H and Collatz.
(I'm still amazed the starting numbers are this high... We only increased the upper bound by less than a percent... in 6 months time, using high-end GPU power, that was not available 10 years ago)
11) Message boards : Number crunching : SIGSEGV segmentation violation errors (Message 6510)
Posted 2871 days ago by Profile Ethian
Thanks, it turned out to be the QT4-libs... :(
(driver is now the 10.3 version, which works out-of-the-box, without using the karmic-specific package, which seems broken). Waiting for WUs to crunch.
12) Message boards : Number crunching : SIGSEGV segmentation violation errors (Message 6496)
Posted 2872 days ago by Profile Ethian
When testing the collatz-ATI_64-app, it fails with the message in the topic title.

The stderr.txt gives the following text :
-----------------------------------------------------
shmget in attach_shmem: Invalid argument
19:09:15 (12189): Can't set up shared mem: -1. Will run in standalone mode.

Running Collatz Conjecture (3x+1) ATI GPU application version 2.01 by Gipsel (Linux64, CAL 1.4 - R1.5 multi-GPU Support)
Reading input file ... done.
Checking 4294967296 numbers starting with 2361185725354183731560
CAL Runtime: 1.4.515
SIGSEGV: segmentation violation
Stack trace (14 frames):
./collatz_2.01_x86_64-pc-linux-gnu__ati14(boinc_catch_signal+0x49)[0x40eb79]
/lib/libpthread.so.0[0x7f86ae2cd190]
/usr/lib/libaticaldd.so[0x7f86ac8dca9a]
/usr/lib/libaticaldd.so[0x7f86ac8dc855]
/usr/lib/libaticaldd.so[0x7f86ac8d8f0f]
/usr/lib/libaticaldd.so[0x7f86ac8d0835]
/usr/lib/libaticaldd.so[0x7f86ac7f2553]
/usr/lib/libaticaldd.so[0x7f86ac91a0fa]
/usr/lib/libaticaldd.so[0x7f86ac9136c5]
/usr/lib/libaticaldd.so[0x7f86ac923a35]
./collatz_2.01_x86_64-pc-linux-gnu__ati14[0x407363]
./collatz_2.01_x86_64-pc-linux-gnu__ati14[0x4091ee]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7f86adf6dabd]
./collatz_2.01_x86_64-pc-linux-gnu__ati14(__gxx_personality_v0+0x1b1)[0x404cc9]

Exiting...
shmget in attach_shmem: Invalid argument
------------------------------------------------------

Operating conditions : Ubuntu 9.10 64 bit (all updates, latest kernel, but no problems recognizing the GPU so far), ATi 4770, all dependencies found. BOINC downloaded from the site, and extracted locally. Other projects run fine, Collatz-CPU-units seem to be OK as well.

Is this some stupidity from my side, or just Ubuntu pulling tricks on me?
13) Message boards : Number crunching : Can't report - Server Can't Open Database (Message 4224)
Posted 2967 days ago by Profile Ethian
I bet you something Slicker is working long hours on this... For now, so be it. Migration problems probably...
14) Message boards : Number crunching : Are you ready? (Message 4134)
Posted 2972 days ago by Profile Ethian

It took years to complete becuase various project's requirements kept getting in my way. I could only work on it in bite size chunks that otherwise didn't affect the schedule of releasing a new client for a project. It would not have been any different for any of the volunteer developers.


And right there is where you can make the difference. If you have a decent plan, and specs, you throw it online, and everyone can help solve the problems along the road. Someone elses problems are always easier, so let them help you :) Doing it all yourself means you spend a lot of time on things, especially if you're already busy. Many hands make light work... and if someone checks it before throwing into the next build, it's proper work as well.
15) Message boards : Number crunching : Linux 64 bits GPU time (Message 3831)
Posted 2981 days ago by Profile Ethian
Does your GPU heat up? How much CPU-power does it use? (if necessary, ">sudo apt-get install htop" should get you a decent, though CLI, CPU-monitor)
16) Message boards : Number crunching : Proposed new BOINC credit system (Message 3503)
Posted 2993 days ago by Profile Ethian
True, BOINC has power, and it is standardizing DC efforts. Applause for that. However, if it continues in its current direction, limiting the freedom of developers, and limiting the effectiveness of GPUs or optimizations, i think it starts to smell like Microsoft.

Next to that, if i see my GPU client run with no BOINC backup whatsoever, i think it might be very feasible to just run Collatz without BOINC. The problem to most users is probably that they will loose their familiar interface, which hurts. The die-hard clan running CLI-based DC is pretty small (ask PSP-PRP for example ;) ).

"Paul D Buck" wrote:
About one in six people that try BOINC do more than a few tasks ...

True... The same goes for Linux, and several more programs. It just means the app is a bit picky about its friends ;)
17) Message boards : Number crunching : Rising pending (Message 3490)
Posted 2994 days ago by Profile Ethian
Might not be, as the turnaround time is also depending on the WU queue that you have. My computer grabs enough WUs to keep it running for say 4-5 hours, so that means i have less WUs now. Turnaround time would still be the same 6-8 hours average. (sorry, but i can't sleep with my GPU fan blowing around, so the thing goes down at night, increasing turnaround a bit)
18) Message boards : Number crunching : Linux 64 bit ATI application (Message 3482)
Posted 2994 days ago by Profile Ethian
HD4770 takes about 22 - 24 minutes per WU, so say 1300-1400 seconds. Ubuntu Karmic, right now CPU-limited (2.8Ghz Core Quad)
19) Message boards : Number crunching : Proposed new BOINC credit system (Message 3470)
Posted 2995 days ago by Profile Ethian
I really don't get why every project should have the same credits per X time stuff. Say we here suddenly develop a far better way to calculate our WUs, which unfortunately doesn't work on all architectures. Should we then grant more credit to the fast guys (and get SETI mad), should we force them to a new client and cut their credits (which means older computers get a free credit boost for example), or just forbid development of a new client to prevent such nasty evolutions from happening? I personally would hate to see RAC drop like mad, and thus eliminate any chance to climb in the competition. (See eOn for a nice example of what happens then. Stalemate for all teams, unless you have a truckload more power than the team above you, and can wait a long time)

Just face it, DA and his friends got themselves in a nasty pickle, and now try to bluff/fight their way out of it. The question then is whether BOINC can live without DA, or whether Collatz can live without BOINC.
20) Message boards : Number crunching : Linux 64 bit ATI application (Message 3218)
Posted 3005 days ago by Profile Ethian
While i'm not getting any work (just joined, that might be the problem), i don't mind testing for you

Ubuntu 9.10_64 (Karmic) BETA (should be officially released today),
HD4770 on Catalyst 9.10
BOINC 6.10.17 (WxWidgets 2.8.7).

Normal WUs work well, not had any GPU ones so far so it might be a bit early.




Main page · Your account · Message boards


Copyright © 2018 Jon Sonntag; All rights reserved.