16-bit values: be smart (5)

Context

We now have conversion operators to handle 16-bit integers. We also created a piece of code to display 16-bit integers as decimal numbers.
The code was quite verbose however. Using those operators, one should really be careful regarding the "type" used. Do not use 16-bit integers when it's not needed.

Here, for example, we have

• One integer N (16-bit)
• divided by ten
• divisor is always 10: 8-bit
• remainder is always less than ten: 8-bit
• quotient may be more than 256: 16-bit
• else flag used by division: 8-bit
• Take remainder and add 48 to have a char
• 48 can be added using 6x8, all of them (including remainder) are always less than 256: 8-bit
• Clear remaining part of divisor: 8-bit
• Move quotient and start again: 16-bit

There is a huge place to improve code here.

The best way is probably to write BF instructions for 8-bit and plain text instructions for 16-bit, and finally replace plain text, to avoid mistakes.

Example:

WHILE

    RIGHT

    >>>++++++++++<<<

    LEFT

    WHILE

        MINUS

        RIGHT

        +>>+>-[-<]<[> RIGHT PLUS LEFT <-<<[->>>+<<<]>]<

        LEFT

    LOOP

    RIGHT

    <++++++[->++++++++<]>>>>[-]

......

LOOP

[.[-] <<< LEFT]

Then, replace WHILE, RIGHT, ... (and you can also remove all '< >' or '> <')

Minified code to print 2056 - 75% smaller - try it

>>>++++++++>++++++++[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>>>>++++++++++<<<<<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]+>[<-]<[->>-<<<]>>->>>>+>>+>-[<-]<[->>>>>+<+>[<-]<[->>+<<<]><<<<<<[->>>+<<<]>]<<<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>++++++[->++++++++<]>>>>[-]>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]+>[<-]<[->>-<<<]>>-<<<<+<+>[<-]<[->>+<<<]>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]<<[.[-]<<<<<<<]

16-bit values: summary and application (4)

Context

Here is a summary of our structures, and operations implemented to handle the basic 8 ones

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Cursor on A

Operation	"4 cells"	"3 cells"
,(read)	,>[-]<	,>[-]<
.(print)	.	.
<(move left)	<<<<	<<<
>(move right)	>>>>	>>>
+(inc)	+<+>[<-]<[->>+<<<]>>	+[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>+<<]>
-(dec)	<+>[<-]<[->>-<<<]>>-	[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>-<<]>-
[(while)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>
](loop)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Application

Let's reuse our previous "decimal printing" algorithm, and replace each instruction by its new implementation, to print a large number (let's say 2056)

Code - 4 cells structure - try it

generate 2056 using 4 cells structure
>>>>>>++++++++>++++++++<
decimal print algorithm rewritten using instruction replacements
>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>>>>>>>>>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>+<+>[<-]<[->>+<<<]>>>>>>>>>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<<+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<+<+>[<-]<[->>+<<<]>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<<<<<<<<<<<<<+<+>[<-]<[->>+<<<]>>>>>>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<+>[<-]<[->>-<<<]>>-.>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Note: 3 cells version's code is about 50% longer, but it's also 3 times longer to execute...

16-bit values: jumps (3)

Context

Note: read first and second part .
As a reminder, we have 2 different structures, named "4 cells" and "3 cells" to represent 16-bit integers.
Let's now redefine instructions + and - on those 2 structures.

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Cursor on A

We can see that these structures mean that we divided N by 256 and stored both quotient and remainder.

