Draw a Mandelbrot set with Brainf * ck

Draw a Mandelbrot set with Brainf * ck

Introduction

mandelbrot(color)

Brainf * ck language specification

Brainf * ck has 8 different instructions

The explanation is borrowed from the Brainfuck (ja) section of wikipedia.

Brainf * ck has an array of at least 30000 cells and an input / output byte stream, which can be manipulated to achieve processing.

Brainf * ck portability issues

According to the English wikipedia Brainfuck (en), there are four portability issues with Brainf * ck:

Cell size

The size of the cell pointed to by the pointer is generally 8 bits, but there are other sizes as well.

There seems to be 16bit, 32bit, or other implementations.

Array size

In the classic implementation, the array consists of 30,000 cells, with the first pointer at the far left (position 0).

However, there seems to be an implementation that has a cell on the left side (the subscript of the array is negative).

Also, when moving beyond the range of the array, it seems that there are implementations that cause an error, implementations that extend the array, implementations that move in the opposite direction of the array, and implementations that do not check the range (moss).

End-of-line code

Not limited to Brainf * ck, but the line feed code is often different.

Most treat LF (\ n) as a line feed code, but there are implementations (or operating systems) that use CR + LF (\ r \ n) or CR only (\ r).

End-of-file behavior

It seems that there are three behaviors (mainly?) When reading the end of the file, depending on the implementation.

Brainf * ck compiler implementation

In order to make a program with some functions with Brainf * ck, I thought that it would be better to add some functions to the compiler, so I made the compiler bf2c in C language. It's a compiler, or more accurately, a translator that translates Brainf * ck sources into C. Code optimization is left to the C compiler.

It has the following features

The following options can be specified for bf2c.

Even if you specify -2 or -4, it depends on the C compiler whether the cell size is 16bit or 32bit. Use short and ʻint` as specifications, respectively.

If you do not specify the version information with -V, the default information is embedded based on the source file name, current date, login name, and so on. For the login name, check the environment variables in the order LOGNAME ʻUSER`` LNAME ʻUSERNAME and use the one with the first non-empty string set (the environment variable to check is python (Refer to getpass.getuser () ). If nothing is set, use " noname "`.

The forced flash of -F was added so that it could be displayed character by character because the program of the Mandelbrot set I made at the beginning was quite slow and I was not sure if it was working with a line-by-line flash. Did.

The compiled run command accepts the following options

However, if the Brainf * ck source file does not use the , command, you cannot specify input file and input message options.

Similarly, you cannot specify output file options if the . command is not used.

Also, the version information and help message will be displayed in the same way.

If the input file and input message are not specified, the standard input is read. Similarly, if no output file is specified, it writes to standard output.

If the default argument of the execution command was specified at compile time ( -I or -M or -O), only one argument can be specified without any option.

Getting Started with Program Development with Brainf * ck

Brainf * ck's instructions are simple, but you can combine some to get the job done. The contents of this level are also described in various articles in Qiita, so I will explain it briefly in a hurry.

Setting the value

You cannot set the value directly in the cell, but you can set any value by combining + and -.

You can clear the value of the currently pointing cell to 0 by doing something like [-].

Loop processing

To realize the function equivalent to the while statement of a general language, it is possible to realize it by preparing a cell for control. For example, if the cell to the left of one is the control cell, you can process the loop by using <[> (Processing in the loop) <]>. However, at the end of "Processing in Loop", the pointer must be returned to its starting position.

Similarly, the function corresponding to the for statement that loops a specified number of times becomes<[-> (processing in the loop) <]>if the counter is on the left side. In this case, the counter has been decremented during processing and is 0 at the end of the loop. It must be copied in advance to avoid destroying the counter.

Move, add, copy data

For example, to add the value pointed to by the current pointer to the value next to it, you can do something like [-> + <]. 1 Applying this, for example, to double it would be [-> ++ <].

To add to two places (on the right side and on the right side), use [-> +> + <<].

