LinuxQuestions.org
Review your favorite Linux distribution.
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 07-07-2017, 11:24 PM   #121
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319

By the way, I searched around for "cheap tricks" for multiprocessing, and I learned that xargs (the bash command) can be used to schedule a sequence of commands to utilize the available processors. So I modified one of my programs to take a command-line argument for the number of digits, and to write its output to a text file (because redirection to stdout may scramble the results), and tried it out as follows on my dual-processor rig:
Code:
time (seq 19 -1 3 | xargs --max-args=1 --max-procs=2 ./arm_v; cat armnums*.txt | sort -n)
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
4679307774
32164049650
32164049651
40028394225
42678290603
44708635679
49388550606
82693916578
94204591914
28116440335967
4338281769391370
4338281769391371
21897142587612075
35641594208964132
35875699062250035
1517841543307505039
3289582984443187032
4498128791164624869
4929273885928088826

real	0m16.633s
user	0m32.556s
sys	0m0.004s
As you see by comparing real vs. user time, this method approximately doubled the speed. Scheduling the jobs in reverse order (longest jobs first) gives better utilization of all processors. Otherwise the last (and longest) job would run by itself at the end. This timeline shows the sequence (not to scale):

Code:
      time: start...................................end
processor0: 19.......15 14 13..........9.....6...4..
processor1: 18 17 16..........12 11 10...8 7...5...3
This is not the most sophisticated kind of multiprocessing, but it can be used for uncoupled jobs, where no information needs to be passed between running processes.

Last edited by Beryllos; 07-07-2017 at 11:27 PM.
 
2 members found this post helpful.
Old 07-08-2017, 12:11 AM   #122
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
Quote:
Originally Posted by Beryllos View Post
As you see by comparing real vs. user time, this method approximately doubled the speed. Scheduling the jobs in reverse order (longest jobs first) gives better utilization of all processors. Otherwise the last (and longest) job would run by itself at the end. This timeline shows the sequence (not to scale):
This is not the most sophisticated kind of multiprocessing, but it can be used for uncoupled jobs, where no information needs to be passed between running processes.
Wow, cool! I didn't know xargs could do that.

I got around the problem of the big numbers taking longer by making an array of all the numbers to test then shuffling them randomly before splitting the array up according to the number of processors (actually cores) the machine has. The computer I'm running this on now is a tethered (connected to a LCD monitor, external keyboard, mouse, etc.) laptop. But it has an Intel Core i7 processor and shows up as 8 separate cores. And, according to the performance monitor, it was taking up an average of about 780% of the processor time so it seemed to work quite well.

There's just that problem of weird non-narcissistic numbers popping up in 4 and higher digits. I haven't been in the mood to work on it today, but maybe tomorrow. It looks like a weird error that may be hard to pin down. I really want to rewrite that section anyway, so maybe doing that will fix the problem.
 
Old 07-11-2017, 01:34 PM   #123
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Just for fun, I wrote a simple C program to find Armstrong numbers with any number of digits. Numbers are represented as integer arrays with one decimal digit stored in each array element. (This required a few array math functions which I provided as well.)

Tested: Running on a 1.8 GHz Pentium-M (single processor), it obtained all the Armstrong numbers of 1 to 39 digits in just under 18 hours.

New idea (?) for boosting the speed: Count rather than sort digits. One of the inefficiencies of my Python program (see Post 92), besides constantly recalculating the powers of digits, was sorting the digits of the sum. The issue is that sorting takes a lot of CPU cycles, and the sort resides in the innermost loop. An alternative is to count digits: how many zeroes, ones, twos, and so on, up to nines. Then the two numbers (actually their combinations of digits) can be compared by comparing counts. Here is a C implementation of that:
Code:
int count_and_compare_digits(int * array1, int * array2, int ndigits)
{
    // array1 and array2 must contain decimal digits
    // ndigits is the number of digits to be compared

    int i;
    int count1[10];  // small static arrays, no need for malloc
    int count2[10];
    
    for (i=0;i<10;++i)
    {
        count1[i] = 0;  // initialize counts
        count2[i] = 0;
    }

    for (i=0;i<ndigits;++i)
    {
        ++count1[array1[i]];  // count according to value of digit
        ++count2[array2[i]];
    }
    
    for (i=0;i<10;++i)
    {
        if (count1[i] != count2[i])  // compare counts
            return 0;  // return 0 when any difference is detected
    }
    return 1;  // return 1 if all digit counts are identical
}
The time requirement (so-called computational complexity) for this algorithm for N digits scales roughly as O(N), whereas sort algorithms tend to scale as O(N*log(N)), so this should be faster.
 
