How far has Collatz conjecture been computationally verified?

Message boards : Science : How far has Collatz conjecture been computationally verified?
Message board moderation

To post messages, you must log in.

1 · 2 · Next

AuthorMessage
Matt Kowal

Send message
Joined: 21 Mar 14
Posts: 2
Credit: 677,506,395
RAC: 0
Message 1906 - Posted: 19 Aug 2019, 20:48:40 UTC

This post on stackexchange raises a few questions regarding the project: https://math.stackexchange.com/questions/3314430/how-far-has-collatz-conjecture-been-computationally-verified

Can you answer any of the open questions and speak to the overall nature and status of the project?

Thank you!
ID: 1906 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Matthew McCleary

Send message
Joined: 11 Oct 19
Posts: 31
Credit: 7,043,853,637
RAC: 605,966
Message 2007 - Posted: 29 Oct 2019, 14:38:18 UTC

I'm interested to hear about this as well.

I love the fact that your project pays so much credit, but I'm not convinced my resources are going toward anything worthwhile. Other BOINC projects are a lot more open about what they're doing and the progress they're making toward their goal.

How about it?
ID: 2007 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile mikey
Avatar

Send message
Joined: 11 Aug 09
Posts: 963
Credit: 24,557,133,931
RAC: 68,714
Message 2008 - Posted: 30 Oct 2019, 14:35:26 UTC - in response to Message 2007.  

I'm interested to hear about this as well.

I love the fact that your project pays so much credit, but I'm not convinced my resources are going toward anything worthwhile. Other BOINC projects are a lot more open about what they're doing and the progress they're making toward their goal.

How about it?


Check out this thread, the Admin answered the question there: https://boinc.thesonntags.com/collatz/forum_thread.php?id=110
ID: 2008 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Matthew McCleary

Send message
Joined: 11 Oct 19
Posts: 31
Credit: 7,043,853,637
RAC: 605,966
Message 2009 - Posted: 30 Oct 2019, 18:32:12 UTC

Yeah, he kind of did.

Has Mr. Sonntag published any papers? What does he ultimately plan to do with this work we're doing for him?
ID: 2009 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile mikey
Avatar

Send message
Joined: 11 Aug 09
Posts: 963
Credit: 24,557,133,931
RAC: 68,714
Message 2010 - Posted: 31 Oct 2019, 10:51:01 UTC - in response to Message 2009.  

Yeah, he kind of did.

Has Mr. Sonntag published any papers? What does he ultimately plan to do with this work we're doing for him?


I have no idea but if you can pm him he will answer once he has time. This may be a bad time as it's Fall in Michigan and that means hunting season.
ID: 2010 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Matthew McCleary

Send message
Joined: 11 Oct 19
Posts: 31
Credit: 7,043,853,637
RAC: 605,966
Message 2079 - Posted: 18 Nov 2019, 20:31:02 UTC - in response to Message 2010.  
Last modified: 18 Nov 2019, 20:49:38 UTC

Yeah, he kind of did.

Has Mr. Sonntag published any papers? What does he ultimately plan to do with this work we're doing for him?


I have no idea but if you can pm him he will answer once he has time. This may be a bad time as it's Fall in Michigan and that means hunting season.


Evidently "hunting season" means we shouldn't count on the -- apparently -- one person who runs this entire project to do anything project-related for months at a time. It's surprising, especially for someone who, like me, is an IT professional.

But no sense in crying about it -- there are always other worthy projects happy to accept my work. Maybe I'll check back in a few months. Maybe not.
ID: 2079 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile mikey
Avatar

Send message
Joined: 11 Aug 09
Posts: 963
Credit: 24,557,133,931
RAC: 68,714
Message 2080 - Posted: 18 Nov 2019, 23:40:09 UTC - in response to Message 2079.  

Yeah, he kind of did.

Has Mr. Sonntag published any papers? What does he ultimately plan to do with this work we're doing for him?


I have no idea but if you can pm him he will answer once he has time. This may be a bad time as it's Fall in Michigan and that means hunting season.


Evidently "hunting season" means we shouldn't count on the -- apparently -- one person who runs this entire project to do anything project-related for months at a time. It's surprising, especially for someone who, like me, is an IT professional.

But no sense in crying about it -- there are always other worthy projects happy to accept my work. Maybe I'll check back in a few months. Maybe not.


That is absolutely true!! It IS a one man Project, even Projects like PrimeGrid have had outages and Seti goes down on a weekly basis for a couple of days!!!

