Author |
Topic: New Puzzle - SIC (Read 3171 times) |
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
 |
New Puzzle - SIC
« on: Oct 4th, 2002, 4:23pm » |
 Quote  Modify
|
I'm not sure if this is really the proper forum, since this doesn't deal with an ACTUAL computer, as such, but it's a bit too computer-sciencey for the other sections. This puzzle was inspired a little exercise in one of my computer science textbooks. After the section introducing us to assembly languages, and using MIPS as an illustration, there was a hypothetical-thought-exercise thing. It described a computer, called the SIC -- the Single Instruction Computer. It had only one operation, and no registers, taking everything from memory. The only operation was called sbn, for Subtract and Branch if Negative. It takes three operands, all of which are memory addresses. It worked like this:
Take the instruction sbn a, b, c.
Let the value at address a equal the value at address a minus the value at address b. (In C code, that'd be *a = *a - *b;)
If the new value at a is less than 0, jump to memory address c and do instructions from there. Otherwise, go to the next instruction. (c is usually interpreted as a label.)
Some assumptions I make when I do this: The book used the notation .+1 in its examples to show that c equalled the next instruction's address, so that even if a < 0, the program would go to the next instruction anyway, as in "sbn a, b, .+1". Whenever I do code in my notebooks, I just leave the third operand empty in this case, as in "sbn a, b", and assume my hypothetical assembler will fill that in for me. I also assume that the values at the addresses are standard 8-bit signed integers, done in two's complement notation, just to keep things consistent. (That sign bit can come in handy...) I also assume that there's a memory address, called "one", that will always start out with the value one. (I try not to change one, of course.) I do this to make incrementation and decrementation easier. I also use it for making boolean values.
The book then described how the instruction set was still capable of doing lots of different things despite having one command. (Although I've noticed that it sometimes does those things very inefficiently.) For example, doing addition. Assume addresses a and b have certain values already. (As the instruction set doesn't have much in the way of I/O, this could be difficult, but we're talking hypothetically here.) Also assume that we can use memory address temp as a temporary storage space.
sbn temp, temp /* Since we don't know what was in temp before, it's uninitialized. But doing this will initialize it and set it to zero, since temp - temp = 0. c is blank, so program flow will always go to the next instruction. */
sbn temp, b /* temp = temp - b; since temp is zero, temp is now equal to -b. Since c is empty, even if -b is less than 0, program flow still goes to the next instruction */
sbn a, temp /* a = a - temp; since temp = -b, this is a - (-b), which is a + b */
A now equals A + B, and we can use temp for some other algorithm later.
Using this basic setup, I figured it could be used to generate a bunch of different computer science puzzles. For example:
(Assume for all of these that you are allowed to use temporary addresses, like temp. Remember that these addresses are uninitialized first.)
Simple: Implement left shift. Given an address a, shift the value in a one bit to the left. Bring in zeroes on the right. (Hint: Remember that left shift is the same as multiply by two...now...how can we do that...?)
Simple: Implement unconditional jump. Make an unconditional jump, that will always jump to to the label at c. Use a temporary variable. (Big Hint: This takes me two instructions. Here's my answer: sbn temp, temp ; sbn temp, one, LABEL.)
Less simple: Implement multiplication. Given two addresses, a and b, set another address c equal to a times b. Assume that the values of a and b are nonnegative, and you can change them. Work on figuring out how to do a loop, too. (Then, do it so that you can't assume they're nonnegative, and do it without changing them. That's a bit harder.)
Less simple: Implement sign checking. Given an address a, set another address b to equal true if the value in a is negative, or set b to false if it is nonnegative. You might want to take this opportunity to find good values to represent true and false with. (Hint: This will come in handy in some of the rotate and shift commands...do you know why?)
Medium: Implement compare-to-zero. Given an address a, set another address b to equal true if the value at a is equal to 0, and false if the value at a is not equal to 0. Do not change the value in a.
Medium: Implement left rotate. Given an address a, rotate it one bit to the left, bringing in the bit from the left on the right side.
Sorta hard: Implement right rotate. Given an address a, rotate the value in the address a one bit to the right, bringing in the bit from the right on the left side.
What other operations could think of to use as puzzles?
|
| « Last Edit: Oct 4th, 2002, 4:25pm by Jeremiah Smith » |
 IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle - SIC
« Reply #1 on: Oct 4th, 2002, 4:49pm » |
Quote Modify
|
By the way, my textbook is "Computer Organization and Design: The Hardware/Software Interface" 2nd edition, by David A. Patterson and John L. Henessey, Morgan Kaufmann Publishers, San Francisco, California. Just so me and William don't get sued for anything 
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
|
Re: New Puzzle - SIC
« Reply #2 on: Oct 5th, 2002, 9:23am » |
Quote Modify
|
Cool puzzle! Here are a few not-simple ones got:
Sign checking (supposing TRUE = 1 and FALSE = 0)
sbn b, b
sbn a, b, .+2
sbn b, ONE
add b, ONE ;using previously defined function
I have one little doubt, though. Does SIC not have a HALT instruction? It might have come in handy for the previous program, like so:
sbn b, b
sbn a, b, .+2
HALT
add b, ONE
HALT
Or are we supposed to code functions in such a way that when control flows out of the code segment, the function's task has been performed? Anyways, here are a couple more:
Loop (suppose we want to loop N times)
sbn i, i ;i is the counter
add i, N
sbn i, ONE, .+(X+3) ;start of actual loop - X is number of sequential commands in loop
<list of sequential commands - or at least commands that do not branch out of the loop>
sbn temp, temp
sbn temp, ONE, .-(X+2)
<Other instructions or HALT>
Multiplication seems quite easy with the above structure, even with the restrictions of not changing a, b and the possibility of their being negative.
Compare to zero (same convention for TRUE and FALSE)
sbn b, b
sbn a, b, .+3
sbn b, a, .+2
add b, ONE
<Other instructions or HALT>
Left rotate
For this one I broke the problem down into 2 cases. If I recall my 2's complement correctly, the first bit is the sign bit, so we have two subcases to bring in the appropriate digit from the left.
sbn leftbit, leftbit
sbn a, leftbit, .+2
sbn leftbit, ONE
add leftbit, ONE
add a, a
add a, leftbit
<Other instructions or HALT>
Still working on right rotate... almost there.
|
| « Last Edit: Oct 5th, 2002, 9:25am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle - SIC
« Reply #3 on: Oct 5th, 2002, 12:10pm » |
Quote Modify
|
No halt instruction, at least not when I do it; I just make it jump to the end of the code segment.
I suppose one could add a few more instructions, such as halt, to make life simpler, while keeping the basic idea of doing everything with subtract-and-branch-if-negatives. For example, I thought of having a second instruction, sbnf, where the "f" stands for function call. This instruction would have a label to a function as the third operand, something like sbnf a, b, ADD. (I tend to use labels, rather than the .+x notation, but whatever floats your boat  ) It would also place the address of the next instruction into a special location, maybe called RETURN or something. So, to call function ADD, you could do something like:
sbn temp, temp
sbn temp, one, ADD
And at the end of the function ADD, you could go back to the main program with
sbn temp2, temp2
sbn temp2, one, RETURN
Of course, that doesn't handle recursion or calling functions from within functions very well, but it's good for small stuff.
Little hint for right rotate: (A simple way, although one that takes up a lot of instructions, is to keep left rotating. For example, these are 8-bit numbers, so if you left rotated 7 times, it would be equivalent to a right rotate. There are other, shorter, ways, but that's the first way I thought of.
And a small suggestion for true and false: (I generally use -1 for true, as opposed to 1. It's easier to generate, simply by
sbn bool, bool
sbn bool, one
and, if you ever implement NOT, it would be the exact opposite of false, which is 0.)
|
| « Last Edit: Oct 5th, 2002, 12:15pm by Jeremiah Smith » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: New Puzzle - SIC
« Reply #4 on: Oct 11th, 2002, 12:24pm » |
Quote Modify
|
Yeah, I thought of doing right rotate as 7 iterations of left rotate - but come on, we can be better than that.
So I gave it some thought and figured out a way with very few instructions (though they might be executed many times). What I actually implemented, and made it very simple, was division. And I think it makes a good puzzle, so here it is:
(medium) Implement division. Given two positive numbers, stored in a and b, find q and r such that a = qb + r. Store them wherever you like.
(Sorta hard) Now implement division WELL. In other words, make it so that dividing 01111110 by 10 will not take 111111 steps. You may take advantage of the fact that the numbers have 8 bits.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle - SIC
« Reply #5 on: Oct 12th, 2002, 10:07pm » |
Quote Modify
|
on Oct 11th, 2002, 12:24pm, Pietro K.C. wrote:| Yeah, I thought of doing right rotate as 7 iterations of left rotate - but come on, we can be better than that. |
|
Yeah, but I suggested that as a very simple and naive answer...I thought of a few other algorithms, but haven't had time to sit down and write out SICode for them.
Quote:So I gave it some thought and figured out a way with very few instructions (though they might be executed many times). What I actually implemented, and made it very simple, was division. And I think it makes a good puzzle, so here it is:
(medium) Implement division. Given two positive numbers, stored in a and b, find q and r such that a = qb + r. Store them wherever you like.
(Sorta hard) Now implement division WELL. In other words, make it so that dividing 01111110 by 10 will not take 111111 steps. You may take advantage of the fact that the numbers have 8 bits. |
|
I never actually dared to do division, although I did decide that it was possible after solving subtraction (duh!) and right shift.
Anyway, try these: AND, OR, and XOR, which I consider medium. (Given a and b, put the answer in c without changing a and b.)
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: New Puzzle - SIC
« Reply #6 on: Oct 13th, 2002, 9:50am » |
Quote Modify
|
Sorry if I seemed snobbish when I said "we can be better than that"!!! This is something I say to myself when I get a not-so-elegant answer to a problem... it was not meant to put your suggestion down, or anything! It was the first way I thought of myself.
About division, the intended answer for the first one is actually just a subtracting loop... not the hardest thing, and not exactly the code you just HAVE to write down... I myself didn't.  The other one is a good load of work!
I'll get going right away on the logical operations. Thanks!
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle - SIC
« Reply #7 on: Oct 13th, 2002, 1:51pm » |
Quote Modify
|
on Oct 13th, 2002, 9:50am, Pietro K.C. wrote:| Sorry if I seemed snobbish when I said "we can be better than that"!!! |
|
Ah, you weren't.
Quote:| About division, the intended answer for the first one is actually just a subtracting loop... not the hardest thing, and not exactly the code you just HAVE to write down... I myself didn't. The other one is a good load of work! |
|
You know, I totally never thought of a subtracting loop. I was so used to thinking of division as an algorithm that was difficult to implement, that I forgot about doing it as just the opposite of multiply... well, I suppose that's one of the benefits of forums with lots of smart people.
I wonder how difficult it would be to make an assembler/interpreter thing for this. (I.e., simulate the SIC, and then make a program to compile all our code into SIC-code. It'd be like Java and its Virtual Machine.) I already have a few ideas for machine code.
(Also, this might be just me, but Virtual Machine may be one of the coolest-sounding phrases in English.)
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle - SIC
« Reply #8 on: Oct 28th, 2002, 10:47am » |
Quote Modify
|
An emulator for a Single Instruction Computer can be found here: http://tuxedo.org/~esr/retro/
Scroll down; it's called oic. (One Instruction Computer). The format of the programs are different than here, and there's a few other things, like I/O, but it's basically the same as the SIC defined here
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: New Puzzle - SIC
« Reply #9 on: Oct 30th, 2002, 2:41pm » |
Quote Modify
|
And while you're on that page, try to learn INTERCAL. It'll make your head explode.
|
|
IP Logged |
My arcade cabinet
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print