Old 07-12-2017, 02:38 AM   #124
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
yes, I want to try something similar, but needs time to implement it. Actually I posted a better solution (instead of sorting), which is definitely faster.
 
Old 07-12-2017, 04:52 AM   #125
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
here are my results:
Code:
3-19 digits:    4.64 sec
3-24 digits:   36    sec
3-29 digits: 3:20    sec
3-39 digits: ~55 mins     (!)
this is written in C and used my own big numbers:
Code:
typedef unsigned long long int ulli;

#define BIGNUM_SIZE 15
#define BIGNUM_LIMIT 1000000000000000

struct bignum {
    ulli a1, a2, a3;
};

void set_bignum(bignum *b, int i) {
    b->a1 = i;
    b->a2 = b->a3 = 0;
}

void normalize_bignum(bignum *a) {
    while (a->a1 > BIGNUM_LIMIT) {
        a->a1 -= BIGNUM_LIMIT;
        a->a2 ++;
    }
    while (a->a2 > BIGNUM_LIMIT) {
        a->a2 -= BIGNUM_LIMIT;
        a->a3 ++;
    }
}

void add_bignum(bignum *a, bignum *b) {
    a->a1 += b->a1;
    a->a2 += b->a2;
    a->a3 += b->a3;
    normalize_bignum(a);
}

void mult_bignum(bignum *a, char b) {
    a->a1 *= b;
    a->a2 *= b;
    a->a3 *= b;
    normalize_bignum(a);
}

int bignum_to_string(char *buf, bignum *b) {
    ulli a1 = b->a1;
    ulli a2 = b->a2;
    ulli a3 = b->a3;
    int i;
    char *p = buf;
    memset(buf, 0, 60);
    for (i=0; i<BIGNUM_SIZE; i++) {
        *p++ = a1 % 10;
        a1 /= 10;
    }
    if ( a2 + a3 ) {
        for (i=0; i<BIGNUM_SIZE; i++) {
            *p++ = a2 % 10;
            a2 /= 10;
        }
        if ( a3 ) {
            for (i=0; i<BIGNUM_SIZE; i++) {
                *p++ = a3 % 10;
                a3 /= 10;
            }
        }
    }
    for ( p=buf+55; p>buf; p--) {
        if ( *p & 0xF )
            break;
        *p = 0;
    }
    return p-buf + 1;
}
Code:
// 65 * X
char test[] = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";

char next_comb_rep(unsigned char vec[], int place) {
    if (place == 0) {
        vec[0] ++;
    } else {
        if (next_comb_rep(vec, place-1)) {
            vec[place]++;
            for (int j=0; j<place; j++) {
                vec[j] = vec[place];
            }
        }
    }
    return vec[place] == 10;
}

void sum_of_power_of_digit(unsigned char digits[], int power) {
    set_bignum(&sum, 0);
    for(int i=0; i<power; ++i) {
        add_bignum(&sum, &powers[digits[i]]);
    }
}

void fill_powers(int base) {
    for (int i=1; i<12; i++) {
         set_bignum(&powers[i], i);
         for(int pow=1; pow<base; ++pow) {
             mult_bignum(&powers[i], i);
         }
    }
}

char del (unsigned char v[], char a, int len) {
    for (int i=0; i<len; i++) {
        if ( v[i] == a ) {
            v[i] = 'X';
            return 0;
        }
    }
    return 1;
}