While [

What we need to do is to start execution of a piece of code if and only if at least one of {quotient, remainder} is not null.

Using 4 cells structure (reminder: like the 3 cells structure, we can leverage the next cell X, after D...)

• If D is not null, move it to X and increase B
• If C is not null, move it to D and increase B
• Move D back to C and X back to D
• Go to B. If not null, enter while (and reset B, and back to C to keep system consistent)
• Note: if B is null, or after while, we'll have to move back to C as well

Using 3 cells structure (reminder: cell X before A is null as well, as it's the C from previous block, and same applies to Y cell in the next block):

• If B is not null, move it to C and increase X
• If A is not null, move it to B and increase X
• Move B back to A and C back to B
• Go to X. If not null, enter while (and reset X, and back to A to keep system consistent)
• Note: if X is null, or after while, we'll have to move back to A as well

Note: actually, code is the same for both structures.

Loop ]

To loop (note: we are on the remainder, but loop started one cell before). We need to evaluate if both quotient and remainder are null or not as before, store the result at the exact same place than before, and loop if not null. Then

• If not null, the current cell will be reset after looping, thanks to our previous reset at the beginning. And it can't be done before looping. Otherwise, there won't be any loop
• If null, then there is nothing to reset, but let's just go back on remainder

Using 4 cells structure:

• If D is not null, move it to X and increase B
• If C is not null, move it to D and increase B
• Move D back to C and X back to D
• Go to B. If not null, loop (no reset needed, nor back to C, as it's done by while)

Using 3 cells structure:

• If B is not null, move it to C and increase X
• If A is not null, move it to B and increase X
• Move B back to A and C back to B
• Go to X. If not null, enter while (and reset X, and back to A to keep system consistent)
• Note: if X is null, or after while, we'll have to move back to A as well

Note: again, code is the same for both structures.

Operation	"4 cells"	"3 cells"
[(while)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>
](loop)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

16-bit values: add / remove 1 (2)

Context

Note: read first part here.
As a reminder, we have 2 different structures, named "4 cells" and "3 cells" to represent 16-bit integers.
Let's now redefine instructions + and - on those 2 structures.

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Cursor on A

We can see that these structures mean that we divided N by 256 and stored both quotient and remainder.

Add

To add 1, we need to increase remainder. And if null (if remainder was equal to 255), we just need to update the quotient as well.

Using 4 cells structure:

• Increment C and set else bit in B
• If C is not null, reset else bit in B
• Move left (in A if C is not null, or B otherwise)
• If current is not null (so, on B, with C = 0), then reset B, increment D, and back to A
• Current position is A in all cases, move back to C

Using 3 cells structure (reminder: cell X before A is null as well, as it's the C from previous block):

• Increment A
• Copy A to C (using cell X on the left to restore A)
• Set X to 1
• If C is not null, reset C and X (and back to C)
• If X is not null (so C was null, so A was null), reset X and increase B (and back to X)
• Current position is X, move back to A

Remove

To remove 1, we need to decrease remainder. But before that, if it is null, then decrease quotient as well.

Using 4 cells structure:

• Set else bit in B
• If C is not null, reset else bit in B
• Move left (in A if C is not null, or B otherwise)
• If current is not null (so, on B, with C = 0), then reset B, decrease D, and back to A
• Current position is A in all cases, move back to C and decrease.

Using 3 cells structure:

• Copy A to C (using cell X on the left to restore A)
• Set X to 1
• If C is not null, reset C and X (and back to C)
• If X is not null (so C was null, so A was null), reset X and decrease B (and back to X)
• Current position is X, move back to A and decrease

Operation	"4 cells"	"3 cells"
+(inc)	+<+>[<-]<[->>+<<<]>>	+[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>+<<]>
-(dec)	<+>[<-]<[->>-<<<]>>-	[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>-<<]>-

As mentioned initially, the 4 cells structure implements new instructions in a more compact way (but uses more cells)

16-bit values: concept, structures, IO and moves (1)

Context

What may be annoying using Brainfuck is the size of the cell. You can't (in theory) have integers greater than 255. Of course, this is the case for most of the programming languages, where integers are encoded using either 32 or 64 bits, but the limit is far higher in those cases.
Obviously, the 'cheating' solution would be to use another BF interpreter implementation that supports 16-, 32- or 64-bit integers. But how to use, let's say, 16-bit integers (up to 65,535) using regular Brainfuck?
Our only option would be to

1. Define a new data structure
2. Re-define all the 8 operators using this new data structure
   What does '+' means ? Add 1. So, how to modify our data that represents an integer N to represents integer 'N+1' instead, and same for - , . < > [ ]

Structure(s)

Actually, I found 2 different data structures, one that uses more memory cells but with faster overrides of operators, and one using less cells but with longer processes.

Actually, both needs 4 cells, but when you have multiple integers in memory, first one uses 4 cells per integer, while second one can use only 3 cells (reusing a cell from previous integer)

In this post and all the coming ones, we'll define the 2 structures and all their operators.

Structure 1 - "4 cells"

Let's have 4 cells A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

A and B are used for logical branching that will occur in our future code.
Using this structure, "having on a value" means having cursor on C

Structure 2 - "3 cells"

Let's have 4 cells A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Again, C is used for logical branching, but also "D", which is the "C" from the previous integer.
Using this structure, "having on a value" means having cursor on A

IO

Using those 2 structures, let's define how to read or print a value. Read means reinitialize the "quotient" (D, or B, according to the structure) and read value in "remainder" (C, or A)

Operation	"4 cells"	"3 cells"
,(read)	,>[-]<	,>[-]<
.(print)	.	.

Moves

Now, let's do the same wit

Operation	"4 cells"	"3 cells"
<(move left)	<<<<	<<<
>(move right)	>>>>	>>>