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-12-2021, 05:53 PM   #31
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655

@GazL - I had some time to explore your code over the weekend. What a pleasure to read well considered code!

I really like your backtracking method, elegant simplicity!

I also had a chance to better understand the nature of the problem, which I should have done much earlier!

I made two incorrect assumptions (you know what they say!):

1. Looking at the shape of possible pairings in the 32 number case, from which my own method of finding the deterministic solution grew, I reached the quick conclusion that the higher end of the range would always be limited to one or two possible pairs... that is blindingly obviously incorrect!

2. From the name given to the problem and the deterministic nature of the (special) case of 32 numbers, I assumed the case itself was known to be unique or at least rare, i.e. "amazing", and did not explore the more general question of how many other series of numbers could be so arranged even though I asked the question.

Even so, the deterministic soloution in the case of the series 1 through 32 is in fact correct, and from what I have now seen, unique.

But as it turns out, the "circle of square pairs" is not so amazing after all, but there are numerous ranges with such solutions! That being the case, your general solver is much more useful!

I did observe a couple of things while writing my deterministic solver which can improve the performance of your own code in some cases (there are some exceptions which I have not yet fully explored).

First, you can get a small but consistent gain from changing your is_a_square() function to require fewer iterations. We can always know what the greatest perfect square and its root will be as that is determined by the max end of the range. It will be the greatest perfect square less than or equal to max*2-1. So if we set that in the initial conditions and iterate only the possible roots we can make a small but useful improvement. To do that I modified your amazing_circle_v2.1.c as follows:

Code:
struct state
{
    int max ;
    int maxroot ;
    int *result ;
    int *seen_values ;
    int pair_count ;
    struct pair * pairs_head ;
    struct pair * pairs_tail ;
    struct pair ** pairs_value_index ;
};

struct state *init_state(struct state *state, int max )
{
    state->max = max ;
    for(state->maxroot=2; (state->maxroot*state->maxroot)<=(state->max*2-1); state->maxroot++)
      ;
    state->maxroot--;
    ...
}

int is_a_square(int x, struct state *state)
{
   int i;
   for(i = state->maxroot; i>1; i--)
      if(x == i*i)
         break;
   return (i>1);
}

Modify callers of is_a_square() to pass state pointer, two places.
That made a change of about 1/2 second out of 12 seconds in the 51 series test case on my old AMD Phenom machine, but it was consistent and affected all results.

The second observation from the detereministic code is that there are always fewer ways to reach the higher squares, so fewer possible pairs for numbers in the high end of the range. By testing those first you eliminate an ever increasing number of possibilities to test from the lower end of the range.

I modified your pair generating/indexing function to index the higher pair possibilities first, with dramatic results:

Code:
int generate_pairs( struct state *state )
{
    struct pair *pairs_head = state->pairs_head ;
    struct pair *pairs_tail = state->pairs_tail ;

    for ( int i = 1 ; i <= state->max ; i++ )
    /*    for ( int j = 1 ; j <= state->max ; j++)*/
        for ( int j = state->max ; j >=1 ; j--)
    ...
}
These results follow from those changes, comparing the revised code to the original:

Code:
./revised 53 1
...
Sequence:
 1, 48, 52, 29, 35, 46, 18, 31, 50, 14, 22, 42, 39, 25, 24, 40, 41, 23, 26, 38, 43, 21, 28, 53, 11, 5, 44, 20, 16, 33, 3, 13, 36, 45, 19, 6, 10, 15, 49, 51, 30, 34, 47, 2, 7, 9, 27, 37, 12, 4, 32, 17, 8.

real    0m0.011s
user    0m0.009s
sys     0m0.001s

./amazing_circle 53 1
Sequence:
 1, 3, 6, 10, 15, 21, 43, 38, 26, 23, 2, 7, 9, 16, 33, 48, 52, 12, 4, 45, 19, 30, 34, 47, 17, 32, 49, 51, 13, 36, 28, 53, 11, 14, 50, 31, 18, 46, 35, 29, 20, 5, 44, 37, 27, 22, 42, 39, 25, 24, 40, 41, 8.

