LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-15-2021, 10:29 PM   #46
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 451

Original Poster
Blog Entries: 4

Rep: Reputation: 213Reputation: 213Reputation: 213

@igadoter: (re. your signature and dislike of rep points)
I'll buy you a beer for your 'amazing circle' thread that started this whole thing.

Gotta come to Jinotega, Nicaragua to claim your reward.

Last edited by dogpatch; 04-15-2021 at 10:37 PM.
 
1 members found this post helpful.
Old 04-16-2021, 01:49 AM   #47
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,000
Blog Entries: 1

Rep: Reputation: Disabled
Great thanks, you made my day, sun is shining more brightly .
 
1 members found this post helpful.
Old 04-16-2021, 04:15 AM   #48
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,800

Rep: Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714
Quote:
Originally Posted by dogpatch View Post
@igadoter: (re. your signature and dislike of rep points)
I'll buy you a beer for your 'amazing circle' thread that started this whole thing.

Gotta come to Jinotega, Nicaragua to claim your reward.
Agreed, thanks for bringing this to our attention. Was just as interesting as the "Armstrong numbers" thread we had a while back.
 
1 members found this post helpful.
Old 04-16-2021, 08:36 AM   #49
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 451

Original Poster
Blog Entries: 4

Rep: Reputation: 213Reputation: 213Reputation: 213
Quote:
Originally Posted by GazL View Post
. . . Was just as interesting as the "Armstrong numbers" thread we had a while back.
. . . or the 2019 New year puzzle thread.

@GazL: Is this the Armstrong numbers thread to which you referred?. That was resurrected after 11 years? And is now 4 years older? I missed it the first two times, but may take a look at it sometime myself. Thanks for the tip.
 
Old 04-16-2021, 09:26 AM   #50
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,800

Rep: Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714
Yep, that's the one.
 
Old Yesterday, 09:50 AM   #51
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,255

Rep: Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456
I downloaded the code from post #42. Is this the last one?
This is the top of the profile (for 56):
Code:
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 34.35    337.33   337.33                             find_next (a.c:240 @ 1979)
 10.79    443.35   106.02                             find_next (a.c:236 @ 1a3b)
 10.66    548.04   104.69                             find_next (a.c:242 @ 199c)
  8.09    627.54    79.50                             find_next (a.c:250 @ 1a10)
  6.04    686.88    59.33                             find_next (a.c:253 @ 1a2f)
  6.00    745.80    58.92                             find_next (a.c:238 @ 196f)
  5.03    795.18    49.38                             find_next (a.c:243 @ 19b6)
  3.65    831.03    35.85                             find_next (a.c:255 @ 1a51)
  3.23    862.74    31.70                             find_next (a.c:249 @ 19f5)
  3.05    892.69    29.95                             find_next (a.c:234 @ 194a)
  2.76    919.76    27.07 243738122   111.05   111.05  find_next (a.c:217 @ 188e)
...
What does it mean? the statement "state->seen_values[candidate - 1]" is the most expensive part of this code (line 240, 243, 250).
 
Old Yesterday, 10:46 AM   #52
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,800

Rep: Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714
It should be the latest. To confirm, If you have the one tagged "version 2.5" on line 1, then it's the latest.

The statement you highlight replaced a for loop that did a sequential search of an array in earlier versions, It's now a single memory access using a pointer and offset so I don't know how one could make it any faster. If you have a faster way of keeping track of what values have been used I'm all ears.

BTW, what profiling tool are you using?
 
Old Yesterday, 11:23 AM   #53
floppy_stuttgart
Member
 
Registered: Nov 2010
Location: EU mainland
Distribution: Debian like
Posts: 874
Blog Entries: 3

Rep: Reputation: 80
a bit mathematic does it ? https://math.stackexchange.com/quest...-of-two-number
 
Old Yesterday, 11:43 AM   #54
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,255

Rep: Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456
that is the default gcc/gprof toolset.
That line is not a single memory access, or at least quite difficult to calculate that address.
Code:
    int *ip = state->seen_values;
    int *rd = &(state->result[depth]);

    while( p && (p->value == value) )
    {
        int candidate = p->adjacent ;

        if ( ! ip[candidate - 1] )
        {
            *rd = candidate ;
            ip[candidate - 1] = candidate ;

            if ( find_next(depth + 1, candidate, state) )
            {
                return 1 ;
            } else {
                *rd = 0 ;
                ip[candidate - 1] = 0;
            }
        }
        p = p->next ;
    }
    return 0;
