My program identifies all the 'one-child' numbers in a range (a
one-child number has only one substring evenly divisible by the length
of the number).

968 has these substrings: [9, 96, 968, 6, 68, 8]
9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number

5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
Only 56 is evenly divisible by 4, so 5671 is a one-child number

$ prog start end [1|2]
examples
$ prog 1 100 1 (no use of printf(), gives incorrect results)
$ prog 1 100 2 (use printf(), gives correct results)
================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//get substring
char *psubstr(char *string, int pos, int length)
{ int cnt;
char *p;
p = malloc(length+1);
while (cnt < length)
{
*(p+cnt) = *(string+pos);
string++;
cnt++;
}
*(p+cnt) = '\0';
return p;
}

int main(int argc, char *argv[])
{ int start = atoi(argv[1]);
int end = atoi(argv[2]);
int printType = atoi(argv[3]);
int i,j,k,len,ssnbr;
int div=0,ocn=0;
char s[10] = "";
char ss[8] = "";
char *pss;

for(i=start;i<=end;i++)
{
//convert number to char
sprintf(s,"%d",i);
len = strlen(s);

//build and evaluate each substring
if(printType == 2) {printf("%s. [",s);}
for (j=0;j<len;j++)
{
for (k=1;k<=len-j;k++)
{
pss = psubstr(s,j,k);
ssnbr = atoi(pss);
if(ssnbr % len == 0) {div+=1;}
if(printType == 2) {printf("%d ",ssnbr);}
}
}
//increment counter, optional print
if(div==1)
{
ocn++;
if(printType == 2) {printf("] *\n");}
}
else
{
if(printType == 2) {printf("]\n");}
}
//reset
div=0;
}

//total count
printf("\n%d one-child numbers from %d to %d", ocn,start,end);
free(pss);
return(0);
} ================================================================

On 30/06/2021 18:26, DFS wrote:
> My program identifies all the 'one-child' numbers in a range (a
> one-child number has only one substring evenly divisible by the length
> of the number).
>
> 968 has these substrings: [9, 96, 968, 6, 68, 8]
> 9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number
>
> 5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
> Only 56 is evenly divisible by 4, so 5671 is a one-child number
>
> $ prog start end [1|2]
> examples
> $ prog 1 100 1   (no use of printf(), gives incorrect results)
> $ prog 1 100 2   (use printf(), gives correct results)
> ================================================================
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> //get substring
> char *psubstr(char *string, int pos, int length)
> {
>    int cnt;
>    char *p;
>    p = malloc(length+1);
>    while (cnt < length)
>    {
>       *(p+cnt) = *(string+pos);
>       string++;
>       cnt++;
>    }
>    *(p+cnt) = '\0';
>    return p;
> }
>

What do you see when you compile with warnings enabled? A quick test
with gcc points out that you are using "cnt" here without initialising
it - thus the behaviour of the code depends entirely on what might
happen to be in registers or the stack when this function is called.

Your main() is also going to leak like a sieve, as you allocate memory
on each call to psubstr but only deallocate the last one. And it
defines "ss" but does not use it, which is almost certainly a bug.

I haven't read the code or attempted to understand it - first pick off
the low-lying fruit that can be found without effort.

On 6/30/2021 1:03 PM, David Brown wrote:
> On 30/06/2021 18:26, DFS wrote:
>> My program identifies all the 'one-child' numbers in a range (a
>> one-child number has only one substring evenly divisible by the length
>> of the number).
>>
>> 968 has these substrings: [9, 96, 968, 6, 68, 8]
>> 9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number
>>
>> 5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
>> Only 56 is evenly divisible by 4, so 5671 is a one-child number
>>
>> $ prog start end [1|2]
>> examples
>> $ prog 1 100 1   (no use of printf(), gives incorrect results)
>> $ prog 1 100 2   (use printf(), gives correct results)
>> ================================================================
>> #include <stdio.h>
>> #include <stdlib.h>
>> #include <string.h>
>>
>> //get substring
>> char *psubstr(char *string, int pos, int length)
>> {
>>    int cnt;
>>    char *p;
>>    p = malloc(length+1);
>>    while (cnt < length)
>>    {
>>       *(p+cnt) = *(string+pos);
>>       string++;
>>       cnt++;
>>    }
>>    *(p+cnt) = '\0';
>>    return p;
>> }
>>
>
> What do you see when you compile with warnings enabled? A quick test
> with gcc points out that you are using "cnt" here without initialising
> it - thus the behaviour of the code depends entirely on what might
> happen to be in registers or the stack when this function is called.
>
> Your main() is also going to leak like a sieve, as you allocate memory
> on each call to psubstr but only deallocate the last one. And it
> defines "ss" but does not use it, which is almost certainly a bug.
>
> I haven't read the code or attempted to understand it - first pick off
> the low-lying fruit that can be found without effort.

using TinyCC 0.9.27 on Windows

$tcc -Wall prog.c -o prog.exe

no warnings whatsoever

