Optimize unsigned integer sqrt

[ckormanyos]

Try to optimize unsigned integer square root, for instance, with the algorithm SqrtRem known from the MPFR author's literature.

[ckormanyos]

New insight has been gained in the area of Karatsuba square root. This is currently under investigation in another project and should be applicable to this issue eventually.

[ckormanyos]

Karatsuby square root is being investigated more deeply in Boost.Multiprecision

[johnmcfarlane]

Assuming that it is a bug to pass a negative value to a sqrt function, might it be best to assert this as a precondition and proceed on the assumption that the value is indeed non-negative? (example)

[ckormanyos]

Assuming that it is a bug to pass a negative value to a sqrt function, might it be best to assert this as a precondition

In wide_integer, this has, indeed, become an open issue with recent supportof signed wide integers. At the moment, I decised to simply return 0 for square roots having argument of 0 or less than 0. This line is shown here.

[johnmcfarlane]

I would think twice about using this function because of that part of the contract. This raises three problems:

1. Correctness: I don't want the wrong value to be returned. sqrt(-1) isn't zero!
2. Trust: I want to be given help catching the bug when I run the code in tests or debug builds. If I have spinach in my teeth, I trust a friend to stop and tell me if they notice.
3. Choice: Assuming my code is correct and bug-free, I don't want to be paying the cost of an unnecessary branch. The user can actually help the optimiser produce better code if they allow it to assume that no contracts are broken, i.e. that no assert conditions are false.

It's a design philosophy choice and not universally accepted -- or even consistently the right choice! But CNL identifies this kind of condition as a bug -- just like divide-by-zero. And bugs are treated with zero tolerance in CNL.

[ckormanyos]

bugs are treated with zero tolerance

Fair enough. It's always a toss-up, provide the wrong answer or throw. But wide-integer is designed to be on-the-metal, no-rtti, exceptions off. I wonder if there is a nice way to handle with these constraints. I do not have the generalized concept of exception, but that would be one option, with special cases for rtti/noexcept.

Ideas?

[johnmcfarlane]

Firstly, it's important distinguish between errors and bugs.

• An error is something that could occur in a bug-free program (e.g. missing file, dropped connection, bad command-line parameter or when somebody yanks a cable out of a socket somewhere). Exceptions may sometimes be a good way to handle errors. Regardless, a thoroughly-written program will provide for such occurrences so that no bug or other catastrophe occurs as a result.
• A bug is something that can -- and must -- be fixed by the software engineer by changing the source code so that it won't occur again. Throwing an exception in a C++ program is unlikely to ever be a good strategy for handling bugs.

Both of these are types of contract violation. The former is of the contract between the program user and the program author. The latter is of the contract between an API implementer and an API user and it is that contract which concerns us here.

There is no single strategy for dealing with the discovery of a bug in a running program. In C++, the basic choices are:

1. Trap the error so the user (who might also happen to be a developer) knows there's a problem.
2. Assume that there are no bugs in the code -- maybe even optimising around that assumption.
3. Try and continue, possibly logging an error.

These choices are mutually exclusive. You might want to pick-and-mix for different types of errors within different areas of the program... but you probably don't. And you cannot easily let the user make the choice at run-time without violating 2) for some users. The choice must be made at build time. The right choice depends on who is using the program and for what purpose:

• Somebody who is testing the program, e.g.

  • a developer investigating a bug,
  • a QA/test engineer, or
  • a CI machine performing automated tests

  will all prefer 1) because bugs are a likelihood and performance and stability are secondary concerns.

• A safety-critical system with backup/redundancy will also prefer 1) because knowingly allowing the program to continue in an incorrect state is an unacceptable risk. A life-support system or the autopilot in an autonomous vehicle provide good examples.

• A safety-critical system without backup/redundancy may prefer 3)

• A performance-critical/resource-constrained application may favour 2). Note that this might also be released by someone who previously tested the program as described above with 1). So the same person builds the program two different ways for two different users. Regardless, they must have a high degree of confidence in the correctness of their program.

• A business-critical system - where money is at stake but lives are not - may prefer either 1) or 3) depending on various factors. A RESTful server with persistent state may eventually identify bad state that has lain unnoticed for a while. The developer can choose what happens on discovery:

  • Do we kill the process and restart it in the hope that the problem goes away for a while, or
  • do we 'soldier on' and hope the problem doesn't cause some catastrophe or other?

  This choice will be affected by the scale of the fleet, exposure to malicious agents and the cost of incorrect behaviour.

Because of the plethora of scenarios and choices, I don't think it is wise to impose a single choice on the user. But in CNL I do provide the following:

• a means of expressing the statement: "THIS IS A BUG",
• a set of defaults which roughly equate to 1),
• a number of preprocessor-based switches and levers that allow the user to opt for 2),
• support for sanitizers so that the code can trap bugs in CNL usage in the same way that they can trap overflow and divide-by-zero errors,
• use of sanitizers in unit tests,
• a few carefully selected, opt-in-only run-time behaviours (e.g. saturation) to satisfy 3).

My goodness, all of this makes me wonder if I shouldn't write a library just for contract checking! I'm currently involved in trying to standardise some of this so that it will be much easier to enact in other libraries. But the most important first step is to provide some kind of assert mechanism to express "THIS IS A BUG!". You might even want to use the assert macro from <cassert>.

HTH and thanks for asking the question. I have been planning to write an article and maybe even present a talk on this subject and this has really helped gather my thoughts.

[ckormanyos]

HTH and thanks for asking the question.

It really did. Thank you @johnmcfarlane

I have been planning to write an article and maybe even present a talk on this subject and this has really helped gather my thoughts.

That would be terrific in my opinion. I'm pretty honed into the areas of error-intolerant, performance-critical, no backup if you'd ever like to exchange ideas on those top-level requirements.

[johnmcfarlane]

Ah, that gets me thinking of numerical errors which are a special case of errors because they are incorrect by degree. I shall make sure to call those out and invite you to review!

[ckormanyos]

call those out and invite you to review

I'd like that. Thx.

[johnmcfarlane]

The first version of the article is available here. Please let me know what you think and whether it's helpful.