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

Groups > comp.lang.c++ > #80934 > unrolled thread

Detect Math Errors in Functions

Back to article view | Back to comp.lang.c++

Contents

  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

Page 1 of 2  [1] 2  Next page →

#80934 — Detect Math Errors in Functions

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?

Thank you,
Joe

void GenerateSequence(unsigned long start)
{
   unsigned long x = start;
   try
   {
     while(x != 1)
     {
       x = (x%2 == 0 ? x/2 : 3*x+1);

       // code to detect math overflow error,
       // if error then do a throw string("Math Overflow");

       cout << x << "\n";
     }
   }
   catch(const string & msg)
   {
     cout << "Program terminated: " << msg << endl;
     exit(1);
   }
}

[toc] | [next] | [standalone]

#80940

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?
>
>Thank you,
>Joe
>
>void GenerateSequence(unsigned long start)
>{
>   unsigned long x = start;
>   try
>   {
>     while(x != 1)
>     {
>       x = (x%2 == 0 ? x/2 : 3*x+1);
>
>       // code to detect math overflow error,
>       // if error then do a throw string("Math Overflow");

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
   if (x%2 == 0)
       x /= 2;
   else
      {
      if (x < ULONG_MAX/3)
         x = 3*x+1;
      else
         // perform appropriate overflow processing
      }

>
>       cout << x << "\n";
>     }
>   }
>   catch(const string & msg)
>   {
>     cout << "Program terminated: " << msg << endl;
>     exit(1);
>   }
>}

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#80943

Am 01.09.2021 um 08:54 schrieb Barry Schwarz:
> 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?
>>
>> Thank you,
>> Joe
>>
>> void GenerateSequence(unsigned long start)
>> {
>>    unsigned long x = start;
>>    try
>>    {
>>      while(x != 1)
>>      {
>>        x = (x%2 == 0 ? x/2 : 3*x+1);
>>
>>        // code to detect math overflow error,
>>        // if error then do a throw string("Math Overflow");
> 
> 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
>     if (x%2 == 0)
>         x /= 2;
>     else
>        {
>        if (x < ULONG_MAX/3)
Better use numeric_limits<unsigned long>::max()
>           x = 3*x+1;
>        else
>           // perform appropriate overflow processing
>        }
> 
>>
>>        cout << x << "\n";
>>      }
>>    }
>>    catch(const string & msg)
>>    {
>>      cout << "Program terminated: " << msg << endl;
>>      exit(1);
>>    }
>> }
> 

[toc] | [prev] | [next] | [standalone]

#80972

On Wed, 1 Sep 2021 09:30:53 +0200, Bonita Montero
<Bonita.Montero@gmail.com> wrote:

>>        if (x < ULONG_MAX/3)
>Better use numeric_limits<unsigned long>::max()

Just out of curiosity, in what way is it better?  Given that it is
more characters to type, does it compile faster?  Does the resulting
program occupy less memory? Will the program execute faster?

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#80977

Am 01.09.2021 um 16:53 schrieb Barry Schwarz:
> On Wed, 1 Sep 2021 09:30:53 +0200, Bonita Montero
> <Bonita.Montero@gmail.com> wrote:
> 
>>>         if (x < ULONG_MAX/3)
>> Better use numeric_limits<unsigned long>::max()
> 
> Just out of curiosity, in what way is it better?  Given that it is
> more characters to type, does it compile faster?  Does the resulting
> program occupy less memory? Will the program execute faster?

One is C-style, one is C++-style and synatactically more explicit.
All other aspects are irrelevant.

[toc] | [prev] | [next] | [standalone]

#80978

On 9/1/21 10:53 AM, Barry Schwarz wrote:
> On Wed, 1 Sep 2021 09:30:53 +0200, Bonita Montero
> <Bonita.Montero@gmail.com> wrote:
> 
>>>        if (x < ULONG_MAX/3)
>> Better use numeric_limits<unsigned long>::max()
> 
> Just out of curiosity, in what way is it better?  Given that it is
> more characters to type, does it compile faster?  Does the resulting
> program occupy less memory? Will the program execute faster?

The only advantage I can see doesn't apply when the type is named
explicitly. std::numeric_limits<T>::max would be a much better approach
to use if T is an arbitrary integer type.

