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

Groups > comp.lang.c > #161546 > unrolled thread

Losing my mind: results change with/without printf() statements

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

Contents

  Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 12:26 -0400
    Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-06-30 19:03 +0200
      Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 13:58 -0400
        Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-06-30 19:44 +0100
          Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 16:16 -0400
            Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-01 00:03 +0100
              Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 23:54 -0400
                Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 10:56 +0200
                Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-01 10:38 +0100
                  Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 02:49 -0700
                    Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 14:44 +0100
                      Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 07:48 -0700
                        Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 09:25 -0700
                          Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 18:33 +0100
                            Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 01:27 -0700
                              Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-04 15:19 +0100
                                Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 09:04 -0700
                                  Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 09:51 -0700
            Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 03:20 -0700
              Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 11:42 +0100
                Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 04:47 -0700
            Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 15:21 +0100
              Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 11:37 -0400
              Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 17:06 +0100
              Re: Losing my mind: results change with/without printf() statements Kaz Kylheku <563-365-8930@kylheku.com> - 2021-07-02 17:41 +0000
                Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 19:09 +0100
                  Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 19:48 +0100
                    Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 03:21 -0700
                      Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 14:01 +0100
                        Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-05 02:44 -0700
                          Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-05 14:43 +0100
                            Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-05 19:42 -0500
                              Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-06 03:36 -0700
                                Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-06 12:27 -0500
                                  Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-06 16:02 -0700
                                    Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-06 20:30 -0400
                                    Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-08 01:02 -0700
                                      Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 05:52 -0700
                                        Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-09 08:24 -0500
                                          Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 07:20 -0700
                                            Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-10 15:27 -0700
                                              Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 00:56 -0700
                                                Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 12:01 -0700
                                                  Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-12 21:30 +0100
                                                    Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-13 00:33 -0700
                                                      Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-13 22:58 +0100
                                                  Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-20 13:38 -0700
                                        Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-09 11:23 -0400
                                          Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 08:43 -0700
                                        Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-11 16:40 +0100
                                          Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 02:51 -0700
                                            Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-12 16:57 +0100
                                              Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-12 17:25 +0100
                                              Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-20 18:03 +0100
        Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 10:46 +0200
          Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 11:52 -0400
            Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 17:16 +0100
              Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 13:27 -0400
        Re: Losing my mind: results change with/without printf() statements luser droog <luser.droog@gmail.com> - 2021-07-12 16:19 -0700
    Re: Losing my mind: results change with/without printf() statements Barry Schwarz <schwarzb@delq.com> - 2021-06-30 11:36 -0700
      Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 16:03 -0400
        Re: Losing my mind: results change with/without printf() statements Barry Schwarz <schwarzb@delq.com> - 2021-06-30 13:22 -0700
        Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 11:03 +0200
    Re: Losing my mind: results change with/without printf() statements Rosario19 <Ros@invalid.invalid> - 2021-07-01 10:49 +0200

Page 1 of 4  [1] 2 3 4  Next page →

#161546 — Losing my mind: results change with/without printf() statements

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);
}
================================================================

[toc] | [next] | [standalone]

#161548

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.

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

#161550

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))
================================================================

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

#161552

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.

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

#161555

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.

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

#161557

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.

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

#161560

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.

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

#161565

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.
> 
> 

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

#161567

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.

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

#161580

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.

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

#161584

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.

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

#161591

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...

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

#161598

On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote:
> 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...


Just to prove to myself that brute force is dead end
Here is rather clever brute force.
It does 1e9 in 26 sec on my aging home PC (i5-3450).

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab)
{
  int nChilds = 0;
  for (int beg = 0; beg < nDigits; ++beg) {
    unsigned r = 0;
    for (int end = beg; end < nDigits; ++end) {
      r = remTab[r*10+digits[end]];
      if (r == 0) {
        ++nChilds;
      }
    }
    if (nChilds > 1)
      return false;
  }
  return nChilds == 1;
}