And "hunting season" means he is a hunter who enjoys his time doing it every year, it is one of lifes small pleasures for those that love it and also do it responsibly like the Admin does.
ID: 2080 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
poppinfresh99

Send message
Joined: 25 Jan 20
Posts: 58
Credit: 1,225,329
RAC: 0
Message 2321 - Posted: 26 Jan 2020, 17:13:56 UTC
Last modified: 26 Jan 2020, 17:21:34 UTC

I don't think he would/could publish a paper until he disproves the conjecture.

If you click on a specific completed task at your "view tasks" webpage, you can see the numbers that are being run via the "stop" number. I just ran
7,172,497,769,750,700,490,752
so the progress is currently slightly less than this! Why doesn't his highest_steps.php page have the progress?
https://boinc.thesonntags.com/collatz/highest_steps.php

My issues are that he doesn't communicate his algorithm or results on this website!

Is every number checked? Does the algorithm wait until 1 is reached, or is there a smart "list" of numbers (such as 2^n) that can be reached instead? I read that new "highs" are checked using a separate algorithm. What is this algorithm?

He doesn't share his results! As far as I know, he hasn't even saved any unique results since 2017. According to highest_steps.php, the results were last updated March 2017.

This project could be so great if communication were improved...
- algorithm were explained
- more results were published more frequently at highest_steps.php

Until communication occurs, this project could be wasting a lot of time and resources.
ID: 2321 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
poppinfresh99

Send message
Joined: 25 Jan 20
Posts: 58
Credit: 1,225,329
RAC: 0
Message 2322 - Posted: 26 Jan 2020, 21:38:01 UTC

Oh, and I just learned from another site that this project began at
2.3612 * 10^21 = 2^71
which is believable upon looking at highest_steps.php

Because the highest number before this search was 10^20 by Yoyo@home---which is less that the starting point here---there really needs to be some honesty from Jon Sonntag being clear where he started. I believe that highest_steps.php is the necessary location for this information.

Dishonesty must be avoided, especially in science.
ID: 2322 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Slicker
Project administrator

Send message
Joined: 11 Jun 09
Posts: 79
Credit: 943,644,517
RAC: 0
Message 3138 - Posted: 7 Feb 2021, 1:04:59 UTC

The project started at the number it did because it picked up where the previous 3x+1@home project left off when it shut down.