[toc] | [prev] | [next] | [standalone]

#80979

On 01/09/2021 15:53, Barry Schwarz wrote:
> On Wed, 1 Sep 2021 09:30:53 +0200, Bonita Montero
> <Bonita.Montero@gmail.com> wrote:
> 
>>>         if (x < ULONG_MAX/3)
>> Better use numeric_limits<unsigned long>::max()
> 
> Just out of curiosity, in what way is it better?  Given that it is
> more characters to type, does it compile faster?  Does the resulting
> program occupy less memory? Will the program execute faster?
> 

Better because that's what BM prefers?  :)  Perhaps it saves the reader 
needing to understand the ULONG_MAX macro, although the intent of 
ULONG_MAX seems clear enough...  New style C++ versus old style C, if 
that's important to you?  Familiarity for the programmers in the 
maintenance team? (..could go either way..)

There's certainly a good case for

    if (x < numeric_limits<decltype (x)>::max() / 3)

if the type of x were unclear, or could be subject to future change but 
it's even more characters to type, if you're intent on saving typing energy.

Or even clearer (with no worries about clever handling of edge cases) 
would be

    if (x <= (numeric_limits<decltype (x)>::max() - 1) / 3)

as that matches /visibly/ with the calculation about to be performed.

Yes, the test will match the same x values, but this way someone reading 
the code won't have to think "aha very clever - integral types in C++ 
must have an even number of bits [is that even correct??? better check 
the standard!] and 2^n mod 3 = 1 when n is even, so the natural -1 that 
seems to be missing won't make any difference.  The test would be off by 
one of n were odd, or if the numeric type were signed, but it's not so 
we're good - cunning!".  (And yes, even then, the value would only be 
"off by one" in the safe direction, but why be off by one at all?  Why 
not be (visibly and clearly) spot on?)


Regards,
Mike.

[toc] | [prev] | [next] | [standalone]

#80944

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>
<https://www.youtube.com/watch?v=5mFpVDpKX70>

[toc] | [prev] | [next] | [standalone]

#80976

On 01/09/2021 08:50, 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.

That kind of test works for pure addition, but not when multiplication 
is involved.

For example, mod 16 we have if x = 8, then y = 3*8 + 1 = 9, and y >= x. 
So your test would fail, but there was overflow!  Barry's test is the 
way I've gone in the past, or use some library class built for the 
purpose of overflow detection.


Mike.

[toc] | [prev] | [next] | [standalone]

#80983

On 01/09/2021 17:38, Mike Terry wrote:
> On 01/09/2021 08:50, 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.
> 
> That kind of test works for pure addition, but not when multiplication
> is involved.
> 
> For example, mod 16 we have if x = 8, then y = 3*8 + 1 = 9, and y >= x.
> So your test would fail, but there was overflow!  Barry's test is the
> way I've gone in the past, or use some library class built for the
> purpose of overflow detection.
> 
> 

You are right, of course - sorry for posting without thinking here.

[toc] | [prev] | [next] | [standalone]

#81069

David Brown <david.brown@hesbynett.no> writes:

> On 01/09/2021 17:38, Mike Terry wrote:
>> On 01/09/2021 08:50, 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.
>> 
>> That kind of test works for pure addition, but not when multiplication
>> is involved.
>> 
>> For example, mod 16 we have if x = 8, then y = 3*8 + 1 = 9, and y >= x.
>> So your test would fail, but there was overflow!  Barry's test is the
>> way I've gone in the past, or use some library class built for the
>> purpose of overflow detection.
>
> You are right, of course - sorry for posting without thinking here.

It's quite alright.  If you had thought a bit more perhaps I wouldn't
now have the references to the short documentaries on the Collatz
conjecture.  (I'm not working on the problem!  I swear.  Lol.  But it's
quite fun to talk about it.)

[toc] | [prev] | [next] | [standalone]

#81052

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.

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

--
Cholo Lennon
Bs.As.
ARG

[toc] | [prev] | [next] | [standalone]

#81053

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

[toc] | [prev] | [next] | [standalone]

#81073

