This code is effective for modest-sized numbers, but can you tell what it does?

[Graeme C.]

// (Without running it)
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

typedef long long Int;

class Facs {
public:
Int a;
Int b;
Facs(Int a, Int b)
: a(a), b(b) {
}
};

int
main(int argc, char **argv) {

Int N;
{
Int P = 1601; // default debugging values
Int Q = 1901;
if (1<argc) {
string s(argv[1]);
istringstream iss(s);
iss >> N; // we'll try this one
if (0==N%2) {
cout << "at least give me an odd number" << endl;
exit(1);
}
cout << "working on "<< N << endl;
} else {
N = P*Q; // the default product to work on
}
}
vector<vector<Facs> > vf;
vf.push_back(vector<Facs>());
vf[0].push_back(Facs(1,1)); // the only solution for gen zero
Int lo = 2;
Int hi = 4;
Int gen = 1;
while (N > lo) {
cout << "generation " << gen << endl;
cout.flush();
const Int tgt = N%hi;
vf.push_back(vector<Facs>()); // for next generation
for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen
const Int& a = vf[gen-1][i].a;
const Int& b = vf[gen-1][i].b;
if (tgt==(a*b)%hi) {
vf[gen].push_back(Facs(a,b));
}
if (tgt==((a+lo)*b)%hi) {
vf[gen].push_back(Facs(a+lo,b));
}
if (tgt==(a*(b+lo))%hi) {
vf[gen].push_back(Facs(a,b+lo));
}
if (tgt==((a+lo)*(b+lo))%hi) {
vf[gen].push_back(Facs(a+lo,b+lo));
}
}
cout << vf[gen].size() << " pairs" << endl;
cout.flush();
lo=hi;
hi*=2;
gen++;
}
// done calculating - scan final gen for result
vector<Facs> rslt;
for (int i=0; i<vf[gen-1].size(); i++) {
if (N == vf[gen-1][i].a * vf[gen-1][i].b) {
rslt.push_back(vf[gen-1][i]);
cout << N << " == "
<< vf[gen-1][i].a << " * "
<< vf[gen-1][i].b << endl;
}
}
return 0;
}

// Can you predict what it does before compiling and running it?
// Regards, Graeme.

[Christian Gollwitzer]

Am 22.04.22 um 13:41 schrieb Graeme C.:
> // (Without running it)
> ...

> // Can you predict what it does before compiling and running it?
> // Regards, Graeme.

When you don't provide the slightest hint what this is good for, why
should we bother to go through this mess and figure it out?

Christian

[Alf P. Steinbach]

I share the sentiment. This looks like someone's homework. But the code
does hint strongly that it finds two factors of a number.

- Alf

[red floyd]

I suspect his homework assignment was "What was this do, and how would
you improve it?"

[Frederick Gotham]

On Friday, April 22, 2022 at 12:41:21 PM UTC+1, g wrote:

> // (Without running it)


Every few months I post a test message to Google Groups to see if it will end up in comp.lang.c++ or comp.lang.c

This post is supposed to go to c++ but it might end up in c.

[Graeme C.]

Pardon me for not going through a full object oriented design for something that
is basically manipulating a few numbers. The vectors are useful and avoid a lot
of mucking about with pointers. IMNSHO It only looks a mess because of the
(lack of) formatting. Feel free to run it through astyle, or your favourite code
formatting program. Run it if you choose, but at least look at the code that
generates the numbers.

This is nobody's homework.

Regards, Graeme.

[Christian Gollwitzer]

Am 22.04.22 um 19:24 schrieb Graeme C.:

> On Saturday, 23 April 2022 at 02:23:06 UTC+10, Frederick Virchanza Gotham wrote:
>> On Friday, April 22, 2022 at 12:41:21 PM UTC+1, g wrote:
>>
>>> // (Without running it)
>>
>>
>> Every few months I post a test message to Google Groups to see if it will end up in comp.lang.c++ or comp.lang.c
>>
>> This post is supposed to go to c++ but it might end up in c.
>
> Pardon me for not going through a full object oriented design for something that
> is basically manipulating a few numbers.

That's not the point.

> Run it if you choose, but at least look at the code that
> generates the numbers.

Why? Convince us!



Christian

[Graeme C.]