real    1m52.386s
user    1m52.343s
sys     0m0.016s
They find different solutions which I have not tried to compare in detail for common sequences, but the time difference is more than a little dramatic!

I see similar but less dramatic results for nearby cases, and even an increase in time for some smaller cases. It will be interesting to see how that holds up, or not, over a larger range.

Code:
amazing 52,   real    0m40.898s
revised 52,   real    0m0.041s

amazing 51,   real    0m12.360s
revised 51,   real    0m11.424s

amazing 48,   real    0m2.563s
revised 48,   real    0m4.374s

Last edited by astrogeek; 04-13-2021 at 12:06 AM.
 
3 members found this post helpful.
Old 04-12-2021, 05:58 PM   #32
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
Quote:
Originally Posted by igadoter View Post
In this place story started https://m.facebook.com/story.php?sto...cus_composer=0 I really hope we will finish this. My idea of "genetic" modifications is good starting point to create more efficient program.
I cannot access that site, it is blocked at the genetic level from here.

Could you summarize for us what you think is applicable to this thread. That would also help keep the discussion complete here on LQ without dependence on outside content which may disappear over time. Thanks!
 
Old 04-12-2021, 07:29 PM   #33
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
It is facebook page where one of my facebook friends posted the picture with amazing circle. He is mathematician. Just I want to emphasize that I am not the author of original circle. That's it Maybe try address starting with facebook not m.facebook. I blocked JavaScript and Facebook redirects here to mobile version m.facebook. Mobile version is supported mostly by php. Maybe you can't acess my timeline on facebook. I click on link I provided and it opens. I verified this before posting. From that post on facebook I copied the picture and posted it here.
 
2 members found this post helpful.
Old 04-12-2021, 07:40 PM   #34
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
It is not a routing matter. When I said it is "blocked at the genetic level" I meant that it is a personal choice to block anything with facebook in the domain name from my field of view and from access to my network. Sorry if my choice of expression obscured rather than clarified my meaning.

Even so, my personal choices aside, it is always preferable to post relevant information in thread here on LQ so that it will remain available to future visitors and not require others to follow off site links, which may disappear over time, to get info. It just keeps everything complete here. Thanks!

Last edited by astrogeek; 04-12-2021 at 07:57 PM.
 
Old 04-12-2021, 08:06 PM   #35
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Thanks, I will remember that.
 
Old 04-12-2021, 11:35 PM   #36
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
I had a little time to play this evening...

Code:
Max   Revised     Amazing
56    0m3.488s   24m46.152s
55    1m37.103s   8m0.734s
54    26.528s     3m22.459s
I suspect the rise and fall of the spread will be cyclic, or periodic in some way related to the distance between the max number and the reachable squares. That distance between each square and the one before increases twice as fast as the max number (or roots) and is root*2-1.
 
1 members found this post helpful.
Old 04-13-2021, 01:31 AM   #37
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
Code:
int sq[10000];

int is_a_square(int x)
{
    return sq[x];
}

void fill_sq()
{
    for (int i=0; i<10000; i++)
        sq[i]=0;
    for (int i=0; i<100; i++)
        sq[i*i]=1;
}

