Sierpinski carpet: Difference between revisions
→{{header|C++}}: added performance focused variant using BCT math
(adding Z80 Assembly implementation) |
(→{{header|C++}}: added performance focused variant using BCT math) |
||
Line 1,327:
=={{header|C++}}==
Performance focused variant (about 7x faster than the div/mod solutions at AMD Ryzen 7 4800H)
<lang cpp>// contributed to rosettacode.org by Peter Helcmanovsky
// BCT = Binary-Coded Ternary: pairs of bits form one digit [0,1,2] (0b11 is invalid digit)
#include <cstdint>
#include <cstdlib>
#include <cstdio>
static constexpr int32_t bct_low_bits = 0x55555555;
static int32_t bct_decrement(int32_t v) {
--v; // either valid BCT (v-1), or block of bottom 0b00 digits becomes invalid 0b11
return v ^ (v & (v>>1) & bct_low_bits); // fix all 0b11 to 0b10 (digit "2")
}
int main (int argc, char *argv[])
{
// parse N from first argument, if no argument, use 3 as default value
const int32_t n = (1 < argc) ? std::atoi(argv[1]) : 3;
// check for valid N (0..9) - 16 requires 33 bits for BCT form 1<<(n*2) => hard limit
if (n < 0 || 9 < n) { // but N=9 already produces 370MB output
std::printf("N out of range (use 0..9): %ld\n", long(n));
return 1;
}
const int32_t size_bct = 1<<(n*2); // 3**n in BCT form (initial value for loops)
// draw the carpet, two nested loops counting down in BCT form of values
int32_t y = size_bct;
do { // all lines loop
y = bct_decrement(y); // --Y (in BCT)
int32_t x = size_bct;
do { // line loop
x = bct_decrement(x); // --X (in BCT)
// check if x has ternary digit "1" at same position(s) as y -> output space (hole)
std::putchar((x & y & bct_low_bits) ? ' ' : '#');
} while (0 < x);
std::putchar('\n');
} while (0 < y);
return 0;
}</lang>
[[File:sierpinski_cpp.png|300px]]
<lang cpp>
| |||