int main() {
    for(int base=3; base<30; ++base) {
        printf("%i digits:\n", base);
        unsigned char vec[base];
        unsigned char vec1[base];
        char buf[60];
        char buf1[60];
        memset(vec, 0, base * sizeof(char));
        fill_powers(base);
        while(1){
            if(next_comb_rep(vec, base-1)) {
                break;
            }
            sum_of_power_of_digit(vec, base);
            memcpy(vec1, vec, base);
            int q = bignum_to_string(buf, &sum);
            if (q != base)
                 continue;

            for (q=0; q<base; q++) {
                if ( del(vec1, buf[q], base) != 0 )
                    break;
            }
            if (q != base)
                 continue;
//            out_vec.emplace_back(num);
            memset(buf1, 0, 60);
            for (q=0; q<base; q++) {
                buf1[q] = buf[base-q-1] + 48;
            }
            printf("%s\n", buf1);
        }
//        std::sort(out_vec.begin(), out_vec.end());
//        for(mpz i : out_vec){
//            cout << i << "\n";
//        }
    }
}
the result is not sorted.
And obviously there are still room for improvement

Last edited by pan64; 07-12-2017 at 05:24 AM.
 
1 members found this post helpful.
Old 07-12-2017, 02:18 PM   #126
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
yes, I want to try something similar, but needs time to implement it. Actually I posted a better solution (instead of sorting), which is definitely faster.
I apologize for not understanding your code and seeing that you did that.

Quote:
Originally Posted by pan64 View Post
here are my results:
Code:
3-19 digits:    4.64 sec
3-24 digits:   36    sec
3-29 digits: 3:20    sec
3-39 digits: ~55 mins     (!)
this is written in C and used my own big numbers...
That is fast!
 
Old 07-13-2017, 12:53 AM   #127
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
Quote:
Originally Posted by Beryllos View Post
I apologize for not understanding your code and seeing that you did that.
You can always ask and we can always discuss how to improve.
 
Old 07-16-2017, 06:07 AM   #128
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
ok, so here are some explanation:
  • to speed up the process we do not need to check all the numbers, but the ones generated using next_comb_rep. This is a great find and a very good improvement.
  • This next_comb_rep function works on char (digit) array (arbitrary length) - the result is stored in the variable vec.
  • We need to sum up power of these digits, which is impossible using predefined c types (because the maximal available length is not enough for us). The already implemented solutions to handle really big numbers are "relatively" slow, therefore I constructed a new type which consist of 3 unsigned long long integers. I restricted their usage to 16 digits, so altogether this can handle 48 digits which is fine for us (and obviously it can be extended if required). Only the required functionality was implemented: set/assign value (to int), multiply by a single digit, add bignum. normalize_bignum is used to handle the internal overflow (when any of internal ulli variables will contain more than 16 digits). Additionally there is a replacement of the traditional to_string or sprintf functionality, because that is quite slow. It is the funtion bignum_to_string which constructs list of digits from left to right (reverse order) and they are in the range 0x0-0x9 instead of '0' - '9' (0x30-0x39), similar way as it was generated/used in next_comb_rep. I use a table to do the conversion, this is named charmap.
  • Now we can invoke the function sum_of_power_of_digits on the generated vec using this bignum type,
  • convert the result bignum_to_string, check its length
  • count the different digits of vec and this bignum and compare them
  • and finally if everything was ok I convert the string to a printable char * (adding 48 to each digit and by reversing the order)
sorting is still missing at the end.
Code:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long int ulli;

int counter[11];

#define BIGNUM_SIZE 16
#define BIGNUM_LIMIT 10000000000000000

struct bignum {
    ulli a1, a2, a3;
};

union charmap_u {
    ulli a_i;
    char a_c[4];
};

typedef struct bignum bignum;
typedef union charmap_u charmap_t;

bignum powers[12];
bignum sum;
charmap_t charmap[10001];

/* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

void set_bignum(bignum *b, int i) {
    b->a1 = i;
    b->a2 = b->a3 = 0;
}

void normalize_bignum(bignum *a) {
    if (a->a1 > BIGNUM_LIMIT) {
        a->a2 += a->a1/BIGNUM_LIMIT;
        a->a1 %= BIGNUM_LIMIT;
    }
    if (a->a2 > BIGNUM_LIMIT) {
        a->a3 += a->a2/BIGNUM_LIMIT;
        a->a2 %= BIGNUM_LIMIT;
    }
}

void add_bignum(bignum *a, bignum *b) {
    a->a1 += b->a1;
    a->a2 += b->a2;
    a->a3 += b->a3;
//    normalize_bignum(a);
}

void mult_bignum(bignum *a, char b) {
    a->a1 *= b;
    a->a2 *= b;
    a->a3 *= b;
    normalize_bignum(a);
}

void ulli_to_string(int *buf, ulli i){
    int j;
    int *p = buf;
    if ( i == 0 )
        return;
    for (j=0; j<4; j++) {
        p[j] = charmap[i%10000].a_i;
	i /= 10000;
    }
}

// returns the length of the string
int bignum_to_string(char *buf, bignum *b) {
    memset(buf, 0, 50);
    int *p = (int *)buf;
    ulli_to_string(p, b->a1);
    p += 4;
    ulli_to_string(p, b->a2);
    p += 4;
    ulli_to_string(p, b->a3);
    int q;
    char *r = buf + 48;
    for (q=48; q>0; q--)
        if ( *r-- )
	    break;
    return ++q;
}
        
/* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

char next_comb_rep(unsigned char vec[], int place) {
    if (place == 0) {
        vec[0] ++;
    } else {
        if (next_comb_rep(vec, place-1)) {
            vec[place]++;
            int j;
            for (j=0; j<place; j++) {
                vec[j] = vec[place];
            }
        }
    }
    return vec[place] == 10;
}

/* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

void sum_of_power_of_digits(unsigned char digits[], int power) {
    set_bignum(&sum, 0);
    int i;
    for(i=0; i<power; ++i) {
        add_bignum(&sum, &powers[digits[i]]);
    }
    normalize_bignum(&sum);
}

/* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

void fill_powers(int base) {
    int i;
    int pow;
    for (i=1; i<11; i++) {
         set_bignum(&powers[i], i);
         for(pow=1; pow<base; ++pow) {
             mult_bignum(&powers[i], i);
         }
    }
}

void fill_charmap() {
    char a, b, c, d;
    int i;
    for (a=0; a<10; a++) {
        for (b=0; b<10; b++) {
            for (c=0; c<10; c++) {
                for (d=0; d<10; d++) {
                    i=1000*d+100*c+10*b+a;
                    charmap[i].a_c[0] = a;
                    charmap[i].a_c[1] = b;
                    charmap[i].a_c[2] = c;
                    charmap[i].a_c[3] = d;
                }
            }
        }
    }
}
        
int compare_digits(unsigned char a[], char b[], int len) {
    int q;
    for (q=0; q<10; q++)
        counter[q] = 0;
    for (q=0; q<len; q++)
	counter[a[q]]++;
    for (q=0; q<len; q++) {
	if ( --counter[(unsigned)b[q]] < 0 )
            break;
    }
    return q;
}

/* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

int main() {
    fill_charmap();
    int base;

    for(base=3; base<30; ++base) {
        printf("%i digits:\n", base);
        unsigned char vec[base];
        char buf[60];
        char buf1[60];
        memset(vec, 0, base * sizeof(char));
        fill_powers(base);
        while(1){
            if(next_comb_rep(vec, base-1)) {
                break;
            }
            int q;
            sum_of_power_of_digits(vec, base);
            q = bignum_to_string(buf, &sum);
	    if ( q != base )
	        continue;
	    q = compare_digits(vec, buf, base);
	    if ( q != base )
	        continue;

            memset(buf1, 0, 60);
            for (q=0; q<base; q++) {
                buf1[q] = buf[base-q-1] + 48;
            }
//            out_vec.emplace_back(num);
            printf("%s\n", buf1);
        }
//        std::sort(out_vec.begin(), out_vec.end());
//        for(mpz i : out_vec){
//            cout << i << "\n";
//        }
    }
    exit(0);
}
with this code the generation of all the 10 based narcissistic numbers was completed within 30 minutes (28:53.03) on my host.

And a few words about multithreading:
generation of 39 digit numbers was running at about 6 minutes (5:55.33) - 38 digits: 5 minutes (4:54.24), 37 digits: 4 minutes (3:55.28), 36 digits: 3 minutes (3:03.60) ...
so probably if we can have enough threads/CPU we can complete it in 6 minutes.
 
1 members found this post helpful.
Old 07-17-2017, 10:28 AM   #129
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
ok, so here are some explanation:
  • to speed up the process we do not need to check all the numbers, but the ones generated using next_comb_rep. This is a great find and a very good improvement.
  • This next_comb_rep function works on char (digit) array (arbitrary length) - the result is stored in the variable vec.
  • We need to sum up power of these digits, which is impossible using predefined c types (because the maximal available length is not enough for us). The already implemented solutions to handle really big numbers are "relatively" slow, therefore I constructed a new type which consist of 3 unsigned long long integers. I restricted their usage to 16 digits, so altogether this can handle 48 digits which is fine for us (and obviously it can be extended if required). Only the required functionality was implemented: set/assign value (to int), multiply by a single digit, add bignum. normalize_bignum is used to handle the internal overflow (when any of internal ulli variables will contain more than 16 digits). Additionally there is a replacement of the traditional to_string or sprintf functionality, because that is quite slow. It is the funtion bignum_to_string which constructs list of digits from left to right (reverse order) and they are in the range 0x0-0x9 instead of '0' - '9' (0x30-0x39), similar way as it was generated/used in next_comb_rep. I use a table to do the conversion, this is named charmap.
  • Now we can invoke the function sum_of_power_of_digits on the generated vec using this bignum type,
  • convert the result bignum_to_string, check its length
  • count the different digits of vec and this bignum and compare them
  • and finally if everything was ok I convert the string to a printable char * (adding 48 to each digit and by reversing the order)
sorting is still missing at the end.
Code:
...
with this code the generation of all the 10 based narcissistic numbers was completed within 30 minutes (28:53.03) on my host.

And a few words about multithreading:
generation of 39 digit numbers was running at about 6 minutes (5:55.33) - 38 digits: 5 minutes (4:54.24), 37 digits: 4 minutes (3:55.28), 36 digits: 3 minutes (3:03.60) ...
so probably if we can have enough threads/CPU we can complete it in 6 minutes.
Thanks for the explanations. I think I understand it all now. You have done a great job coding it for speed.

I see that you made at least two speed-related improvements since your previous code (in Post 125):
  • Converting bignum to string with charmap[], a lookup table for 4-digit segments, should be much quicker than using /10 and %10 for every digit. This is important because this conversion is done for every number that is tested.
  • Without going into a detailed analysis or test, I suspect that compare_digits() requires fewer operations than del(), so it should be faster.
I was wondering why you dimension powers[12] and fill it up to the 10th power. I thought powers[10] and filling only to the 9th power would be sufficient. Similarly I think it would be sufficient to dimension charmap[10000]. Did I miss the reason for the extra elements? (These would not impact the speed. I am just wondering whether this is a matter of function or style.)
 
Old 07-19-2017, 11:37 PM   #130
smeezekitty
Senior Member
 
Registered: Sep 2009
Location: Washington U.S.
Distribution: M$ Windows / Debian / Ubuntu / DSL / many others
Posts: 2,339

Rep: Reputation: 231Reputation: 231Reputation: 231
Code:
>>[-]+[>>>>>>[-]<<[-]>>>[<<<+>>>-]<<<[>>>+<+<<-]>>>>>[-]<<<[>[>>>+<<<-
]>>>[<<<+>>+>-]<<<<-]>>[-]<<[-]>[<+>-]<[>+>+<<-][-]>>[<<<<[-]>>>>>[<<<
<<+>>>>>-]<<<<<[>>>>>+<<<+<<-]>>>>-]>[-]<<<[>>>+<<<-]<<<<[-]>>[-]<[>+<
-]>[<+<+>>-]>[-]<<<[>>>>[-]<<<[>>>+<<<-]>>>[<<<+>>+>-]<<<<-]>>[-]<<[-]
>[<+>-]<[>+>+<<-][-]>>[>>[-]<[>+<-]>[<+<<<+>>>>-]<<-]>[-]<<<[>>>+<<<-]
[-]>>>>[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>+>>>>-]<<<<<[-]>
[>>>>[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>+>>>>>-]<<<<-][-]>>
>>[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>+>>>>-][-]<<<<[>>>>>>
>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>+>>>>-]<<
<<<<<<-]<[-]>>>>>[<<<<<+>>>>>-]>>>>>>>[-]<<<[-]<[>+<-]>[<+>>>>+<<<-][-
]<<<<<[>>>>>+<<<<<-]>>>>>[<<<<<+>>>>>>>>+<<<-]<<<<[-]<<<<<[>>>>>+<<<<<
-]>>>>>[<<<<<+>>>>>>>>>>>>+<<<<<<<-]>>>>[-]>>[-]>[<+>-]<[>+<<<+>>-][-]
<[>+<-]>[<+<->>-][-]>>[-]<<<<[>>>>+<<<<-]>>>>[<<<<+>>+>>-]<<<<[-]+>>[<
<->>[-]]<<[>>[-]>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<<<<<<<[-]<<<<<<<[>>>>>
>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>[-]>
>+<<<[>[->+<<-[>>[-]<[>+<-]]>[-<+>]<]]>>>[>]<<<<<<<[-]>>[-]>[<+>-]<[>+
<<<+>>-]<<[<<<<<<[-]+++++++[<<<<<<<++++++>>>>>>>-]<<<<<<<++++++.>>>>>>
>[-]+++++++[<<<<<<<------>>>>>>>-]<<<<<<<------>>>>>>>[-]+++++++[<<<++
++++>>>-]<<<++++++.>>>[-]+++++++[<<<------>>>-]<<<------>>>>>>>>>[-]]<
<<<<<[-]+++++++[>++++++<-]>++++++.<[-]++++++++++.[-]+++++++[>------<-]
>------>>>[-]]<<<+<[-]>>>>>>>>>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<[-]<<<<<
<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>>>>+<<<-]>>>>[-]+++++++++>>
+<<<[>[->+<<-[>>[-]<[>+<-]]>[-<+>]<]]>>>[>]<<<<<<<<<<<<<<<[-]>>>>>>>>[
-]>>>[<<<+>>>-]<<<[>>>+<<<<<<<<<<<+>>>>>>>>-]<<<<<<<<[<<<+>>>>[-]<[-]]
>>>>>>>>[-]>>>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<[-]<<<<<<<<<<<<<[>>>>>>>>
>>>>>+<<<<<<<<<<<<<-]>>>>>>>>>>>>>[<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>+<<<-
 
Old 07-20-2017, 12:50 AM   #131
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,573
Blog Entries: 11

Rep: Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588Reputation: 3588
I am sure that is clever and interesting in some way, but please maintain the focused spirit of unobfuscated and shared knowledge already established in this thread by providing some elucidation!
 
Old 07-20-2017, 01:03 AM   #132
smeezekitty
Senior Member
 
Registered: Sep 2009
Location: Washington U.S.
Distribution: M$ Windows / Debian / Ubuntu / DSL / many others
Posts: 2,339

Rep: Reputation: 231Reputation: 231Reputation: 231
Quote:
Originally Posted by astrogeek View Post
I am sure that is clever and interesting in some way, but please maintain the focused spirit of unobfuscated and shared knowledge already established in this thread by providing some elucidation!
Alright. That BF isn't written by hand. It is generated as specified by a scripting language.

The input script:
Code:
VAR A
VAR am
VAR B
VAR bm
VAR C
VAR cm
VAR total
VAR sum
DO
MULTIPLY cm C C
MULTIPLY cm C
MULTIPLY bm B B
MULTIPLY bm B
MULTIPLY am A A
MULTIPLY am A
ASSIGN sum cm
ADD sum bm
ADD sum am
IF sum = total
IF A > 0
ADD A 48
PRINT A
SUBTRACT A 48
ADD B 48
PRINT B
SUBTRACT B 48
ENDIF
ADD C 48
PRINT C
PRINT 10
SUBTRACT C 48
ENDIF
INC C
IF C > 9
CLEAR C
INC B
ENDIF
IF B > 9
CLEAR B
INC A
ENDIF
INC total
WHILE total != 500
How each symbol translates:
Code:
VAR(A  ):
p=0

VAR(am  ):
p=0

VAR(B  ):
p=0

VAR(bm  ):
p=0

VAR(C  ):
p=0

VAR(cm  ):
p=0

VAR(total  ):
p=0

VAR(sum  ):
p=0

DO(  ):
p=0
>>[-]+[
MULTIPLY(cm C C):
p=2
>>>>>>[-]<<[-]>>>[<<<+>>>-]<<<[>>>+<+<<-]>>>>>[-]<<<[>[>>>+<<<-]>>>[<<<+>>+>-]<<
<<-]
MULTIPLY(cm C ):
p=8
>>[-]<<[-]>[<+>-]<[>+>+<<-][-]>>[<<<<[-]>>>>>[<<<<<+>>>>>-]<<<<<[>>>>>+<<<+<<-]>
>>>-]>[-]<<<[>>>+<<<-]
MULTIPLY(bm B B):
p=8
<<<<[-]>>[-]<[>+<-]>[<+<+>>-]>[-]<<<[>>>>[-]<<<[>>>+<<<-]>>>[<<<+>>+>-]<<<<-]
MULTIPLY(bm B ):
p=4
>>[-]<<[-]>[<+>-]<[>+>+<<-][-]>>[>>[-]<[>+<-]>[<+<<<+>>>>-]<<-]>[-]<<<[>>>+<<<-]

MULTIPLY(am A A):
p=4
[-]>>>>[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>+>>>>-]<<<<<[-]>[>>>>[-]<<
<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>+>>>>>-]<<<<-]
MULTIPLY(am A ):
p=4
[-]>>>>[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>+>>>>-][-]<<<<[>>>>>>>>[-]
<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>+>>>>-]<<<<<<<<-]<[-]>>>
>>[<<<<<+>>>>>-]
ASSIGN(sum cm ):
p=8
>>>>>>>[-]<<<[-]<[>+<-]>[<+>>>>+<<<-]
ADD(sum bm ):
p=12
[-]<<<<<[>>>>>+<<<<<-]>>>>>[<<<<<+>>>>>>>>+<<<-]
ADD(sum am ):
p=12
<<<<[-]<<<<<[>>>>>+<<<<<-]>>>>>[<<<<<+>>>>>>>>>>>>+<<<<<<<-]
IF(sum = total):
p=8
>>>>[-]>>[-]>[<+>-]<[>+<<<+>>-][-]<[>+<-]>[<+<->>-][-]>>[-]<<<<[>>>>+<<<<-]>>>>[
<<<<+>>+>>-]<<<<[-]+>>[<<->>[-]]<<[
IF(A  gt  0):
p=12
>>[-]>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<<<<<<<[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[<
<<<<<<+>>>>>>>>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>[-]>>+<<<[>[->+<<-[>>[-]<[>+<-]]>[-
<+>]<]]>>>[>]<<<<<<<[-]>>[-]>[<+>-]<[>+<<<+>>-]<<[
ADD(A 48 ):
p=14
<<<<<<[-]+++++++[<<<<<<<++++++>>>>>>>-]<<<<<<<++++++
PRINT(A  ):
p=1
.
SUBTRACT(A 48 ):
p=1
>>>>>>>[-]+++++++[<<<<<<<------>>>>>>>-]<<<<<<<------
ADD(B 48 ):
p=1
>>>>>>>[-]+++++++[<<<++++++>>>-]<<<++++++
PRINT(B  ):
p=5
.
SUBTRACT(B 48 ):
p=5
>>>[-]+++++++[<<<------>>>-]<<<------
ENDIF(  ):
p=5
>>>>>>>>>[-]]
ADD(C 48 ):
p=14
<<<<<<[-]+++++++[>++++++<-]>++++++
PRINT(C  ):
p=9
.
PRINT(10  ):
p=9
<[-]++++++++++.
SUBTRACT(C 48 ):
p=8
[-]+++++++[>------<-]>------
ENDIF(  ):
p=9
>>>[-]]
INC(C  ):
p=12
<<<+
IF(C  gt  9):
p=9
<[-]>>>>>>>>>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<[-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[
<<<<<<<+>>>>>>>>>>+<<<-]>>>>[-]+++++++++>>+<<<[>[->+<<-[>>[-]<[>+<-]]>[-<+>]<]]>
>>[>]<<<<<<<<<<<<<<<[-]>>>>>>>>[-]>>>[<<<+>>>-]<<<[>>>+<<<<<<<<<<<+>>>>>>>>-]<<<
<<<<<[
CLEAR(C  ):
p=8
>[-]
INC(B  ):
p=9
<<<<+
ENDIF(  ):
p=5
>>>[-]]
IF(B  gt  9):
p=8
>>>>>>>>[-]>>>>>[-]>[-]>[-]>[-]>[-]<<<<[-]<<<[-]<<<<<<<<<<<<<[>>>>>>>>>>>>>+<<<<
<<<<<<<<<-]>>>>>>>>>>>>>[<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>+<<<-]>>>>[-]+++++++++>>+
<<<[>[->+<<-[>>[-]<[>+<-]]>[-<+>]<]]>>>[>]<<<<<<<<<[-]>>>>[-]>[<+>-]<[>+<<<<<+>>
>>-]<<<<[
CLEAR(B  ):
p=16
<<<<<<<<<<<[-]
INC(A  ):
p=5
<<<<+
ENDIF(  ):
p=1
>>>>>>>>>>>>>>>[-]]
INC(total  ):
p=16
<<<+
WHILE(total != 500):
p=13
<<<<<<<<<<<[-]>>>>>>>>>>>>>>>>[-]<<<<<[>>>>>+<<<<<-]>>>>>[<<<<<+<<<<<<<<<<<+>>>>
>>>>>>>>>>>>-][-]++++++++++++++++++++++[<<<<<<<<<<<<<<<<---------------------->>
>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<----------------]
the output

Code:
0
1
153
370
371
407
I whipped up a little program to generate BF. I can post the source if someone wants but it's bad code with bugs. I only wrote it to kill some time.
 
2 members found this post helpful.
Old 07-20-2017, 01:29 AM   #133
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
but 2, 3, 4 .... 9 are missing (all the single digit numbers are ok).
 
Old 07-20-2017, 01:46 AM   #134
smeezekitty
Senior Member
 
Registered: Sep 2009
Location: Washington U.S.
Distribution: M$ Windows / Debian / Ubuntu / DSL / many others
Posts: 2,339

Rep: Reputation: 231Reputation: 231Reputation: 231
Quote:
Originally Posted by pan64 View Post
but 2, 3, 4 .... 9 are missing (all the single digit numbers are ok).
Oh that's because it only checks x^3 from 000-999 like the original thread was doing
 
Old 07-20-2017, 01:53 AM   #135
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
in that case 0 and 1 are wrong, they are not 3-digit numbers.
 
  


Reply


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
printing line numbers for code bauer172uw Programming 3 04-13-2006 11:10 PM
C programming - sorting random numbers Gigantor Programming 8 12-05-2005 10:32 PM
Printing numbers from a text file dynamically mrobertson Programming 1 06-28-2005 08:19 AM
printing numbers without using semicolon vijeesh_ep Programming 18 09-08-2004 11:59 AM
printing line numbers? fisheromen1031 Programming 1 07-27-2004 02:19 PM

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

All times are GMT -5. The time now is 01:17 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