I don't feel the need to convince you. I wrote this code and thought
you people might be interested to see what I'd done but if that's not
the case then I can certainly go on living without your feedback.

Regards, Graeme.

[Andrey Tarasevich]

On 4/22/2022 4:41 AM, Graeme C. wrote:
> const Int& a = vf[gen-1][i].a;
> const Int& b = vf[gen-1][i].b;

This is valid in the context of the code presented (albeit somewhat
risky in general case), but still kinda weird. Why by reference?

--
Best regards,
Andrey Tarasevich

[Graeme C.]

On Saturday, 23 April 2022 at 12:19:02 UTC+10, Andrey Tarasevich wrote:
> On 4/22/2022 4:41 AM, Graeme C. wrote:
> > const Int& a = vf[gen-1][i].a;
> > const Int& b = vf[gen-1][i].b;
> This is valid in the context of the code presented (albeit somewhat
> risky in general case), but still kinda weird. Why by reference?

By reference because it seemed the most concise method of accessing
those numbers (the previous generation never changes) given that the
code soon accesses them multiple times. I guess it could be changed to
keep a local copy of vf[gen-1][i] but that's the way I wrote it. The inherent
inefficiency of the method completely dwarfs the gains to be had here.

Regards, Graeme.

[Andrey Tarasevich]

Well, it might have efficiency-related implications, but I'm not talking
about efficiency, I'm talking about readability of the code. You asked
us to analyze the code by eye. So, the readability matters.

It will immediately catch they eye of any professional programmer, even
on a passing glance: you are storing references into a vector and at the
same time `push_back`ing something into a... um... very similar vector.
This triggers the question: do these references survive those `push_back`s?

Your code is fine in that regard, since closer inspection immediately
reveals that the references in question refer into `[gen - 1]` vector
and `push_back` always go into `[gen]` vector, but still... The question
still pops up and distracts from reading the code. It is unnecessarily
disruptive.

[Graeme C.]

Fair comment, Andrey. There's no compelling reason to use references
there. Just deleting the two associated ampersands is enough to bring
it back to 'normality'.

Regards, Graeme.

[Juha Nieminen]

Graeme C. <gra...@gmail.com> wrote:
> using namespace std;

I'd stop using that. The prefixes increase code readability.
(Yes, they do.)

> typedef long long Int;

It's clearer if you use the newer alternative:

using Int = long long;

> string s(argv[1]);
> istringstream iss(s);
> iss >> N; // we'll try this one

It's easier to just say N = std::atoll(argv[1]);
(Ostensibly we don't care about exact validity of the argument).

> vector<vector<Facs> > vf;
> vf.push_back(vector<Facs>());

Could just write:

std::vector<std::vector<Facs>> vf(1);

> Int lo = 2;
> Int hi = 4;
> Int gen = 1;
> while (N > lo) {

...
> lo=hi;
> hi*=2;
> gen++;
> }

Isn't that just the same thing as:

Int gen = 1;
for(Int lo = 2, hi = 4; lo < N; lo *= 2, hi *= 2, ++gen)

> cout << "generation " << gen << endl;
> cout.flush();

Outputting std::endl already flushes the stream. There's no need to flush
it again.

> for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen

std::vector::size() returns a value of type std::size_t. You shouldn't be
using an int with it.

> const Int& a = vf[gen-1][i].a;
> const Int& b = vf[gen-1][i].b;

As others have commented there's no need to use references here. In fact,
it's likely going to produce less efficient code (I'm not sure the compiler
is allowed to optimize the references away).

Handing elementary types by value is more efficient than handling them by
reference.

[Tim Rentsch]

Juha Nieminen <nos...@thanks.invalid> writes:

> Graeme C. <gra...@gmail.com> wrote:

[...]

>> for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen
>
> std::vector::size() returns a value of type std::size_t. You
> shouldn't be using an int with it.

I don't want to start a holy war, but in this particular case
there is no problem comparing a signed type to a size_t (which is
an unsigned type). More generally, whenever a value of a signed
type has a non-negative value, as is obviously true in this
construct, then there is never a problem comparing a value of a
signed type to a value of an unsigned type.

Some people prefer using an unsigned type for indexing variables
like 'i' above, and that a reasonable style choice here IMO. But
there is nothing logically wrong with giving 'i' a signed type
here instead.

