Emulating Recursion on the TI-84+

November 30, 2008

Yes… it’s true I think about these things in my free time. It actually happened in the middle of a math class I was taking. We were talking about the Fibonacci sequence and I was thinking that it would be neat to have a recursive implementation on my calculator. Now, I know that the iterative approach is actually faster, but the idea of a true recursive implementation was a fun idea. Now, it may be possible using assembly programming for the calculator, but I don’t really know how to do that.

After a little bit of thinking I decided that programming with the calculator BASIC reminded me a bit of MIPS assembly (I can hear some people groan already). You see the calculator lists can be used as a make shift stack and since all the variables A – Z are global you can simply designate one of those as your “stack pointer”. So I adopted the convention that the S variable is the stack pointer and that the R variable is for returning values. Anything else is fair game. I suppose if I really wanted to put thought into this I would pick some of them as temporary and others for function arguments. However I didn’t want to spend that much time working on this.

The basic idea here is that when you want to call a function (IE another program) at the beginning of your function you simply preserve the state of any variables you wish to change by using the list. I happen to use L5, but you could use any list you wanted. The stack pointer starts at 0 and each time you add to the list to increment the stack pointer by the number of items you added. Then at the end of your function you restore the state of any variables you used and “return” by setting the R variable to be the return value.

Now this has some limitations. First of all the TI-BASIC is quite slow even on my 84+ Silver Edition. The second is that a list can only hold 1000 elements so your stack is essentially size 1000. That being said it is still fun to play around with the idea of recursion or the more broad idea of function calls. For instance I wrote a program to do prime factorization which uses a helper program to tell if a number is prime or not.

Here is the code of the main program FIB which is the recursive Fibonacci number finder:

:ClrList L6
:ClrHome
:
:Prompt A
:
:"SET STACK PTR
:1 => S
:
:"GET FIB NUM
:prgmFIBR
:Disp R

Now here is the program which does the real work, FIBR:

:"STOPPING
:"CONDITION
:If A<=2
:Then
:1 => R
:Return
:End
:
:"PUSH VARS
:"ON STACK
:A => L6(S)
:B => L6(S+1)
:T => L6(S+2)
:"Increase stack pointer
:S+3 => S
:
:A => B
:0 => T
:
:"FIBR(n-1)
:A-1 => A
:prgmFIBR
:T+R => T
:
:"FIBR(n-2)
:A-1 => A
:prgmFIBR
:T+R => T
:
:T => R
:
:"POP VARS
:"OFF STACK
:L6(S-3) => A
:L6(S-2) => B
:L6(S-1) => T
:
:"DEC. STACK
:"POINTER
:S-3 => S

If you actually went through the trouble of putting this into your calculator you run the program FIB and enter a positive integer. The program will then return the nth fibanocci number. This is a simple program but I think it gets at the idea of recursion. In any case it doesn’t have too practical a purpose it’s just for fun 🙂

Advertisements

Windows OneCare — An Epic Fail

November 27, 2008

Recently I have had the … “pleasure” of being able to deal with a piece of software known as Windows OneCase. Quite honestly I have never used a more ironic piece of software. Windows OneCare is supposed to be an all in one firewall/spyware/antivirus/backup system. Here is what Microsoft has to say about it:

