Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161600
| From | Bart <bc@freeuk.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Losing my mind: results change with/without printf() statements |
| Date | 2021-07-02 18:33 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <sbnima$7p0$1@dont-email.me> (permalink) |
| References | (7 earlier) <8735syjrwf.fsf@bsb.me.uk> <54aa8ed0-7069-44c8-a582-d05aa8541ac8n@googlegroups.com> <87fswwhlu4.fsf@bsb.me.uk> <bf39ecc9-f6c8-499a-8fed-c17d725b10fbn@googlegroups.com> <245d9902-b854-44d9-9a8e-f4fa2d2fd044n@googlegroups.com> |
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.
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