main ()
{
    ....
    fill_sq()
    ...
theoretically this should work faster and also quite simple, but (as I wrote) gave no any speed improvement, because the time spent in this function is negligible.
find_next was invoked more than 500 M times and is_a_square was only invoked [less than] 3000 times.

@astrogeek: with your modification (still using 51 numbers) the number of calls (to find_next) was 436M, therefore the full execution time was almost the same.
But using 52 numbers there was a dramatic change, there were only 1.4M calls and obviously the execution time was less than a second.

Last edited by pan64; 04-13-2021 at 01:33 AM.
 
3 members found this post helpful.
Old 04-13-2021, 06:29 AM   #38
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 astrogeek View Post
@GazL - I had some time to explore your code over the weekend. What a pleasure to read well considered code!
Thanks for the kind words.

Your observation about reversing the generated pairs list for efficiency is very interesting. Thanks for that.

As for is_a_square(), I suspected there were more efficient ways of doing it, but it's only called in find_next() when it thinks it has a full sequence and just needs to check it wraps correctly, so I didn't worry about optimising it. Combining your and pan's observations, I'm wondering if generating a lookup array of root values for numbers from 4 to max + max - 1 would be the most efficient process, though I suspect gains will still be minor due to the relatively small number of calls made.

I'll look into both.

Last edited by GazL; 04-13-2021 at 06:33 AM.
 
Old 04-13-2021, 09:32 AM   #39
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Using astrogeeks suggestion of changing the order of pairs, along with a sqrt lookup table, and changing the default start of sequence value to be sequence_max, speeds things up significantly. v2.2 attached.

Code:
$ time ./amazing_circle 99 | tail -2
Sequence:
 99, 97, 72, 49, 95, 74, 70, 51, 93, 76, 68, 53, 91, 78, 66, 55, 89, 80, 64, 57, 87, 82, 62, 59, 85, 84, 60, 61, 83, 86, 58, 63, 81, 88, 56, 65, 79, 90, 54, 67, 77, 92, 52, 69, 75, 94, 50, 71, 98, 46, 35, 29, 20, 44, 37, 27, 73, 96, 48, 33, 16, 9, 40, 41, 23, 26, 38, 43, 21, 28, 36, 45, 19, 30, 6, 10, 39, 42, 7, 18, 31, 5, 4, 32, 17, 8, 1, 15, 34, 47, 2, 14, 11, 25, 24, 12, 13, 3, 22.

real	0m7.889s
user	0m7.888s
sys	0m0.003s
$
Thanks to all involved in this thread. Was a lot of fun!

P.S. And as astrogeek pointed out, not quite as "amazing" as we originally thought, but still cool!

Last edited by GazL; 04-15-2021 at 07:05 AM.
 
2 members found this post helpful.
Old 04-13-2021, 10:44 AM   #40
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
yes, now comes the next step: find all the different solutions. (or the number of different circles)
 
Old 04-13-2021, 12:05 PM   #41
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 pan64 View Post
yes, now comes the next step: find all the different solutions. (or the number of different circles)
That's pretty easy to do with my code, but it's going to be cpu intensive for the larger numbers.

proof of concept diff (needs cleaning up):
Code:
--- amazing_circle_v2.2.c	2021-04-13 15:26:50.737773927 +0100
+++ amazing_all.c	2021-04-13 17:32:12.057721526 +0100
@@ -167,6 +167,23 @@
 
     return state ;
 }
+void print_sequence( struct state *state )
+{
+    if ( ! state->result )
+    {
+        printf("No sequence calculated.\n");
+        return ;
+    }
+
+    printf("Sequence:\n") ;
+
+    for ( int i = 0 ; i < state->max ; i++ )
+        printf(" %d,", state->result[i]);
+
+    printf("\b.\n");
+
+    return ;
+}
 
 int find_next( int depth, int value, struct state *state )
 {
@@ -175,8 +192,10 @@
     if ( depth == state->max )
     {
         if ( state->sqrt_table[state->result[0] + state->result[state->max - 1]] )
-            return 1 ;
-        else
+        {
+            print_sequence( state ) ;
+            return 0 ;
+        } else
             return 0 ;
     }
 
@@ -220,24 +239,6 @@
     return find_next(0, sequence_start, state) ;
 }
 