With OneCare comes greater peace of mind, knowing your home network, computers, and vital personal data are better protected from online threats—not to mention that any children can surf in greater safety, too! (http://onecare.live.com/standard/en-us/3/saferonline.htm)

I find this to be hardly the case. First of all I think it is a conflict of interest for Microsoft to be selling antivirus software to their own flawed operating system. Are they admitting that they can’t make an operating system secure enough to project against all of the threats that are out there? It doesn’t make sense that you should have to spend extra money to keep your Windows systems working correctly.

That point aside Windows OneCare does not do at all what Microsoft promises. First of all I find that it works no better than any normal piece of antivirus software. It seems to locate your basic virus/malware and it puts it in quarantine for you. Oddly enough most of these viruses/malware came from Internet Explorer and were sitting in the IE Temporary Files I won’t even touch on the blaring issues there.

Secondly I have never seen a single piece of software slow down a computer more than Windows OneCare. Whether running on Vista or XP I have seen OneCare add MINUTES to the log in time of an average computer. This is unacceptable! A product like OneCare is supposed to make life easier… not harder. Additionally, just to open OneCare to change settings requires them to display one of those repeating “progress bars”. This is after it’s already running in the system tray! Does the configuration interface take up so much memory that they have to load it separate?

OneCare also attempts to rate the state of your system. This is one of the biggest jokes yet. I don’t think I have seen it give a system the best rating possible any time after a week or so. It seems that your system slowly slides into a dark abyss. It’s like self condemning software. Also, if it knows the state of your system is only “Fair” then why the heck doesn’t it DO something about it? Is it too lazy? I’m not sure, but I have to chuckle when it basically admits it can’t do anything to help you.

Finally we have the OneCare firewall. Doesn’t Windows already have a firewall? Is Microsoft saying that their firewall is not good enough? I’m really not sure what the point is. Now, maybe OneCare simply uses the Windows firewall as a backend, which I would hope that it does because otherwise Microsoft is yet again making implicit statements about their own product. I don’t know for sure what it uses and have tried to research it. I would certainly be interested to know.

That is just about all I have to say for Windows OneCare. I would recommend it for anyone looking to slow their system down and waste $50 in the process.


Windows …

November 25, 2008

Recently I was asked by a friend to rid his Windows XP machine of a particularly annoying virus/malware. It faked the Windows Security Center and was constantly displaying annoying pop-ups. It sat in the system tray and would not go away. It disabled your ability to change the desktop background and also disallowed you from accessing the task manager. Anytime you clicked on it the virus would open Internet Explorer and try to make you download some other virus.

I searched around the Internet for a while trying to see if people had several problems. After trying a bunch of different solutions I decided I should just investigate the problem by myself. First I checked in the usual places such as msconfig and in the Run folder in the registry to see if it had added any entries there. That didn’t turn out to be very fruitful. I loaded up TRK and ran the AVG Scanner and the BitDefender Scanner and both of them came up with some minor entries, but not the actual problem virus. Eventually, in a moment of desperation I cleared out all of the IE Temporary Folders. As it turns out the virus had installed itself in there. I imagine it was activating itself through the “Active Desktop” feature of Windows which is why they didn’t want you changing the background.

As I would find out getting rid of the virus was the “easy” part. After that was gone I spent another hour trying to make it so you could change the background again. Everything I read said it was real easy… you just click the “Web” tab under “Customize Desktop” which was under the tab for changing the desktop background. Well… this virus had removed that tab altogether. I then followed several guides to try and get the tab back. No luck >_<. Eventually I resorted to a System Restore, which I actually hate, but that ended up solving the problem. Though it rolled back my installation of Spybot S&D which was a bit of a pain, but I figured it worthwhile to reinstall it since this person said they didn’t want to use Firefox.

This sort of experience is what makes me love Linux that much more… 🙂 . I have been a Gentoo user for a little over 4 years now and I will take a broken package problem over an annoying virus any day!


Theme Change

November 25, 2008

Yeah… I changed the theme. I actually liked the old one more, but it made Firefox lag like crazy when I tried to view my posts. I put up with it for a while, but I got sick of it. Luckily WordPress has a good deal of pre-made themes that look nice. I’m not sure how much I like this one. Perhaps it will grow on me… or perhaps I will change it again.

I heard it has something to do with what happens one someone takes a small sliver of a graphic and repeats it a bunch of tiles. Typically this happens when someone wants to make a gradient. I tried to load the page in Konqueror and it loaded great. I can only assume Konqueror caches a larger graphic or something along those lines… It’s a shame Firefox loads pages like that so poorly.


Reseting a Linux Password

November 22, 2008

While in the computer science lab today another student approached me with the following dilemma. They needed to do some programming over Thanksgiving break, but were not going to have Internet access to ssh into the lab machines. The student had installed Ubuntu on their laptop, but had forgotten the password because they had not used it in a while. They wanted to completely reinstall, but I said they would take quite a while when they could probably just reset the password. I offered to help and this sent me down an hour long journey to reset their password 🙂 mainly because I had to keep getting more and more equipment from my dorm room.

My first attempt was simply to pop in a Linux boot CD and chroot into their existing installation. From there I figured I would be root and could simply passwd my way to victory. This failed because his CD ROM drive, which was in shambles, refused to load the boot CD. Not one to give up easily I resorted to pulling out his hard drive and hooking it up to a little device I have which converts a hard drive to a USB device. Since I have Linux on my laptop I figured I’d just chroot over to his setup and be done with it. Well… that didn’t work because he had a 64-bit machine and when the chroot tried to run his version of bash it failed miserably. This makes sense because I only have a 32-bit machine.

I wasn’t going to give up there either. The next step I took was to change the password on my system and copy the hash out of my /etc/shadow to his /etc/shadow. For those who don’t know /etc/shadow is where Linux stores it’s hashed passwords. The idea behind the hash is that it is sort of  a one way encryption. In theory it is impossible to reverse the hash and the only way to figure out what it belongs to would be to hash every possible combination of letters, numbers, punctuation, etc. This works great for passwords though because when validating a password you simply need to hash the users attempt and compare it with the hash of the real password. Since the hash for a given string always comes out the same you know it’s a match if the hashes match.

After a few attempts at typing in the hash correctly I was able to reset his password and we logged into his machine without any troubles 🙂 .

I always love a good tech support challenge 😀


Euler Project

November 20, 2008

As pointed out by Wes it has indeed been some time since I posted anything on this blog. About once a week it occurs to me that I would really enjoy writing about this or that, but I just haven’t had the time lately. Part of the reason is how long it actually takes me to get a post up. It typically takes me around 30 to 40 minutes to write something mildly interesting, and then another 10 or 20 to proof read it. It is not as if I couldn’t find that sort of time, but typically I only have it at night, and when I am tried I find it very hard to concentrate on what I am writing 🙂

In any case I want to write about Project Euler today. About a week ago my Professor introduced to to Project Euler. They have a list of computer science and math problems that they ask you to solve, and typically the problem involves you needing to have some sort of mathematical intuition as well as coding skill. One simply makes an account on their site and when you think you have a solution to the problem you submit your answer and the site tells you if you got the right answer or not. So far I have been working on the earlier problems in the list when time permits. For a lot of them I tend to hack together a solution in Python within 5 to 10 minutes. I have heard the later problems get harder, and I await the challenge. Project Euler meets the strange need to write random small computer programs that perform an operation which is “cool” to only a small group of people. I also like the mathematical challenges that some of the problems provide, and it gives me a good test of my problem solving skills, which I think are very important to any computer scientist. The other interesting part to these problems is that Project Euler guarantees that your program should find a solution in under one minute of run time. This adds an extra challenge because you can’t necessarily brute force the answer :).

While writing solutions to these problems I have noticed how much slower Python is than C in certain cases. I have read many different guides to optimizing Python code and applied optimizations everywhere I can, and still the C equivalent to my solutions  runs drastically faster. I am not suggesting that C is necessarily a better language or something. Certainly, one expects a compiled language to outperform a scripting language, but since I had never done any formal study before I found this quite interesting. I do enjoy the speed at which I can throw together the solutions in Python, and I’m glad I taught myself Python a year or two ago because I have used it many times since then.

Anyway, I have a lot more to write about, and have been keeping a list. Hopefully over Thanksgiving break I will be able to put in an entry or two. At the very least when this semester ends I will have plenty of time to write blog entries and plan to be more active during that time.