Alf P. Steinbach wrote:
> 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! :)
No wonder, since my FORTRAN 66 days I remember that the only useful data 
structure is an array.. -Pavel
> 
> 
>>> <https://www.youtube.com/watch?v=5mFpVDpKX70>
>> Nice video, thanks!
> 
> - Alf

[toc] | [prev] | [next] | [standalone]

#80989

Joseph Hesse <joeh@gmail.com> wrote:
> 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?

This doesn't answer the question you are asking, and while what you
are doing may be interesting for curiosity's sake, or to practice the
art of programming, it's ultimately relatively futile because quite
famously the conjecture has been tested for all starting numbers
up to about 2^68.

It might be a more interesting exercise to be able to calculate
the collatz sequence for arbitrarily large numbers. You can use
a multi-precision library such as GMP to do calculations with
such numbers (which also indirectly solves your problem because
the numbers won't overflow, but grow as needed instead).

[toc] | [prev] | [next] | [standalone]

#80997

Am 01.09.2021 um 07:31 schrieb Joseph Hesse:
> 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?
> 
> Thank you,
> Joe
> 
> void GenerateSequence(unsigned long start)
> {
>    unsigned long x = start;
>    try
>    {
>      while(x != 1)
>      {
>        x = (x%2 == 0 ? x/2 : 3*x+1);

Will x ever has a chance to become 1 ?

> 
>        // code to detect math overflow error,
>        // if error then do a throw string("Math Overflow");
> 
>        cout << x << "\n";
>      }
>    }
>    catch(const string & msg)
>    {
>      cout << "Program terminated: " << msg << endl;
>      exit(1);
>    }
> }

[toc] | [prev] | [next] | [standalone]

#81018

On 01/09/2021 21:02, Bonita Montero wrote:
> Am 01.09.2021 um 07:31 schrieb Joseph Hesse:
>> 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?
>>
>> Thank you,
>> Joe
>>
>> void GenerateSequence(unsigned long start)
>> {
>>    unsigned long x = start;
>>    try
>>    {
>>      while(x != 1)
>>      {
>>        x = (x%2 == 0 ? x/2 : 3*x+1);
> 
> Will x ever has a chance to become 1 ?
> 

Yes.

The conjecture is that it will always become 1, regardless of the
starting point.  This has been confirmed up to x = 2 ^ 68, but of course
that is not a proof.

[toc] | [prev] | [next] | [standalone]

#80999

I think the most portbale solution is this:

#include <iostream>
#include <stdexcept>

using namespace std;

void GenerateSequence( unsigned long start )
{
	unsigned long x = start;
	try
	{
		while( x != 1 )
		{
			if( !(x % 2) )
				x /= 2;
			else
				if( 3 * x / x == x && 3 * x + 1 > 3 * x )
					x = 3 * x + 1;
				else
					throw range_error( "GenerateSequence: out of range" );
			cout << x << endl;
		}
	}
	catch( range_error &re )
	{
		cout << re.what() << endl;
	}
}

[toc] | [prev] | [next] | [standalone]

#81013

Am 01.09.2021 um 21:10 schrieb Bonita Montero:
> I think the most portbale solution is this:
> 
> #include <iostream>
> #include <stdexcept>
> 
> using namespace std;
> 
> void GenerateSequence( unsigned long start )
> {
>      unsigned long x = start;
>      try
>      {
>          while( x != 1 )
>          {
>              if( !(x % 2) )
>                  x /= 2;
>              else
>                  if( 3 * x / x == x && 3 * x + 1 > 3 * x )
                    if( 3 * x / 3 == x && 3 * x + 1 > 3 * x )
>                      x = 3 * x + 1;
>                  else
>                      throw range_error( "GenerateSequence: out of range" );
>              cout << x << endl;
>          }
>      }
>      catch( range_error &re )
>      {
>          cout << re.what() << endl;
>      }
> }

[toc] | [prev] | [next] | [standalone]

#81014

Look at this fantastic optimization of clang 11:

bool f( unsigned x )
{
	return 3 * x / 3 == x && 3 * x + 1 > 3 * x;
}

	mov	eax, ecx
	mov	ecx, 3
	mul	ecx
	setno	cl
	cmp	eax, -1
	setne	al
	and	al, cl
	ret

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web