Multiplication in Brainfuck - minimum number of evaluations [closed]

Given two numbers in tape location #0 and tape location #1 in Brainfuck, compute their product into another tape location (specify with answer). Optimize for the least amount of time-units used, where the interpretation of any command uses one time-unit. As example, here is a quick C++ program to determine the number of time-units used by a Brainfuck program:

#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#define MEMORY 10000
#define DATATYPE uint32_t
#define ALWAYSPOSITIVE true

DATATYPE tape[MEMORY];
int loc, instp;

int main(int argc, char* argv[]) {
std::string infile = "a.bf";
bool numeric = false;
bool debug = false;
std::string flag;
for(int i=1; i<argc; i++) {
std::string arg = argv[i];
if(arg == '-') flag = arg;
else {
if(flag == "-i" || flag == "--in") infile = arg;
}

if(flag == "-n" || flag == "--numeric") numeric = true;
if(flag == "-d" || flag == "--debug") debug = true;
}
if(infile == "") {
std::cerr << "Fatal: no input file specified. Usage: ./pp2bf -i <file> [-n] [-d]" << std::endl;
return 1;
}
std::ifstream progf(infile);
std::string prog; std::string line;
std::stack<int> loop;
while(progf >> line) prog += line;
instp = 0; uint64_t instc = 0, ptmove = 0, mchange = 0;
int maxaccessedmem = 0;
while(instp != prog.size()) {
char inst = prog[instp];
if(debug) {
std::cout << inst << " #" << instp << " @" << loc;
for(int i=0; i<=maxaccessedmem; i++)
std::cout << " " << tape[i];
std::cout << "\n";
}
if(inst == '[') {
if(!tape[loc]) { // automatically advance to matching ]
int n = 1;
for(int i=instp+1;;i++) {
if(prog[i] == '[') n++;
if(prog[i] == ']') n--;
if(n == 0) {
instp = i+1;
break;
}
}
continue;
}
loop.push(instp);
} else if(inst == ']') {
if(tape[loc]) {
instp = loop.top() + 1;
continue;
} else {
loop.pop();
}
} else if(inst == '>') {
loc++;
maxaccessedmem = std::max(maxaccessedmem, loc);
ptmove++;
if(loc == MEMORY) {
std::cerr << "Fatal: Pointer out of bounds (try increasing memory) @ instruction " << instp << std::endl;
return 1;
}
} else if(inst == '<') {
loc--;
ptmove++;
if(loc == -1) {
std::cerr << "Fatal: Pointer out of bounds @ instruction " << instp << std::endl;
return 1;
}
} else if(inst == '+') {
mchange++;
tape[loc]++;
} else if(inst == '-') {
mchange++;
if(tape[loc] == 0) {
if(ALWAYSPOSITIVE) {
std::cerr << "Fatal: Negative tape value at " << loc << " @ instruction " << instp << std::endl;
return 1;
} else {
std::cerr << "Warning: Tape value at " << loc << " @ instruction " << instp << std::endl;
}
}
tape[loc]--;
} else if(inst == '.') {
mchange++;
if(numeric) {
std::cout << (DATATYPE)(tape[loc]) << std::endl;
} else {
std::cout << (char)(tape[loc]);
}
} else if(inst == ',') {
mchange++;
if(numeric) {
int inp; std::cin >> inp;
tape[loc] = inp;
} else {
char inp; std::cin >> inp;
tape[loc] = inp;
}
}
instp++;
instc++;
}
std::cout << "\nTerminated after " << instc << " time-units." << \
"\nMoved pointer " << ptmove << " times." << \
"\nChanged a memory location " << mchange << " times." << std::endl;
}

Note: In this implementation the tape is allotted 10K locations and each tape is an unsigned 32-bit integer - not the 8 bits used in a standard Brainfuck implementation.

For starters, here's mine:

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

When you compile the C++ program as rbf, save the Brainfuck program as mult.bf, run ./rbf -i mult.bf -n, and type 1000 followed by pressing Enter twice, the following output appears:

1000000

Terminated after 17011009 time-units.
Moved pointer 12006004 times.
Changed a memory location 5001003 times.

Your goal is to minimize the first value (i.e. 17011009). In case of ties minimize the second (12006004) and then the third (5001003).

The standard test case is

1000
1000

However, your code shouldn't be optimized for this test case only, but expend minimal time-units for any two numbers.

EDIT: For well-formedness, and not hardcoding an answer, take the sum of the expended time units in all test cases

x
x

where x = 900...1000 inclusive to get the final time units expended.

closed as unclear what you're asking by Xcali, Wheat Wizard, Peter Taylor, mbomb007, Jo KingJul 11 at 5:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to the site! This is has the potential to be a good challenge there are just a couple of things I am concerned about. The first is how are loops timed? There are two ways that loops can happen that are identical in behavior but different in number of operations. The first is that the ] always puts the ip back to [ and [ does the checking and skipping. The second is that [ checks and skips the loop if zero while ] is continues on if zero and returns to the beginning of the loop if not. You ought to explain how exactly timing is scored. – Wheat Wizard Jul 9 at 12:51
• Firstly, thank you very much for being interested in my question! How it is timed is that the first [ counts towards the time, and every ] is counted towards the time, including the one in which terminates the program. But I appear to have forgot that an address can be 0... oops! ;) – w33z8kqrqk8zzzx33 Jul 9 at 12:55
• The second thing is: optimizing for time units used on it's own is not a sufficient winning criterion for us here. We require winning criteria to unambiguously rank answers. There should be no debate as to whether which answer is better or if the two answers are the same score. Your criterion does not quite do that. It is clear which answer is faster sometimes, but because there are answers that are faster for some inputs and slower for others how are those ranked? (My personal recommendation is to have answers get a concrete score by summing their scores across a number of specific cases) – Wheat Wizard Jul 9 at 12:57
• Increasing with size of input is not necessarily in conflict with my last comment. Say for example I have two answers, answer A is faster or slower mostly dependent on the size of the first input (that is that large values here make it very slow but large values in the second have little effect), while B is the opposite being more dependent on the second input. B will be faster than a sometimes for example if given 10000, 4 but A will also be faster sometimes for example if given 4, 10000. There are all sorts of other ways for this to happen too (this is just an example). – Wheat Wizard Jul 9 at 13:07
• Ah, yes: this is present in my solution, too (4, 1000 is ~79K time units whilst 1000,4 is ~68K time units). I'll consider on how to improve this. – w33z8kqrqk8zzzx33 Jul 9 at 13:14

7,009,011 timesteps for $$\1000*1000\$$
This increases the counter on both the initial transfer and the second transfer back to the original position. This makes it almost the same efficiency for both orderings of the input, for example, $$\100*1000\$$ is $$\709011\$$ steps, while $$\1000*100\$$ is $$\700911\$$ steps.