Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.arch |
| Subject | Re: A useless machine |
| Date | 2026-02-17 18:17 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260217181710.00007342@yahoo.com> (permalink) |
| References | (2 earlier) <20260215153526.00005240@yahoo.com> <20260215183335.0000649e@yahoo.com> <10mt67k$996a$1@dont-email.me> <20260216123131.00003e22@yahoo.com> <20260217154123.00000257@yahoo.com> |
On Tue, 17 Feb 2026 15:41:23 +0200 Michael S <already5chosen@yahoo.com> wrote: > On Mon, 16 Feb 2026 12:31:31 +0200 > Michael S <already5chosen@yahoo.com> wrote: > > > On Sun, 15 Feb 2026 19:19:16 -0000 (UTC) > > Thomas Koenig <tkoenig@netcologne.de> wrote: > > > > > Michael S <already5chosen@yahoo.com> schrieb: > > > > > > > "Unknown" is a correct theoretically answer, but I can provide a > > > > very educated guess that on average it would take ~500 steps and > > > > the worst case would not exceed 2000 steps. > > > > So, bad news are that overall it will take more than a million > > > > years on your machine. And good news are that it'll take less > > > > than 2 million years. > > > > > > Not as bad, very many simplifications are possible. > > > > > > For one, you can discount all even numbers as starting values. > > > > O.k. > > > > > You can go further: If you look at residues modulo 2^n of your > > > starting numbers, there are only A076227(n) "interesting" > > > remaiders that you need to look at. > > > > Can not say that I understood. > > > > > If you take n=39, only 3611535862 cases > > > need to be looked at, so only 3611535862/2^39 of all cases need to > > > be looked at, a reduction of a factor around 150. You can also > > > do some more reductions (only 2/3 of those numbers need checking > > > if you can calculate the remainder by 3 fast). There are > > > different tradeoffs for different n, of course (a factor of 16 > > > for n=10, for example). > > > > > > > Hopefully now I figured out what you are talking about, except of 2/3 > part and apart from the meaning of A076227(n). > I experimented a little with these ideas and it seems that reduction > in number of steps is nowhere near the reduction in number of tested > cases. My test vectors were 2**32 consecutive points starting at > 2**52 or 2**53. I tried different modulo filters in range from 2**5 > to 2**31. Two modes of filtering were used. > In "simple" mode I just filtered out "non-interesting" inputs, but > did nothing special about "interesting" inputs. > In "advanced" mode I accelerated processing of "interesting" inputs by > means of starting their testing from point x0= (x/M)*A[x%M]+B[x%M], > where tables A[] and B[] were pre-calculated during filter build step. > Obviously, "advanced" mode filtering requires ~3 times more memory > plus multiplier + plus some logic. > > Here are my results: > $ ./nsteps2 4503599627370496 0x100000000 > Initial value = 4503599627370496 (0010000000000000). > #values = 4294967296 (0000000100000000) > Unfiltered : 22501638882 steps. 4294967296 tests. 5.239 steps/iter > n*4+3 : 17132929762 steps. 1073741824 tests. 15.956 steps/iter > n*2**5+m : 15924970210 steps. 939524096 tests. 16.950 steps/iter > n*2**5+m * : 8408777442 steps. 939524096 tests. 8.950 steps/iter > n*2**10+m : 11948770018 steps. 503316480 tests. 23.740 steps/iter > n*2**10+m * : 7088288929 steps. 503316480 tests. 14.083 steps/iter > n*2**15+m : 9003713250 steps. 289013760 tests. 31.153 steps/iter > n*2**15+m * : 4818894105 steps. 289013760 tests. 16.674 steps/iter > n*2**20+m : 6973854434 steps. 181379072 tests. 38.449 steps/iter > n*2**20+m * : 3496505674 steps. 181379072 tests. 19.277 steps/iter > n*2**25+m : 5574414306 steps. 125809408 tests. 44.308 steps/iter > n*2**25+m * : 2543845543 steps. 125809408 tests. 20.220 steps/iter > n*2**29+m : 4660796778 steps. 95710352 tests. 48.697 steps/iter > n*2**29+m * : 2008917951 steps. 95710352 tests. 20.990 steps/iter > n*2**30+m : 4493358006 steps. 89757100 tests. 50.061 steps/iter > n*2**30+m * : 1915335033 steps. 89757100 tests. 21.339 steps/iter > n*2**31+m : 4212222570 steps. 81419608 tests. 51.735 steps/iter > n*2**31+m * : 1780554493 steps. 81419608 tests. 21.869 steps/iter > > $ ./nsteps2 0x20000000000000 0x100000000 > Initial value = 9007199254740992 (0020000000000000). > #values = 4294967296 (0000000100000000) > Unfiltered : 22501540484 steps. 4294967296 tests. 5.239 steps/iter > n*4+3 : 17132831364 steps. 1073741824 tests. 15.956 steps/iter > n*2**5+m : 15924871812 steps. 939524096 tests. 16.950 steps/iter > n*2**5+m * : 8408679044 steps. 939524096 tests. 8.950 steps/iter > n*2**10+m : 11948671620 steps. 503316480 tests. 23.740 steps/iter > n*2**10+m * : 7088271089 steps. 503316480 tests. 14.083 steps/iter > n*2**15+m : 9003614852 steps. 289013760 tests. 31.153 steps/iter > n*2**15+m * : 4818766141 steps. 289013760 tests. 16.673 steps/iter > n*2**20+m : 6973756036 steps. 181379072 tests. 38.449 steps/iter > n*2**20+m * : 3496390679 steps. 181379072 tests. 19.277 steps/iter > n*2**25+m : 5574315908 steps. 125809408 tests. 44.308 steps/iter > n*2**25+m * : 2543741535 steps. 125809408 tests. 20.219 steps/iter > n*2**29+m : 4660698380 steps. 95710352 tests. 48.696 steps/iter > n*2**29+m * : 2008935493 steps. 95710352 tests. 20.990 steps/iter > n*2**30+m : 4493259608 steps. 89757100 tests. 50.060 steps/iter > n*2**30+m * : 1915241920 steps. 89757100 tests. 21.338 steps/iter > n*2**31+m : 4212124172 steps. 81419608 tests. 51.734 steps/iter > n*2**31+m * : 1780581916 steps. 81419608 tests. 21.869 steps/iter > 'Advanced' mode marked with '*' > > As you can see, 2**10 filter reduces # of processed points by factor > of 8.5, but number of processing steps reduced only 1.9x in simple > mode and 3.2x in advanced mode. > For 2**20 filter ratios are, respectively, 23.7, 3.2 and 6.4 > For 2**31 filter, 52.7, 5.3 and 12.6 > There was bug in my testing code. In reality filtering is somewhat more efficient. Here are corrected results: Initial value = 4503599627370496 (0010000000000000). #values = 4294967296 (0000000100000000) Unfiltered : 22501638882 steps. 4294967296 tests. 5.239 steps/iter n*4+3 : 17132929762 steps. 1073741824 tests. 15.956 steps/iter n*2**5+m : 13374833378 steps. 536870912 tests. 24.913 steps/iter n*2**5+m * : 8408777442 steps. 536870912 tests. 15.663 steps/iter n*2**10+m : 9935504098 steps. 268435456 tests. 37.013 steps/iter n*2**10+m * : 5187551970 steps. 268435456 tests. 19.325 steps/iter n*2**15+m : 7857750754 steps. 169738240 tests. 46.293 steps/iter n*2**15+m * : 3449537250 steps. 169738240 tests. 20.323 steps/iter n*2**20+m : 6242468578 steps. 111935488 tests. 55.768 steps/iter n*2**20+m * : 2410906338 steps. 111935488 tests. 21.538 steps/iter n*2**25+m : 4838650338 steps. 73364736 tests. 65.953 steps/iter n*2**25+m * : 1716934242 steps. 73364736 tests. 23.403 steps/iter n*2**29+m : 3856366938 steps. 51085096 tests. 75.489 steps/iter n*2**29+m * : 1338119106 steps. 51085096 tests. 26.194 steps/iter n*2**30+m : 3856366938 steps. 51085096 tests. 75.489 steps/iter n*2**30+m * : 1261491462 steps. 51085096 tests. 24.694 steps/iter n*2**31+m : 3666319938 steps. 47284156 tests. 77.538 steps/iter n*2**31+m * : 1184863818 steps. 47284156 tests. 25.058 steps/iter Initial value = 9007199254740992 (0020000000000000). #values = 4294967296 (0000000100000000) Unfiltered : 22501540484 steps. 4294967296 tests. 5.239 steps/iter n*4+3 : 17132831364 steps. 1073741824 tests. 15.956 steps/iter n*2**5+m : 13374734980 steps. 536870912 tests. 24.912 steps/iter n*2**5+m * : 8408679044 steps. 536870912 tests. 15.662 steps/iter n*2**10+m : 9935405700 steps. 268435456 tests. 37.012 steps/iter n*2**10+m * : 5187453572 steps. 268435456 tests. 19.325 steps/iter n*2**15+m : 7857652356 steps. 169738240 tests. 46.293 steps/iter n*2**15+m * : 3449438852 steps. 169738240 tests. 20.322 steps/iter n*2**20+m : 6242370180 steps. 111935488 tests. 55.768 steps/iter n*2**20+m * : 2410807940 steps. 111935488 tests. 21.537 steps/iter n*2**25+m : 4838551940 steps. 73364736 tests. 65.952 steps/iter n*2**25+m * : 1716835844 steps. 73364736 tests. 23.401 steps/iter n*2**29+m : 3856268540 steps. 51085096 tests. 75.487 steps/iter n*2**29+m * : 1338020708 steps. 51085096 tests. 26.192 steps/iter n*2**30+m : 3856268540 steps. 51085096 tests. 75.487 steps/iter n*2**30+m * : 1261393064 steps. 51085096 tests. 24.692 steps/iter n*2**31+m : 3666221540 steps. 47284156 tests. 77.536 steps/iter n*2**31+m * : 1184765420 steps. 47284156 tests. 25.056 steps/iter 2**10 filter reduces # of processed points by factor of 16.0, but number of processing steps reduced only 2.7x in simple mode and 4.3x in advanced mode. For 2**20 filter ratios are, respectively, 38.4, 3.6 and 9.3 For 2**31 filter: 90.8, 6.1 and 19.0 > Pay attention that for implementation in FPGA even filtering with > modulo 2**29 (~12M entries) is impractical. Assuming advanced mode, > 12M entries occupy 1000 Mbits. In non-expensive FPGA it simply does > not fit. In very expensive FPGA it fits, but barely. > > Let's take, for example, Altera Stratix-10 GX 2800. By the standard of > previous decade, it is a real behemoth with 2.75M Logic Elements > (LEs). Assuming that each tester unit occupies 500 LEs there is room > for 5500 units. Looking into my tables above, you want 1 filter per > ~20 tester units, so 275 filters needed. And how many available? Just > two! > And here I made even bigger mistake. The size of internal memory of GX 2800 is 229 Mbit. So 2**29 filter does not fit at all. > For modulo 2**20 it's a little better. Each filter consists of ~45,000 > entries and occupies ~2.7 Mbits. So you can fit 80+ filters in GX > 2800. But you want 5500 / 19 = 290, so still unbalanced. > Here correct numbers are as folowing: Each filter consists of 27,328 entries and occupies ~1.7 Mbits. So you can fit 130+ filters in GX 2800. But you want 5500 / 19 = 290, so still unbalanced. > For modulo 2**15 (2205 entries, ~100 Kbits) there is enough memory to > fit desired number of replica. But small filter like that is > significantly less effective, reducing # of steps (in advanced mode) > only by 4.7x. > Here it should be: For modulo 2**15 (1295 entries, ~60 Kbits) there is enough memory to fit desired number of replica. But small filter like that is significantly less effective, reducing # of steps (in advanced mode) only by 6.5x. > It is possible that there exist smarter algorithms for partition of > work between parallel tester units that can greatly reduce need for > access to filtering tables relatively to simple scheme that I assumed > in above estimates. But I think that they point stands - this sort of > filtering is not a silver bullet. It can improve throughput, but it's > unlikely that it can improve it by more than one order of magnitude. > Despite corrected mistakes my conclusions are the same.
Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-14 09:57 +0000
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 18:48 +0000
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-14 20:18 +0100
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 21:22 +0000
Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-14 13:30 -0800
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 12:50 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 13:48 -0600
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-21 21:40 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 15:17 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 04:50 -0600
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:01 -0700
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 14:43 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 12:38 -0600
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:51 +0100
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-26 01:27 +0000
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-26 09:21 +0100
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:11 -0700
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:58 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 12:27 -0600
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 15:14 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-22 11:41 -0500
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:53 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-23 10:52 -0500
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-14 21:19 -0800
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 03:58 -0500
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 13:14 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 15:46 +0000
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 10:56 -0500
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-15 19:16 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:40 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-26 19:31 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-18 18:22 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-18 22:56 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 12:10 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-21 01:56 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 19:23 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 20:36 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 10:46 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-22 12:45 +0100
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 16:35 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:12 -0500
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:47 -0500
Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-21 15:39 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 03:16 +0200
Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-22 14:48 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 23:25 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-19 11:51 +0100
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 23:12 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-20 15:11 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-19 15:27 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-20 11:41 +0200
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 18:41 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-23 11:10 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-23 17:24 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 06:44 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 01:38 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 03:16 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 04:52 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 11:16 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 13:19 -0600
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:14 -0700
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-20 08:01 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 15:35 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 18:33 +0200
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:19 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:31 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 15:41 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 18:17 +0200
Re: A useless machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-02-15 22:41 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:52 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 16:45 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 18:01 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:42 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:59 +0100
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 21:53 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:40 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 20:34 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-16 16:08 +0100
Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-16 07:50 -0800
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 18:31 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-18 21:56 +0100
csiph-web