You can copy the values, assuming that the right side is all 0s. First, enter the same value one next to one and two next to it as [-> +> + <<]. After that, if you move to the next two and add the value to the original position (destructive version) [>>, you can copy the value [-<< +] <<.

Brainf * ck's processing is basically destructive, so copying data is very frequent.

Conditional branch

Conditional branching such as the ʻif` statement in general languages is also realized in the form of a one-time loop.

For example, if you want to perform (then) process 1 if the current value is other than 0, and (else) process 2 if it is 0, prepare one cell as a work and use it as a flag. Here, we will use the next one as a flag for else and assume that the value is 0.

First, set the else flag to 1 > + <. And loop with the current value [. If the current value is non-zero, it will enter the loop, and if it is 0, it will not enter the loop. Inside the loop, the current value is cleared to 0, [-], and the else flag is also cleared >-<. After that, process 1 is executed and the loop is exited ].

Then loop based on the else flag > [. Clear the flag for else, -, execute process 2, and exit the loop] <.

This is the same process as ʻif`. At the end of the process, both the current value and the flag are 0.

In summary, > + <[[-]>-<(Process 1)]> [-(Process 2)] <It looks like this.

Brainf * ck programming with macros

If you assemble the above contents, you will be able to perform various processes.

But honestly, you can't do it, right?

Therefore, I decided to prepare a certain amount of cohesive processing as a macro and use it for programming.

For now, consider a macro that calls a function (or method) and returns the corresponding Brainf * ck instruction.

Basic macro

I wrote the macro in Python for the time being.

For example, a macro that moves a pointer looks like this.

def move_ptr(pos: int) -> str:
    """
Move pointer

    >>> move_ptr(0)
    ''
    >>> move_ptr(2)
    '>>'
    >>> move_ptr(-3)
    '<<<'
    """
    return ">" * pos if 0 <= pos else "<" * (-pos)

If you do this, the macro (provisional) that processes at the specified position and returns to the original position when finished will look like this.

def exec_pos(pos: int, statement: str) -> str:
    "Execute processing at the specified position"
    return move_ptr(pos) + statement + move_ptr(-pos)

However, programming by combining macros may cause unnecessary processing. For example, a process like ʻexec_pos (3, "+") + exec_pos (4, "-") outputs the result >>> + <<< >>>>-<<<< I will end up. The<<<>>>` on the way is useless, isn't it?

So, first we will make some basic macros.

import re


def delete_useless(statement: str) -> str:
    """
Useless movement/Offset and delete calculations

    >>> delete_useless("+++--<<>>>")
    '+>'
    >>> delete_useless("---++>><<<")
    '-<'
    >>> delete_useless(">++++[-][-]")
    '>[-]'
    >>> delete_useless(">--[-]++[-]")
    '>[-]'
    """
    while True:
        if "<>" in statement:
            #Offsetting useless movement, part 1
            statement = statement.replace("<>", "")
            continue
        if "><" in statement:
            #Offsetting useless movement, part 2
            statement = statement.replace("><", "")
            continue
        if "+-" in statement:
            #Offsetting useless addition and subtraction, part 1
            statement = statement.replace("+-", "")
            continue
        if "-+" in statement:
            #Offsetting useless addition and subtraction, part 2
            statement = statement.replace("-+", "")
            continue
        if "+[-]" in statement or "-[-]" in statement:
            #Remove addition / subtraction before zero clear
            statement = re.sub(r'[-+]+\[-\]', "[-]", statement)
            continue
        if "[-][-]" in statement:
            #Multiple zero clears at once
            statement = statement.replace("[-][-]", "[-]")
            continue
        break
    return statement


def delete_useless_all(statement: str) -> str:
    """
Useless movement/Offset and delete calculations. Delete the last useless process

    >>> delete_useless_all("[+>-<]>++++[-][-]")
    '[+>-<]'
    >>> delete_useless_all("[-<+>][-]>>++")
    '[-<+>]'
    >>> delete_useless_all("[-<+>][-]<<--")
    '[-<+>]'
    """
    statement = delete_useless(statement)
    while statement:
        if statement[-1] in "-+><":
            #At the end"+" "-" ">" "<"Is deleted
            statement = re.sub(r'[-+><]+$', "", statement)
            continue
        if statement.endswith("[-]"):
            #At the end"[-]"Is deleted
            statement = re.sub(r'\[-\]$', "", statement)
            continue
        break
    return statement


def block_of(*statements: str) -> str:
    """
Combine multiple instructions

    >>> block_of("[", "-", "]")
    '[-]'
    """
    return delete_useless("".join(statements))


def program_of(*statements: str) -> str:
    source = delete_useless_all("".join(statements))
    source = re.sub(r'(.{1,72})', "\\1\n", source)
    return source

Somehow, there is some logic that seems crazy, but I don't care because it's a disposable code anyway. The function name is also unclear, but I can't help it because I don't understand English.

The point is a macro that removes unnecessary movements and calculations that are easy to understand, and a block macro that makes it easier to write macros together.

Using these, you can rewrite ʻexec_pos` as follows.

def exec_pos(pos: int, statement: str) -> str:
    """
Execute processing at the specified position

    >>> exec_pos(3, "+")
    '>>>+<<<'
    >>> exec_pos(3, "<+>")
    '>>+<<'
    """
    return block_of(
        move_ptr(pos),
        statement,
        move_ptr(-pos)
    )

Value setting macro

The value setting macro looks like the following.

def inc_pos(pos: int) -> str:
    """
Increment the specified position

    >>> inc_pos(2)
    '>>+<<'
    """
    return exec_pos(pos, "+")


def dec_pos(pos: int) -> str:
    """
Decrement the designated position

    >>> dec_pos(3)
    '>>>-<<<'
    """
    return exec_pos(pos, "-")


def clear_pos(pos: int) -> str:
    """
Clear the specified position

    >>> clear_pos(3)
    '>>>[-]<<<'
    """
    return exec_pos(pos, "[-]")


def set_value(pos: int, value: int) -> str:
    """
Set the specified value

    >>> set_value(2, 3)
    '>>[-]+++<<'
    >>> set_value(2, -1)
    '>>[-]-<<'
    """
    (op, value) = ("+", value) if 0 < value else ("-", -value)
    return block_of(
        clear_pos(pos),
        exec_pos(pos, op * value)
    )

The logic of set_value seems to be a little crazy, but it looks like this on the premise that the work can not be used.

For example, if you want to set the initial value (all 0s on the right side can be used for the work), you can set it with a little more thought.

import math


def _init_value_sub(value: int) -> str:
    "Initial value setting.Premise that it can be used for work after the next"
    (op1, op2) = ("+", "-")
    if value < 0:
        value = -value
        (op1, op2) = ("-", "+")
    if value < 16:
        return op1 * value
    len0 = value
    str0 = op1 * value
    xmin = int(math.sqrt(value))
    xmax = int(math.ceil(value / 2.0))
    for x in range(xmin, xmax + 1):
        strx = _init_value_sub(x)
        lenx = len(strx)
        # len0 = x * y1 +Divided into c1 shape
        y1 = value // x
        c1 = value % x
        len1 = lenx + y1 + c1 + 7
        if len1 < len0:
            len0 = len1
            str0 = ">" + strx + "[<" + op1 * y1 + ">-]<" + op1 * c1
        if c1 != 0:
            # len0 = x * y2 -Divided into c1 shape
            y2 = y1 + 1
            c2 = x - c1
            len2 = lenx + y2 + c2 + 7
            if len2 < len0:
                len0 = len2
                str0 = ">" + strx + "[<" + op1 * y2 + ">-]<" + op2 * c2
    return str0


def init_value(pos: int, value: int) -> str:
    """
Initial value setting.
Premise that it can be used for work after the next.Be careful in the order of initialization
    """
    return delete_useless(exec_pos(pos, _init_value_sub(value)))

However, assuming that the optimization is applied after translating to C language, set_value (), which seems to be awkward, may be more efficient.

Loop macro

It is a loop system.

def while_loop(pos: int, *statements: str) -> str:
    """
while loop.
    >>> while_loop(3, ">>+<<")
    '>>>[<+>]<<<'
    """
    return block_of(
        exec_pos(pos, "["),
        block_of(*statements),
        exec_pos(pos, "]")
    )


def for_loop(pos: int, *statements: str) -> str:
    """
repetition.Destructive version
    >>> for_loop(3, "+")
    '>>>[-<<<+>>>]<<<'
    """
    return block_of(
        exec_pos(pos, "[-"),
        block_of(*statements),
        exec_pos(pos, "]")
    )


def for_safe(pos: int, work1: int, statement: str) -> str:
    """
repetition.Non-destructive version(However, do not update the reference to pos during the loop.)
    >>> for_safe(3, 4, "+")
    '>>>[->+<<<<+>>>]>[-<+>]<<<<'
    """
    return block_of(
        for_loop(pos, inc_pos(work1), statement),
        move_data(work1, pos)
    )

The non-destructive version of the for loop is destroyed and then returned to the end.

If you have two works, you can copy the value and then loop at the copy destination, but for the time being, you only have to look at the value in the loop, so this is the first step.

Copy / mobile macro

Move or copy data.

def move_data(source: int, destination: int) -> str:
    "1 byte move/Or add."
    return for_loop(source, inc_pos(destination))


def copy_data(source: int, destination: int, work1: int) -> str:
    "1 byte copy."
    return block_of(
        clear_pos(destination),
        for_safe(source, work1, inc_pos(destination))
    )


def override_data(source: int, destination: int) -> str:
    "1 byte move."
    return block_of(
        clear_pos(destination),
        move_data(source, destination)
    )


def swap_data(target1: int, target2: int, work1: int) -> str:
    "Swapping values between 1 bytes"
    return block_of(
        move_data(target1, work1),
        move_data(target2, target1),
        move_data(work1, target2)
    )

Conditional branch macro

A macro for a simple ʻif` statement.

Work is required to add the else clause, so for the time being, only then.

def if_nz_then(pos: int, then_statement: str) -> str:
    "if_Destructive version of nz.A simplified version of then only"
    return while_loop(
        pos,
        clear_pos(pos),
        then_statement
    )


def if_one_then(pos: int, then_statement: str) -> str:
    "Assuming the position of pos is 1 or 0.Process if 1(Destructive version)."
    return while_loop(
        pos,
        dec_pos(pos),
        then_statement
    )

ʻIf_one_then is almost the same as ʻif_nz_then, but if the value is either 0 or 1, the source size will be slightly smaller, so we have prepared it. Maybe it doesn't make much sense.

A little tricky macro

We also have some weird macros. A non-destructive version of the ʻif` statement that came to my mind and arithmetic processing using it (addition, subtraction, multiplication with carry).

However, since the work is required at a strange position, the pointer movement is different (eventually the same) between the then clause and the ʻelse` clause, which is a bit confusing macro.

Perhaps it is a drag on optimization in C language.

def if_nz_tricky(
        pos: int,
        n: int,
        m: int,
        then_statement: str,
        else_statement: str = "") -> str:
    """
    if_Non-destructive version of nz.A little tricky
Prerequisites
      *(ptr + pos + n) == 0
      *(ptr + pos + m) == 0
      *(ptr + pos + n + m) == 0
    ※ n ==m is OK
    """
    return block_of(
        move_ptr(pos),
        inc_pos(n),  # pos+n =flags for else
        "[",  #For NZ
        dec_pos(n),  #Clear the else flag
        exec_pos(-pos, then_statement),
        move_ptr(m),  #NZ is pos+m /Z remains pos
        "c]",
        move_ptr(n),  #NZ is pos+n+m /Z is pos+n
        "[-",  #For Z
        exec_pos(-pos - n, else_statement),
        move_ptr(m),  #NZ is pos+n+Remain m/Z also pos+n+Move to m
        "c]",
        move_ptr(-pos - n - m)
    )


def if_z_tricky(
        pos: int,
        n: int,
        m: int,
        then_statement: str,
        else_statement: str = "") -> str:
    """
    if_Non-destructive version of z.A little tricky
Prerequisites
      *(ptr + pos + n) == 0
      *(ptr + pos + m) == 0
      *(ptr + pos + n + m) == 0
    ※ n ==m is OK
    """
    return if_nz_tricky(pos, n, m, else_statement, then_statement)


def inc_data_tricky(pos: int, digit: int) -> str:
    """
Increment with carry.A little tricky
Prerequisites
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """

    if 1 < digit:
        #Need to carry up
        return block_of(
            inc_pos(pos),
            if_z_tricky(pos, 1, 1,
                        inc_data_tricky(pos - 1, digit - 1))
        )
    else:
        #No need to carry
        return inc_pos(pos)


def dec_data_tricky(pos: int, digit: int) -> str:
    """
Decrement with carry-down.A little tricky
Prerequisites
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """
    if 1 < digit:
        return block_of(
            if_z_tricky(pos, 1, 1,
                        dec_data_tricky(pos - 1, digit - 1)),
            dec_pos(pos)
        )
    else:
        return dec_pos(pos)


def add_data_tricky(source: int, pos: int, work: int, digit: int) -> str:
    """
1 byte addition. pos += source.There is a carry.Non-destructive version.A little tricky
Prerequisites
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """
    return for_safe(source, work, inc_data_tricky(pos, digit))


def multi_data_tricky(
        source1: int,
        source2: int,
        pos: int,
        digit: int) -> str:
    """
1 byte multiplication. pos = source1 * source2.There is a carry.Non-destructive version.A little tricky
Prerequisites
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
      *(ptr + pos + 3) == 0
      *(ptr + pos + 4) == 0
    """
    return for_safe(
        source1,
        pos + 3,
        add_data_tricky(source2, pos, pos + 4, digit)
    )

Brainf * ck simulator

You may have noticed that the first macro had doctest listed, but not in the middle.

As for basic macros, it is a simple code, so I could easily check the result with doctest, but for macros with movement, it is necessary to verify that the output code works rather than what it is. there is.

Therefore, I created a Brainf * ck simulator (interpreter-like) in python and verified its operation with unittest (because as it gets more complicated, I don't know what's wrong if the macro doesn't work properly).

Unit testing is important.

Brainf * ck stack machine plan

I made various programs with the above macro.

It was a hassle to think about where to put the work, which made me feel like I actually assembled it. If it is too far away, the source code will be uselessly large.

As a result of various thoughts, the idea is that it would be better to use a stack machine (stack processing language). Well, it's a macro like a stack processing language.

Also, in the case of the Mandelbrot set, decimal addition / subtraction / multiplication is required, but initially we used fixed-point decimals in two's complement representation. However, the calculation speed was very slow (although there is a high possibility of a logic problem), so this time I tried using a fixed-point decimal number of sign + absolute value.

Fixed-point decimals are 1 byte for the integer part and 1 byte for the decimal part (that is, they have a precision of 1/256).

Basic stack operation macro

I changed the fixed-point decimal to sign + integer part (1 byte) + decimal part (1 byte), so I tried to make one element of the stack 4 bytes.

1byte integers are stored at the beginning of 4bytes.

For fixed-point decimals, the first 1 byte is empty, the 2nd byte is the integer part, the 3rd byte is the decimal part, and the 4th byte is the sign (positive for 0, negative for 1).

… Why did I put the sign behind?

Also, it is assumed that the above macros are registered in the file bf_core.py.

import bf_core as c

#There are two types of numbers:
#・ 1 byte integer(Unsigned) {VALUE, 0, 0, 0}
#・ 3byte fixed point decimal. {0,Integer part,Decimal part,Sign 0/1}Sign + absolute value

#One element of the stack is fixed at 4 bytes
ELEMENT_SIZE = 4
#The top of the stack is one element before
TOP = ELEMENT_SIZE * (-1)
#The second on the stack is two elements before
SECOND = ELEMENT_SIZE * (-2)
#The current stack position is empty
NOW = 0
#Move one element back when stacked
NEXT = ELEMENT_SIZE * (1)

#Placement of 1-byte integers{Integer value, 0, 0, 0 }
IDX_BYTE = 0
IDX_DMY1 = 1
IDX_DMY2 = 2
IDX_DMY3 = 3

#Placement of fixed-point decimals{ 0,Integer part,Decimal part,Code(0=+/1=-) }
IDX_DMY = 0
IDX_INT = 1
IDX_DEC = 2
IDX_SGN = 3

def push_byte(value: int) -> str:
    "Stack a 1-byte integer at the top of the stack"
    value = int(value) & 0xff
    return c.block_of(
        c.init_value(NOW + IDX_BYTE, value & 0xff),
        c.move_ptr(NEXT)
    )


def push_decimal(value: float) -> str:
    "Stack 3 bytes fixed point at the top of the stack"
    (sign, value) = (0, value) if 0 <= value else (1, -value)
    value = int(value * 256) & 0xffff
    return c.block_of(
        c.init_value(NOW + IDX_INT, (value >> 8) & 0xff),
        c.init_value(NOW + IDX_DEC, value & 0xff),
        c.init_value(NOW + IDX_SGN, sign),
        c.move_ptr(NEXT)
    )


def drop() -> str:
    "Discard the top of the stack"
    return c.block_of(
        c.clear_pos(TOP + 3),
        c.clear_pos(TOP + 2),
        c.clear_pos(TOP + 1),
        c.clear_pos(TOP + 0),
        c.move_ptr(TOP)
    )


def dup(num: int) -> str:
    "Copy the elements of the stack and put them on the top of the stack. num=0 copies the beginning"
    pos = -ELEMENT_SIZE * (num + 1)
    return c.block_of(
        c.copy_data(pos + 0, NOW + 0, NOW + 1),
        c.copy_data(pos + 1, NOW + 1, NOW + 2),
        c.copy_data(pos + 2, NOW + 2, NOW + 3),
        c.copy_data(pos + 3, NOW + 3, NEXT),
        c.move_ptr(NEXT)
    )


def swap(num: int) -> str:
    "Swap the first element of the stack with the corresponding element of the stack. 1<=Be num"
    pos = -ELEMENT_SIZE * (num + 1)
    work = NOW
    return c.block_of(
        c.swap_data(pos + 0, TOP + 0, work),
        c.swap_data(pos + 1, TOP + 1, work),
        c.swap_data(pos + 2, TOP + 2, work),
        c.swap_data(pos + 3, TOP + 3, work)
    )


def override(num: int) -> str:
    "Overwrite the corresponding element of the stack with the first element of the stack. 1<=Be num."
    pos = -ELEMENT_SIZE * (num + 1)
    return c.block_of(
        c.override_data(TOP + 3, pos + 3),
        c.override_data(TOP + 2, pos + 2),
        c.override_data(TOP + 1, pos + 1),
        c.override_data(TOP + 0, pos + 0),
        c.move_ptr(TOP)
    )

It's like that.

Stack version loop macro

With a 1-byte integer on the top of the stack, it loops the number of times.

When the loop ends, the first 1-byte integer on the stack is discarded.

loop_last is used to interrupt the loop processing, but unlike the general brake, the processing itself is executed until the end of the loop ] (think of it as just setting the end flag). Kato. Actually, I just cleared the control variable to 0).

def loop_of(*statements: str) -> str:
    "Loop for 1 byte integer of TOP"
    return c.block_of(
        c.for_loop(TOP, *statements),
        c.move_ptr(TOP)
    )


def loop_last(num: int) -> str:
    "Get ready to end the loop.num is the position of the control variable in the loop.Processing continues"
    pos = -ELEMENT_SIZE * (num + 1)
    return c.clear_pos(pos + IDX_BYTE)

byte version addition / subtraction macro

Addition and subtraction of 1 byte.

If two 1byte integers are on the stack, add or subtract the two. After the calculation, the original two elements are deleted and replaced with the calculation result (that is, one element on the stack is reduced).

def add_byte() -> str:
    "1 byte addition"
    return c.block_of(
        c.for_loop(TOP + IDX_BYTE, c.inc_pos(SECOND + IDX_BYTE)),
        c.move_ptr(TOP)
    )


def sub_byte() -> str:
    "1 byte subtraction"
    return c.block_of(
        c.for_loop(TOP + IDX_BYTE, c.dec_pos(SECOND + IDX_BYTE)),
        c.move_ptr(TOP)
    )

byte version conditional branch macro

This is a 1-byte ʻif` statement.

After the end of the ʻif` statement, the first 1-byte integer on the stack is discarded.

Also, since the work uses the other part of the 1-byte element (remaining 3 bytes), The depth of the stack does not change.

def if_nz(then_statement: str, else_statement: str = "") -> str:
    "When the first 1 byte of the stack is NZ.Discard the top of the stack after the end"
    else_statement = c.delete_useless(else_statement)
    if else_statement != "":
        else_flag = TOP + IDX_DMY1
        return c.block_of(
            c.set_value(else_flag, 1),
            c.if_nz_then(
                TOP + IDX_BYTE,
                c.dec_pos(else_flag) + then_statement),
            c.if_one_then(
                else_flag,
                else_statement),
            c.move_ptr(TOP)
        )
    else:
        return c.block_of(
            c.if_nz_then(
                TOP + IDX_BYTE,
                then_statement),
            c.move_ptr(TOP)
        )


def if_z(then_statement: str, else_statement: str = "") -> str:
    "When the first 1 byte of the stack is Z.Discard the top of the stack after the end"
    return if_nz(else_statement, then_statement)


def if_eq(value: int, then_statement: str, else_statement: str = "") -> str:
    "When the first 1 byte of the stack is equal to value.Discard the top of the stack after the end"
    return c.block_of(
        push_byte(value),
        sub_byte(),
        if_z(then_statement, else_statement)
    )

Fixed-point decimal macro

Fixed-point decimal calculations (addition, subtraction, multiplication) and ʻif` statements.

Due to the sign + absolute value expression, addition and subtraction is unexpectedly troublesome.

I think that it may be better to use the Karatsuba method for multiplication, but I am worried that it may not change because addition and subtraction seems to be slower than expected, but now I am calculating with the long division method.

def if_nz_decimal(then_statement: str, else_statement: str = "") -> str:
    "When the 3-byte fixed point is NZ.Discard the top of the stack after the end"
    nz_flag = TOP + IDX_DMY
    else_flag = TOP + IDX_INT
    then_flag = TOP + IDX_DEC
    return c.block_of(
        c.clear_pos(TOP + IDX_SGN),
        c.if_nz_then(TOP + IDX_DEC, c.inc_pos(nz_flag)),
        c.if_nz_then(TOP + IDX_INT, c.inc_pos(nz_flag)),
        c.inc_pos(else_flag),
        c.if_nz_then(nz_flag, c.dec_pos(else_flag) + c.inc_pos(then_flag)),
        c.if_one_then(then_flag, then_statement),
        c.if_one_then(else_flag, else_statement),
        c.move_ptr(TOP)
    )


def if_z_decimal(then_statement: str, else_statement: str = "") -> str:
    "When the 3-byte fixed point is NZ.Discard the top of the stack after the end"
    return if_nz_decimal(else_statement, then_statement)


def if_negative_decimal(then_statement: str, else_statement: str = "") -> str:
    "When the 3-byte fixed point is a negative number.Discard the top of the stack after the end"
    then_flag = TOP + IDX_DEC
    else_flag = TOP + IDX_INT
    return c.block_of(
        c.clear_pos(then_flag),
        c.set_value(else_flag, 1),
        c.if_nz_then(
            TOP + IDX_SGN,
            c.dec_pos(else_flag) + c.inc_pos(then_flag)
        ),
        c.if_one_then(then_flag, then_statement),
        c.if_one_then(else_flag, else_statement),
        c.move_ptr(TOP)
    )


def _add_abs() -> str:
    "Addition of absolute values of 3byte fixed point"
    # SECOND/Assuming that the signs of TOP are the same
    return c.block_of(
        c.clear_pos(TOP + IDX_SGN),
        c.for_loop(SECOND + IDX_DEC, c.inc_data_tricky(TOP + IDX_DEC, 2)),
        c.for_loop(SECOND + IDX_INT, c.inc_pos(TOP + IDX_INT)),
        c.override_data(TOP + IDX_DEC, SECOND + IDX_DEC),
        c.override_data(TOP + IDX_INT, SECOND + IDX_INT)
    )


def _dec_both_abs_int() -> str:
    "Decrement both integers until one becomes 0"
    count = NOW
    work1 = NOW + 1
    return c.block_of(
        c.copy_data(SECOND + IDX_INT, count, work1),
        c.for_loop(
            count,
            c.if_z_tricky(
                TOP + IDX_INT,
                ELEMENT_SIZE,  # work2 = NOW + IDX_INT
                ELEMENT_SIZE,  # work3 = NEXT + IDX_INT
                then_statement=loop_last(count),
                else_statement=c.block_of(
                    c.dec_pos(SECOND + IDX_INT),
                    c.dec_pos(TOP + IDX_INT)
                )
            )
        )
    )


def _dec_both_abs_decimal() -> str:
    "Decimate both decimals until one becomes 0"
    count = NOW
    work1 = NOW + 1
    return c.block_of(
        c.copy_data(SECOND + 2, count, work1),
        c.for_loop(
            count,
            c.if_z_tricky(
                TOP + IDX_DEC,
                ELEMENT_SIZE,  # work2 = NOW + IDX_DEC
                ELEMENT_SIZE,  # work3 = NEXT + IDX_DEC
                then_statement=loop_last(count),
                else_statement=c.block_of(
                    c.dec_pos(SECOND + IDX_DEC),
                    c.dec_pos(TOP + IDX_DEC)
                )
            )
        )
    )


def _if_nz_int_swap() -> str:
    "If the integer part of SECOND is other than 0, TOP/Turn over SECOND"
    work = NOW
    return c.if_nz_tricky(
        SECOND + IDX_INT,
        ELEMENT_SIZE * 2,  # work2 = NOW + IDX_INT
        ELEMENT_SIZE * 2,  # work3 = NEXT + NEXT + IDX_INT
        then_statement=c.block_of(
            c.swap_data(SECOND + IDX_INT, TOP + IDX_INT, work),
            c.swap_data(SECOND + IDX_DEC, TOP + IDX_DEC, work),
            c.swap_data(SECOND + IDX_SGN, TOP + IDX_SGN, work)
        )
    )


def _if_top_decimal_is_nz_then_override() -> str:
    "If the decimal part of TOP is other than 0, move TOP to SECOND"
    return c.if_z_tricky(
        TOP + IDX_DEC,
        ELEMENT_SIZE,  # work1 = NOW + IDX_DEC
        ELEMENT_SIZE,  # work2 = NEXT + IDX_DEC
        then_statement=c.clear_pos(TOP + IDX_SGN),
        else_statement=c.block_of(
            c.override_data(TOP + IDX_SGN, SECOND + IDX_SGN),
            c.move_data(TOP + IDX_DEC, SECOND + IDX_DEC)
        )
    )


def _top_minus_second() -> str:
    "Subtract from TOP by the decimal part of SECOND and move to the position of SECOND"
    return c.block_of(
        #Move sign(Move first with tricky measures)
        c.override_data(TOP + IDX_SGN, SECOND + IDX_SGN),
        #Decimal only a fraction of SECOND
        c.for_loop(
            SECOND + IDX_DEC,
            c.dec_data_tricky(TOP + IDX_DEC, 2)
        ),
        #Move results to SECOND
        c.move_data(TOP + IDX_DEC, SECOND + IDX_DEC),
        c.move_data(TOP + IDX_INT, SECOND + IDX_INT)
        # TODO -0.0 to 0.Should it be converted to 0?
    )


def _sub_abs() -> str:
    "Subtraction of absolute value of 3byte fixed point"
    #Dec until either becomes 0.The answer is the one that remains(Including the code)
    return c.block_of(
        #Decrement both integers until one becomes 0
        _dec_both_abs_int(),
        #If the integer part of SECOND is other than 0, TOP/Turn over SECOND
        _if_nz_int_swap(),
        c.if_nz_tricky(
            TOP + IDX_INT,
            ELEMENT_SIZE,  # work1 = NEXT + IDX_INT
            ELEMENT_SIZE,  # work2 = NEXT + NEXT + IDX_INT
            then_statement=_top_minus_second(),
            else_statement=c.block_of(
                # TOP/When both SECONDs have an integer part of 0
                _dec_both_abs_decimal(),
                _if_top_decimal_is_nz_then_override()
            )
        )
    )


def add_decimal() -> str:
    "Addition of fixed-point decimals"
    #Addition of absolute values if the signs are the same
    #If the signs are different, subtract the absolute value
    work = SECOND + IDX_DMY
    diff_work = TOP + IDX_DMY
    same_flag = SECOND + IDX_DMY
    return c.block_of(
        c.for_safe(SECOND + IDX_SGN, work, c.inc_pos(diff_work)),
        c.for_safe(TOP + IDX_SGN, work, c.dec_pos(diff_work)),
        c.inc_pos(same_flag),
        c.if_nz_then(diff_work, c.dec_pos(same_flag) + _sub_abs()),
        c.if_nz_then(same_flag, _add_abs()),
        drop()
    )


def sub_decimal() -> str:
    "Fixed-point decimal subtraction"
    #Invert the sign and add(A-B => A+(-B))
    plus_flag = NOW + IDX_DMY
    return c.block_of(
        c.inc_pos(plus_flag),
        c.if_one_then(TOP + IDX_SGN, c.dec_pos(plus_flag)),
        c.if_one_then(plus_flag, c.inc_pos(TOP + IDX_SGN)),
        add_decimal()
    )


def _multi_decimal_abs() -> str:
    "Multiplication of 3byte fixed-point absolute values"
    #The integer part and the decimal part are calculated in byte units, similar to long division.
    #             A1. A2
    #           x B1. B2
    # ---------------------
    #               .A1xB2 A2xB2
    #       +  A1xB1.A2xB1
    # ----------------------
    #            R1 .  R2    R3
    #          <--------->Required range
    idx_a1 = SECOND + IDX_INT
    idx_a2 = SECOND + IDX_DEC
    idx_b1 = TOP + IDX_INT
    idx_b2 = TOP + IDX_DEC
    idx_r1 = NOW + IDX_INT
    idx_r2 = NOW + IDX_DEC
    idx_r3 = NOW + IDX_DEC + 1

    #Calculated from the upper digit due to carry processing
    return c.block_of(
        c.multi_data_tricky(idx_a1, idx_b1, idx_r1, 1),  # AxC (1 byte)
        c.multi_data_tricky(idx_a1, idx_b2, idx_r2, 2),  # AxD (2 bytes including carry)
        c.multi_data_tricky(idx_a2, idx_b1, idx_r2, 2),  # BxC (2 bytes including carry)
        c.multi_data_tricky(idx_a2, idx_b2, idx_r3, 3),  # BxD (3 bytes including carry)
        c.clear_pos(idx_r3),  #Clear R3 because only the carry-up is required
    )


def _xor_sign() -> str:
    #+ If the signs are the same, minus if they are different
    idx_as = SECOND + IDX_SGN
    idx_bs = TOP + IDX_SGN
    idx_rs = NOW + IDX_SGN
    sign_work = NEXT
    return c.block_of(
        c.for_loop(idx_as, c.inc_pos(sign_work)),
        c.for_loop(idx_bs, c.dec_pos(sign_work)),
        c.if_nz_then(sign_work, c.inc_pos(idx_rs))
    )


def multi_decimal() -> str:
    "3byte fixed point multiplication"
    # A * B => R
    return c.block_of(
        _multi_decimal_abs(),  #Find the absolute value of R
        _xor_sign(),  #Find the sign of R
        c.move_ptr(NEXT),  #The state of the stack is{A, B, R}
        override(2),  #Overwrite R to position A
        drop()  #Delete B
    )


def if_lt_decimal(then_statement: str, else_statement: str = "") -> str:
    return c.block_of(
        swap(1),  # {A, B} -> {B, A}In order of. then/To not change the number of stacks when executing else
        dup(1),  # {B, A, B}
        sub_decimal(),  # {B, R (= A - B)}
        #A if R is negative< B
        if_negative_decimal(then_statement, else_statement),
        drop()  # drop B
    )


def if_ge_decimal(then_statement: str, else_statement: str = "") -> str:
    return if_lt_decimal(else_statement, then_statement)


def if_gt_decimal(then_statement: str, else_statement: str = "") -> str:
    return c.block_of(
        swap(1),
        if_lt_decimal(then_statement, else_statement)
    )


def if_le_decimal(then_statement: str, else_statement: str = "") -> str:
    return if_gt_decimal(else_statement, then_statement)

I'm cutting corners in one place, and there are two types of 0, + 0.0 and -0.0. Therefore, ʻif_negative_decimalwill judge-0.0` as a negative number.

Actually, since this function is used to judge the divergence of the Mandelbrot set, it may be judged by mistake once in a while. Well, it's within the margin of error, isn't it?

Character output macro

It is a one-character output and a (looks crazy) character string output macro.

def put_char() -> str:
    "1 byte at the top of the stack(One character)Output"
    return c.block_of(
        c.exec_pos(TOP, "."),
        drop()
    )


def put_str(message: str) -> str:
    result = c.clear_pos(NOW)
    for ch in message:
        result += c.init_value(NOW, ord(ch))
        #TODO ↑ It is better to check if the difference from the previous value is shorter
        result += c.exec_pos(NOW, ".")
        result += c.clear_pos(NOW)
    return c.delete_useless(result)

Draw Mandelbrot set

It's finally the main subject.

See below for more information on the Mandelbrot set.

Would it be like this if it were written in C language?

#include <stdio.h>

#define X_BEGIN -2.0
#define X_END 1.0
#define Y_BEGIN -0.9375
#define Y_END 0.9375

//Number of repetitions
#define C_MAX 26
//Divergence threshold(2.Squared value of 0)
#define THRESHOLD2 4

void main(void)
{
    int columns = 128;
    int rows = 40;
    //X-axis addition value
    float x_step = (X_END - X_BEGIN) / (columns - 1);
    //Y-axis addition value
    float y_step = (Y_END - Y_BEGIN) / (rows - 1);

    float y0 = Y_BEGIN;
    for (int y = 0; y < rows; y++)
    {
        float x0 = X_BEGIN;
        for (int x = 0; x < columns; x++)
        {
            float cx = x0;
            float cy = y0;
            float zx = 0;
            float zy = 0;
            char ch = ' ';
            char count = 'A' - 1;
            for (int c = 0; c < C_MAX; c++)
            {
                float zx2 = zx * zx;
                float zy2 = zy * zy;
                float size2 = zx2 + zy2;

                if (size2 > 4.0)
                {
                    //Divergence
                    ch = count;
                    break;
                }
                else
                {
                    float zx_next = zx2 - zy2 + cx;
                    float zy_next = zx * zy * 2 + cy;
                    if (zx_next == zx && zy_next == zy)
                    {
                        //convergence
                        break;
                    }
                    else
                    {
                        zx = zx_next;
                        zy = zy_next;
                        count++;
                    }
                }
            }
            putchar(ch);
            x0 += x_step;
        }
        putchar('\n');
        y0 += y_step;
    }
}

I think there are many other points, such as whether the decimal number should be float or the comparison between floats with ==, but I'll leave it for now.

To make it as easy to write as possible with Brainf * ck, to determine if the absolute value of a complex number exceeds 2.0, replace the squared value with the determination if it exceeds 4.0 without using sqrt. I am.

Let's write this in Brainf * ck.

By the way, stack macros are assumed to be saved in bf_stack.py.

import bf_core as c
import bf_stack as s


#X-axis range
(X_BEGIN, X_END) = (-2.0, 1.0)
#Y-axis range
(Y_BEGIN, Y_END) = (-0.9375, 0.9375)

#Number of repetitions
C_MAX = 26
#Divergence threshold(2.Squared value of 0)
THRESHOLD2 = 4


def mandelbrot(columns: int, rows: int) -> str:
    #X-axis addition value
    x_step = (X_END - X_BEGIN) / (columns - 1)
    #Y-axis addition value
    y_step = (Y_END - Y_BEGIN) / (rows - 1)

    return c.program_of(

        # #0: y0 = y_begin
        s.push_decimal(Y_BEGIN),

        # #1: y = rows
        s.push_byte(rows),
        s.loop_of(  # for(y)

            # #2: x0 = x_begin
            s.push_decimal(X_BEGIN),

            # #3: x = columns
            s.push_byte(columns),
            s.loop_of(  # for(x)

                s.dup(1),  # #4: cx = x0
                s.dup(4),  # #5: cy = y0
                s.push_decimal(0),  # #6: zx = 0
                s.push_decimal(0),  # #7: zy = 0
                s.push_byte(ord(" ")),  # #8: ch = ' '
                s.push_byte(ord("A") - 1),  # #9: count = 'A'-1

                s.push_byte(C_MAX),  # #10: c = 26
                s.loop_of(  # for(c)

                    # #11: zx2 = zx * zx
                    s.dup(4),
                    s.dup(0),
                    s.multi_decimal(),

                    # #12: zy2 = zy * zy
                    s.dup(4),
                    s.dup(0),
                    s.multi_decimal(),

                    # #13: size2 = zx2 + zy2
                    s.dup(1),
                    s.dup(1),
                    s.add_decimal(),

                    # #14: THRESHOLD2
                    s.push_decimal(THRESHOLD2),
                    # if size2 > 4.0
                    s.if_gt_decimal(
                        then_statement=c.block_of(
                            #Divergence

                            # ch = count
                            s.dup(5),  # #15
                            s.override(7),

                            # for_c break
                            s.loop_last(4)
                        ),
                        else_statement=c.block_of(
                            # #15: zx_next = zx2 - zy2 + cx
                            s.dup(3),
                            s.dup(3),
                            s.sub_decimal(),
                            s.dup(11),
                            s.add_decimal(),

                            # #16: zy_next = zx * zy * 2 + cy
                            s.dup(9),
                            s.dup(9),
                            s.multi_decimal(),
                            s.dup(0),
                            s.add_decimal(),
                            s.dup(11),
                            s.add_decimal(),

                            # #17: if zx_next == zx && zy_next == zy
                            s.dup(1),  # zx_next
                            s.dup(11),  # zx
                            s.sub_decimal(),
                            # #17: 0(zx_next == zx) or 1(zx_next != zx)
                            s.if_nz_decimal(
                                s.push_byte(1) + s.swap(1),
                                s.push_byte(0) + s.swap(1)),
                            s.dup(1),  # zy_next
                            s.dup(11),  # zy
                            s.sub_decimal(),
                            # #18: 0(zx_next == zx) or 1(zx_next != zx)
                            s.if_nz_decimal(
                                s.push_byte(1) + s.swap(1),
                                s.push_byte(0) + s.swap(1)),
                            # #17: 0(zx_next == zx && zy_next == zy) or other
                            s.add_byte(),
                            s.if_z(
                                then_statement=c.block_of(
                                    #convergence
                                    s.swap(1),
                                    s.drop(),  # drop zy_next
                                    s.swap(1),
                                    s.drop(),  # drop zx_next
                                    s.loop_last(5)  # last c
                                ),
                                else_statement=c.block_of(
                                    # zx = zx_next
                                    s.swap(1),
                                    s.override(10),

                                    # zy = zy_next
                                    s.swap(1),
                                    s.override(10),

                                    # count += 1
                                    s.dup(6),
                                    s.push_byte(1),
                                    s.add_byte(),
                                    s.override(7)
                                )
                            )
                        )
                    ),
                    s.drop() * 2  # drop zy2, zx2
                ),
                s.drop(),  # drop count
                s.put_char(),  # putchar(ch)
                s.drop() * 4,  # drop zy, zx, cy, cx

                # #4: x0 += x_step
                s.dup(1),
                s.push_decimal(x_step),
                s.add_decimal(),
                s.override(2)
            ),
            # drop x0
            s.drop(),

            # #2: putchar("\n")
            s.push_byte(ord("\n")),
            s.put_char(),

            # #2: y0 += y_step
            s.dup(1),
            s.push_decimal(y_step),
            s.add_decimal(),
            s.override(2)
        )
    )


if __name__ == '__main__':
    program = mandelbrot(128, 40)
    print(program)

When you actually use the stack processing macro, it is difficult because you have to write the elements of the stack in relative positions.

Anyway, save this as mandelbrot.py and run it.

python3 -B mandelbrot.py > mandelbrot.bf
./bf2c -F mandelbrot.bf
gcc -O2 -o mandelbrot mandelbrot.c
./mandelbrot

I think the compilation will finish soon, but it will take about 5-7 seconds to run. slow.

By the way, I think that you can compile normally with a general Brainf * ck compiler, but please use a compiler that is optimized as much as possible.

Also, I think it will take a long time with the Brainf * ck interpreter. At the very least, I think it's better to use an interpreter that works for optimization.

mandelbrot

There is Implementation of Mandelbrot set in famous Brainf * ck, but it only takes 1-2 seconds, so it's still improved There seems to be room.

Color the Mandelbrot set

To be precise, the Mandelbrot set is a set of complex numbers that does not diverge, so the black part of the result is the Mandelbrot set.

However, following the general Mandelbrot set drawing application, I will color it according to the number of times it diverges.

Since the source is simple, it is omitted (registered in github as a sample of the compiler). If you move it on a terminal that can use ANSI escape sequences, it will be colored.

mandelbrot(color)

application

After that, you can draw Julia set etc. with just a little modification.

julia(color)

Recommended Posts

Draw a Mandelbrot set with Brainf * ck
Draw a graph with NetworkX
Draw a graph with networkx
Draw a loose graph with matplotlib
Draw a beautiful circle with numpy
Draw a graph with Julia + PyQtGraph (3)
Draw a graph with pandas + XlsxWriter
Draw a graph with PySimple GUI
Easily draw a map with matplotlib.basemap
Set up a Samba server with Docker
Draw a heart in Ruby with PyCall
Draw a graph with PyQtGraph Part 1-Drawing
Draw a flat surface with a matplotlib 3d graph
Set up a simple HTTPS server with asyncio
Draw a graph with Japanese labels in Jupyter
How to draw a 2-axis graph with pyplot
Set up a local server with Go-File upload-
Draw a graph with PyQtGraph Part 3-PlotWidget settings
Draw a graph by processing with Pandas groupby
[Python] Draw a directed graph with Dash Cytoscape
Try to draw a life curve with python
[Python] Draw a Mickey Mouse with Turtle [Beginner]
Set up a local server with Go-File download-
Draw a graph with PyQtGraph Part 4-PlotItem settings
Draw a graph with matplotlib from a csv file
Draw a graph with PyQtGraph Part 6-Displaying a legend
Draw a graph with PyQtGraph Part 5-Increase the Y-axis
[Python] Draw a Qiita tag relationship diagram with NetworkX
[Python] How to draw a line graph with Matplotlib
I tried to draw a route map with Python
A story that struggled with the common set HTTP_PROXY = ~
Forcibly draw something like a flowchart with Python, matplotlib
Draw a graph with PyQtGraph Part 2--Detailed plot settings
[Python] How to draw a scatter plot with Matplotlib
Set up a Python development environment with Sublime Text 2
[Vagrant] Set up a simple API server with python
A4 size with python-pptx
Decorate with a decorator
Study math with Python: Draw a sympy (scipy) graph with matplotlib
Set up a Python development environment with Visual Studio Code
Set up a web server with CentOS7 + Anaconda + Django + Apache
[Visualization] I want to draw a beautiful graph with Plotly