static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print)
{
  // initialize look-up table
  uint8_t remTab[200];
  for (int i = 0; i < nDigits*10; ++i)
    remTab[i] = i % nDigits;

  // initialize array of digits
  uint8_t digits[20];
  uint64_t x = first;
  for (int i = 0; i < nDigits; ++i) {
    digits[nDigits-1-i] = x % 10;
    x /= 10;
  }

  unsigned long long cnt = 0;
  for (x = first; x <= last; ++x) {
    if (isOneChild(digits, nDigits, remTab)) {
      ++cnt;
      if (print)
        printf("%llu\n", (unsigned long long)x);
    }
    uint8_t lsDig = digits[nDigits-1] + 1;
    digits[nDigits-1] = lsDig;
    if (lsDig == 10) {
      digits[nDigits-1] = 0;
      for (int i = nDigits-2; i >= 0; --i) {
        uint8_t d = digits[i] + 1;
        if (d == 10) {
          digits[i] = 0;
        } else {
          digits[i] = d;
          break;
        }
      }
      lsDig = 0;
    }
  }
  return cnt;
}

int count_digits(unsigned long long x)
{
  int c = 0;
  while (x) {
    ++c;
    x /= 10;
  }
  return c;
}

unsigned long long ndig_max(int nDigits)
{
  unsigned long long x = 1;
  for (int i = 0; i < nDigits; ++i)
    x *= 10;
  return x - 1;
}

int main(int argz, char** argv)
{
  if (argz < 3) {
    fprintf(stderr, "Consult DFS!\n");
    return 1;
  }

  char* endp;
  unsigned long long first = strtoull(argv[1], &endp, 0);
  if (endp == argv[1]) {
    fprintf(stderr, "%s is not a number.\n", argv[1]);
    return 1;
  }

  unsigned long long last = strtoull(argv[2], &endp, 0);
  if (endp == argv[2]) {
    fprintf(stderr, "%s is not a number.\n", argv[2]);
    return 1;
  }

  bool print = false;
  if (argz > 3 && argv[3][0]=='p')
    print = true;

  unsigned long long cnt = 0;
  while (first <= last) {
    int nDigits = count_digits(first);
    unsigned long long rangeLast = ndig_max(nDigits);
    if (rangeLast > last)
      rangeLast = last;
    cnt += countOneChildsInRange(first, rangeLast, nDigits, print);
    first = rangeLast + 1;
  }
  printf("Found %llu one-childs\n", cnt);

  return 0;
}

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

#161600

On 02/07/2021 17:25, Michael S wrote:
> On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote:
>> On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote:

>>>> 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...
> 
> 
> Just to prove to myself that brute force is dead end
> Here is rather clever brute force.
> It does 1e9 in 26 sec on my aging home PC (i5-3450).
> 
> #include <stdint.h>
> #include <stdbool.h>
> #include <stdlib.h>
> #include <stdio.h>
> 
> static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab)
> {
>    int nChilds = 0;
>    for (int beg = 0; beg < nDigits; ++beg) {
>      unsigned r = 0;
>      for (int end = beg; end < nDigits; ++end) {
>        r = remTab[r*10+digits[end]];
>        if (r == 0) {
>          ++nChilds;
>        }
>      }
>      if (nChilds > 1)
>        return false;
>    }
>    return nChilds == 1;
> }
> 
> static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print)
> {
>    // initialize look-up table
>    uint8_t remTab[200];
>    for (int i = 0; i < nDigits*10; ++i)
>      remTab[i] = i % nDigits;
> 
>    // initialize array of digits
>    uint8_t digits[20];
>    uint64_t x = first;
>    for (int i = 0; i < nDigits; ++i) {
>      digits[nDigits-1-i] = x % 10;
>      x /= 10;
>    }
> 
>    unsigned long long cnt = 0;
>    for (x = first; x <= last; ++x) {
>      if (isOneChild(digits, nDigits, remTab)) {
>        ++cnt;
>        if (print)
>          printf("%llu\n", (unsigned long long)x);
>      }
>      uint8_t lsDig = digits[nDigits-1] + 1;
>      digits[nDigits-1] = lsDig;
>      if (lsDig == 10) {
>        digits[nDigits-1] = 0;
>        for (int i = nDigits-2; i >= 0; --i) {
>          uint8_t d = digits[i] + 1;
>          if (d == 10) {
>            digits[i] = 0;
>          } else {
>            digits[i] = d;
>            break;
>          }
>        }
>        lsDig = 0;
>      }
>    }
>    return cnt;
> }
> 
> int count_digits(unsigned long long x)
> {
>    int c = 0;
>    while (x) {
>      ++c;
>      x /= 10;
>    }
>    return c;
> }
> 
> unsigned long long ndig_max(int nDigits)
> {
>    unsigned long long x = 1;
>    for (int i = 0; i < nDigits; ++i)
>      x *= 10;
>    return x - 1;
> }
> 
> int main(int argz, char** argv)
> {
>    if (argz < 3) {
>      fprintf(stderr, "Consult DFS!\n");
>      return 1;
>    }
> 
>    char* endp;
>    unsigned long long first = strtoull(argv[1], &endp, 0);
>    if (endp == argv[1]) {
>      fprintf(stderr, "%s is not a number.\n", argv[1]);
>      return 1;
>    }
> 
>    unsigned long long last = strtoull(argv[2], &endp, 0);
>    if (endp == argv[2]) {
>      fprintf(stderr, "%s is not a number.\n", argv[2]);
>      return 1;
>    }
> 
>    bool print = false;
>    if (argz > 3 && argv[3][0]=='p')
>      print = true;
> 
>    unsigned long long cnt = 0;
>    while (first <= last) {
>      int nDigits = count_digits(first);
>      unsigned long long rangeLast = ndig_max(nDigits);
>      if (rangeLast > last)
>        rangeLast = last;
>      cnt += countOneChildsInRange(first, rangeLast, nDigits, print);
>      first = rangeLast + 1;
>    }
>    printf("Found %llu one-childs\n", cnt);
> 
>    return 0;
> }