[Öö Tiib]

The issue as I read it was about chance that int is 32 bits, the
vf[gen-1] has 2,200,000,000 elements and so the ++ will be
applied to INT_MAX that is undefined behavior.

[Paavo Helde]

25.04.2022 15:27 Tim Rentsch kirjutas:
> Juha Nieminen <nos...@thanks.invalid> writes:
>
>> Graeme C. <gra...@gmail.com> wrote:
>
> [...]
>
>>> for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen
>>
>> std::vector::size() returns a value of type std::size_t. You
>> shouldn't be using an int with it.
>
> I don't want to start a holy war, but in this particular case
> there is no problem comparing a signed type to a size_t (which is
> an unsigned type).

I don't really care if such code uses signed or unsigned types. However,
there is a problem when comparing signed and unsigned types, namely the
gcc compiler issues warnings for them with -Wall, and sometimes these
warnings are actually useful.

So, in order to not lose these useful warnings in the avalanche of
non-useful ones, one should use matching types in such simple code, it
does not cost anything.

[Vir Campestris]

On 25/04/2022 13:40, Öö Tiib wrote:
> The issue as I read it was about chance that int is 32 bits, the
> vf[gen-1] has 2,200,000,000 elements and so the ++ will be
> applied to INT_MAX that is undefined behavior.

Some of us remember when int was only 16 bits...

There's actually no guarantee that int and size_t are the same size,
never mind the signed problem.

