From: already5chosen@yahoo.com
On Tue, 17 Feb 2026 15:41:23 +0200
Michael S wrote:
> On Mon, 16 Feb 2026 12:31:31 +0200
> Michael S wrote:
>
> > On Sun, 15 Feb 2026 19:19:16 -0000 (UTC)
> > Thomas Koenig wrote:
> >
> > > Michael S 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
[continued in next message]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
