Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161601
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Losing my mind: results change with/without printf() statements |
| Date | 2021-07-02 17:41 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210702095301.721@kylheku.com> (permalink) |
| References | (1 earlier) <sbi84p$ajn$1@dont-email.me> <Yg2DI.3867$mR.1082@fx33.iad> <hY2DI.505463$N5n7.405017@fx05.ams4> <Gi4DI.1867$t64.414@fx13.iad> <87a6n4hk4c.fsf@bsb.me.uk> |
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".
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.
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.
The next level of optimization would be to leave the child counting
to the d-specific routines:
/* return number of one-child five-digit numbers */
long long onechild_count_d5(void)
{
/* All these are of the form 5nnnn where the nnnn part
does not contain 0 or 5 anywhere. */
/* In other words, the number of combinations of the 8 digits
1-4, 6-9. */
return 8 * 8 * 8 * 8;
}
This is just an example; I don't mean to insinuate that optimizing d = 5
makes a significant difference if you're going after F(10**19).
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
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