Sollux - Blog Posts
sol n' fef! got bored ... watercolour brushes my beloved ...
freakyb0b is calling? 0h shit, g0tta answer this 0ne...
Nae Nae before you get a whoopin
unary to binary (back again, an objects journey) (part 1)
ok, so last time I didn't actually get to converting from unary to binary again.
So I guess I will do that here. (HAHA I JUST GOT IT TO DIVIDE WITH REMAINDER. APPLYING THAT TO THE CONVERSION IN PART 2)
so to do this we have to find the largest power of two not greater than the number, then the largest power of two not greater then what is remaining of the number, and repeat until we reach zero.
OR we can
find the largest power of two not greater than the number, then for each power of two less than the number, if it is not greater than it, use a 1 and subtract it from the remaining number.
and then for both of these, of course, reverse the result at the end so it is in the right order.
I think so far the second one of these sounds better.
but come to think of it, repeated integer division by two might work well.
that is, instead of repeated doubling, and then checking which one is larger, it might be faster to do repeated halving. (with a remained of either zero or one)
this could be then used to make a integer base 2 logarithm, with a remainder thing.
and instead of checking each power of two less than it, we could just find the integer base 2 log, and the base 2 log of the "remainder" and the base 2 log of THAT remainder and so on.
that seems like its the best way to me so far, but how do we take the integer logarithm AND get the log remainder thing?
getting the logarithm is fairly simple, just keep dividing by the number until you reach 1.
but how do you get the remainder part? and also how do you do the integer division in the first place with these number like things that we have created?
well lets answer the first of those questions first.
It seems like the remainder of the logarithm is probably related to the remainders of the divisions that make it up.
so lets look at taking the integer base 2 logarithm of 9:
9 4 (rem 1) 2 1
that took 3 halvings, and there was one remainder of one.
what if we try on 10 or something though?
10 5 2 (rem 1) 1
that also took 3 steps and one remainder, but the remainder was on a different step.
now lets try 11
11
5 (rem 1) 2 (rem 1) 1 (rem 0)
now wait, theres a pattern here, which might allow for converting it even faster.
the remainders of the divisions are the remainders of the logs expressed in binary!
we COULD turn them back into unary, so we could take the log of it again,
but what we are doing it converting it into binary anyway! (so that would be a silly step)
so if we look at what we were doing with the repeated division again, but looking at the numbers in binary, it will be pretty evident how to convert it in a better way.:
lets try 9 again (which is 1001)
1001
100 (rem 1) 10 (rem 0) 1 (rem 0) 0 (rem 1)
whats that? the remainders are the number we want in binary?
and now that I think of that it was kind of obvious?
yes. I for some reason did not think of that earlier.
so yeah, thats what we will do, we will repeatedly integer divide the number by 2 until we reach zero, and the remainders will be the number in binary.
but wait, we haven't even written out how to divide the number by two in the first place!
well turns out its not actually that hard to do.
in a loop (that keeps looping provided the number is not zero) subtract one, and if its still not zero, subtract one again. if it is zero after the first subtracting, the remainder of that division is 1. (only the last loop will cause the remainder to be 1) count the number of times where 2 was subtracted.
so like for 5 that would be
5 3 1 1 2 0 2 (remainder 1)
so that gives the correct answer (2 with remainder zero)
ok, now to implement this integer division by 2 in drocta ~ATH (wow! already? that was fast! /sarcasm)
//given that NUM is the variable that has the name we are halving BIFURCATE [NUM,NUM]2NUM; BIFURCATE 2NUM[NUMCPY,JUNK]; BIFURCATE [BLAH,BLAH]2BLAH; BIFURCATE 2NULL[SUBCOUNT,REMAINDER]; ~ATH(NUMCPY){ BIFURCATE 2BLAH[UNEVEN,JUNK]; BIFURCATE NUMCPY[JUNK,NUMCPY]; BIFURCATE [NUMCPY,NUMCPY]2NUMCPY; BIFURCATE 2NUMCPY[NUMCPYCPY,JUNK]; ~ATH(NUMCPYCPY){ BIFURCATE [BLAH,SUBCOUNT]SUBCOUNT; BIFURCATE NUMCPY[JUNK,NUMCPY]; BIFURCATE 2NULL[UNEVEN,NUMCPYCPY]; } ~ATH(UNEVEN){ BIFURCATE [BLAH,REMAINDER]REMAINDER; BIFURCATE 2NULL[UNEVEN,JUNK]; } } BIFURCATE [NUMCPY,NUMCPY]2NUMCPY; BIFURCATE 2NUMCPY[NUMDIV2,JUNK];
ok, that should divide the number by 2, put the result in NUMDIV2, and put the remainder in REMAINDER.
this takes linear time based on the size of the unary number. (provided I didn't make a mistake)
so now it is time to make sure it works, hold on a second while I check it. (I mean, im not going to post this until after I check it, so it doesn't really make sense to tell you to wait, because you just keep reading, but as I am writing this, I am about to test it.)
ok, I tested it. and it didn't seem to work, but then I realized that I made a mistake in making the test. (I checked the wrong variable)
but yeah, turns out that works...
ok, so now we need to repeatedly divide the number by two to get the remainders.
and we need to store these remainders in a list or something.
reading the contents of user input, and calculator improvement
This post will cover how to actually determine WHAT the user has typed, instead of just how long it is. It will also include how to interpret what the user enters as a binary number, so that its easier to type.
An Essential part of making it interpret binary numbers is making it double numbers repeatedly.
This actually has a few ways that can be done, so this is one of the first situations where coding style for this problem might differ from person to person. Because of this, I will say more than one way to do it.
The first way to do this it to copy the number twice, and then start from zero and add both of the copies. This is relatively inefficient, and would take
a copy thing, consisting of two bifurcates (which would take a little time)
where the size of the initial number is N, 2N normal bifurcates, 2N reverse bifurcates, and 4N lines relating to the actual loop
assuming each command takes the same amount of time (which is an oversimplification) this would take 9N+C line times. (C is a constant) This might be acceptable, but there is a more efficient and nicer looking way.
The second way is nicer looking, but still not the most effecient. However, when multiplying by a larger number(such as 3, or 4, or even large numbers), this method is part of what would be used.
The second method is essentially copying the number (using a reverse bifurcate and a normal bifurcate), and then adding the number to zero, except instead of each loop increasing the new number by one, it increases it by two. This is shorter, and it looks nicer. It also only takes half as many normal bifurcates. As a result, the number of steps it would take (again assuming each step is the same length) is 8N+C, instead of 9N+C
this one I will write out, but it is still not the best way:
//N is the number initially BIFURCATE [NULL,NULL]2NULL; BIFURCATE [N,N]G; BIFURCATE G[NCOPY,JUNK]; BIFURCATE 2NULL[RESULT,JUNK]; ~ATH(NCOPY){ BIFURCATE NCOPY[JUNK,NCOPY]; BIFURCATE [BLAH,RESULT]RESULT; BIFURCATE [BLAH,RESULT]RESULT; }
ok, so yeah. that takes N, and puts twice N into RESULT, but it is still inefficient.
A more efficient version is to copy the initial number, and add the number to itself. This way you only have to do half the number of reverse BIFURCATE statements. This is much more efficient, taking instead the steps:
a copy thing, consisting of two bifurcates (which would take a little time)
where the size of the initial number is N, N normal bifurcates, N reverse bifurcates, and 2N lines relating to the actual loop
This has 7N+C steps, which is a significant improvement. I think it is the fastest way to double a number in drocta ~ATH.
It is as follows (N is the number)
BIFURCATE [N,N]G; BIFURCATE G[NCOPY,RESULT]; ~ATH(NCOPY){ BIFURCATE NCOPY[JUNK,NCOPY]; BIFURCATE [BLAH,RESULT]RESULT; }
This is shortest and fastest solution I have found. If you find a shorter or faster method, please tell me.
Ok. Now we can double numbers. That is good. That is an important step. But we still haven't gotten user input to be read in any reasonable way.
Hang on, I'm GETTING TO THAT. GEEZ. (I'm kidding, no one has been complaining about my taking so long, other than myself)
Ok, so here goes:
To interpret the binary number input and convert it to a "number", we can follow the following algorithm:
start with zero.(this is before the loop)
If there are any characters left, double the number that is being created.
remove the first character from the remaining characters. If it is "1" or whatever symbol (or alternatively if it is not "0"), add one to the number that is being created. Otherwise, continue onto step 4 without doing anything first.
go back to the start of the loop (step 2)
Ok. thats the algorithm we are going to use. But I STILL haven't explained how to recognize what the next character is. Seriously what is up with that?
What you do is you bifurcate the rest of the input into [the next character,the rest of the input].
Now you have the next character. Then what you do is you reverse bifurcate it with some other object, and then you check whether that object is already dead or not.
But how do you make it so the combination is already dead? How do you get the object for the character before the user has even inputed it?
Answer: You don't. Not in the current version of drocta ~ATH anyway. You will have to tell the user to enter all the characters they will be using ahead of time. Yes this is horrible and stupid. No its not exactly like that in the comic. Its ~ATH what do you expect? :P
that might change in future versions, but I will try to stay backwards compatible with that.
but anyway, back to comparing it:
so you say something along the lines of:
import comparingobject CMP1; othercodehere makeNEQ1besomethingalive BIFURCATE [CMP1,CHAR]EQ1; BIFURCATE [NULL,NULL]2NULL; ~ATH(EQ1){ print yep, they are equal; BIFURCATE 2NULL[EQ1,NEQ1]; } ~ATH(NEQ1){ print nope, they are not equal; BIFURCATE 2NULL[NEQ1,JUNK]; }
in the othercodehere you get the character a head of time, and say BIFURCATE[CMP1,THECHARTHATMATCHESWITHCMP1]D; D.DIE();
That makes it so that it will go through the one section of code if the character is the right one, but something else if it is something else.
Which is what we want.
So to put it all together, and make the thing that interprets the input as a binary number(hold on tight(ok, what, why did I say that), this will be a long one(why am I talking like this?)):
import blah BLAH; print please enter whatever character you will be using for binary zero.; INPUT ZEROCHAR; BIFURCATE ZEROCHAR[ZEROCHAR,JUNK]; import chrcmp CMP0; BIFURCATE [CMP0,ZEROCHAR]D; D.DIE(); print please enter whatever character you will be using for binary one.; INPUT ONECHAR; BIFURCATE ONECHAR[ONECHAR,JUNK]; import chrcmp CMP1; BIFURCATE [CMP1,ONECHAR]D; D.DIE(); BIFURCATE [NULL,NULL]2NULL; BIFURCATE 2NULL[OUTNUM,JUNK]; print please input the binary number you want.(it will be converted to unary); INPUT BINNUM; ~ATH(BINNUM){ BIFURCATE [OUTNUM,OUTNUM]G; BIFURCATE G[NCOPY,OUTNUM]; ~ATH(NCOPY){ BIFURCATE NCOPY[JUNK,NCOPY]; BIFURCATE [BLAH,OUTNUM]OUTNUM; } BIFURCATE BINNUM[CHAR,BINNUM]; BIFURCATE [CMP0,CHAR]NEQ0; ~ATH(NEQ0){ BIFURCATE [BLAH,OUTNUM]OUTNUM; BIFURCATE 2NULL[NEQ0,JUNK]; } } print ok, going to print it out in unary, with each digit on one line. If the number you entered was large you might want to close the program instead of hitting enter.; INPUT JUNK; BIFURCATE [OUTNUM,OUTNUM]GOUTNUM; BIFURCATE GOUTNUM[OUTNUMCOPY,JUNK]; ~ATH(OUTNUMCOPY){ BIFURCATE OUTNUMCOPY[JUNK,OUTNUMCOPY]; print 1; } print Am I a terrible person for writing this?;
Oh gosh. I wish I could indent in tumblr. that is terrible to read. tumblr is a terrible source code editor.
One time someone called me a masochaist for writing this type of stuff.
And then we just have to put that together with the adding thing, and then maybe add a better way of outputting the number. maybe in binary.
HAHAHAHAH
ok, yeah, I'm going to put it together in the next post, not this one, because I have to homework now.(using the noun homework as a verb was intentional)
yeah. putting it together in the next post.
As always, if something was confusing, please ask for clarification.
User input, and a basic calculator.
Most programs people use have some form of user input. A calculator isn't much use if it always uses the same numbers after all!
~ATH of course accepts user input and output as shown in the file Roxy sent Jane.
Also I just found out you can put more than one read more line in one post.
The input command has the syntax:
INPUT VARNAME;
What this does is when program execution meets this line, the program pauses execution, allowing the user to input text. When the user hits enter, program execution will continue and the variable VARNAME will be made to point to an object corresponding to the text the user entered.
This object is such that the left half is the object that corresponds to the first character. If there is no character after that, the right half will be the NULL object. Otherwise the right half will be the object corresponding to the input without the first character. If they hit enter without inputting any characters the object will just be the NULL object.
Now that we have that all explained, we can start to make programs that actually take user input!
As you might have guessed from the title, the thing we will be making is a very basic calculator. All it does is add two numbers, like in the last example.
But in this, it will get the numbers from the user!
One simple way to do this is to use the length of the input text as the number: The way we define what we call numbers just so happens (heh) to be such that if we interpret the object for the input string as a number, the number will be the same as the length of the input!
This isn't the greatest solution, but it is easier than other methods. We will use this method first and then move on to other methods that are harder to write, but will be nicer when using the end program.
HERE WE GO:
ok, so like I said, much of it is pretty much the same as that previous program, so we might as well just include said here:
SOME CODE TO GET A AND B HERE import bluh BLAH; BIFURCATE [BLAH,A]ATEMP; BIFURCATE [BLAH,B]BTEMP; BIFURCATE ATEMP[JUNK,ATEMP]; BIFURCATE BTEMP[JUNK,BTEMP]; BIFURCATE [BLAH,NULL]C; BIFURCATE C[JUNK,C]; ~ATH(ATEMP){ BIFURCATE ATEMP[JUNK,ATEMP]; BIFURCATE [BLAH,C]C; } ~ATH(BTEMP){ BIFURCATE BTEMP[JUNK,BTEMP]; BIFURCATE [BLAH,C]C; } BIFURCATE [BLAH,C]CTEMP; BIFURCATE CTEMP[JUNK,CTEMP]; ~ATH(CTEMP){ BIFURCATE CTEMP[JUNK,CTEMP]; print some text; } print DONE!;
so pretty much what we need to do it put the code to get A and B where that goes(at the beginning), as well as stuff to tell the user how to print stuff.
Like I said, the objects from the input commands can be interpreted as numbers.
so this becomes:
print INPUT SOMETHING WITH THE NUMBER OF CHARACTERS AS THE FIRST NUMBER YOU WANT TO ADD; INPUT A; print INPUT SOMETHING WITH THE NUMBER OF CHARACTERS AS THE SECOND NUMBER YOU WANT TO ADD; IMPORT B; import bluh BLAH; BIFURCATE [BLAH,A]ATEMP; BIFURCATE [BLAH,B]BTEMP; BIFURCATE ATEMP[JUNK,ATEMP]; BIFURCATE BTEMP[JUNK,BTEMP]; BIFURCATE [BLAH,NULL]C; BIFURCATE C[JUNK,C]; ~ATH(ATEMP){ BIFURCATE ATEMP[JUNK,ATEMP]; BIFURCATE [BLAH,C]C; } ~ATH(BTEMP){ BIFURCATE BTEMP[JUNK,BTEMP]; BIFURCATE [BLAH,C]C; } BIFURCATE [BLAH,C]CTEMP; BIFURCATE CTEMP[JUNK,CTEMP]; ~ATH(CTEMP){ BIFURCATE CTEMP[JUNK,CTEMP]; print some text; } print DONE!;
So yeah. That should work. I still need to test this, but I am pretty dang sure that this works.(have to go do homework now) In the next post I will explain how to make it so that the user can type in the number as an actual number!
Welcome.
If its not obvious, this blog will teach techniques in a version of ~ATH Specifically, drocta ~ATH. And yes, I'm serious. I believe that I probably am the author of the longest ( possibly up to third longest) ~ATH program. Specifically, bubble sort. Further, I believe I am the author of the first ~ATH interpreter. (I am the drocta of drocta ~ATH) Link here: http://www.mspaforums.com/showthread.php?50314-ATH-interpreter This blog is intended to serve as a tutorial on writing things in drocta ~ATH. First I will go over the syntax. Then how to make conditional like things. Then how to make finite loops. Then perhaps storing "numbers". Then copying "numbers" Then comparing "numbers" Then lists In such a way I intend to work our way up to you understanding how to write bubble sort in drocta ~ATH. After that, we might even implement brainf*** in it. Or a universal Turing machine. Of course, when I say "numbers", the quotes are there for a reason. Numbers are not built into drocta ~ATH. One has to build them. Now how do I tag things...? Ah, that's how. In case it wasn't clear, the interpreter for drocta ~ATH does not attempt the impossible. It cannot trigger the apocalypse. It's just a python script that interprets ~ATH scripts. Don't worry if you don't already know how to program. I intend to make the posts fairly accessible.