-void print_sequence( struct state *state )
-{
-    if ( ! state->result )
-    {
-        printf("No sequence calculated.\n");
-        return ;
-    }
-
-    printf("Sequence:\n") ;
-
-    for ( int i = 0 ; i < state->max ; i++ )
-        printf(" %d,", state->result[i]);
-
-    printf("\b.\n");
-
-    return ;
-}
-
 int main( int argc, char *argv[] )
 {
     int sequence_max = 0 ;
@@ -267,13 +268,7 @@
 
     printf("\nCalculating sequence, please wait...\n");
 
-    if ( calculate_sequence(sequence_start, &state) )
-    {
-        print_sequence( &state ) ;
-        return 0;
-    }
-
-    printf("Could not calculate sequence.\n");
+    calculate_sequence(sequence_start, &state) ;
 
     return 1;
 }
output:
Code:
98 possible pairs that sum to a square:
  1, 24
  1, 15
  1, 8
  1, 3
  2, 23
  2, 14
  2, 7
  3, 33
  3, 22
  3, 13
  3, 6
  3, 1
  4, 32
  4, 21
  4, 12
  4, 5
  5, 31
  5, 20
  5, 11
  5, 4
  6, 30
  6, 19
  6, 10
  6, 3
  7, 29
  7, 18
  7, 9
  7, 2
  8, 28
  8, 17
  8, 1
  9, 27
  9, 16
  9, 7
  10, 26
  10, 15
  10, 6
  11, 25
  11, 14
  11, 5
  12, 24
  12, 13
  12, 4
  13, 23
  13, 12
  13, 3
  14, 22
  14, 11
  14, 2
  15, 21
  15, 10
  15, 1
  16, 33
  16, 20
  16, 9
  17, 32
  17, 19
  17, 8
  18, 31
  18, 7
  19, 30
  19, 17
  19, 6
  20, 29
  20, 16
  20, 5
  21, 28
  21, 15
  21, 4
  22, 27
  22, 14
  22, 3
  23, 26
  23, 13
  23, 2
  24, 25
  24, 12
  24, 1
  25, 24
  25, 11
  26, 23
  26, 10
  27, 22
  27, 9
  28, 21
  28, 8
  29, 20
  29, 7
  30, 19
  30, 6
  31, 33
  31, 18
  31, 5
  32, 17
  32, 4
  33, 31
  33, 16
  33, 3

Calculating sequence, please wait...
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.
... works by pretending that a completed circle isn't. Each possible sequence will be reported twice, once in each direction. When I've had time to look at it a little more I might add an --all option to the cli.

Last edited by GazL; 04-13-2021 at 12:07 PM.
 
1 members found this post helpful.
Old 04-15-2021, 07:00 AM   #42
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Here we go, final tarted-up version, with -a and -v options.

edit:
oops, just spotted a duplication issue, and a few other tweaks.
version 2.5 (just reuploaded and hopefully really,really final this time)
Attached Files
File Type: txt circle.c.txt (7.7 KB, 20 views)

Last edited by GazL; 04-15-2021 at 10:03 AM.
 
2 members found this post helpful.
Old 04-15-2021, 10:21 AM   #43
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Downloaded but from 41 up largest number in sequence is duplicated and there are missing numbers, for n = 41 number 37 is missing.
Code:
% ./a.out 41 | grep -v result | wc -w 
41
% ./a.out 41 | grep -v result | tr ' ' '\n' | sort -n 
.
33
34
35
36
38
39
40
41
41
 
Old 04-15-2021, 10:45 AM   #44
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Yep, I forgot to set seen_values[] for the first value in v2.4 when I fixed the duplicate results issue. Should be fixed now in the reupload v2.5
 
2 members found this post helpful.
Old 04-15-2021, 10:19 PM   #45
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Well, i've finally (huff! puff!) gotten a working program, one that generates valid rings of squares, and the results seem to be the same as code already posted here. I have no clean code to upload yet, and hope to spend the weekend (and probably beyond) cleaning my code, adding options, and, possible speeding it up a bit. At present it's much slower than GazL's and others.

Throughout, i have retained the concept of a ring of data, with no arbitrary starting point and direction of flow. Have found that these arbitray factors can have a big impact upon process time, especially for generating the first valid ring. Perhaps this can lead to some performance gains.
 
1 members found this post helpful.
  


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:26 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