LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
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: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237

@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,248
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,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
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: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
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,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Yep, that's the one.
 
Old 04-17-2021, 09:50 AM   #51
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,490

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
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 04-17-2021, 10:46 AM   #52
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
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 04-17-2021, 11:23 AM   #53
floppy_stuttgart
Member
 
Registered: Nov 2010
Location: EU mainland
Distribution: Debian like
Posts: 908
Blog Entries: 4

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

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
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 04-17-2021, 12:22 PM   #55
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
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 04-17-2021, 01:35 PM   #56
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
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; 04-17-2021 at 02:04 PM.
 
Old 04-17-2021, 01:49 PM   #57
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,490

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
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.
 
1 members found this post helpful.
Old 04-17-2021, 04:28 PM   #58
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
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; 04-17-2021 at 04:29 PM.
 
Old 04-18-2021, 04:04 AM   #59
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
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
Edit: I ma^T uploading amazing circles for 97, 98, 99 - they can be computed relatively fast - below 6 min.
Attached Files
File Type: txt amc-97_99.txt (1.5 KB, 4 views)

Last edited by igadoter; 04-20-2021 at 04:45 AM.
 
Old 04-23-2021, 01:15 PM   #60
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Here at last is something to upload; have included the latest DataRing.h.txt include file as a separate upload, as more general use code. The other WonderRing.cpp.txt contains several pieces specific to this Ring of Squares challenge, as noted within the txt file. You may have to change some include file specs; my gcc compiler is pretty old.

DataRing.h.txt
WonderRing.cpp.txt

A few notes on what i've been doing off-line. Forgive me if i'm treating of things that you folks have long since conquered.

1. From the beginning, i've treated the sequences as rings, with indeterminate start, end, and flow direction. In fact, rings of data strike me as a concept with practical applications elsewhere. Probably it's already been done, and probably better than my amateurish C++ code. See DataRing.h.txt and comments.

2. Rather than code functions to calculate squares and square roots, i always simply used a static array of squares. It then occurred to me that this array could be any series of target numbers, say Fibonacci or Armstrong. To try this idea, i made an array of prime numbers and was able to easily generate rings of primes with pretty much the same code. (Caveat: you can't generate a ring of primes with an odd number of elements. Think about it.) The output of rings of primes was very fast but grew in number VERY quickly when the -a (all_rings) option was employed. For example, the command
Code:
PrimeRing 16 -a
displays 81024 valid rings of 16 elements, while recursing through RecursFind() for only 1016063 cycles (depending upon the starting, or seed number - see below).

3. With rings of data, it was a simple matter to include an option (-o) to order the elements of the rings before dumping to the screen. This did not involve any sorting or rearranging of the elements; simply alter the head, tail, and flow direction to give the desired order. This, along with the -a option, allowed the program to identify and discard any mirror (duplicate) rings. So, for example
Code:
 SquareRing 34 6 -a
yields
Code:
22 valid rings generated
670991 cycles of RecursFind()
while
Code:
SquareRing 34 6 -ao
gives
Code:
11 valid rings generated and ordered
670991 cycles of RecursFind()
Note that no processing time is saved, since all rings are still generated, just that not all are accepted and displayed.

4. Speaking of processing time, most of my computer time since my last LQ visit was spent trying to get my program to run more efficiently and faster. That deserves a separate post, below.

Caveat: Am still getting an occasional floating point error; haven't yet tracked it down.

Last edited by dogpatch; 04-23-2021 at 02:35 PM. Reason: add caveat (also update 2nd attachment)
 
  


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 01:37 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