(I think you or someone else on clc warned me away from tcc in the past,
but it's so handy)

I made the fixes you spotted

* initialized cnt to 0
* free(pss) in the k loop
* removed the unused char 'ss'

and it now works. Thanks man!

I'm gonna guess the uninitialized variable is the culprit... checked...
that was it.

I'm a little surprised about the performance of this C program, though.
A python version (below) that also doesn't print anything until the
end result is 2x faster for smaller values of 'end'. But when 'end' is
10^5 and up, the C code smokes the python.

Later I'll try it on Linux/gcc, where I expect the performance to be
much better.

================================================================
import sys
start = int(sys.argv[1])
end = int(sys.argv[2])
div,ocn = 0,0
for i in range(start,end+1):
istr = str(i)
ilen = len(istr)
for j in range(0,ilen):
for k in range(j+1,ilen+1):
if int(istr[j:k]) % ilen == 0:
div+=1
if div == 1: ocn+=1
div = 0
print("\n%d one-child numbers from %d to %d" % (ocn,start,end))
================================================================

On Wed, 30 Jun 2021 12:26:02 -0400, DFS <nospam@dfs.com> wrote:

>My program identifies all the 'one-child' numbers in a range (a
>one-child number has only one substring evenly divisible by the length
>of the number).
>
>968 has these substrings: [9, 96, 968, 6, 68, 8]
>9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number
>
>5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
>Only 56 is evenly divisible by 4, so 5671 is a one-child number
>
>$ prog start end [1|2]
>examples
>$ prog 1 100 1 (no use of printf(), gives incorrect results)
>$ prog 1 100 2 (use printf(), gives correct results)
>================================================================
>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>
>//get substring
>char *psubstr(char *string, int pos, int length)
>{
> int cnt;
> char *p;
> p = malloc(length+1);
> while (cnt < length)

Since cnt is not initialized or assigned a value, you have no idea how
often the loop is executed, if at all. Didn't your compiler warn you
about using an indeterminate value? If not, you should up the warning
level.

When I initialize cnt to 0, the program prints 29 in either case.

The difference is not caused by the use of printf. It is caused by
the random value that happens to be in the memory occupied by cnt.

> {
> *(p+cnt) = *(string+pos);
> string++;
> cnt++;
> }
> *(p+cnt) = '\0';
> return p;
>}
>
>
>int main(int argc, char *argv[])
>{
> int start = atoi(argv[1]);
> int end = atoi(argv[2]);
> int printType = atoi(argv[3]);
> int i,j,k,len,ssnbr;
> int div=0,ocn=0;
> char s[10] = "";
> char ss[8] = "";
> char *pss;
>
> for(i=start;i<=end;i++)
> {
> //convert number to char
> sprintf(s,"%d",i);
> len = strlen(s);
>
> //build and evaluate each substring
> if(printType == 2) {printf("%s. [",s);}
> for (j=0;j<len;j++)
> {
> for (k=1;k<=len-j;k++)
> {
> pss = psubstr(s,j,k);

pss now points to memory that was allocated in psubstr. psubstr will
allocate new memory each iteration of this loop. The memory is not
freed until the very end of the program. The address of the previous
allocation is lost. You have multiple memory leaks.

> ssnbr = atoi(pss);
> if(ssnbr % len == 0) {div+=1;}
> if(printType == 2) {printf("%d ",ssnbr);}
> }
> }
>
> //increment counter, optional print
> if(div==1)
> {
> ocn++;
> if(printType == 2) {printf("] *\n");}
> }
> else
> {
> if(printType == 2) {printf("]\n");}
> }
>
> //reset
> div=0;
>
> }
>
>//total count
>printf("\n%d one-child numbers from %d to %d", ocn,start,end);
>free(pss);

This frees only the last memory allocated.

>return(0);
>}
>================================================================

--
Remove del for email

On 30/06/2021 18:58, DFS wrote:
> On 6/30/2021 1:03 PM, David Brown wrote:

>> What do you see when you compile with warnings enabled?  A quick test
>> with gcc points out that you are using "cnt" here without initialising
>> it - thus the behaviour of the code depends entirely on what might
>> happen to be in registers or the stack when this function is called.
>>
>> Your main() is also going to leak like a sieve, as you allocate memory
>> on each call to psubstr but only deallocate the last one.  And it
>> defines "ss" but does not use it, which is almost certainly a bug.
>>
>> I haven't read the code or attempted to understand it - first pick off
>> the low-lying fruit that can be found without effort.
>
>
>
> using TinyCC 0.9.27 on Windows
>
> $tcc -Wall prog.c -o prog.exe
>
> no warnings whatsoever
>
> (I think you or someone else on clc warned me away from tcc in the past,
> but it's so handy)

You're allowed to use gcc with lots of options from time to time to
check that all's well. Then go back to the much faster compiler.

>
> I made the fixes you spotted
>
> * initialized cnt to 0
> * free(pss) in the k loop
> * removed the unused char 'ss'
>
>
> and it now works.  Thanks man!

I added this at the start of main:

if (argc<4) {
printf("Usage: %s start end 1/2\n",argv[0]);
exit(0);
}

Otherwise it crashes if run with no inputs.

> I'm a little surprised about the performance of this C program, though.
>  A python version (below) that also doesn't print anything until the
> end result is 2x faster for smaller values of 'end'.  But when 'end' is
> 10^5 and up, the C code smokes the python.

> Later I'll try it on Linux/gcc, where I expect the performance to be
> much better.

I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy
(accelerated version of Python) took 17 seconds.

tcc took 56 seconds, only 35% slower than gcc-O3.

But I suspect that in all cases, what is dominant is the conversion from
int to text, from text back to int, and applying the mod operator. All
things that happen outside of the code generated from your source.

On 6/30/2021 2:36 PM, Barry Schwarz wrote:
> On Wed, 30 Jun 2021 12:26:02 -0400, DFS <nospam@dfs.com> wrote:
>
>> My program identifies all the 'one-child' numbers in a range (a
>> one-child number has only one substring evenly divisible by the length
>> of the number).
>>
>> 968 has these substrings: [9, 96, 968, 6, 68, 8]
>> 9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number
>>
>> 5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
>> Only 56 is evenly divisible by 4, so 5671 is a one-child number
>>
>> $ prog start end [1|2]
>> examples
>> $ prog 1 100 1 (no use of printf(), gives incorrect results)
>> $ prog 1 100 2 (use printf(), gives correct results)
>> ================================================================
>> #include <stdio.h>
>> #include <stdlib.h>
>> #include <string.h>
>>
>> //get substring
>> char *psubstr(char *string, int pos, int length)
>> {
>> int cnt;
>> char *p;
>> p = malloc(length+1);
>> while (cnt < length)
>
> Since cnt is not initialized or assigned a value, you have no idea how
> often the loop is executed, if at all. Didn't your compiler warn you
> about using an indeterminate value? If not, you should up the warning
> level.
>
> When I initialize cnt to 0, the program prints 29 in either case.

Right. Thanks for your testing.

> The difference is not caused by the use of printf.

Any idea, then, why using printf() returns correct results?

The substr function is called the same number of times regardless.

> It is caused by the random value that happens to be in the
> memory occupied by cnt.

I didn't note in my op but the incorrect value shown with no printf() is
always 9, which is the number of one-child values in F(10^1).

Without printf()
F(10^1) = 9
F(10^2) = 9
F(10^3) = 9
F(10^4) = 9
F(10^5) = 9

With printf()
F(10^1) = 9
F(10^2) = 29
F(10^3) = 389
F(10^4) = 3090
F(10^5) = 7186

So it doesn't seem to be random.

But since cnt isn't initialized, does the compiler auto-assign a 0 on
the first call to cnt++?

On 6/30/2021 2:44 PM, Bart wrote:
> On 30/06/2021 18:58, DFS wrote:
>> On 6/30/2021 1:03 PM, David Brown wrote:
>
>>> What do you see when you compile with warnings enabled?  A quick test
>>> with gcc points out that you are using "cnt" here without initialising
>>> it - thus the behaviour of the code depends entirely on what might
>>> happen to be in registers or the stack when this function is called.
>>>
>>> Your main() is also going to leak like a sieve, as you allocate memory
>>> on each call to psubstr but only deallocate the last one.  And it
>>> defines "ss" but does not use it, which is almost certainly a bug.
>>>
>>> I haven't read the code or attempted to understand it - first pick off
>>> the low-lying fruit that can be found without effort.
>>
>>
>>
>> using TinyCC 0.9.27 on Windows
>>
>> $tcc -Wall prog.c -o prog.exe
>>
>> no warnings whatsoever
>>
>> (I think you or someone else on clc warned me away from tcc in the
>> past, but it's so handy)
>
> You're allowed to use gcc with lots of options from time to time to
> check that all's well. Then go back to the much faster compiler.

For my little code it's about a half-second either way.

>> I made the fixes you spotted
>>
>> * initialized cnt to 0
>> * free(pss) in the k loop
>> * removed the unused char 'ss'
>>
>>
>> and it now works.  Thanks man!
>
> I added this at the start of main:
>
>     if (argc<4) {
>         printf("Usage: %s start end 1/2\n",argv[0]);
>         exit(0);
>     }
>
> Otherwise it crashes if run with no inputs.

Thou must read the instructions:

$ prog start end [1|2]

>> I'm a little surprised about the performance of this C program,
>> though.   A python version (below) that also doesn't print anything
>> until the end result is 2x faster for smaller values of 'end'.  But
>> when 'end' is 10^5 and up, the C code smokes the python.
>
>> Later I'll try it on Linux/gcc, where I expect the performance to be
>> much better.
>
> I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy
> (accelerated version of Python) took 17 seconds.

Not bad numbers for python and F(10^7), but this code is part of me
trying to solve Project Euler 413, which asks for F(10^19).

You can't brute force that with a desktop PC.

> tcc took 56 seconds, only 35% slower than gcc-O3.
>
> But I suspect that in all cases, what is dominant is the conversion from
> int to text, from text back to int, and applying the mod operator. All
> things that happen outside of the code generated from your source.

I don't understand 'happen outside'.

Thanks for looking at it.

On Wed, 30 Jun 2021 16:03:37 -0400, DFS <nospam@dfs.com> wrote:

>On 6/30/2021 2:36 PM, Barry Schwarz wrote:
>> On Wed, 30 Jun 2021 12:26:02 -0400, DFS <nospam@dfs.com> wrote:
>>
>>> My program identifies all the 'one-child' numbers in a range (a
>>> one-child number has only one substring evenly divisible by the length
>>> of the number).
>>>
>>> 968 has these substrings: [9, 96, 968, 6, 68, 8]
>>> 9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child number
>>>
>>> 5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
>>> Only 56 is evenly divisible by 4, so 5671 is a one-child number
>>>
>>> $ prog start end [1|2]
>>> examples
>>> $ prog 1 100 1 (no use of printf(), gives incorrect results)
>>> $ prog 1 100 2 (use printf(), gives correct results)
>>> ================================================================
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <string.h>
>>>
>>> //get substring
>>> char *psubstr(char *string, int pos, int length)
>>> {
>>> int cnt;
>>> char *p;
>>> p = malloc(length+1);
>>> while (cnt < length)
>>
>> Since cnt is not initialized or assigned a value, you have no idea how
>> often the loop is executed, if at all. Didn't your compiler warn you
>> about using an indeterminate value? If not, you should up the warning
>> level.
>>
>> When I initialize cnt to 0, the program prints 29 in either case.
>
>Right. Thanks for your testing.
>
>
>> The difference is not caused by the use of printf.
>
>Any idea, then, why using printf() returns correct results?
>
>The substr function is called the same number of times regardless.

Once you have undefined behavior, all bets are off. While it may be
true that psubstr is called the same number of times, the while will
definitely iterate a different number of times depending an the random
value in cnt.

Furthermore, after the first call to psubstr returns, cnt will equal
length. If the memory occupied by cnt is unchanged, on subsequent
calls the while loop will terminate immediately since cnt is not less
than length (until length changes as in going from 9 to 10).

The bottom line is that undefined behavior can have any result. One
of the worst results is to sometimes do what you want or expect.

> > It is caused by the random value that happens to be in the
> > memory occupied by cnt.
>
>I didn't note in my op but the incorrect value shown with no printf() is
>always 9, which is the number of one-child values in F(10^1).

When I ran my test case with cnt initialized to 3 (a random value), I
also got 9 as the result, both with and without printf.
>Without printf()
>F(10^1) = 9
>F(10^2) = 9
>F(10^3) = 9
>F(10^4) = 9
>F(10^5) = 9
>
>
>With printf()
>F(10^1) = 9
>F(10^2) = 29
>F(10^3) = 389
>F(10^4) = 3090
>F(10^5) = 7186
>
>
>So it doesn't seem to be random.
>
>But since cnt isn't initialized, does the compiler auto-assign a 0 on
>the first call to cnt++?

--
Remove del for email

DFS <nospam@dfs.com> writes:

> On 6/30/2021 2:44 PM, Bart wrote:
<cut>
>> But I suspect that in all cases, what is dominant is the conversion
>> from int to text, from text back to int, and applying the mod
>> operator. All things that happen outside of the code generated from
>> your source.
>
> I don't understand 'happen outside'.

I think he means that your calls to atoi are doing most of the work, so
you can't get much more speed from tinkering with the code you actually
wrote.

That's not quite right in that you can get a good speed-up by not
generating all those sub-strings. You already have the full number in
's' so you can get sub-string numbers by doing this:

char save = s[j+k];
s[j+k] = 0;
ssnbr = atoi(s+j);
s[j+k] = save;

Having said that, Bart's point still holds. This can be seen as a
purely arithmetical problem. There is no need for strings conversions
(and hence atoi) at all. Whether that would make the code faster is not
obvious, but I suspect it might. I've not have time to try it.

> Thanks for looking at it.

Your code looks a little old fashioned. But even sticking to old C
standards you could tidy it up a but. For example, it's neater to
declare int div = 0; in the block that needs it, rather than "resetting"
at the bottom of the loop.

--
Ben.

On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
>
>> On 6/30/2021 2:44 PM, Bart wrote:
> <cut>
>>> But I suspect that in all cases, what is dominant is the conversion
>>> from int to text, from text back to int, and applying the mod
>>> operator. All things that happen outside of the code generated from
>>> your source.
>>
>> I don't understand 'happen outside'.
>
> I think he means that your calls to atoi are doing most of the work, so
> you can't get much more speed from tinkering with the code you actually
> wrote.
>
> That's not quite right in that you can get a good speed-up by not
> generating all those sub-strings. You already have the full number in
> 's' so you can get sub-string numbers by doing this:
>
> char save = s[j+k];
> s[j+k] = 0;
> ssnbr = atoi(s+j);
> s[j+k] = save;

Geez, that block means less code overall, and the prog runs
significantly faster. Where do you mad geniuses come from?

> Having said that, Bart's point still holds. This can be seen as a
> purely arithmetical problem. There is no need for strings conversions
> (and hence atoi) at all. Whether that would make the code faster is not
> obvious, but I suspect it might. I've not have time to try it.

Careful of gotchas. These are all the substrings of 104, including the
leading-zero dropped '04':

[1 10 104 0 4 4]

Note that it's a one-child number because out of all those substrings,
only 0 is evenly divisible by 3 (the length of 104).

>> Thanks for looking at it.
>
> Your code looks a little old fashioned. But even sticking to old C
> standards you could tidy it up a but. For example, it's neater to
> declare int div = 0; in the block that needs it, rather than "resetting"
> at the bottom of the loop.

First I had it just above the j loop, but moved it down to be near its
last use.

On 30/06/2021 19:58, DFS wrote:
> On 6/30/2021 1:03 PM, David Brown wrote:
>> On 30/06/2021 18:26, DFS wrote:
>>> My program identifies all the 'one-child' numbers in a range (a
>>> one-child number has only one substring evenly divisible by the length
>>> of the number).
>>>
>>> 968 has these substrings: [9, 96, 968, 6, 68, 8]
>>> 9 and 96 and 6 are evenly divisible by 3, so 968 is not a one-child
>>> number
>>>
>>> 5671 has these substrings: [5, 56, 567, 5671, 6, 67, 671, 7, 71, 1]
>>> Only 56 is evenly divisible by 4, so 5671 is a one-child number
>>>
>>> $ prog start end [1|2]
>>> examples
>>> $ prog 1 100 1   (no use of printf(), gives incorrect results)
>>> $ prog 1 100 2   (use printf(), gives correct results)
>>> ================================================================
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <string.h>
>>>
>>> //get substring
>>> char *psubstr(char *string, int pos, int length)
>>> {
>>>     int cnt;
>>>     char *p;
>>>     p = malloc(length+1);
>>>     while (cnt < length)
>>>     {
>>>        *(p+cnt) = *(string+pos);
>>>        string++;
>>>        cnt++;
>>>     }
>>>     *(p+cnt) = '\0';
>>>     return p;
>>> }
>>>
>>
>> What do you see when you compile with warnings enabled?  A quick test
>> with gcc points out that you are using "cnt" here without initialising
>> it - thus the behaviour of the code depends entirely on what might
>> happen to be in registers or the stack when this function is called.
>>
>> Your main() is also going to leak like a sieve, as you allocate memory
>> on each call to psubstr but only deallocate the last one.  And it
>> defines "ss" but does not use it, which is almost certainly a bug.
>>
>> I haven't read the code or attempted to understand it - first pick off
>> the low-lying fruit that can be found without effort.
>
>
>
> using TinyCC 0.9.27 on Windows
>
> $tcc -Wall prog.c -o prog.exe
>
> no warnings whatsoever
>
> (I think you or someone else on clc warned me away from tcc in the past,
> but it's so handy)

That was probably me. Using tcc for development is a silly idea - get a
decent compiler that will help your development. A screwdriver kit from
a Christmas cracker may be handy when you want something very small and
light, but you don't use it for fixing your car.

At the very least, paste your code into <https://godbolt.org> and use
"gcc -O2 -Wall -Wextra" there.

>
>
> I made the fixes you spotted
>
> * initialized cnt to 0
> * free(pss) in the k loop
> * removed the unused char 'ss'
>
>
> and it now works.  Thanks man!
>
>
> I'm gonna guess the uninitialized variable is the culprit... checked...
> that was it.

Yes. The other points were wastage and inefficiency, but would not
affect the correctness.

>
> I'm a little surprised about the performance of this C program, though.
>  A python version (below) that also doesn't print anything until the end
> result is 2x faster for smaller values of 'end'.  But when 'end' is 10^5
> and up, the C code smokes the python.
>

There are many things that can affect performance, and Python can be
surprisingly efficient at times. It's fun to try this kind of thing and
see how you can improve the speeds. (You could try pypy, for example.)

> Later I'll try it on Linux/gcc, where I expect the performance to be
> much better.
>
>
> ================================================================
> import sys
> start = int(sys.argv[1])
> end   = int(sys.argv[2])
> div,ocn = 0,0
> for i in range(start,end+1):
>     istr = str(i)
>     ilen = len(istr)
>     for j in range(0,ilen):
>         for k in range(j+1,ilen+1):
>             if int(istr[j:k]) % ilen == 0:
>                 div+=1
>     if div == 1: ocn+=1
>     div = 0
> print("\n%d one-child numbers from %d to %d" % (ocn,start,end))
> ================================================================
>

On Wed, 30 Jun 2021 12:26:02 -0400, DFS <nospam@dfs.com> wrote:

>//get substring
>char *psubstr(char *string, int pos, int length)
>{
> int cnt;

if length is 10 and cnt is 1000

> char *p;
> p = malloc(length+1);
> while (cnt < length)
> {
> *(p+cnt) = *(string+pos);
> string++;
> cnt++;
> }
> *(p+cnt) = '\0';

this write one 0 out the memory allocated

if cnt=0 in the start at end of loop cnt=length=3
0 1 2 3 index space memory reserved (4 spaces)
at end of loop cnt=length=3 ok

> return p;
>}

On 01/07/2021 05:54, DFS wrote:
> On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> On 6/30/2021 2:44 PM, Bart wrote:
>> <cut>
>>>> But I suspect that in all cases, what is dominant is the conversion
>>>> from int to text, from text back to int, and applying the mod
>>>> operator. All things that happen outside of the code generated from
>>>> your source.
>>>
>>> I don't understand 'happen outside'.
>>
>> I think he means that your calls to atoi are doing most of the work, so
>> you can't get much more speed from tinkering with the code you actually
>> wrote.
>>
>> That's not quite right in that you can get a good speed-up by not
>> generating all those sub-strings.  You already have the full number in
>> 's' so you can get sub-string numbers by doing this:
>>
>>    char save = s[j+k];
>>    s[j+k] = 0;
>>    ssnbr = atoi(s+j);
>>    s[j+k] = save;
>
>
> Geez, that block means less code overall, and the prog runs
> significantly faster.  Where do you mad geniuses come from?
>

I haven't studied the code (or the problem), but if that change also
removes the call to the function with malloc(), it will help significantly.

Whenever you see "malloc" in your code, think "slow". When you have a
malloc in the middle of your inner loop, think "very slow". Avoid it if
at all possible - and in your original code, it is useless.

To see the cost of malloc, go back to the original code (with the "int
cnt = 0;" fix). Figure out the maximum length (9, for 32-bit int) and
have a single "static char buff[9];". Use that instead of malloc in
psubstr, and measure the difference in time.

>
>> Having said that, Bart's point still holds.  This can be seen as a
>> purely arithmetical problem.  There is no need for strings conversions
>> (and hence atoi) at all.  Whether that would make the code faster is not
>> obvious, but I suspect it might.  I've not have time to try it.
>
> Careful of gotchas.  These are all the substrings of 104, including the
> leading-zero dropped '04':
>
> [1 10 104 0 4 4]
>
> Note that it's a one-child number because out of all those substrings,
> only 0 is evenly divisible by 3 (the length of 104).
>
>
>
>
>>> Thanks for looking at it.
>>
>> Your code looks a little old fashioned.  But even sticking to old C
>> standards you could tidy it up a but.  For example, it's neater to
>> declare int div = 0; in the block that needs it, rather than "resetting"
>> at the bottom of the loop.
>
> First I had it just above the j loop, but moved it down to be near its
> last use.
>
>

On 30/06/2021 22:03, DFS wrote:
> On 6/30/2021 2:36 PM, Barry Schwarz wrote:
>> On Wed, 30 Jun 2021 12:26:02 -0400, DFS <nospam@dfs.com> wrote:
>>

>>>
>>> //get substring
>>> char *psubstr(char *string, int pos, int length)
>>> {
>>>     int cnt;
>>>     char *p;
>>>     p = malloc(length+1);
>>>     while (cnt < length)
>>

> So it doesn't seem to be random.

The value of "cnt" here is "indeterminate" - C says nothing about what
it might be. In practice, it will be a left-over from whatever happened
before this function was called. By luck - nothing but luck - the call
to printf had left zero in the register or stack address used by cnt. A
different compiler, or different flags, or different source code could
result in completely different answers.

>
> But since cnt isn't initialized, does the compiler auto-assign a 0 on
> the first call to cnt++?
>

No.

Non-static local data is not automatically initialised.

DFS <nospam@dfs.com> writes:

> On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> On 6/30/2021 2:44 PM, Bart wrote:
>> <cut>
>>>> But I suspect that in all cases, what is dominant is the conversion
>>>> from int to text, from text back to int, and applying the mod
>>>> operator. All things that happen outside of the code generated from
>>>> your source.
>>>
>>> I don't understand 'happen outside'.
>> I think he means that your calls to atoi are doing most of the work, so
>> you can't get much more speed from tinkering with the code you actually
>> wrote.
>> That's not quite right in that you can get a good speed-up by not
>> generating all those sub-strings. You already have the full number in
>> 's' so you can get sub-string numbers by doing this:
>> char save = s[j+k];
>> s[j+k] = 0;
>> ssnbr = atoi(s+j);
>> s[j+k] = save;
>
> Geez, that block means less code overall, and the prog runs
> significantly faster. Where do you mad geniuses come from?

Actually there is no genius involved (IMO). It's mostly the result of
having written and (possibly more importantly) read code for more than
40 years. You pick up stuff along the way.

>> Having said that, Bart's point still holds. This can be seen as a
>> purely arithmetical problem. There is no need for strings conversions
>> (and hence atoi) at all. Whether that would make the code faster is not
>> obvious, but I suspect it might. I've not have time to try it.
>
> Careful of gotchas. These are all the substrings of 104, including
> the leading-zero dropped '04':

Whether that's a gotcha or not depends on how you tackle the problem.

I've written an arithmetic version (i.e. no strings) and it is
significantly faster again. I thought it probably would be. You might
want to have a go...

>>> Thanks for looking at it.
>> Your code looks a little old fashioned. But even sticking to old C
>> standards you could tidy it up a but. For example, it's neater to
>> declare int div = 0; in the block that needs it, rather than "resetting"
>> at the bottom of the loop.
>
> First I had it just above the j loop, but moved it down to be near its
> last use.

I'm not sure that's really my point. div is used only in that loop so
this pattern

for (....) {
int count = 0;
....
code that might do count += 1;
....
}

is clearer and better overall than this pattern:

int count = 0;
....
for (....) {
....
code that might do count += 1;
....
count = 0;
}

--
Ben.

On Thursday, July 1, 2021 at 12:38:21 PM UTC+3, Ben Bacarisse wrote:
> DFS <nos...@dfs.com> writes:
>
> > On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
> >> DFS <nos...@dfs.com> writes:
> >>
> >>> On 6/30/2021 2:44 PM, Bart wrote:
> >> <cut>
> >>>> But I suspect that in all cases, what is dominant is the conversion
> >>>> from int to text, from text back to int, and applying the mod
> >>>> operator. All things that happen outside of the code generated from
> >>>> your source.
> >>>
> >>> I don't understand 'happen outside'.
> >> I think he means that your calls to atoi are doing most of the work, so
> >> you can't get much more speed from tinkering with the code you actually
> >> wrote.
> >> That's not quite right in that you can get a good speed-up by not
> >> generating all those sub-strings. You already have the full number in
> >> 's' so you can get sub-string numbers by doing this:
> >> char save = s[j+k];
> >> s[j+k] = 0;
> >> ssnbr = atoi(s+j);
> >> s[j+k] = save;
> >
> > Geez, that block means less code overall, and the prog runs
> > significantly faster. Where do you mad geniuses come from?
> Actually there is no genius involved (IMO). It's mostly the result of
> having written and (possibly more importantly) read code for more than
> 40 years. You pick up stuff along the way.
> >> Having said that, Bart's point still holds. This can be seen as a
> >> purely arithmetical problem. There is no need for strings conversions
> >> (and hence atoi) at all. Whether that would make the code faster is not
> >> obvious, but I suspect it might. I've not have time to try it.
> >
> > Careful of gotchas. These are all the substrings of 104, including
> > the leading-zero dropped '04':
> Whether that's a gotcha or not depends on how you tackle the problem.
>
> I've written an arithmetic version (i.e. no strings) and it is
> significantly faster again.

Does it include replacement of division by reciprocal multiplication?

> I thought it probably would be. You might
> want to have a go...
> >>> Thanks for looking at it.
> >> Your code looks a little old fashioned. But even sticking to old C
> >> standards you could tidy it up a but. For example, it's neater to
> >> declare int div = 0; in the block that needs it, rather than "resetting"
> >> at the bottom of the loop.
> >
> > First I had it just above the j loop, but moved it down to be near its
> > last use.
> I'm not sure that's really my point. div is used only in that loop so
> this pattern
>
> for (....) {
> int count = 0;
> ....
> code that might do count += 1;
> ....
> }
>
> is clearer and better overall than this pattern:
>
> int count = 0;
> ....
> for (....) {
> ....
> code that might do count += 1;
> ....
> count = 0;
> }
>
> --
> Ben.

On Wednesday, June 30, 2021 at 11:16:53 PM UTC+3, DFS wrote:
> On 6/30/2021 2:44 PM, Bart wrote:
> > On 30/06/2021 18:58, DFS wrote:
> >> On 6/30/2021 1:03 PM, David Brown wrote:
> >
> >>> What do you see when you compile with warnings enabled? A quick test
> >>> with gcc points out that you are using "cnt" here without initialising
> >>> it - thus the behaviour of the code depends entirely on what might
> >>> happen to be in registers or the stack when this function is called.
> >>>
> >>> Your main() is also going to leak like a sieve, as you allocate memory
> >>> on each call to psubstr but only deallocate the last one. And it
> >>> defines "ss" but does not use it, which is almost certainly a bug.
> >>>
> >>> I haven't read the code or attempted to understand it - first pick off
> >>> the low-lying fruit that can be found without effort.
> >>
> >>
> >>
> >> using TinyCC 0.9.27 on Windows
> >>
> >> $tcc -Wall prog.c -o prog.exe
> >>
> >> no warnings whatsoever
> >>
> >> (I think you or someone else on clc warned me away from tcc in the
> >> past, but it's so handy)
> >
> > You're allowed to use gcc with lots of options from time to time to
> > check that all's well. Then go back to the much faster compiler.
> For my little code it's about a half-second either way.
> >> I made the fixes you spotted
> >>
> >> * initialized cnt to 0
> >> * free(pss) in the k loop
> >> * removed the unused char 'ss'
> >>
> >>
> >> and it now works. Thanks man!
> >
> > I added this at the start of main:
> >
> > if (argc<4) {
> > printf("Usage: %s start end 1/2\n",argv[0]);
> > exit(0);
> > }
> >
> > Otherwise it crashes if run with no inputs.
> Thou must read the instructions:
> $ prog start end [1|2]
> >> I'm a little surprised about the performance of this C program,
> >> though. A python version (below) that also doesn't print anything
> >> until the end result is 2x faster for smaller values of 'end'. But
> >> when 'end' is 10^5 and up, the C code smokes the python.
> >
> >> Later I'll try it on Linux/gcc, where I expect the performance to be
> >> much better.
> >
> > I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy
> > (accelerated version of Python) took 17 seconds.
> Not bad numbers for python and F(10^7), but this code is part of me
> trying to solve Project Euler 413, which asks for F(10^19).
>
> You can't brute force that with a desktop PC.

If you understand that it can't be done by brute force then why are you trying to do just that?
Supposedly, the speed of your code could be improved by factor of 10 or, with a bit of algorithmic
smarts, even by factor of 100. It's still does not bring your to the point where we can tackle the challenge
either with a single desktop PC or with networks of few thousands of 50-core servers.

> > tcc took 56 seconds, only 35% slower than gcc-O3.
> >
> > But I suspect that in all cases, what is dominant is the conversion from
> > int to text, from text back to int, and applying the mod operator. All
> > things that happen outside of the code generated from your source.
> I don't understand 'happen outside'.
>
> Thanks for looking at it.

On 02/07/2021 11:20, Michael S wrote:
> On Wednesday, June 30, 2021 at 11:16:53 PM UTC+3, DFS wrote:
>> On 6/30/2021 2:44 PM, Bart wrote:

>>> I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy
>>> (accelerated version of Python) took 17 seconds.
>> Not bad numbers for python and F(10^7), but this code is part of me
>> trying to solve Project Euler 413, which asks for F(10^19).
>>
>> You can't brute force that with a desktop PC.
>
> If you understand that it can't be done by brute force then why are you trying to do just that?
> Supposedly, the speed of your code could be improved by factor of 10 or, with a bit of algorithmic
> smarts, even by factor of 100. It's still does not bring your to the point where we can tackle the challenge
> either with a single desktop PC or with networks of few thousands of 50-core servers.

It wouldn't get very far using 'int' types either, which limits it to
F(10^9). It would need to use uint64_t (with changes to atoi etc) to
manage F(10^19).

I guess that's why that limit was chosen.

Python of course could go well beyond F10^19), given enough time.

On Friday, July 2, 2021 at 1:43:06 PM UTC+3, Bart wrote:
> On 02/07/2021 11:20, Michael S wrote:
> > On Wednesday, June 30, 2021 at 11:16:53 PM UTC+3, DFS wrote:
> >> On 6/30/2021 2:44 PM, Bart wrote:
>
> >>> I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy
> >>> (accelerated version of Python) took 17 seconds.
> >> Not bad numbers for python and F(10^7), but this code is part of me
> >> trying to solve Project Euler 413, which asks for F(10^19).
> >>
> >> You can't brute force that with a desktop PC.
> >
> > If you understand that it can't be done by brute force then why are you trying to do just that?
> > Supposedly, the speed of your code could be improved by factor of 10 or, with a bit of algorithmic
> > smarts, even by factor of 100. It's still does not bring your to the point where we can tackle the challenge
> > either with a single desktop PC or with networks of few thousands of 50-core servers.
> It wouldn't get very far using 'int' types either, which limits it to
> F(10^9). It would need to use uint64_t (with changes to atoi etc) to
> manage F(10^19).
>
> I guess that's why that limit was chosen.
>
> Python of course could go well beyond F10^19), given enough time.

Read posts of Ben Bacarisse. atai() or similar functions are not needed at all.
If you are a bit smart about algorithms then 64-bit arithmetic is not needed either.
In fact, even 32-bit arithmetic is not necessary.
Suppose, you have a substring "abc...x". You have its reminder r1 already calculated.
Then, for a substring "abc...xy" reminder is equal to (r1*10+x) % nDig.
For nDig<=19 all numbers involved in calculations fit in uint8_t.
As a next step, you can replace modulo operation with table lookup, which would be quicker,
because lookup table is small and easily fits in L1D cache.
But all that wouldn't help to even remotely approach a problem of size 10**19.

Michael S <already5chosen@yahoo.com> writes:

> On Thursday, July 1, 2021 at 12:38:21 PM UTC+3, Ben Bacarisse wrote:
>> DFS <nos...@dfs.com> writes:
>>
>> > On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
>> >> DFS <nos...@dfs.com> writes:
>> >>
>> >>> On 6/30/2021 2:44 PM, Bart wrote:
>> >> <cut>
>> >>>> But I suspect that in all cases, what is dominant is the conversion
>> >>>> from int to text, from text back to int, and applying the mod
>> >>>> operator. All things that happen outside of the code generated from
>> >>>> your source.
>> >>>
>> >>> I don't understand 'happen outside'.
>> >> I think he means that your calls to atoi are doing most of the work, so
>> >> you can't get much more speed from tinkering with the code you actually
>> >> wrote.
>> >> That's not quite right in that you can get a good speed-up by not
>> >> generating all those sub-strings. You already have the full number in
>> >> 's' so you can get sub-string numbers by doing this:
>> >> char save = s[j+k];
>> >> s[j+k] = 0;
>> >> ssnbr = atoi(s+j);
>> >> s[j+k] = save;
>> >
>> > Geez, that block means less code overall, and the prog runs
>> > significantly faster. Where do you mad geniuses come from?
>> Actually there is no genius involved (IMO). It's mostly the result of
>> having written and (possibly more importantly) read code for more than
>> 40 years. You pick up stuff along the way.
>> >> Having said that, Bart's point still holds. This can be seen as a
>> >> purely arithmetical problem. There is no need for strings conversions
>> >> (and hence atoi) at all. Whether that would make the code faster is not
>> >> obvious, but I suspect it might. I've not have time to try it.
>> >
>> > Careful of gotchas. These are all the substrings of 104, including
>> > the leading-zero dropped '04':
>> Whether that's a gotcha or not depends on how you tackle the problem.
>>
>> I've written an arithmetic version (i.e. no strings) and it is
>> significantly faster again.
>
> Does it include replacement of division by reciprocal multiplication?

No, it's a plain integer / and % version. Have you got one that does
something clever with the divisions?

--
Ben.

DFS <nospam@dfs.com> writes:

> Not bad numbers for python and F(10^7), but this code is part of me
> trying to solve Project Euler 413, which asks for F(10^19).

I didn't know that. As you say, a different algorithm is called for.

(My best naive version gets F(10^9) in 4m21.489s and F(10^7) in 2.177s.)

--
Ben.

On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote:
> Michael S <already...@yahoo.com> writes:
>
> > On Thursday, July 1, 2021 at 12:38:21 PM UTC+3, Ben Bacarisse wrote:
> >> DFS <nos...@dfs.com> writes:
> >>
> >> > On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
> >> >> DFS <nos...@dfs.com> writes:
> >> >>
> >> >>> On 6/30/2021 2:44 PM, Bart wrote:
> >> >> <cut>
> >> >>>> But I suspect that in all cases, what is dominant is the conversion
> >> >>>> from int to text, from text back to int, and applying the mod
> >> >>>> operator. All things that happen outside of the code generated from
> >> >>>> your source.
> >> >>>
> >> >>> I don't understand 'happen outside'.
> >> >> I think he means that your calls to atoi are doing most of the work, so
> >> >> you can't get much more speed from tinkering with the code you actually
> >> >> wrote.
> >> >> That's not quite right in that you can get a good speed-up by not
> >> >> generating all those sub-strings. You already have the full number in
> >> >> 's' so you can get sub-string numbers by doing this:
> >> >> char save = s[j+k];
> >> >> s[j+k] = 0;
> >> >> ssnbr = atoi(s+j);
> >> >> s[j+k] = save;
> >> >
> >> > Geez, that block means less code overall, and the prog runs
> >> > significantly faster. Where do you mad geniuses come from?
> >> Actually there is no genius involved (IMO). It's mostly the result of
> >> having written and (possibly more importantly) read code for more than
> >> 40 years. You pick up stuff along the way.
> >> >> Having said that, Bart's point still holds. This can be seen as a
> >> >> purely arithmetical problem. There is no need for strings conversions
> >> >> (and hence atoi) at all. Whether that would make the code faster is not
> >> >> obvious, but I suspect it might. I've not have time to try it.
> >> >
> >> > Careful of gotchas. These are all the substrings of 104, including
> >> > the leading-zero dropped '04':
> >> Whether that's a gotcha or not depends on how you tackle the problem.
> >>
> >> I've written an arithmetic version (i.e. no strings) and it is
> >> significantly faster again.
> >
> > Does it include replacement of division by reciprocal multiplication?
> No, it's a plain integer / and % version. Have you got one that does
> something clever with the divisions?
>
> --
> Ben.

No, I didn't.
Have more interesting things to do.
Besides, brute force is so obvious dead end...

On 7/2/2021 10:21 AM, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
>
>> Not bad numbers for python and F(10^7), but this code is part of me
>> trying to solve Project Euler 413, which asks for F(10^19).
>
> I didn't know that. As you say, a different algorithm is called for.
>
> (My best naive version gets F(10^9) in 4m21.489s and F(10^7) in 2.177s.)

That's very good.

"Each problem has been designed according to a 'one-minute rule', which
means that although it may take several hours to design a successful
algorithm with more difficult problems, an efficient implementation will
allow a solution to be obtained on a modestly powered computer in less
than one minute."

https://projecteuler.net

On 7/1/2021 4:46 AM, David Brown wrote:
> On 30/06/2021 19:58, DFS wrote:

> At the very least, paste your code into <https://godbolt.org> and use
> "gcc -O2 -Wall -Wextra" there.

Incredible site - thanks for the link.

-Wall -Wextra is pretty strict. It even warned of unused 'argc' from
main().

> There are many things that can affect performance, and Python can be
> surprisingly efficient at times. It's fun to try this kind of thing and
> see how you can improve the speeds. (You could try pypy, for example.)

I saw Bart tried pypy and got good results. I tried pypy3 on the below
and got a 13.8x speed increase over python for F(10^6) and F(10^7).

>> ================================================================
>> import sys
>> start = int(sys.argv[1])
>> end   = int(sys.argv[2])
>> div,ocn = 0,0
>> for i in range(start,end+1):
>>     istr = str(i)
>>     ilen = len(istr)
>>     for j in range(0,ilen):
>>         for k in range(j+1,ilen+1):
>>             if int(istr[j:k]) % ilen == 0:
>>                 div+=1
>>     if div == 1: ocn+=1
>>     div = 0
>> print("\n%d one-child numbers from %d to %d" % (ocn,start,end))
>> ================================================================
>>
>

On 02/07/2021 15:21, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
>
>> Not bad numbers for python and F(10^7), but this code is part of me
>> trying to solve Project Euler 413, which asks for F(10^19).
>
> I didn't know that. As you say, a different algorithm is called for.
>
> (My best naive version gets F(10^9) in 4m21.489s and F(10^7) in 2.177s.)
>

For F(10^7) I got 9.4 seconds with gcc-O3 with the C version below that
uses atoi equivalents. I seem to remember that my machine is quite a bit
slower than yours. Use of u64 rather than int doesn't affect the results.

I started on a version with no text conversions, but it got messy.

---------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long u64;

u64 strsubstring(char* s, int length) {
u64 result;
char c;

c=s[length];
s[length]=0;
result=atoll(s);
s[length]=c;
return result;
}

int onechild(u64 n) {
char s[128];
int slen=sprintf(s,"%llu",n);
int count;
u64 m;

count=(n%slen)==0;

for (int w=0; w<(slen-1); ++w) {
for (int i=0; i<slen-w; ++i) {
m=strsubstring(s+i,w+1);
if ((m%slen)==0) {
++count;
if (count>1) return 0;
}
}
}

return count==1;
}

int main(void) {
int count=0;
u64 n=10000000;

for (int i=1; i<n; ++i) {
count+=onechild(i);
}

printf("F(%llu) = %d\n",n, count);
}