My telephone is a computer!
code-challenge algorithm primes
I finally took the plunge and purchased a push-button telephone. It seemed a waste to just bin the old telephone, so I got working with some surplus chips and boards and things, and a soldering iron, and made it into a computer!
Now I need a program. DialCode(c) can do Prime Numbers! I think.
So I need some help with an algorithm for Prime Numbers, with the following limitations:
10 variables, which can contain any number from zero upwards, limited only by 32,767; (Var0 - Var9)
10 labels; (Label0 - Label9)
10 Machine Instructions;
EndBlock: Ends a block - if the block was actioned, implicity Continue Main is executed,
otherwise continues with next instruction (EndBlock)
Test > 0: Starts a block, can test multiple variables (If > 0 Var0 ...)
Test = 0: Starts a block, can test multiple variables (If = 0 Var0 ...)
Set variable to another variable (Var0 = Var1)
Set variable to 1 (Var0 = 1)
Set variable to 0 (Var0 = 0)
Increment variable by 1 (Var0 +)
Decrement variable by 1 (Var0 -)
Unconditional branch to label (Br Label0)
Continue MAIN (Continue MAIN)
Output variable (Output Var0)
Instructions prior to the first Test
are executed only once, at the start of the program.
Continue MAIN
can be within a block or a "special case" unconditional use which is the target for the completion of a non-nested block.
The first Test
defines MAIN
.
MAIN
is executed an "installation setting" number of times. These are 10 for Testing, and 1,200 for Production.
A Test
can define an internal block if appearing before an EndBlock
. The completion of an internal block does not cause automatic iteration (but an explicit Continue MAIN can be used for that).
All variables are initially zero.
Example program
Var1 = 1
If > 0 Var1 Var3
Var2 +
EndBlock
If > 0 Var2
Var1 +
Var3 +
EndBlock
Var2 +
Continue MAIN
Output Var1
Output Var2
Output Var3
MAIN
is defined here by the first IF > 0
. The first test is not true. The second test is not true. Var2
gets one added, and MAIN
starts up again (the unconditional Continue MAIN
). The first test is still not true. The second test is now true, and Var1
and Var3
get one added. Since the block was executed, there is an implicit Continue MAIN
. From this point on, the first IF > 0
will always be true, its block will be executed, with another implicit Continue MAIN
so the program will finish quickly.
The above program demonstrates how to implement a "case-like" structure. Put another way:
Var1 = 1
BlockControl repeat 10 times
case
Var1 > 0 And Var3 > 0
Var2 +
break
case
Var2 > 0
Var1 +
Var3 +
break
case
other
Var2 +
EndBlockControl
Output Var1
Output Var2
Output Var3
The output from the program will be 2, 9, 1.
Algorithm can be demonstrated in any language, even pseudo-code (if guaranteed to work). Explanations will probably make your Answer more popular.
It is not required to write an emulator of the CPU, only to limit your choice of instructions in your language to those logically equivalent to what is supported by the CPU. DialCode(c) itself is a subset of your language (subject to differences in syntax)!
There is no input. Output can be whatever is convenient. Feel free to use any specialist libraries, as long as they follow the above limitations.
The Winner must work to the limitations. The most popular working algorithm will be chosen. Where submissions are effectively the same algorithm, the one posted first, which I was able to understand, is the tie-breaker.
Sandbox Questions
I can't find a question here about generating Primes only using addition and subtraction. I know one way to do it, so all the guff above is to funnel thought towards a known solution. The solution I've seen uses 10 variables, 10 or fewer types of instructions, and Labels are fun, but not necessarily necessary.
Not sure of a reasonable time-limit to impose before the Accept.
When I came across an algorithm for this, I thought it was really cool. Very easy to implement without knowing how the algorithm actually works, difficult to come up with the algorithm. Great fun finding out how the algorithm works.
I would like to see a wide range of answers in a lot of languages, so that even fairly inexperienced users can have a crack at implementing. That's not going to work with one question, because I don't think it is an easy type of algorithm to develop (without foreknowledge or practice).
So I was thinking one question to get an algorithm, a second question for implementation. I was thinking of "fastest code" but that puts Assembler/compiled languages/others as the natural rankings for that.
Prompted by a comment by @isaacg, I'm now thinking "total number of DialCode(C) instructions executed" may work for a follow-up implementation question.
So, Question One - get a nice algorithm. Question Two, implement in as few DialCode(C) instructions as possible.
Any implementation is going to be Ssssslllllooooooowwwwww, with a capital S. Fewest DialCode(C) instructions is fastest code, whatever language the DialCode(C) is written in. Reasonably level playing field.
I'll have a go at the suggested shortening of the question :-)