Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on reading ``o(1)'' Date: Tue, 28 Mar 2017 21:05:17 -0300 Organization: Aioe.org NNTP Server Lines: 74 Message-ID: <86efxhaqwy.fsf@toledo.com> References: <86vaqydwqx.fsf@toledo.com> <871stj7nge.fsf@bsb.me.uk> NNTP-Posting-Host: PsmsIGUojJunCAfmNghHww.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:Dot92kmZ0m7y4oxjfqyu+9pAifk= Xref: csiph.com comp.programming:7671 Ben Bacarisse writes: > Daniel Bastos writes: > >> Suppose f in o(1). By definition, there's a natural number n(0) such >> that for any c > 0 >> >> 0 <= f < c * 1 = c >> >> for any n >= n(0). (AFAIK, c is a real number.) That seems to imply >> that f = 0 because that's the only thing that could be less than any >> c > 0. > > Not exactly. First, I would not write n(0) so it looks like a function. This notation is great! Let me defend it. Consider n as a function that takes an argument 0 and gives you the constant ``n0'' --- as you like to write. Functions can give anything you prefers to read. :-) Suppose now that you want n_{0_y} --- using TeX notation. Look how horrible this notation is for USENET. Much better to write n(0,y) because it already says n is dependent on 0 and y and you can just imagine the function n giving you any symbol you'd prefer to see. I picked this notation up with Brian M. Scott, an admirable mathematician who used to hang out at alt.algebra.help. I'd like to take this opportunity to leave here my sincere thanks to him. For years, he scrutinized my arguments and carefully explained a lot of difficult mathematics (to me). None of my university professors could ever give me all that attention. (Another who did the same was Paul Sperry. I think sometimes they'd distribute my threads among the two of them.) While we're here, thank you too. It's not the first time you clarify a lot of the trouble I go through with mathematics. Thank you. (Obviously I'm grateful to everyone who contributes. For example, Kaz Kylheku.) > Call it n0 or make up a new name for it, M, say. Second, I would > write f like a function (because it is one!). Here I agree. It's just that sometimes I get lazy, but I prefer f(n) too. Sometimes the n is there for really nothing. So when it's very clear... But I were not the one typing, I'd put it there. :-) >> So I thought saying f in o(1) would be useless, but searching for its >> use I see mathematicians writing it out in apparently meaningful ways. > > Well, it's not entirely meaningless because it permits a (possibly very > large) number of exception for "small n". So f being o(1) makes f > approach 0 but f(10000) could be 10^700. I think I see. f is asymptotically zero (if I may say it that way), but it can vary wildly while n is still ``small''. >> As for example in ``[t]he most obvious method to find small prime >> divisors of n is trial division: divide n by 2, 3, 5, etc. This takes >> time y^{1 + o(1)} if n has y^o(1) bits.''[1] >> >> I don't believe he meant ``if n has y^0 bits''. So how should I >> read ``o(1)''? > > I must say I could not follow this quote at all, but since the paper is > about problems with a fixed size to one of the components (finding the > "small" prime divisors for some definition of "small", for example) it > is not unlikely that o(1) might crop up. You can't say the cost is > actually zero, but it is only non-zero for a finite number of cases. > > I'm sorry I can't be less vague. No need to sorry about that. Thank you. >> [1] How to find small factors of integers. D.J. Bernstein, 2002. >> URL: https://cr.yp.to/papers/sf.pdf