Send me examples of CPU and GPU code which uses 256 bit integers that are still 4-6 times faster and I'll look into integrating it.
A little faster is meaningless as a standalone app does have to do internal verification (e.g. check the best result with two non-optimized algorithms which is known to make sure the output matches.

There's also constantly checking whether to checkpoint, write out checkpoint data so that it can be suspended and start back up later, check to see if BOINC wants it to quit, track percentage complete, track time remaining to finish, and do error or overflow checking with error logging. It also has to run on everything from an nVidia 8400GS with 16 stream processors and 64MB RAM to the latest AMD and nVidia GPUs. It also has to be able to cross compile on all platforms, work on both 32 and 64 bit machines, and be compatible with at least one encryption library that is guaranteed to encrypt and decrypt the same on all client platforms and the server.
ID: 3138 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
poppinfresh99

Send message
Joined: 25 Jan 20
Posts: 58
Credit: 1,225,329
RAC: 0
Message 3141 - Posted: 7 Feb 2021, 15:31:50 UTC - in response to Message 3138.  

Hello,

I see that you know a lot about computers: BOINC, encryption, 256-bit integers, etc.!

While you are thinking about all of that great stuff, please keep in mind the scientific GOAL of this project. The one thing that MUST be done is to have a VALID algorithm. Yours is currently not valid.

David Barina has some excellent valid code.
https://github.com/xbarin02/collatz/tree/master/src
He wants to find the MAX number, so, for your purposes, I wouldn't recommend it because there are faster approaches for reducing numbers.

I have used many of the great things in his code (a 3^1 or 3^2 sieve, interlacing, etc.) and have written what I call my "repeated k steps" code found here...
https://www.bradleyknockel.com/collatz/
The "repeated k steps" approach is best for testing the Collatz conjecture (but cannot find the MAX number). My CPU and GPU codes are vastly (78 or 36 times) faster than yours.
I basically took an algorithm (Algorithm 1) from
http://www.ijnc.org/index.php/ijnc/article/download/135/144
and sped it up. Part of how I sped them up was using my "sieveless" approach also described at my webpage. I believe that David Barina is now working to use my "sieveless" approach for accomplishing his goal. Another way that I speed it up is using a 3^2 sieve for the CPU code and a 3^1 sieve for GPU code. Perhaps the paper also didn't do what I do with a variable called deltaN to eliminate extra numbers from my 2^k sieve (I learned this trick from David Barina).

If you want to keep counting steps to 1, you must change your algorithm to be valid. See Algorithm 2 of the above paper. Basically, you cannot use sieves when counting steps to 1. I would certainly recommend that you stop counting steps to 1 because...
- Code counting steps to 1 will not be vastly faster
- Since the beginning of this project (or, by looking at your highest_steps.php, maybe since the end of 2013), this project has been doing it wrong, so maybe let's just forget about counting. In the case that your project has been using a sieve only since 2013, this doesn't change much because most work has been accomplished since 2013...
https://www.boincstats.com/stats/86/project/detail/credit
- There is no clear way of defining a step. Does (3*n + 1) / 2 count as 1 step or 2? In light of David Barina's new algorithm using bit shifts, the best definition of a step becomes even less obvious.

If you take my advice and stop counting steps to 1, then you should probably start from where David Barina left off: at 2^68. This is because all numbers must be tested with Algorithm 1. To make this work for BOINC, please see the parts of my webpage found by searching for "If you want to run both the GPU and CPU code simultaneously" and "If you have already have up to some number tested by a non-sieveless approach" and "If you want to use general GPUs..."

Regarding your requirement for 256-bit integers, I recommend that you use 128-bit integers instead. 128-bit overflow is rare, and 256-bit integers are slow. My approach is simply to check for and print instances of 128-bit overflow. Perhaps a better approach than printing is to use
#include <gmp.h>
when overflow occurs. This effectively gives you infinite-bit integers (until your RAM runs out I suppose), but then we must worry about GPU watchdog timers. If you are interested in using gmp.h, see David Barina's code for how this works...
https://github.com/xbarin02/collatz/blob/master/src/worker/worker.c

As for checkpointing, with my "sieveless" approach, you can just make the tasks small (a few minutes each), so no checkpoints needed.

In the part of my webpage found by searching for "If you want to use general GPUs...", I give ideas on how to use any GPU. I also give an idea on how to reject low-end GPUs that have arithmetic errors. I strongly recommend rejecting some GPUs in favor of getting valid results! As for 128-bit integers, maybe also reject GPUs that cannot correctly handle this data type (Intel on macOS and Windows)? Do we want overcomplicate the code to accommodate the weakest GPUs? As for 32-bit computers, do we want to accommodate them? If you do, I provide a suggestion for doing so, but various things would need to be rewritten.

If you don't change your code and project, your only other valid option is shutting down the project. You have a lot of knowledge about BOINC that I do not have, so I think you could easily adapt my codes to work with BOINC. Heck, I could even be convinced to do it over the summer. At minimum, you must remove your sieve if you keep publishing your "highest steps" results. And you must have another device validate the results because most CPUs and GPUs don't have ECC RAM, though my concerns with a GPU watchdog timer and GPU arithmetic errors should also be addressed.

I see that you have deleted most of my forum posts, which might be the correct choice if you plan on fixing your BOINC project (to start fresh). If you delete them again, please know that this would be the incorrect choice and that I have them all saved and backed up.
ID: 3141 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Crunch3r
Volunteer moderator
Volunteer developer

Send message
Joined: 30 Jun 09
Posts: 5
Credit: 7,535,491,352
RAC: 131
Message 3143 - Posted: 7 Feb 2021, 20:23:48 UTC - in response to Message 3141.  
Last modified: 7 Feb 2021, 20:25:36 UTC

Hello,

I see that you know a lot about computers: BOINC, encryption, 256-bit integers, etc.!

While you are thinking about all of that great stuff, please keep in mind the scientific GOAL of this project. The one thing that MUST be done is to have a VALID algorithm. Yours is currently not valid.

David Barina has some excellent valid code.
https://github.com/xbarin02/collatz/tree/master/src
He wants to find the MAX number, so, for your purposes, I wouldn't recommend it because there are faster approaches for reducing numbers.

I have used many of the great things in his code (a 3^1 or 3^2 sieve, interlacing, etc.) and have written what I call my "repeated k steps" code found here...
https://www.bradleyknockel.com/collatz/
The "repeated k steps" approach is best for testing the Collatz conjecture (but cannot find the MAX number). My CPU and GPU codes are vastly (78 or 36 times) faster than yours.
I basically took an algorithm (Algorithm 1) from
http://www.ijnc.org/index.php/ijnc/article/download/135/144
and sped it up. Part of how I sped them up was using my "sieveless" approach also described at my webpage. I believe that David Barina is now working to use my "sieveless" approach for accomplishing his goal. Another way that I speed it up is using a 3^2 sieve for the CPU code and a 3^1 sieve for GPU code. Perhaps the paper also didn't do what I do with a variable called deltaN to eliminate extra numbers from my 2^k sieve (I learned this trick from David Barina).

If you want to keep counting steps to 1, you must change your algorithm to be valid. See Algorithm 2 of the above paper. Basically, you cannot use sieves when counting steps to 1. I would certainly recommend that you stop counting steps to 1 because...
- Code counting steps to 1 will not be vastly faster
- Since the beginning of this project (or, by looking at your highest_steps.php, maybe since the end of 2013), this project has been doing it wrong, so maybe let's just forget about counting. In the case that your project has been using a sieve only since 2013, this doesn't change much because most work has been accomplished since 2013...
https://www.boincstats.com/stats/86/project/detail/credit
- There is no clear way of defining a step. Does (3*n + 1) / 2 count as 1 step or 2? In light of David Barina's new algorithm using bit shifts, the best definition of a step becomes even less obvious.

If you take my advice and stop counting steps to 1, then you should probably start from where David Barina left off: at 2^68. This is because all numbers must be tested with Algorithm 1. To make this work for BOINC, please see the parts of my webpage found by searching for "If you want to run both the GPU and CPU code simultaneously" and "If you have already have up to some number tested by a non-sieveless approach" and "If you want to use general GPUs..."

Regarding your requirement for 256-bit integers, I recommend that you use 128-bit integers instead. 128-bit overflow is rare, and 256-bit integers are slow. My approach is simply to check for and print instances of 128-bit overflow. Perhaps a better approach than printing is to use
#include <gmp.h>
when overflow occurs. This effectively gives you infinite-bit integers (until your RAM runs out I suppose), but then we must worry about GPU watchdog timers. If you are interested in using gmp.h, see David Barina's code for how this works...
https://github.com/xbarin02/collatz/blob/master/src/worker/worker.c

As for checkpointing, with my "sieveless" approach, you can just make the tasks small (a few minutes each), so no checkpoints needed.

In the part of my webpage found by searching for "If you want to use general GPUs...", I give ideas on how to use any GPU. I also give an idea on how to reject low-end GPUs that have arithmetic errors. I strongly recommend rejecting some GPUs in favor of getting valid results! As for 128-bit integers, maybe also reject GPUs that cannot correctly handle this data type (Intel on macOS and Windows)? Do we want overcomplicate the code to accommodate the weakest GPUs? As for 32-bit computers, do we want to accommodate them? If you do, I provide a suggestion for doing so, but various things would need to be rewritten.

If you don't change your code and project, your only other valid option is shutting down the project. You have a lot of knowledge about BOINC that I do not have, so I think you could easily adapt my codes to work with BOINC. Heck, I could even be convinced to do it over the summer. At minimum, you must remove your sieve if you keep publishing your "highest steps" results. And you must have another device validate the results because most CPUs and GPUs don't have ECC RAM, though my concerns with a GPU watchdog timer and GPU arithmetic errors should also be addressed.

I see that you have deleted most of my forum posts, which might be the correct choice if you plan on fixing your BOINC project (to start fresh). If you delete them again, please know that this would be the incorrect choice and that I have them all saved and backed up.


Replying in a respectful manner does get you somewhere... who would have thought.
Besides that,I DELETED YOUR POSTS, because of your condescending way of posting. I told you to stop it and you didn't listen. Be respectful and your voice will be heard.
Thank you.
ID: 3143 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Wedge009

Send message
Joined: 21 Jan 20
Posts: 4
Credit: 5,720,325,616
RAC: 0
Message 3155 - Posted: 10 Feb 2021, 10:24:01 UTC
Last modified: 10 Feb 2021, 10:26:45 UTC

Some background: I started contributing to this project because it was the only one at the time that I checked that had a Linux-based application that made use of Intel-based GPUs. Einstein@home has Intel GPU applications, but are only Windows-based. Since then, it looks like a relatively new project, Minecraft@home, has a Linux-based Intel GPU application but that isn't something I'm particularly interested in.

I recognise this project is popular because of its high credit reward, even though I understand the BOINC credit system is arbitrary in nature and has no real meaning or significance beyond what its users assign to it. I admit this appeals a little to me as well, even though my primary reasoning for running this project is the aforementioned availability of applications.

Nonetheless, I would consider contributing to such a project a waste if the science it purportedly works on is questionable or proven to be invalid and from what I have read this can be hard to determine if the communication isn't there (I fully understand this is a hobby project by an individual as opposed to a scientific or educational institution and there are limitations on time and effort that can be expended). I'd consider it an even greater waste than cryptocurrency because while I might not agree with how such things work and the drain on society they create, clearly enough people are on board with them that they do produce economic value for them and that is the nature of how our economy works. In comparison, burning energy for invalid science doesn't even have that economic value or reward.

On the other hand if we can be confident of the project's validity, code optimisations - especially if they yield significant improvements and can be verified to still produce valid results - would be beneficial to all involved and the science being run as well. Which is where I think the open-source question comes in.

Edit: It seems there have been some head-butting among some participants and admins here and that's unfortunate. I understand people have invested time and effort into this project and sometimes criticism can be taken personally, whether intended that way or not. I'm not interested in 'taking sides', however, I'd simply like to resolve some objective questions about the project in a clear and constructive way.

tl;dr: Is it possible for the project to report what has been researched during its lifetime, how that fits in with other previous efforts, and how the results obtained to date have been verified? If not, I'm inclined to reconsider my contributions to the project - that isn't intended as a threat in any way (after all, I'm hardly the most significant contributor) but to highlight that good project communities thrive on good communication and are receptive to constructive criticism and feedback.

With respect.
ID: 3155 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
poppinfresh99

Send message
Joined: 25 Jan 20
Posts: 58
Credit: 1,225,329
RAC: 0
Message 3165 - Posted: 13 Feb 2021, 5:15:01 UTC - in response to Message 3143.  
Last modified: 13 Feb 2021, 5:15:34 UTC

I DELETED YOUR POSTS


Is it possible for one of the admins to bring the main deleted threads back? The following were deleted...
- A productive collaboration between myself and another user to understand the algorithm behind this project. We found the kernel used by this project and discussed his FPGA results...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=153
- I posted information I discovered about how to benchmark this project (CPU and GPU), but I can just repeat myself here: Jon S. runs (or at least ran) 3*2^44 = 5.3e13 numbers each task
- I share my new algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=223
- I point out a fatal error in this BOINC project's algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=224
- I break the sad news regarding results being invalid to the cafe...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=225
ID: 3165 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Slicker
Project administrator

Send message
Joined: 11 Jun 09
Posts: 79
Credit: 943,644,517
RAC: 0
Message 3166 - Posted: 13 Feb 2021, 6:30:50 UTC - in response to Message 3165.  

Crunch3r is a moderator and a volunteer developer. He spent a lot of time helping with the initial application in order to tweak the compiler settings to get the most performance out of every app (both CPU and GPU) for each platform. He even sent AMD bug fixes for their compiler because their compiler created bugs. When all the GPUs switched to OpenCL, they ALL had bugs in their compilers. Apple was the worst. Code that ran under 32 and 64 bit Windows and Linux would fail under Apple. It wouldn't even compile the kernels. It reminded me of the way Microsoft's IE didn't adhere to HTML standards and never really has (until now when Edge is now chrome based).

You can't count on processing until a number is less than the starting number because with tens of thousands of work units being run simultaneously, you have no idea whether the "lower than your starting number" has actually been completed.

The goal of the project isn't to find the highest steps. the goal is to find a number that doesn't resolve. That's the reason for using 256 bit math. Just in case it overflows.

The project has used GMP. It's slow as molasses. That was version 1.0 of the apps.

Anything returned by the GPU is then checked by the CPU using a brute force, non optimized method to check the result. So your incredible speed won't ever be see in the app. In addition, the results are also checked by the server. There are also checks with total steps, average steps, high steps, and randomly checked numbers, all of which don't use ANY optimizations to assure that the results are valid.

Using smaller WUs just crashes the server. BOINC requires WUs use shared memory and be pre-loaded in order to send to clients. Unless I re-write the BOINC server code, there is a limit on how many work units can be cached in advance. BOINC also requires the use of MySQL which doesn't handle memory nearly as well as Oracle or SQL Server. As such, unless the entire database fits in RAM, performance goes down drastically.

If the work generator daemon's request of the number of work units available times out, the default action is to generate more work units. The result is that the next query will take even longer and it will create more work units. Eventually, you end you with hundreds of thousands of work units even though you didn't need any. That means you really CAN'T guarantee any number that is less than the starting number has been resolved.

Clients can abort work units at any time. And they do. So you can't expect a lower starting number to have been validated as they may have aborted the work unit.

A client may overclock the their GPU to the point where the output is garbage. Every once in a while, the garbage is so bad that the validator crashes attempting to read it. That causes the daemons to all stop working since it will be several minutes before the validator is automatically restarted and when it starts, it will just crash again. The offending work unit needs to be terminated in order for it to continue. I don't monitor the project 24/7. In just a few hours, the backlog can grow such that the database exceeds the RAM. When that happens, everything goes to shit.

You state that you can't use a sieve but then you choose to ignore certain numbers in your own app. Explain how that isn't the same thing. A sieve eliminates checking numbers that are know to resolve to 4,2,1. I don't claim that by using a sieve the max steps is always reported. That's because that is not the goal. The goal is to find a number that doesn't resolve. And, depending upon the sieve size used, some numbers with higher steps than have been found will be ignored. But they will resolve. So then it becomes a "do you want BOINC credits or to find the highest steps? If you eliminate all the numbers which are 2x of a known number that resolves, then it is guaranteed to resolve since x/2 will end up being only 1 step more. There are numerous papers written on how sieves CAN be used to reduce the numbers needed to be checked if trying to find numbers that don't resolve in 4,2,1.

Small work units also require more network bandwidth. Comcast has threatened to cut off my Internet due to use of too much bandwidth. Switching to another provider would cost about $24K/year. That's not going to happen since this is paid for by myself.

Lastly, until any application is run against a non-optimized 3x+1 or x/2 algorithm, the results can't be considered valid. That means a GPU app which takes 3 minutes to complete may take a CPU 2 weeks to complete. And, one valid work unit does not mean all work units will be valid. That's why it takes MONTHS to valid a new application. Do that for 32 bit and 64 bit for Win XP, Win 7, Win 10, Linux (multiple versions), and OS/X. At over $200/month for electricity just to test apps for several months, you can appreciate why, unless there is a major breakthrough, I don't stop everything to work on it.

That and I have a full time job as well as a number of hobbies and this is only one of them. Given the 70% reduction due to Covid-19, I'm not exactly excited to spend more on electricity. While I'm fortunate to not be unemployed, I don't have an infinite budget and since this is a hobby, I have no intentions to ever take donations to run it.

So, I would reiterate what several others have said. If you feel so deeply that this project is doing it wrong, start your own BOINC project and find out for yourself what it really takes for an app to work. If may be many times faster, but once you add in the BOINC overhead and bullet proof error checking, you may find it doesn't work nearly as fast as you expect.
ID: 3166 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
poppinfresh99

Send message
Joined: 25 Jan 20
Posts: 58
Credit: 1,225,329
RAC: 0
Message 3175 - Posted: 25 Feb 2021, 8:46:38 UTC - in response to Message 3166.  

Hello,

I just noticed your message.


>>> You can't count on processing until a number is less than the starting number because with tens of thousands of work units being run simultaneously, you have no idea whether the "lower than your starting number" has actually been completed.

What I mean by the starting number is the 9 in the following example...
9 -> 14 -> 7 -> 11 -> 17 -> 26 -> 13 -> 20 -> 10 -> 5 -> 8 -> 4 -> 2 -> 1
Once you get to 7, you stop because it is less than the starting 9. Just 2 steps are needed instead of the above many steps.
Then, when you test the starting number of 10, it immediately reduces to 5, so you move to 11. Of course, a good sieve would prevent 9, 10, and 11 from ever being tested, but you get the idea.
For this to work, you can't skip anything not excluded by a sieve.


>>> The goal of the project isn't to find the highest steps. the goal is to find a number that doesn't resolve. That's the reason for using 256 bit math. Just in case it overflows.

Awesome! So the *vastly* faster algorithms should work! Though I'd never use 256-bit integers to do it.


>>> The project has used GMP. It's slow as molasses. That was version 1.0 of the apps.

You'd only use GMP for the *very rare* numbers that overflow 128-bit integers. Or simply print these very rare numbers to be checked with Python 3 or whatever (instead of GMP) at some later date. There will be no slowdown. These numbers are very rare.


>>> Anything returned by the GPU is then checked by the CPU using a brute force, non optimized method to check the result. So your incredible speed won't ever be see in the app. In addition, the results are also checked by the server. There are also checks with total steps, average steps, high steps, and randomly checked numbers, all of which don't use ANY optimizations to assure that the results are valid.

I completely reject your statement that checking results prevents fast speeds. You can always create checksums of steps-to-reduce-below-starting-number as you go then compare the checksum with another device that is validating the task. These checksums require minimal computational time. David Barina's code makes these checksums if you want to see how they are done. I temporarily put them in my "sieveless" code as well to compare my checksums against his (they were the same), though my "repeated k steps" code hasn't yet been compared to any other code (though it indirectly has via my "reduce to 1" code reproducing known records).


>>> Using smaller WUs just crashes the server. BOINC requires WUs use shared memory and be pre-loaded in order to send to clients. Unless I re-write the BOINC server code, there is a limit on how many work units can be cached in advance. BOINC also requires the use of MySQL which doesn't handle memory nearly as well as Oracle or SQL Server. As such, unless the entire database fits in RAM, performance goes down drastically.

I mentioned the small amount of time my tasks can take just to show how flexible my "sieveless" approach is. Set the task size to whatever you want. Simply change the variable called TASK_SIZE.


>>> You state that you can't use a sieve but then you choose to ignore certain numbers in your own app. Explain how that isn't the same thing. A sieve eliminates checking numbers that are know to resolve to 4,2,1. I don't claim that by using a sieve the max steps is always reported.

Thanks for clarifying your goal! I thought your goal was to find highest steps because you reduce numbers to 1 and your only posted results are the counts of the steps. I have been asking for over a year for various things like what your goal was, and now I finally know! Yes, please use every sieve you can think of! My 2^k sieves reduce even more numbers than yours, and I use a 3^1 or 3^2 sieve.


>>> Lastly, until any application is run against a non-optimized 3x+1 or x/2 algorithm, the results can't be considered valid. That means a GPU app which takes 3 minutes to complete may take a CPU 2 weeks to complete. And, one valid work unit does not mean all work units will be valid. That's why it takes MONTHS to valid a new application. Do that for 32 bit and 64 bit for Win XP, Win 7, Win 10, Linux (multiple versions), and OS/X. At over $200/month for electricity just to test apps for several months, you can appreciate why, unless there is a major breakthrough, I don't stop everything to work on it.

I would say that any code that is 78 or 36 times faster (for CPU and GPU, respectively) is worth your validation process. It is a major breakthrough.



>>>> That and I have a full time job as well as a number of hobbies and this is only one of them. Given the 70% reduction due to Covid-19, I'm not exactly excited to spend more on electricity. While I'm fortunate to not be unemployed, I don't have an infinite budget and since this is a hobby, I have no intentions to ever take donations to run it.

We're in the same boat!


>>> So, I would reiterate what several others have said. If you feel so deeply that this project is doing it wrong, start your own BOINC project and find out for yourself what it really takes for an app to work. If may be many times faster, but once you add in the BOINC overhead and bullet proof error checking, you may find it doesn't work nearly as fast as you expect.

Justifying wasting people's time and electricity on "someone else should do better" is just a cop out. I have said many times that I'm not interested.

Sure, BOINC may slightly slow down my code, but the speedups are basic math...
(1) By not reducing to 1 and just reducing below the starting number, you only need to do 3.492652 steps on average, which is a *vast* improvement over the 4.8 log2(N) steps of your current approach.
(2) For a 2^k sieve and a given k, I exclude about 25% more numbers than you by removing numbers that join the paths of smaller numbers.
(3) My "sieveless" method allows me to run FAR larger sieves. A 2^26 sieve requires me to test 1.3% of numbers, but a 2^60 sieve, which my "sieveless" technique can do, would probably run only 0.05% of numbers. This is a vast improvement.
(4) Using a 3^1 sieve allows you to run 67% of the numbers you currently run. A 3^2 sieve allows you to test 55% of the numbers you currently run.
ID: 3175 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Peter Hucker of the Scottish Boinc Team

Send message
Joined: 5 Jul 11
Posts: 45
Credit: 508,573,847
RAC: 4,125
Message 3176 - Posted: 25 Feb 2021, 15:51:43 UTC - in response to Message 3166.  
Last modified: 25 Feb 2021, 16:08:59 UTC

since this is a hobby, I have no intentions to ever take donations to run it.
Does not compute. If somebody offered to donate money to one of my hobbies, I'd take it. Why would you refuse money if one of us wanted to help? There are 3000 active users. A lot of us would pitch in a small amount. That all adds up.
ID: 3176 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Peter Hucker of the Scottish Boinc Team

Send message
Joined: 5 Jul 11
Posts: 45
Credit: 508,573,847
RAC: 4,125
Message 3177 - Posted: 25 Feb 2021, 16:16:25 UTC - in response to Message 3165.  

I DELETED YOUR POSTS


Is it possible for one of the admins to bring the main deleted threads back? The following were deleted...
- A productive collaboration between myself and another user to understand the algorithm behind this project. We found the kernel used by this project and discussed his FPGA results...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=153
- I posted information I discovered about how to benchmark this project (CPU and GPU), but I can just repeat myself here: Jon S. runs (or at least ran) 3*2^44 = 5.3e13 numbers each task
- I share my new algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=223
- I point out a fatal error in this BOINC project's algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=224
- I break the sad news regarding results being invalid to the cafe...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=225

Deleting posts instead of replying to them shows something is up. Censorship stinks of something.
ID: 3177 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile P4x5BTBLisD75cAA3ALRoHfKynT

Send message
Joined: 2 Jan 21
Posts: 8
Credit: 135,589,661
RAC: 0
Message 3178 - Posted: 25 Feb 2021, 16:17:27 UTC - in response to Message 3176.  
Last modified: 25 Feb 2021, 16:18:21 UTC

since this is a hobby, I have no intentions to ever take donations to run it.
Does not compute. If somebody offered to donate money to one of my hobbies, I'd take it. Why would you refuse money if one of us wanted to help? There are 3000 active users. A lot of us would pitch in a small amount. That all adds up.



I agree with this. Im sure many of us are professional software engineers and wear various hats of skill for a living. I for one have some cash and moderate skill (that book the size of the universe of things I do not know is getting smaller) and i would love to have somebody donate money to my hobbies. I love the 11 meter and 10 meter radio for example. Nobody giving me money for those hobbies. Your lucky XD
ID: 3178 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile P4x5BTBLisD75cAA3ALRoHfKynT

Send message
Joined: 2 Jan 21
Posts: 8
Credit: 135,589,661
RAC: 0
Message 3179 - Posted: 25 Feb 2021, 16:23:33 UTC - in response to Message 3177.  
Last modified: 25 Feb 2021, 16:37:00 UTC

I DELETED YOUR POSTS


Is it possible for one of the admins to bring the main deleted threads back? The following were deleted...
- A productive collaboration between myself and another user to understand the algorithm behind this project. We found the kernel used by this project and discussed his FPGA results...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=153
- I posted information I discovered about how to benchmark this project (CPU and GPU), but I can just repeat myself here: Jon S. runs (or at least ran) 3*2^44 = 5.3e13 numbers each task
- I share my new algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=223
- I point out a fatal error in this BOINC project's algorithm...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=224
- I break the sad news regarding results being invalid to the cafe...
https://boinc.thesonntags.com/collatz/forum_thread.php?id=225

Deleting posts instead of replying to them shows something is up. Censorship stinks of something.



Ive seen your posts around. Idk you have developed your own project it seems and should go implement it as you see fit? I don't think your being censored but from what I have read and understand you are being a nuance and have ignored what the admins have said in regards to your posts. So go and implement your own boinc project. Im not discounting anything you have said. It seems like you are a smart guy or something to that effect.

Let me enlighten you. You can not come into other peoples spaces and say things like "I break the sad news" or "I point out a fatal error".. and then not expect those people to remove your posts... You are using what i like to call nuclear bombs or world ending statements. In a war of words that people have, called discussion, you my friend walked into a space and farted with your mouth hole and then you actually detonated a weapon of mass destruction, in terms of how you have a conversation. Sorry man. You are way to pointed with your statements and i understand why you were censored. For one when i first read your post... with no basis at all what so ever... i stopped mining this project.... I am now mining it again so no worries but you my friend did something that is a big no no in the conversation forum world. You yelled fire in a crowded space.

Your lucky our not banned or something worse that the internet has to offer ;)

Let me now give you the benefit of the doubt. If your english is not so well then let me tell you you need to practice your english... its way too on the accusatory side. It almost seems like you have a personal vendetta against somebody here... Ide actually not mind having to translate straight from the language you are coming from... it takes away confusion actually lol.
ID: 3179 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · Next

Message boards : Science : How far has Collatz conjecture been computationally verified?


©2022 Jon Sonntag; All rights reserved