Well, it's fast (about 65 seconds on my machine, perhaps 20 times as 
fast as my program). But I can't say it's that easy to follow!

It seems to rely on the fact that consecutive numbers are being tested, 
so can optimise blocks all having the same numbers of digits. (Exactly 
how, I don't know yet.)

So I guess it can't be used to get the one-child status of an arbitrary 
number. That's probably the only advantage of the simpler algorithm, 
other than being simpler.

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

#161637

On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote:
> On 02/07/2021 17:25, Michael S wrote: 
> > On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote: 
> >> On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote: 
> 
> >>>> 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... 
> > 
> > 
> > Just to prove to myself that brute force is dead end 
> > Here is rather clever brute force. 
> > It does 1e9 in 26 sec on my aging home PC (i5-3450). 
> > 
> > #include <stdint.h> 
> > #include <stdbool.h> 
> > #include <stdlib.h> 
> > #include <stdio.h> 
> > 
> > static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab) 
> > { 
> > int nChilds = 0; 
> > for (int beg = 0; beg < nDigits; ++beg) { 
> > unsigned r = 0; 
> > for (int end = beg; end < nDigits; ++end) { 
> > r = remTab[r*10+digits[end]]; 
> > if (r == 0) { 
> > ++nChilds; 
> > } 
> > } 
> > if (nChilds > 1) 
> > return false; 
> > } 
> > return nChilds == 1; 
> > } 
> > 
> > static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print) 
> > { 
> > // initialize look-up table 
> > uint8_t remTab[200]; 
> > for (int i = 0; i < nDigits*10; ++i) 
> > remTab[i] = i % nDigits; 
> > 
> > // initialize array of digits 
> > uint8_t digits[20]; 
> > uint64_t x = first; 
> > for (int i = 0; i < nDigits; ++i) { 
> > digits[nDigits-1-i] = x % 10; 
> > x /= 10; 
> > } 
> > 
> > unsigned long long cnt = 0; 
> > for (x = first; x <= last; ++x) { 
> > if (isOneChild(digits, nDigits, remTab)) { 
> > ++cnt; 
> > if (print) 
> > printf("%llu\n", (unsigned long long)x); 
> > } 
> > uint8_t lsDig = digits[nDigits-1] + 1; 
> > digits[nDigits-1] = lsDig; 
> > if (lsDig == 10) { 
> > digits[nDigits-1] = 0; 
> > for (int i = nDigits-2; i >= 0; --i) { 
> > uint8_t d = digits[i] + 1; 
> > if (d == 10) { 
> > digits[i] = 0; 
> > } else { 
> > digits[i] = d; 
> > break; 
> > } 
> > } 
> > lsDig = 0; 
> > } 
> > } 
> > return cnt; 
> > } 
> > 
> > int count_digits(unsigned long long x) 
> > { 
> > int c = 0; 
> > while (x) { 
> > ++c; 
> > x /= 10; 
> > } 
> > return c; 
> > } 
> > 
> > unsigned long long ndig_max(int nDigits) 
> > { 
> > unsigned long long x = 1; 
> > for (int i = 0; i < nDigits; ++i) 
> > x *= 10; 
> > return x - 1; 
> > } 
> > 
> > int main(int argz, char** argv) 
> > { 
> > if (argz < 3) { 
> > fprintf(stderr, "Consult DFS!\n"); 
> > return 1; 
> > } 
> > 
> > char* endp; 
> > unsigned long long first = strtoull(argv[1], &endp, 0); 
> > if (endp == argv[1]) { 
> > fprintf(stderr, "%s is not a number.\n", argv[1]); 
> > return 1; 
> > } 
> > 
> > unsigned long long last = strtoull(argv[2], &endp, 0); 
> > if (endp == argv[2]) { 
> > fprintf(stderr, "%s is not a number.\n", argv[2]); 
> > return 1; 
> > } 
> > 
> > bool print = false; 
> > if (argz > 3 && argv[3][0]=='p') 
> > print = true; 
> > 
> > unsigned long long cnt = 0; 
> > while (first <= last) { 
> > int nDigits = count_digits(first); 
> > unsigned long long rangeLast = ndig_max(nDigits); 
> > if (rangeLast > last) 
> > rangeLast = last; 
> > cnt += countOneChildsInRange(first, rangeLast, nDigits, print); 
> > first = rangeLast + 1; 
> > } 
> > printf("Found %llu one-childs\n", cnt); 
> > 
> > return 0; 
> > }
> Well, it's fast (about 65 seconds on my machine, 