for (int i = 0;
is however traditional. I suspect at least in part because int is
easiest to type.

Andy

[Juha Nieminen]

Yeah, it's not that much about the signedness, but about the size.
After all, the program accepts a 'long long' value as input, so
ostensibly the vector might have more than INT_MAX and even more
than UINT_MAX elements (might not be the case with this particular
program, I haven't checked, but in general it could be).

[Tim Rentsch]

Juha Nieminen <nos...@thanks.invalid> writes:

Does this mean that if the loop variable 'i' had been given type
'long long' then you would have no complaints?

[Malcolm McLean]

If you need to interate in reverse

for (int i = (int) v.size()-1; i >= 0; i--)

you can't substitute a size_t.
You can do

size_t i = v.size();
while(i--)
so there's a workaround.

[Andrey Tarasevich]

If one needs to iterate in reverse one uses

for (std::size_t i = v.size(); i > 0; )
{
--i;
...
}

or

for (std::size_t i = v.size(); i-- > 0; )
{
...
}

or even plain

for (std::size_t i = v.size(); i != -1; --i)
{
...
}

These are not "workarounds". These are idioms.

[Manfred]

Change the last one to:

for (std::size_t i = v.size(); i != 0; --i)
{
...
}

[Manfred]

However, what you really should do is:

using MyVector = std::vector<int>;

...

for (MyVector::reverse_iterator it = v.rbegin(); v.rend() != it; ++it)
{
...
}

[Andrey Tarasevich]

No, no, no.

There is an error in the last one indeed. It was supposed to be this

for (std::size_t i = v.size() - 1; i != -1; --i)
{
...
}

This is the correct version. It is intended to illustrate the fact that
unsigned indexing can be made to look as natural as the signed one. It
has to be used with caution, since it won't work properly with "small"
(i.e. promoted) unsigned types. But still...

[Andrey Tarasevich]

On 4/30/2022 10:20 AM, Manfred wrote:
>
> However, what you really should do is:
>
>   using MyVector = std::vector<int>;
>
>   ...
>
>   for (MyVector::reverse_iterator it = v.rbegin(); v.rend() != it; ++it)
>   {
>     ...
>   }
>

Well... yes and no. Reverse iterators are intended to encapsulate the
"offset by 1" idiom. In indexing terms it is equivalent to

for (std::size_t i = v.size(); i > 0; --i)
{
// Remember to work with v[i - 1] instead of v[i]
}

When wrapped into iterators it is superficially elegant, yet comes at a
price. In more performance-conscious situations it might prove to be too
expensive. In such contexts a better idea would be to learn and use the
alternative reverse iteration idioms, which are not that complicated.

[Manfred]

On 4/30/2022 7:40 PM, Andrey Tarasevich wrote:
> On 4/30/2022 10:20 AM, Manfred wrote:
>>
>> However, what you really should do is:
>>
>>    using MyVector = std::vector<int>;
>>
>>    ...
>>
>>    for (MyVector::reverse_iterator it = v.rbegin(); v.rend() != it; ++it)
>>    {
>>      ...
>>    }
>>
>
> Well... yes and no. Reverse iterators are intended to encapsulate the
> "offset by 1" idiom. In indexing terms it is equivalent to
>
>   for (std::size_t i = v.size(); i > 0; --i)
>   {
>     // Remember to work with v[i - 1] instead of v[i]
>   }
>

I wouldn't assume this. If I had to implement a reverse iterator I might
have to do something like that, for example because the standard gives
guarantees about "one past the end" pointers, but not about "one before
the beginning".

But an implementation is more free than I would be. A standard library
implementor could use, for example, some "one before the beginning"
guarantee given by the implementation, that would lead to a different
pattern.

> When wrapped into iterators it is superficially elegant, yet comes at a
> price. In more performance-conscious situations it might prove to be too
> expensive.

Hmm. Instead, I think that using a standard library feature would be
recommended for performance reasons too.

[Tim Rentsch]

Paavo Helde <ees...@osa.pri.ee> writes:

> 25.04.2022 15:27 Tim Rentsch kirjutas:
>
>> Juha Nieminen <nos...@thanks.invalid> writes:
>>
>>> Graeme C. <gra...@gmail.com> wrote:
>>
>> [...]
>>
>>>> for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen
>>>
>>> std::vector::size() returns a value of type std::size_t. You
>>> shouldn't be using an int with it.
>>
>> I don't want to start a holy war, but in this particular case
>> there is no problem comparing a signed type to a size_t (which is
>> an unsigned type).
>
> I don't really care if such code uses signed or unsigned types.
> However, there is a problem when comparing signed and unsigned
> types, namely the gcc compiler issues warnings for them with -Wall,
> and sometimes these warnings are actually useful.

IME these warnings from gcc give false positives too often to
be used on every single compile. Of course it can be useful
to turn them on now and then, to make sure nothing is askew,
but trying to avoid them even in all the false positive cases
is IMO more trouble than it is worth.

> So, in order to not lose these useful warnings in the avalanche of
> non-useful ones, one should use matching types in such simple code,
> it does not cost anything.

That seems plainly false. Any change that incurs some programming
effort and disturbs what code is written obviously costs something.
A claim could be made that the cost is worth the benefit, but
clearly the cost is greater than zero.

[Scott Lurndal]

Tim Rentsch <tr.1...@z991.linuxsc.com> writes:
>Paavo Helde <ees...@osa.pri.ee> writes:
>
>> 25.04.2022 15:27 Tim Rentsch kirjutas:
>>
>>> Juha Nieminen <nos...@thanks.invalid> writes:
>>>
>>>> Graeme C. <gra...@gmail.com> wrote:
>>>
>>> [...]
>>>
>>>>> for (int i=0; i<vf[gen-1].size(); i++) { // from previous gen
>>>>
>>>> std::vector::size() returns a value of type std::size_t. You
>>>> shouldn't be using an int with it.
>>>
>>> I don't want to start a holy war, but in this particular case
>>> there is no problem comparing a signed type to a size_t (which is
>>> an unsigned type).
>>
>> I don't really care if such code uses signed or unsigned types.
>> However, there is a problem when comparing signed and unsigned
>> types, namely the gcc compiler issues warnings for them with -Wall,
>> and sometimes these warnings are actually useful.
>
>IME these warnings from gcc give false positives too often to
>be used on every single compile. Of course it can be useful
>to turn them on now and then, to make sure nothing is askew,
>but trying to avoid them even in all the false positive cases
>is IMO more trouble than it is worth.

I beg to differ. We include -Wall and -Werror on all compiles
(well over 2 million lines of C/C++).

It is far too common for C programmers to use 'int' when
the domain of the value doesn't include negative numbers.

[Paavo Helde]

10.05.2022 17:18 Tim Rentsch kirjutas:

> Paavo Helde <ees...@osa.pri.ee> writes:

>> So, in order to not lose these useful warnings in the avalanche of
>> non-useful ones, one should use matching types in such simple code,
>> it does not cost anything.
>
> That seems plainly false. Any change that incurs some programming
> effort and disturbs what code is written obviously costs something.
> A claim could be made that the cost is worth the benefit, but
> clearly the cost is greater than zero.

One can argue that it's using of mismatching types in a comparison which
means non-zero programming effort.

If the types used in a comparison are of different types and especially
of different signedness, the programmer needs to know the promotion
rules which might depend on the operand sizes, which in turn might
depend on the platform/implementation.

The programmer needs to think through what happens when the signed
operand becomes negative. Is it possible and what happens then?

Even more to the point, when a maintenance programmer comes around and
sees the code, they have to think it through again, every time. Why are
incompatible types used in comparison? Was it an oversight and is it
possible it might cause problems?

I will see that as a significant programming effort. YMMV.

[Tim Rentsch]

This sounds like you are offering an implicit argument that
because your group does it all the time it follows that it's
a good idea. I don't find such an argument convincing in any
way.

> It is far too common for C programmers to use 'int' when
> the domain of the value doesn't include negative numbers.

Such cases would still be caught if the signed/unsigned warnings
were turned on only before every code review rather than on every
single compile.

[Tim Rentsch]

Paavo Helde <ees...@osa.pri.ee> writes:

> 10.05.2022 17:18 Tim Rentsch kirjutas:
>
>> Paavo Helde <ees...@osa.pri.ee> writes:
>>
>>> So, in order to not lose these useful warnings in the avalanche of
>>> non-useful ones, one should use matching types in such simple code,
>>> it does not cost anything.
>>
>> That seems plainly false. Any change that incurs some programming
>> effort and disturbs what code is written obviously costs something.
>> A claim could be made that the cost is worth the benefit, but
>> clearly the cost is greater than zero.
>
> One can argue that it's using of mismatching types in a comparison
> which means non-zero programming effort.

That contrast is different than what I was talking about, but let
me respond to your comments here.

> If the types used in a comparison are of different types and
> especially of different signedness, the programmer needs to know the
> promotion rules which might depend on the operand sizes, which in
> turn might depend on the platform/implementation.

This is an overstatement. Comparing two signed types, or two
unsigned types, is always safe, regardless of the widths of the
types involved. It's only when one type is signed and the other
type is unsigned, and the unsigned type is "larger" than int, that
there is even just possibly a problem; for example, comparing a
signed type against an unsigned char, or unsigned short, or
unsigned bit-field whose width is less than the width of unsigned
int, will never give a result different than what the unconverted
values would indicate.

> The programmer needs to think through what happens when the signed
> operand becomes negative. Is it possible and what happens then?

These questions do need to be considered but that doesn't mean
they are difficult necessarily. If we see a code fragment like

int a[] = { ... };

for( Index i = 0; i < sizeof a / sizeof a[0]; i++ ){ ... }

it's immediately obvious that the value in 'i' is non-negative, no
matter whether the type Index is signed or unsigned. Almost no
mental effort is needed.

> Even more to the point, when a maintenance programmer comes around
> and sees the code, they have to think it through again, every time.
> Why are incompatible types used in comparison? Was it an oversight
> and is it possible it might cause problems?

This observation doesn't change the argument. Any factors needing
consideration for the original developer still need consideration
for maintenance work. The same kind of response applies.

> I will see that as a significant programming effort. YMMV.

No one is saying that there is no programming effort involved.
Whether the effort is _significant_ in each case is a different
question. Furthermore, the comments you make are looking at only
one side of the equation. It isn't always practicable to choose
the two types involved so that they must be the same; for example,
one type could be dictated by the type of a third party function
interface, and the other type could be dictated by language
semantics (subtracting one pointer from another gives a signed
type, but sizeof gives an unsigned type). Even when it is feasible
to give the two types the same signedness, doing that may entail
other tradeoffs that have their own costs. For example, if a
parameter 'n' has an unsigned type, we know that it has a
non-negative value. Changing the type of 'n' to be a signed type
would mean either more code in the function to accommodate a
possible negative value of 'n', or more mental effort during
development or maintenance to consider whether such code is needed,
etc (and quite possibly both). A proposed rule that comparands
should /always/ have the same signedness tacitly assumes that this
factor always outweighs all other factors. That assumption simply
isn't right: sometimes it does, but sometimes it doesn't.