Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161602
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Losing my mind: results change with/without printf() statements |
| Date | 2021-07-02 19:09 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <874kdch9k0.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <Yg2DI.3867$mR.1082@fx33.iad> <hY2DI.505463$N5n7.405017@fx05.ams4> <Gi4DI.1867$t64.414@fx13.iad> <87a6n4hk4c.fsf@bsb.me.uk> <20210702095301.721@kylheku.com> |
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> On 2021-07-02, Ben Bacarisse <ben.usenet@bsb.me.uk> 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.)
>
> The obvious thing here is to encode custom divisibility tests for
> d = [1,19].
>
> For certain divisors, we can test divisibility on the base 10
> representation without converting to integer. It's a waste of
> time to convert "1235" into 1235 to test it for divisibility by 5,
> when we just have to apply the condition "last digit is 0 or 5".
In the "arithmetic" versions, there are no strings.
> Moreover, in the d=5 case, we can short-circuit to an answer
> for each five-digit number. It's a one-child if it starts with 5.
> and doesn't contain 0 or any other 5.
Yes, there are various opportunities for short-circuiting many cases. I
wonder if that's enough to make 10^19 tractable.
Also, problems like this are supposed to be satisfying, and
special-casing sub-string divisibility for lots of different lengths
does not meet that criterion (in my view).
>
> int onechild_d5(char *num)
> {
> return num[0] == '5' && strpbrk(num + 1, "05") == 0;
> }
>
> Proof:
>
> 1. If the number contains a 5 or 0 in any position other than the first,
> then it has at least two substrings divisible by 5: that 0 or 5 itself,
> plus strings terminating in that 0 or 5. Therefore, the one-child number
> doesn't have a 5 or 0 in any position other than first.
>
> 2. A number cannot have leading zeros under the rules, therefore a
> one-child number doesn't have a 0 in the first position.
>
> 3. The one-child number for d = 5 must have a 0 or 5 somewhere;
> therefore it must have a 5 in the first position.
>
> I would write onechild_d1 through onechild_d19 functions, stuffing
> them with d-specific shortcuts. Put them into a table, and then
> drive them with a main program that does this:
>
> int d;
> long long one_child_count;
>
> for (oc = 0, d = 1; d <= 19; d++) {
> char n[20];
>
> /* generate d-digit number in n,
> stepping it from 100...000 to 99999. */
>
> oc += (octab[d](n) != 0);
> }
>
> Incrementing n textually might be faster than repeated sprintfs. So that
> is to say, for a given d, we fill the buffer n with:
>
> "10000000" // 1 followed by d-1 zeros
>
> Then we increment textually. We maintain a pointer to the last digit.
> If it is '9', we set it to zero, and increment the next digit, otherwise
> we increment it.
>
> Dollars to doughnuts says this will beat sprintf because there are no
> divisions by ten going on.
If you wanted to use the string representation then stepping is surely
going to be a win. Mind you, I'd use digit values rather that ASCII
0-9. Maybe that's what you were thinking anyway.
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web