int a // a = 0
int b // b = 0
int c // c = 0
a++ // a = 1
a++ // a = 2
b = a * a // b = 4
c = a << a // c = 8
c = b * c // c = 32
c = c + a // c = 34
b = b >> a // b = 1
c << b // c = 1156
c++ // c = 1157
c = c * a // c = 2314
Well, that does complicate things quite a bit. I threw those lines out of my algorithm generator and the frequency of valid programs generated dropped by ~4 orders of magnitude.
The next (week) question might be, how to optimally produce an arbitrary large number out of zero. For example, 15 lines is enough to produce 23142314. But is this the minimum?
The optimal is to either minimize the energy or the time required, by my book. Or to minimize algorithmic steps. Doesn’t really matter which one of those definitions you adopt, they are closely related.
It’s like the Kolmogorov’s complexity. Which program language to use as the reference? Doesn’t really matter. Just use the one I gave, or modify it in any sensible way. Then find a very good solution for 23142314 - or any other interesting number. They are all interesting.
Here is a new problem:
https://protokol2020.wordpress.com/2017/06/05/create-2314/
Preliminary solution based on random search
I’ve hit on a bunch of similar solutions, but
2 * (1 + 34^2)seems to be the common thread.Let’s rewrite this in something C-like:
13 lines.
Yep. Effectively you’re just writing code in a very restricted subset of assembly language.
A more interesting exercise would be to write a program which would output such code with certain (I suspect, limited) guarantees of optimality .
Say a number (below 1 billion), I’ll give you (optimal) code.
You had a genetic algorithm at some point—is that what you are using?
I wouldn’t call it genetic. But yes, I have an algorithm to solve this kind of problems.
13 lines are also just enough for 23142314.
You can’t do
You must first create 5 in a variable, say B.
Well, that does complicate things quite a bit. I threw those lines out of my algorithm generator and the frequency of valid programs generated dropped by ~4 orders of magnitude.
You can’t even shift by 1. You have to create 1 first, out of zero. Just like God.
In which case, best I can do is 10 lines
Good enough, congratulations!
The next (week) question might be, how to optimally produce an arbitrary large number out of zero. For example, 15 lines is enough to produce 23142314. But is this the minimum?
Define “optimal”. Optimizing for the utility function of min(my effort), I could misuse more company resources to run random search on.
The optimal is to either minimize the energy or the time required, by my book. Or to minimize algorithmic steps. Doesn’t really matter which one of those definitions you adopt, they are closely related.
It’s like the Kolmogorov’s complexity. Which program language to use as the reference? Doesn’t really matter. Just use the one I gave, or modify it in any sensible way. Then find a very good solution for 23142314 - or any other interesting number. They are all interesting.
Just doing left shifts will scale you up very quickly:
Sure. But those numbers are like hubs, you need a “local line” to get to a “non-hub” number, which are majority.
It isn’t.
Define “shortest”. Least lines? Smallest file size? Least (characters * nats/char)?
Least lines.