Your ability to enjoy slow PCs does not surprise me any more.

> perhaps 20 times as 
> fast as my program). 

If your program uses strings then only 20 times is a little disappointing.

> But I can't say it's that easy to follow! 

Because I wrote it for myself, as a one time exercise and put in virtually no comments.
Still, even in commentless state, it's likely easier to follow for most people than
the code of DFS that started this thread.

> 
> It seems to rely on the fact that consecutive numbers are being tested, 
> so can optimise blocks all having the same numbers of digits. (Exactly 
> how, I don't know yet.) 
> 
> So I guess it can't be used to get the one-child status of an arbitrary 
> number.

It can. It just would be much slower at that then function built for a purpose of
examining a single number. But, I'd guess, even in this scenario it would be within
factor of 3-5 from the best speed achievable with atoi()/strtoull().

> That's probably the only advantage of the simpler algorithm, 
> other than being simpler.

I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal
of mindless brute force. It ended up ~7 times slower than the variant presented above which
is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than
Ben's.

But utility of "mindless brute force" in this challenge is not to be fast, but too look fast and be slow,
in order to convince people that the challenge can't be solved on this path.

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

#161644

On 04/07/2021 09:27, Michael S wrote:
> On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote:

>> Well, it's fast (about 65 seconds on my machine,
> 
> Your ability to enjoy slow PCs does not surprise me any more.

It's not that slow if my 2010 AMD-whatever is only 2.5 times as slow as 
an Intel i5. Or is your main machine even faster?

(My machine can build all of my language projects from scratch (some 100 
modules and 150Kloc) in about half a second. The compiler isn't even 
optimised. It's hard to see the benefit of spending £100s on a faster 
machine.)

> 
>> perhaps 20 times as
>> fast as my program).
> 
> If your program uses strings then only 20 times is a little disappointing.

You mean, you expected it to be slower (more than 20 times) or faster?

I didn't make any attempt at a fast program except to implement a 
slightly simpler algorithm than the OP's, and one I could understand.

But since it depends heavily on atoll(), I made a custom version of that 
(in newstrsubstring() below). That made it 3 times faster.

I then got a further 50% boost by replacing sprintf with atoi.

Now it's only about 4.5 times slower than your version. (290 seconds vs 
66 seconds for F(10^9).)

So if yours was to take 7,000 years for F(10^9) based on your i5, mine 
would now take only 30,000 years instead of 140,000. Lopping off 110,000 
years is not a bad result for 5 minutes' work...

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

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

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

u64 newstrsubstring(char* s, int length) {
// length should be >=1
     u64 result;

     result=*s-'0';
     ++s;
     while (--length) {
         result=result*10+*s -'0';
         ++s;
     }
     return result;
}


