API tools faq
paste
Advertisement
algorithmuscanorj

A207324 Draft for a sequencer program based on the SJT algo.

algorithmuscanorj
Dec 28th, 2012
390
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 17.72 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * SeaDragon 0.59 (2012 Sept 18th)
  3.  * By R.J. Cano, <aallggoorriitthhmmuuss@gmail.com>
  4.  *
  5.  * Program released under the terms of the GNU General public license 3.0 (GNU-GPL 3.0)
  6.  *
  7.  *
  8.  *
  9.  *      << If people do not believe that mathematics is simple, it is only because
  10.  *          they do not realize how complicated life is. >>
  11.  *                  --John von Neumann
  12.  *
  13.  *
  14.  *
  15.  *
  16.  *  Hint for authors and contributors about C programs:
  17.  *
  18.  *      It is suggested when compiling C programs verify if it's written in an
  19.  *      acceptable way using a command like: "gcc -O2 -W -Wall my_oeis_program.c"
  20.  *
  21.  *  (Thanks to: Joerg Arndt)
  22.  *
  23.  *
  24.  *
  25.  *
  26.  *  Important:
  27.  *
  28.  *      Leak-bug feature still keept for research purposes, but it was partially fixed
  29.  *      reducing the leaks...
  30.  *
  31.  *      by a factor of:
  32.  *          [leaks_prime/leaks](n)= ( n/4 + 1 + 1/(n-1) )
  33.  *      from:
  34.  *          leaks_prime(n)= ( (n+4)*(n-1) + 4 )/2
  35.  *      to:
  36.  *          leaks(n)= 2*(n-1);
  37.  *
  38.  *  In other words, leaks were reduced from quadratic to linear according the work case.
  39.  *
  40.  *  ( At purpose,the 8 bytes block size mentioned for the leaks, depends on machine specifications )
  41.  *
  42.  *  Now assuming for certain machine a blocksize of 2 raised to "z", if you were ask to estimate for
  43.  *  which upper size "N" the program leaks when run an amount of 2 raised to "lambda" bytes, then you
  44.  *  should answer this: N= ( 2 raised to (lambda-z-1) ) plus 1;
  45.  *
  46.  *  As straightforward as it sounds... (Of course it have sense only for "lambda" greater than "z")
  47.  *
  48.  */
  49.  
  50. #include <stdio.h>
  51. #include <stdlib.h>
  52.  
  53. /*---------> non-standard datatype definitions <-----------------------------------------------------------*/
  54.  
  55. typedef struct matrix_linear_stack {
  56.  
  57.   long integer_value;
  58.   struct matrix_linear_stack *arrow;
  59.  
  60. } matrix_linear_stack;
  61.  
  62.  
  63. /*---------> non-standard constant values definition <------------------------------------------------------*/
  64.  
  65.  const long __mode_ZERO = 0;
  66.  const long __mode_EQUAL = 1;
  67.  const long __mode_DETERMINANT = 2;
  68.  const long __TOKEN_TEMPLATE   = 0;
  69.  const long __UNIT    = 1;
  70.  long generator_settings = 0;
  71.  long __config_generator[3][2];
  72.  
  73. /*---------> Suitable globals <-----------------------------------------------------------------------------*/
  74.  
  75. matrix_linear_stack *__the_ring_stckPointerReference_HEAD, *__the_ring_stckPointerReference_TAIL;
  76.  
  77. // About the ring:
  78. // Warning: After calling close__the_ring() a first time, don't call it again before a call to open_the_ring() of course
  79. // for the same parameter list (Else it would have possible harmful and unpredictible consequences).
  80.  
  81. /*---------> non-standards called by main(); <-----------------------------------------------------*/
  82.  
  83. void configure_modes(void);
  84.  
  85. void runSequencer(int, long);
  86.  
  87. /*---------> non-standards called by others; <-----------------------------------------------------*/
  88.  
  89. void finalizer_matrix(matrix_linear_stack **, matrix_linear_stack**);
  90.  
  91. void print_matrix(matrix_linear_stack **);
  92.  
  93. void myTryfor_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack**, matrix_linear_stack**, long);
  94.  
  95. void mode_matrix_waterfall(void);
  96.  
  97. matrix_linear_stack* generate_square_matrix(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, long);
  98.  
  99. void initializer_matrix(matrix_linear_stack **, matrix_linear_stack**);
  100.  
  101. matrix_linear_stack* extract_first_nodes(matrix_linear_stack**, matrix_linear_stack**, long);
  102.  
  103. void concat_matrices_node_by_node(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**);
  104.  
  105. /*---------> additional non-standards (some of them called by more than one function); <-----------------------------------------------------*/
  106.  
  107. long only_initialized(matrix_linear_stack**);
  108.  
  109. long absolute_value(long);
  110.  
  111. matrix_linear_stack* insert_new_node(long, matrix_linear_stack**);
  112.  
  113. void close__the_ring(matrix_linear_stack**, matrix_linear_stack**);
  114.  
  115. void open_the_ring(matrix_linear_stack**, matrix_linear_stack**);
  116.  
  117. long LeibnitzLaplaceSignature(long);
  118.  
  119. /*------------------------------------------------------------------------------------------------------------------------------*/
  120.  
  121. int main(void) {
  122.  
  123.   int j, _OScurrentExecutionFeedbackCode = EXIT_SUCCESS;
  124.   long N;
  125.  
  126.   configure_modes(); // Don't change this, it is for initialization.
  127.  
  128.   printf("%s%s","\n\nDemonstration program: ", "\n\n\tShould be run the sequencer only for a particular SJT-array? (1=yes, 0=No) ");  
  129.   scanf("%i", &j);
  130.   getchar();  
  131.   printf("%s","\n\n\tWhich is the upper size? (try first 1-11 on 32-bit machines): ");
  132.   scanf("%li", &N);
  133.   getchar();
  134.  
  135.   runSequencer(j, N);
  136.  
  137.   return _OScurrentExecutionFeedbackCode;
  138.  
  139. }
  140.  
  141. /*------------------------------------------------------------------------------------------------------------------------------*/
  142.  
  143. void configure_modes(void) {
  144.  
  145.   __config_generator[__mode_ZERO][__TOKEN_TEMPLATE] = 0;
  146.   __config_generator[__mode_ZERO][__UNIT]  = 0;
  147.  
  148.   __config_generator[__mode_EQUAL][__TOKEN_TEMPLATE] = 0;
  149.   __config_generator[__mode_EQUAL][__UNIT]  = 1;
  150.  
  151.   __config_generator[__mode_DETERMINANT][__TOKEN_TEMPLATE] = 1;
  152.   __config_generator[__mode_DETERMINANT][__UNIT]  = 0;
  153.  
  154. }
  155.  
  156. /*------------------------------------------------------------------------------------------------------------------------------*/
  157.  
  158. void runSequencer(int just_for_the_Nth_array, long N) {
  159.  
  160.   long k;
  161.  
  162.   matrix_linear_stack *J0_head, *J0_tail;
  163.  
  164.   for (k=(just_for_the_Nth_array ? N : 1);k<=N;k++) {
  165.     myTryfor_SteinhausJohnsonTrotterAlgorithm(&J0_head, &J0_tail, k);
  166.     print_matrix(&J0_head);
  167.     finalizer_matrix(&J0_head, &J0_tail);
  168.   }
  169.  
  170.   printf("\n\n\tSequencer execution completed successfully.\n");    
  171.  
  172. }
  173.  
  174. /*------------------------------------------------------------------------------------------------------------------------------*/
  175.  
  176. void finalizer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
  177.  
  178.   while (*stckPointerReference_HEAD != NULL) {
  179.  
  180.     (*stckPointerReference_TAIL) = (*stckPointerReference_HEAD);
  181.     (*stckPointerReference_HEAD) = (*stckPointerReference_HEAD)->arrow;
  182.     free( *stckPointerReference_TAIL );
  183.  
  184.   }
  185.  
  186.     (*stckPointerReference_TAIL) = NULL;
  187.  
  188. }
  189.  
  190. /*------------------------------------------------------------------------------------------------------------------------------*/
  191.  
  192. void print_matrix(matrix_linear_stack **stckPointerReference_HEAD) {
  193.  
  194.   matrix_linear_stack* focus= *stckPointerReference_HEAD;
  195.  
  196.   if ( NULL == focus ) {
  197.  
  198.     printf(" Not initialized! ");
  199.  
  200.   } else {
  201.  
  202.     if ( -1 == (focus->integer_value) ) {
  203.  
  204.       focus = focus->arrow;
  205.  
  206.       if ( NULL == focus ) {
  207.  
  208.     printf(" initialized but empty. ");
  209.  
  210.       } else {;}
  211.  
  212.     } else {
  213.  
  214.     }
  215.  
  216.     while ( NULL != focus ) {
  217.  
  218.       printf("\n%li", (focus->integer_value) );
  219.  
  220.       focus = focus->arrow;
  221.     }
  222.  
  223.   }
  224.  
  225. }
  226.  
  227. /*------------------------------------------------------------------------------------------------------------------------------*/
  228.  
  229. void myTryfor_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack **J_head, matrix_linear_stack **J_tail, long _SIZE) {
  230.  
  231.   matrix_linear_stack *JJ_head;
  232.   matrix_linear_stack *JJ_tail;
  233.   matrix_linear_stack *P_head;
  234.   matrix_linear_stack *P_tail;
  235.   matrix_linear_stack *Q_head;
  236.   matrix_linear_stack *Q_tail;
  237.  
  238.   long diagonal;
  239.  
  240.   long _CASE = 1;
  241.  
  242.   mode_matrix_waterfall();
  243.  
  244.   generate_square_matrix(NULL, NULL, J_head, J_tail, 1);
  245.  
  246.   while (_CASE < _SIZE) {
  247.  
  248.     _CASE++;
  249.     diagonal = -1;
  250.     initializer_matrix(&JJ_head, &JJ_tail);
  251.  
  252.     while ( !only_initialized(J_head) ) {
  253.  
  254.       P_head = extract_first_nodes(J_head, &P_tail, (_CASE-1)) ;
  255.       generate_square_matrix(&P_head, &P_tail, &Q_head, &Q_tail, _CASE*diagonal);
  256.       concat_matrices_node_by_node(&JJ_tail, &Q_head, &Q_tail);
  257.       finalizer_matrix(&P_head, &P_tail);
  258.  
  259.       diagonal *= -1;
  260.  
  261.     }
  262.  
  263. /*
  264.  *  This lines fixes partially the leakage.
  265.  */
  266.     finalizer_matrix(J_head, J_tail);
  267. /**/
  268.     *J_head = JJ_head;
  269.     *J_tail   = JJ_tail;
  270.     JJ_head = NULL;
  271.     JJ_tail   = NULL;
  272.  
  273.   }
  274.  
  275. }
  276.  
  277. /*------------------------------------------------------------------------------------------------------------------------------*/
  278.  
  279. void  mode_matrix_waterfall(void) {
  280.  
  281.   generator_settings = __mode_DETERMINANT;
  282.  
  283. }
  284.  
  285. /*------------------------------------------------------------------------------------------------------------------------------*/
  286.  
  287. matrix_linear_stack* generate_square_matrix(matrix_linear_stack **baseRef_head, matrix_linear_stack **baseRef_tail, matrix_linear_stack **ref_answer_head, matrix_linear_stack **ref_answer_tail, long TOKEN_TEMPLATE) {
  288.  
  289.   long counting_L = 1;
  290.   long counting_X = 1;
  291.   long counting_Y = 1;
  292.   long matrix_size = absolute_value(TOKEN_TEMPLATE);
  293.   long newValuetobeIncluded;
  294.  
  295.   matrix_linear_stack *BASE_head, *BASE_tail;
  296.  
  297.   if ( ( (baseRef_head) == (baseRef_tail) ) && ( NULL == (baseRef_head) ) ) {
  298.  
  299.     initializer_matrix(&BASE_head, &BASE_tail);
  300.     insert_new_node(0, &BASE_tail);
  301.  
  302.   } else if ( (baseRef_head != NULL) && (baseRef_tail != NULL) ) {
  303.  
  304.     BASE_head = *baseRef_head;
  305.     BASE_tail   = *baseRef_tail;
  306.  
  307.   } else {
  308.  
  309.     return NULL;
  310.  
  311.   }
  312.  
  313.   close__the_ring(&BASE_head, &BASE_tail);
  314.  
  315.   initializer_matrix(ref_answer_head, ref_answer_tail);
  316.  
  317.   matrix_size = absolute_value(TOKEN_TEMPLATE);
  318.  
  319.   while (counting_L <= (matrix_size*matrix_size)) {
  320.  
  321.     if (BASE_head->integer_value == -1) { BASE_head = BASE_head->arrow; }
  322.  
  323.     newValuetobeIncluded = (TOKEN_TEMPLATE < 0) ? ( ( counting_X + counting_Y == (matrix_size+1) ) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) ) : ( (counting_X - counting_Y == 0) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) );
  324.  
  325.     if ( ( 0 == newValuetobeIncluded ) && ( __mode_ZERO != generator_settings) ) {
  326.  
  327.       newValuetobeIncluded+= (BASE_head->integer_value);
  328.       BASE_head = BASE_head->arrow;
  329.  
  330.     }
  331.  
  332.     insert_new_node(newValuetobeIncluded, ref_answer_tail);
  333.  
  334.     counting_L++;
  335.     counting_X++;
  336.     if (counting_X > matrix_size) {
  337.       counting_X = 1;
  338.       counting_Y++;
  339.     }
  340.   }
  341.  
  342.   open_the_ring(&BASE_head, &BASE_tail);
  343.  
  344.   return (*ref_answer_head);
  345. }
  346.  
  347. /*----------------------------------------------------------------------------------------------------------------------(OJO)---*/
  348.  
  349. void initializer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
  350.  
  351.   (*stckPointerReference_HEAD) = NULL;
  352.   (*stckPointerReference_TAIL) = insert_new_node( -1, stckPointerReference_HEAD );
  353.  
  354. }
  355.  
  356. /*------------------------------------------------------------------------------------------------------------------------------*/
  357.  
  358. matrix_linear_stack* extract_first_nodes(matrix_linear_stack** ref_from_source, matrix_linear_stack** stckPointerReference_TAIL, long arg_howmanymustbe) {
  359.  
  360.   long counting = 1;
  361.   long howmanymustbe = ( 0 == arg_howmanymustbe ) ? 1 : arg_howmanymustbe;
  362.   matrix_linear_stack *focus = (*ref_from_source)->arrow;
  363.   matrix_linear_stack *answer;
  364.  
  365.   initializer_matrix(&answer, stckPointerReference_TAIL);
  366.  
  367.   while ( counting < howmanymustbe ) {
  368.  
  369.     focus = focus->arrow;
  370.     counting++;
  371.  
  372.   }
  373.  
  374.   (*stckPointerReference_TAIL)->arrow     = (*ref_from_source)->arrow;
  375.   (*ref_from_source)->arrow = focus->arrow;
  376.   focus->arrow         = NULL;
  377.   (*stckPointerReference_TAIL) = focus;
  378.  
  379.   return answer;
  380.  
  381. }
  382.  
  383. /*------------------------------------------------------------------------------------------------------------------------------*/
  384.  
  385. void concat_matrices_node_by_node(matrix_linear_stack **operand_left_tail, matrix_linear_stack **operand_right_head, matrix_linear_stack **operand_right_tail) {
  386.  
  387.   matrix_linear_stack *slayer = *operand_right_head;
  388.   *operand_right_head = NULL;
  389.   (*operand_left_tail)->arrow = slayer->arrow;
  390.   slayer->arrow               = NULL;
  391.   free(slayer);
  392.   *operand_left_tail          = *operand_right_tail;
  393.   *operand_right_tail         = NULL;
  394.  
  395. }
  396.  
  397. /*------------------------------------------------------------------------------------------------------------------------------*/
  398.  
  399. long  only_initialized(matrix_linear_stack** stckPointerReference_HEAD) {
  400.  
  401.  
  402.  
  403.   if ( 0 != ( NULL != stckPointerReference_HEAD ) ) {
  404.     if ( 0 != ( NULL != *stckPointerReference_HEAD ) ) {
  405.       if ( 0 != ( NULL == (*stckPointerReference_HEAD)->arrow ) ) {
  406.     if ( -1 == (*stckPointerReference_HEAD)->integer_value ) {
  407.       return 1;
  408.     }
  409.       }
  410.     }
  411.   }
  412.  
  413.   return 0;
  414.  
  415. }
  416.  
  417. /*------------------------------------------------------------------------------------------------------------------------------*/
  418.  
  419. long absolute_value(long argument) {
  420.  
  421.   return ( argument * LeibnitzLaplaceSignature(argument) );
  422.  
  423. }
  424.  
  425. /*------------------------------------------------------------------------------------------------------------------------------*/
  426.  
  427. matrix_linear_stack* insert_new_node(long value_assigned, matrix_linear_stack **stckPointerReference_TAIL) {
  428.  
  429.   matrix_linear_stack *focus;
  430.   matrix_linear_stack *inserto = (matrix_linear_stack *)( malloc( sizeof( matrix_linear_stack ) ) );
  431.  
  432.   matrix_linear_stack *answer_ref = inserto;
  433.   inserto->integer_value  = value_assigned;
  434.   inserto->arrow = NULL;
  435.  
  436.   if (( NULL == (*stckPointerReference_TAIL) ) && (-1 == value_assigned)) {
  437.  
  438.     (*stckPointerReference_TAIL) = inserto;
  439.  
  440.   } else if ( NULL != (*stckPointerReference_TAIL) ) {
  441.  
  442.       focus = (*stckPointerReference_TAIL);
  443.       while ( NULL != focus->arrow ) { focus = focus->arrow; }
  444.       focus->arrow = inserto;
  445.       if ( focus == (*stckPointerReference_TAIL) ) { (*stckPointerReference_TAIL) = inserto; }
  446.  
  447.   }
  448.  
  449.   return answer_ref;
  450. }
  451.  
  452. /*------------------------------------------------------------------------------------------------------------------------------*/
  453.  
  454. void close__the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
  455.  
  456.   __the_ring_stckPointerReference_HEAD = *stckPointerReference_HEAD;
  457.   __the_ring_stckPointerReference_TAIL   = *stckPointerReference_TAIL;
  458.   (*stckPointerReference_TAIL)->arrow = *stckPointerReference_HEAD;
  459.  
  460. }
  461.  
  462. /*------------------------------------------------------------------------------------------------------------------------------*/
  463.  
  464. void open_the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
  465.  
  466.   (*stckPointerReference_HEAD)       = __the_ring_stckPointerReference_HEAD;
  467.   (*stckPointerReference_TAIL)         = __the_ring_stckPointerReference_TAIL;
  468.   (*stckPointerReference_TAIL)->arrow = NULL;
  469.  
  470. }
  471.  
  472. /*------------------------------------------------------------------------------------------------------------------------------*/
  473.  
  474. long LeibnitzLaplaceSignature(long argument) {
  475.  
  476.   long answer;
  477.  
  478.   answer = (argument < 0) ? (-1) : (1) ;
  479.  
  480.   return answer;
  481.  
  482. }
  483.  
  484. /*===============================================> "The End" <===================================================================
  485.  *
  486.  *  Below is a sample output, run from the author's machine:
  487.  *
  488.  *-------------------------------------------------------------------------------------------------------------------------------
  489.  
  490.  rjcano@seadragon:~/oeis-experiments$ g++ -x c -O2 -Wall ./seadragon_v049.c && ./a.out
  491.  
  492.  Demonstration program:
  493.  
  494.     Should be run the sequencer only for a particular SJT-array? (1=yes, 0=No) 0
  495.  
  496.     Which is the upper size? (try first 1-11 on 32-bit machines): 10
  497.  
  498.  .
  499.  .
  500.  .
  501.  2
  502.  1
  503.  3
  504.  4
  505.  5
  506.  6
  507.  7
  508.  8
  509. 10
  510.  9
  511.  2
  512.  1
  513.  3
  514.  4
  515.  5
  516.  6
  517.  7
  518.  8
  519.  9
  520. 10
  521.  
  522.         Sequencer execution completed successfully.
  523.  
  524. Memory usage summary: heap total: 359036024, heap peak: 290304264, stack peak: 728
  525.          total calls   total memory   failed calls
  526.  malloc|   44879439      359035512              0
  527. realloc|          2            512              0  (nomove:0, dec:0, free:0)
  528.  calloc|          0              0              0
  529.    free|   44879421      359035864
  530. Histogram for block sizes:
  531.     0-15       44879439   4% ==================================================
  532.   256-271             2  <1%
  533.  
  534. rjcano@seadragon:~/oeis-experiments$ uname -a
  535. Linux seadragon 3.2.28-smp #2 SMP Thu Aug 23 12:58:19 CDT 2012 i686 Genuine Intel(R) CPU N270   @ 1.60GHz GenuineIntel GNU/Linux
  536.  
  537. rjcano@seadragon:~/oeis-experiments$ g++ -v
  538. Reading specs from /usr/lib/gcc/i486-slackware-linux/4.7.1/specs
  539. COLLECT_GCC=g++
  540. COLLECT_LTO_WRAPPER=/usr/libexec/gcc/i486-slackware-linux/4.7.1/lto-wrapper
  541. Target: i486-slackware-linux
  542. Configured with: ../gcc-4.7.1/configure --prefix=/usr --libdir=/usr/lib --mandir=/usr/man --infodir=/usr/info --enable-shared --enable-bootstrap --enable-languages=ada,c,c++,fortran,go,java,lto,objc --enable-threads=posix --enable-checking=release --enable-objc-gc --with-system-zlib --with-python-dir=/lib/python2.7/site-packages --disable-libunwind-exceptions --enable-__cxa_atexit --enable-libssp --enable-lto --with-gnu-ld --verbose --enable-java-home --with-java-home=/usr/lib/jvm/jre --with-jvm-root-dir=/usr/lib/jvm --with-jvm-jar-dir=/usr/lib/jvm/jvm-exports --with-arch-directory=i386 --with-antlr-jar=/root/slackware-current/source/d/gcc/antlr-runtime-3.4.jar --enable-java-awt=gtk --disable-gtktest --with-arch=i486 --target=i486-slackware-linux --build=i486-slackware-linux --host=i486-slackware-linux
  543. Thread model: posix
  544. gcc version 4.7.1 (GCC)
  545.  
  546. rjcano@seadragon:~/oeis-experiments$ memusage -V
  547. memusage (GNU libc) 2.15
  548. Copyright (C) 2012 Free Software Foundation, Inc.
  549. This is free software; see the source for copying conditions.  There is NO
  550. warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  551. Written by Ulrich Drepper.
  552.  
  553. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!