On Thu, 03 Mar 2011 09:07:12 -0800 "Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> wrote:
On 3/3/2011 6:57 AM, Chad Nelson wrote:
And I thought I had answered it, by moving almost all of the functions out of the integer_t class. Apparently I misunderstood your intent, though it's something I'd have wanted to do eventually anyway.
What difference, from the point-of-view of the interface or from the user, does it make if the algorithms are implemented in the integer_t class scope or a detail namespace scope? It seems you misunderstood the desire for decoupling the algorithms from the data structure.
Yes, apparently I did. I wish you'd said something about it when I asked for the last preliminary review. It's rather late to make huge changes to the library at this point.
See also Mathias' email regarding "genericity"; I agree with his evaluation in this regard and won't repeat it.
'Fraid I have to disagree, at least for now. I'll expand on this in replies to the later messages that I see waiting for me.
Is this decoupling the "something [you]'d have wanted to do eventually anyway", or are you referring to something else?
I was referring to moving almost everything out of the integer_t class.
2) In a similar vein, I would like to see the cryptographic functionality decoupled from the xint::integer_t data structure as well, and released separately.
That's one of the most common reasons that people want to use a large-integer library. Separating those functions from the library would make it that much harder for potential users to get everything working.
Can you be more specific on *how* it would be "much harder", from the user's perspective?
Not "much harder," but "that much harder." And no, I can't at present, as it would depend on exactly how the separate functions are made available.
Also, good things: I like the policy-based design, and I think it's the right direction. The Boost.Parameter arity thing may get onerous (see comment below), and one thing you could do to work around it is to just accept a mpl::map of tags, since I'm guessing your not using Boost.Parameter's deduction functionality (awesome and powerful, but unnecessary in this case, I think).
I believe it *is* using deduced parameters. I don't recall the terminology, but that's what Dave Abrahams called it when I described the interface.
I'm referring to
http://www.boost.org/doc/libs/1_46_0/libs/parameter/doc/html/index.html#dedu... [...]
If I understand that correctly, then yes, I'm using that.
* http://www.oakcircle.com/xint_docs/namespaceboost_1_1xint.html
integer_t<...> square (const integer_t<...> n)
The complexity is just O(n^2). If you want to more precise, don't use O(...), just state the number of additions/subtractions and multiplications.
Are you sure about that complexity? That function doesn't just multiply a number by itself, it uses an algorithm explicitly designed for squaring a number, which is more efficient. I think the complexity on that one is correct.
Ummm...yes, the stated complexity is correct, but O(n(n+1)/2) = O(n^2).
So asymptotically speaking, it's not any faster than using the naive grade-school multiplication algorithm. Like I said, unless you want to give a precise operation count, it's just O(n^2).
Um... if you plug a concrete number into both equations, the answers are quite different.
integer_t<...> pow (const integer_t<...> n, const integer_t<...> e)
I suspect this complexity is, really, O( # of bits in the result ), as the last one or two multiplies are what dominate.
I'm pretty sure the complexity on that one is correct as well.
Yeah, I don't think I'm right, either, but let's analyze this...
The asymptotic work in your loop in detail::pow is the same as the following loop (we'll assume that e >>= 1 is a constant-time operation):
for(; e != 0; e >>= 1) p = square(p);
Okay so far.
Let p have np bits. Each successive loop iteration *doubles* the number of bits in p, so the work for each successive iteration is np^2, (2np)^2, (4np)^2, ..., ((2^ne)*np)^2 (there are ne loop iterations, where ne is the number of bits in e).
As far as I can tell, that's correct. ((2^ne)*np)^2 seems to describe the total amount of work done.
The total work is then
(1 + 4 + 4^2 + ... + 4^ne) * np^2 = O(4^ne * np^2) = O(e^2 * np^2)
I followed that all the way to the last step, then I got lost. If... O(4^ne * np^2) == O(e^2 * np^2) ...then logically... 4^ne == e^2 ...but if you plug in concrete numbers, that doesn't work out. If e is 0x800 (2048), then... ne == 12 4^12 == 16777216 2048^2 == 4194304 ...and 16777216 is not equal to 4194304.
By my count, you're drastically underestimating the complexity ;) Let me know if you agree with the above analysis, I could be wrong.
I see that my complexity estimate is much lower than it should be. I didn't take into account that the number of bits it deals with doubles in each iteration. It looks like 4^ne should replace ne in my estimate, would you agree?
integer_t<...> square_root (const integer_t<...> n)
You should mention that the algorithm is just Newton iteration with initial guess 2^floor(log2(n)/2) (where n is the input value).
What benefit would that add to the documentation? The average developer using the library won't care what method is used. If they're interested, can't they check the implementation source code to see?
There are many different algorithms to compute a square root; even users want to know what algorithms you're using so they can use your library with confidence.
I don't see it, but I'll take your word for it. Documentation updated to include that.
Also, your complexity claim implies a bounded number of Newton iterations, independent of the inputs, as each loop through the while loop is O(n^2) (where n is the # of bits) due to the division... that may be the case, and if so, you might want to back that up with a reference or something, but I suspect you should have maybe a log(n) in there (where n is the # of bits), as Newton has "only" quadratic convergence.
That's one of the complexity values that I'm not sure of. I haven't been able to find any reference that pins down a value for it, so that was an educated guess.
Well, I stand by my observation here. Given that Newton has quadratic convergence, I would quote the complexity as O(log(nn)*nn^2), nn = log2(input).
As I'm not familiar with quadratic convergence (too long since high school), I can neither confirm nor deny that, so I'll take your word for it. I've modified the documentation.
I believe there is an O(n) square_root algorithm that would be asymptotically faster, but...I'd have to look it up...
That's the best one that I was able to come up with in the time I had. If you can point me to a good description of a more efficient one, I'll be happy to implement it.
I believe this is what I was thinking of, though the description is a bit terse:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digi...
I don't have time to dig into that in detail tonight, but it looks very much like a binary search algorithm, very similar to what I'm already using.
int is_prime (const integer_t<...> n, callback_t callback=no_callback)
Given the documentation, I think a more descriptive name, such as is_probably_prime_rabin_miller, would be better.
Maybe, but a lot more typing for an arguable benefit. The documentation specifies its limitations, I believe that's sufficient.
The "arguable" benefits are: - the name is no longer misleading; is_prime doesn't actually check if its input is prime; and - it is clear in what sense the input is determined to be probably prime.
It *does* check whether the input is prime, with a vanishingly small chance that it is mistaken.
Again, think about someone *reading* code that uses this is_prime function.
He would expect that it reports whether the input is prime or not, which is exactly the case. With a name like is_probably_prime_rabin_miller, he would probably feel obliged to look up the Rabin-Miller primality test and figure out what "probably" means in this context (at least, I would). I think the shorter name is preferable for the reader, as it accurately conveys the author's intent.
Also, I'm not sure how small "infinitesimally" small is...it seems the wikipedia page only guarantees at most a 1/4^5 chance of a false positive (given the current implementation), but in practice it states the chance is much much less.
Applied Cryptography, Second Edition, page 260 states that "for a 256-bit n, the odds of error in six tests are less than 1 in 2^51", and the odds get slimmer the larger the number is. (On the previous page, it says of 2^50 that "[...] if you consider that the odds of the number being composite are 300 million times less than the odds of winning top prize in a state lottery, you might not worry about it so much.")
It also recommends only five tests, which is what the library uses.
Thanks for clearing that up. I think such a reference should be added to the documentation.
Done.
http://www.oakcircle.com/xint_docs/structboost_1_1xint_1_1options_1_1threads...
"Note that even with this option, it is still your responsibility to ensure that only one thread accesses a particular integer object at a time."
You seem to imply that it is not thread safe under any circumstances for multiple threads to even have *read* access to an xint::integer_t object. Is that the case, and if so, why?
Any number of threads can *read* an integer simultaneously. But if even one is *writing* to the integer, all bets are off -- no other thread can safely access it for any reason until the write is done. This is extensively detailed on the page titled "The threadsafe Template Parameter", off the index page.
Okay, then all I ask is that on the originally referenced page, it should be stated that multiple reader access is okay. That's what I had guessed, but not what one might infer upon the way it is written.
Done.
http://www.oakcircle.com/xint_docs/classboost_1_1xint_1_1integer__t.html
template<...> class boost::xint::integer_t<>
"You can specify several template parameters for the type. Most of these parameters must be specified via helper classes defined in the boost::xint::options namespace. See the list and descriptions there."
So that covers "most" of the template parameters...what about the rest?
There's only one other, the custom allocator. It's mentioned in the description on that page as well, at the bottom.
Mentioning it here, too, would be helpful.
I've written a new and more detailed description on the integer_t page, noting the defaults and what alternatives each option has.
integer_t<...> & operator+= (const integer_t<...> b) integer_t<...> & operator-= (const integer_t<...> b)
Why are these parameters passed by value?
This was mentioned in an earlier message. I didn't recall the reason then, but I've looked into it: it's partly due to Dave Abraham's "Want Speed? Pass by Value." article (possibly by misunderstanding, I'll review that in the next few days to find out), and partly because the internal COW system makes copies very cheap -- I suspect, as cheap as pass-by-reference. Most of those pass-by-value functions should probably be changed, we'll see what I come up with.
I'm pretty sure a COW copy is never cheaper than a reference copy, and probably always less cheap (given the reference count that needs incrementing).
Yes, I've reviewed the article, and it was a misunderstanding. I'll change the parameters to const references for the next release.
Besides, COW isn't on by default...
It's used internally regardless, as I control everything within the library and can ensure that it's used safely. The thread-safe option only prevents it for integers returned to the user.
I'm also not a fan of the integer_t::integer_t(const integer_t& b, bool force_thread_safety) constructor; isn't there already an "ensure_unique" member function already there (in the implementation) that ensures an integer_t object has sole ownership of its storage? Indeed, looking more at some source files, I would guess this is _make_unique. I would consider such a member function preferable to this constructor overload, especially given how the mysterious boolean parameter looks in client code (see integer_t::sign comment above).
Please see the aforementioned "The threadsafe Template Parameter" page. That Boolean parameter will be used so rarely that I don't think it's unreasonable to ask the reader of the client code to look it up if he runs across it.
That page, or your explanation here, doesn't justify why you think this constructor overload is preferable to a make_unique member function. Sorry, "because that's the way it is now" doesn't count ;)
I had a publicly-available make_unique function in an earlier iteration of the library, and was criticized for it, so I removed it. I don't remember if it was you personally doing the criticizing, but you-the-Boost-community can't have it both ways. :-)
http://www.oakcircle.com/xint_docs/basic__types__and__includes_8hpp.html
"#define BOOST_PARAMETER_MAX_ARITY 6"
This is not guaranteed to actually have any effect. Think about if Boost.Parameter gets included before any xint header does. Better (and, yes, more onerous) to document that xint::integer_t uses Boost.Parameter and hence the user must set this macro to at least 6.
Good point. Added to the to-do list.
If BOOST_PARAMETER_MAX_ARITY is already defined, you can check if it is at least 6, and if not, #error with a helpful error message.
That's probably the best way to go about it. I believe Boost.Parameter defines it (as 5) if it's not already defined when the library is first encountered, so that should be easy enough. -- Chad Nelson Oak Circle Software, Inc. * * *