Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #81053

Re: Detect Math Errors in Functions

Show all headers | View raw

On 6 Sep 2021 05:20, Cholo Lennon wrote:
> On 9/1/21 4:50 AM, David Brown wrote:
>> On 01/09/2021 08:54, Barry Schwarz wrote:
>>> On Wed, 1 Sep 2021 07:31:53 +0200, Joseph Hesse <joeh@gmail.com>
>>> wrote:
>>>
>>>> The famous unproven Collatz math conjecture says that if you start with
>>>> any positive integer n and generate a sequence by repeatedly apply the
>>>> rule that if n is even the next term is n/2, otherwise the next term is
>>>> 3*n + 1, then eventually the sequence will reach 1.
>>>>
>>>> I wrote a C++ function that will generate the sequence from any 
>>>> positive
>>>> starting integer, see below, header files omitted.  Since there is
>>>> integer arithmetic involved, there might be a math overflow.  How does
>>>> one write code to detect math underflow or overflow errors in functions
>>>> that do math computations?
>>>>
>>> In this particular case, it seems to me to be easier to prevent the
>>> overflow before it occurs rather than try to detect it after it
>>> occurs.  You could replace the previous assignment with
>>
>> I agree with that.  I've always preferred the "look before you leap"
>> approach, rather than the "close your eyes, make the jump and let
>> someone else sweep up the mess" tactic.
>>
>> (The rest is to the OP, rather than Barry.)
>>
>> Another option is to use gcc's overflow-detecting builtins, or other
>> equivalent extensions for other compilers.  If you are trying to do this
>> checking as fast as possible, you might be looking at SIMD support
>> through compiler vector extensions or processor-specific intrinsics.
>>
>> For unsigned types, you can of course just do "y = 3 * x + 1;" and check
>> for "y < x", as the overflow is defined as wrapping.
>>
>> You would probably also want to use "long long" (or uint64_t), rather
>> than "long" (which is 32-bit on some systems), as you want big numbers.
>>   You might even want compiler-specific 128-bit types - after all, the
>> conjecture is known to be true up to at least 2 ^ 68.
>>
>>
>> The conjecture itself is rather interesting.  Here are a couple of
>> interesting videos on it (there are many, but these are from reliable
>> and interesting sources, to save you from dry lectures or trisectors who
>> say they have solved it):
>>
> 
>> <https://www.youtube.com/watch?v=094y1Z2wpJg>
> Coincidence? I watched the video last week, I didn't know about the 
> Collatz conjecture until I watched it.

Andrew Koenig (secretary of the first C++ standard, colleague at Bell 
labs with Bjarne Stroustrup, the Koenig of "Koenig lookup" etc.) used 
the Collatz sequence as an example basis for what he intended to be a 
series of articles in the late Dr. Dobbs Journal, where he started out 
discussing recursive functions, and in the second article I think it 
was, pointed out how a little rewrite with an extra parameter in a 
helper function could make Collatz sequence function tail recursive.

As I understood it he intended to continue that by showing how 
`std::vector` as function result type would still give O(n^2) behavior, 
whereas a DIY linked list made that O(n).

However, I pointed out in a comment (I'm now ashamed to say with 
needlessly harsh words :( ) that C++11 move semantics, applied properly, 
reduced also the `std::vector` result case to O(n). And `std::vector` is 
much more convenient and safe than a DIY linked list. `std::vector` FTW! :)


>> <https://www.youtube.com/watch?v=5mFpVDpKX70>
> Nice video, thanks!

- Alf

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Detect Math Errors in Functions Joseph Hesse <joeh@gmail.com> - 2021-09-01 07:31 +0200
  Re: Detect Math Errors in Functions Barry Schwarz <schwarzb@delq.com> - 2021-08-31 23:54 -0700
    Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-01 09:30 +0200
      Re: Detect Math Errors in Functions Barry Schwarz <schwarzb@delq.com> - 2021-09-01 07:53 -0700
        Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-01 17:50 +0200
        Re: Detect Math Errors in Functions James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-09-01 12:28 -0400
        Re: Detect Math Errors in Functions Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-09-01 17:38 +0100
    Re: Detect Math Errors in Functions David Brown <david.brown@hesbynett.no> - 2021-09-01 09:50 +0200
      Re: Detect Math Errors in Functions Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-09-01 16:38 +0100
        Re: Detect Math Errors in Functions David Brown <david.brown@hesbynett.no> - 2021-09-01 19:25 +0200
          Re: Detect Math Errors in Functions Hope Rouselle <hrouselle@jevedi.com> - 2021-09-06 11:04 -0300
      Re: Detect Math Errors in Functions Cholo Lennon <chololennon@hotmail.com> - 2021-09-06 00:20 -0300
        Re: Detect Math Errors in Functions "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2021-09-06 07:23 +0200
          Re: Detect Math Errors in Functions Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2021-09-06 20:34 -0400
  Re: Detect Math Errors in Functions Juha Nieminen <nospam@thanks.invalid> - 2021-09-01 18:22 +0000
  Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-01 21:02 +0200
    Re: Detect Math Errors in Functions David Brown <david.brown@hesbynett.no> - 2021-09-02 11:53 +0200
  Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-01 21:10 +0200
    Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-02 05:31 +0200
      Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-02 07:51 +0200
    Re: Detect Math Errors in Functions Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2021-09-06 20:47 -0400
      Re: Detect Math Errors in Functions red floyd <no.spam.here@its.invalid> - 2021-09-06 20:24 -0700
        Re: Detect Math Errors in Functions Juha Nieminen <nospam@thanks.invalid> - 2021-09-08 10:20 +0000
          Re: Detect Math Errors in Functions David Brown <david.brown@hesbynett.no> - 2021-09-08 13:17 +0200
            Re: Detect Math Errors in Functions Hope Rouselle <hrouselle@jevedi.com> - 2021-09-08 10:24 -0300
      Re: Detect Math Errors in Functions Bonita Montero <Bonita.Montero@gmail.com> - 2021-09-07 09:10 +0200

csiph-web