On Mon, 2003-03-24 at 16:33, jw schultz wrote: > On Mon, Mar 24, 2003 at 10:56:42AM +1100, Donovan Baarda wrote: > > On Mon, 2003-03-24 at 03:36, jw schultz wrote: [..] > > > hadn't a decent fast integer sqrt function at hand. I don't > > > really care to start bringing in the math lib just for this > > > one calculation. I've cobbled together one that is OK. > > [...] > > > > In case you didn't notice the "count non-zero shifts" is an approximate > > integer log2 function. There are integer approximations for sqrt that > > you can use, including Newton-Raphson;
Actually, Newton-Raphson is not really an approximation (when compared to "count non-zero shifts"), but you can turn it into one by stopping iteration when the answer is close enough. > > int sqrt(int R) { > > int x,x1; > > > > x = 1024; /* starting guess close to what we expect */ > > repeat { > > x1 = x; > > x = (x1 + R/x1) >> 1; > > } while (x-x1); > > return x; > > } > > I'm more concerned with cycle count and cache effects than > loop iterations. Division, at least historically, is an > expensive operation compared to multiplication. The above converges surprisingly quickly... for arbitrary numbers up to 2^36 it typically converges within 10 iterations. For numbers under 2^20 it seems to converge within 5 iterations. Also, this is only done once per file to determine the block-size to use. If you are really concerned about divisions, there is another algorithm that uses only multiplies, and does one iteration per bit in the solution... for a 64bit integer it is 32 iterations to find the solution. It's nice for implementing in assembler on micros without a hardware division, but it's a bit messier to implement in C. > > If we must have an upper limit on block size, I'd prefer it to be > > continuous up to the 4G mark. This means an upper limit of 64K. > > I'm ambivalent. We don't seem to have a problem with > huge block sizes. One possibility would be to allow the user to > set a ceiling by adding an option (--max-block-size) > > My inclination at the moment (may change my mind) would be > to have no upper bound and see if anyone else has a problem. > If problems appear we could either impose a limit or add a > --max-block-size. I think --max-block-size would be a waste of time... people can always specify a particular block size if they are unhappy with the heuristic. I suspect that no-limit will prove to work well. > On the whole i'd say we are zeroing in on something good. > I'll see about regenerating the patches. Yeah... I think I'll have to implement this heuristic in pysync now :-) -- ---------------------------------------------------------------------- ABO: finger [EMAIL PROTECTED] for more info, including pgp key ---------------------------------------------------------------------- -- To unsubscribe or change options: http://lists.samba.org/mailman/listinfo/rsync Before posting, read: http://www.tuxedo.org/~esr/faqs/smart-questions.html