>> That's probably the only advantage of the simpler algorithm,
>> other than being simpler.
> 
> I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal
> of mindless brute force. It ended up ~7 times slower than the variant presented above which
> is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than
> Ben's.

So somewhat slower than mine now, but mine still uses strings.

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

#161646

On Sunday, July 4, 2021 at 5:20:01 PM UTC+3, Bart wrote:
> On 04/07/2021 09:27, Michael S wrote: 
> > On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote: 
> 
> >> Well, it's fast (about 65 seconds on my machine, 
> > 
> > Your ability to enjoy slow PCs does not surprise me any more.
> It's not that slow if my 2010 AMD-whatever is only 2.5 times as slow as 
> an Intel i5. Or is your main machine even faster? 

This home desktop is from 2012 and even then was considered inexpensive, while not the cheapest possible.
Naturally, PCs I use to do a "real work" like FPGA development are significantly faster.

> 
> (My machine can build all of my language projects from scratch (some 100 
> modules and 150Kloc) in about half a second. The compiler isn't even 
> optimised. It's hard to see the benefit of spending £100s on a faster 
> machine.)

Comfortable web browsing, may be?

> > 
> >> perhaps 20 times as 
> >> fast as my program). 
> > 
> > If your program uses strings then only 20 times is a little disappointing.
> You mean, you expected it to be slower (more than 20 times) or faster? 
> 

I meant to say that I expected for may program to be more than 20 times faster than variants resembling one in the first post of this thread.

> I didn't make any attempt at a fast program except to implement a 
> slightly simpler algorithm than the OP's, and one I could understand. 
> 
> But since it depends heavily on atoll(), I made a custom version of that 
> (in newstrsubstring() below). That made it 3 times faster. 
> 
> I then got a further 50% boost by replacing sprintf with atoi. 
> 
> Now it's only about 4.5 times slower than your version. (290 seconds vs 
> 66 seconds for F(10^9).) 
> 

Well, string-to-number and number-to-string conversions are biggest offenders in original code. 
Or did he also have memory allocation in the inner loop? I don't remember.
So, if you replaced conversions with custom routines, you're already pretty close to my variant. 
The only remaining major difference is my use of look-up tables instead of modulo operations.
I also saved a little time by not doing number-to-string conversion in the 3rd innermost loop, 
for (x = first; x <= last; ++x) {...}
but that's probably not very significant if at all significant.


> So if yours was to take 7,000 years for F(10^9) based on your i5, mine 
> would now take only 30,000 years instead of 140,000. Lopping off 110,000 
> years is not a bad result for 5 minutes' work... 
> 

You mean F(10**19) ?
I am afraid your estimate is too optimistic, at least for your code and your PC.
I expect F(10**19) to take 4*1e10 as much time as F(10**9), which would be 370,000 years.


> ------------------------------------------
> u64 strsubstring(char* s, int length) { 
> u64 result; 
> char c; 
> 
> c=s[length]; 
> s[length]=0; 
> result=atoll(s); 
> s[length]=c; 
> return result; 
> }
> u64 newstrsubstring(char* s, int length) { 
> // length should be >=1 
> u64 result; 
> 
> result=*s-'0'; 
> ++s; 
> while (--length) { 
> result=result*10+*s -'0'; 
> ++s; 
> } 
> return result;
> } 
> 
> 
> >> That's probably the only advantage of the simpler algorithm, 
> >> other than being simpler. 
> > 
> > I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal 
> > of mindless brute force. It ended up ~7 times slower than the variant presented above which 
> > is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than 
> > Ben's.
> So somewhat slower than mine now, but mine still uses strings.

But running "arithmetic" variant on my home PC is faster than your code on your home PC :-)
BTW, I don't think that your code could be still considered as "uses strings" in C language sense of the word.

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

#161647

On Sunday, July 4, 2021 at 7:04:46 PM UTC+3, Michael S wrote:
> I also saved a little time by not doing number-to-string conversion in the 3rd innermost loop, 
> for (x = first; x <= last; ++x) {...} 
> but that's probably not very significant if at all significant.

I measured it. 
Without this optimization the programs runs ~1.5 times slower. So, optimization is not insignificant.
But I admit that at minimal performance cost it can be expressed in more comprehensible way.

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

#161581

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.

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

#161582

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.

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

Page 1 of 4  [1] 2 3 4  Next page →

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

csiph-web