it looks (for me) using this ip and rd will speed up the execution (more than 10%)
 
Old Yesterday, 12:22 PM   #55
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,800

Rep: Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714Reputation: 3714
I would have expected the optimizer to have dealt with some of that, but perhaps I was giving gcc too much credit. Thanks, I'll look into it.
 
Old Yesterday, 01:35 PM   #56
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,000
Blog Entries: 1

Rep: Reputation: Disabled
Miracle happens. As it was time consuming to count amazing circle for 56 and higher number it is relatively fast
Code:
% gcc amazing_circle_v2.1.c
% time a.out 59
1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 50, 31, 18, 7, 2, 23, 58, 42, 39, 25, 56, 8, 17, 32, 49, 51, 13, 36, 28, 53, 47, 34, 30, 19, 45, 55, 26, 38, 43, 57, 24, 12, 37, 44, 20, 29, 52, 48, 33, 16, 9, 40, 41, 59, 22, 27, 54, 46, 35.

real	0m47.545s
user	0m47.543s
sys	0m0.000s
now
Code:
% time a.out 65 1 

real - didn't wait to finish 

% time a.out 65 2
 2, 7, 9, 16, 20, 5, 4, 12, 13, 3, 1, 8, 17, 32, 49, 51, 30, 6, 10, 15, 21, 28, 36, 64, 57, 43, 38, 26, 55, 45, 19, 62, 59, 41, 23, 58, 63, 18, 46, 54, 27, 37, 44, 56, 65, 35, 29, 52, 48, 33, 31, 50, 14, 22, 42, 39, 61, 60, 40, 24, 25, 11, 53, 47, 34.

real	0m37.535s
user	0m37.528s
sys	0m0.001s
so it is not as difficult to find sequence but starting point seems to be important. It is not difficult cause must be a lot of such sequences - deterministic algorithm is just pure lack. If there are many such sequences there is great chance to find one.

Edit: My small addition to is_square test
Code:
// is_square logical table 
char *p;
p = (char *) malloc((MAXSIZE*MAXSIZE+1)*sizeof(char));

for (int i = 1; i < MAXSIZE + 1; i++)
	    *(p+i*i) = 'A';
it test all squares up to MAXSIZE*MAXSIZE. For n test is satisfied if *(p+n) == 'A', fails if
*(p+n) == '\0'. The last this dependency from starting point gives me following idea
Code:
% a.out N $(($RANDOM % N))
say with N = 76 the third run gave almost immediate answer. So put time limit execution up to 1 minut and execute that command.

Last edited by igadoter; Yesterday at 02:04 PM.
 
Old Yesterday, 01:49 PM   #57
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,255

Rep: Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456Reputation: 5456
Quote:
Originally Posted by igadoter View Post
Miracle happens.
...
so it is not as difficult to find sequence but starting point seems to be important. It is not difficult cause must be a lot of such sequences - deterministic algorithm is just pure lack. If there are many such sequences there is great chance to find one.
I was thinking about an algorithm to find out the "best" starting point.
Right now I think we can calculate the number of pairs for every number in the circle and I think we need to find the one with the lowest number of pairs (and probably we can go further to find the number of second/third/... neighbors). But probably this is not really useful.
 
Old Yesterday, 04:28 PM   #58
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,000
Blog Entries: 1

Rep: Reputation: Disabled
With randomization and timeout 60 seconds it took me 6 min to find sequence of 97 numbers (1 .. 97). But it seems some numbers are more lucky. Timeout 60 sec means that program found sequence in period of time shorter than 60 sec.

Last edited by igadoter; Yesterday at 04:29 PM.
 
Old Today, 04:04 AM   #59
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,000
Blog Entries: 1

Rep: Reputation: Disabled
I think that improvement will be if program would accept starting sequence - you can think about first number as 0-level randomization Providing longer starting sequence is higher randomization. Just pick starting sequence randomly.
Code:
% amazing_circle 127 1 3 13 23
 
  


Reply

Tags
circle, perfect square, programming challenge, ring, ring data type


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
damnit!!! i cant see what im typing.. fonts are squares iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM
characters as squares in mozilla icyfire Linux - Software 4 09-18-2003 04:22 PM
white squares appear on screen saver? bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 11:30 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration