computer science

15 Articles

The Python documentation for str.strip().

Faster String Processing With Bloom Filters

September 21, 2023 by 8 Comments

At first, string processing might seem very hard to optimize. If you’re looking for a newline in some text, you have to check every character in the string against every type of newline, right? Apparently not, as [Abhinav Upadhyay] tells us how CPython does some tricks in string processing.

The trick in question is based on bloom filters, used here to quickly tell whether a character possibly matches any in a predefined set. A bloom filter works by condensing a set of more complex data to a couple of bits in an array. When an element is added, a bit is set, the index of which is determined by a hash function. To test whether an element might be in the filter, the same is done but by testing the bit instead of setting it. This effectively allows a fast check of whether an element might be in the filter.

CPython doesn’t stop optimizing there: instead of a complicated hash function, it simply uses the lowest 6 bits. It also has a relatively small bit array at only 64 bits which allows it to avoid memory all together, which in turn makes the comparisons much faster. [Abhinav] goes far into more detail in his article, definitely worth a read for any computer scientists among us.

Nowadays there is ever increasing amounts of talk about AI (specifically large language models), so why not apply an LLM to Python to fix the bugs for you?

Taking A Crack At The Traveling Salesman Problem

October 21, 2020 by 16 Comments

The human mind is a path-planning wizard. Think back to pre-lockdown days when we all ran multiple errands back to back across town. There was always a mental dance in the back of your head to make sense of how you planned the day. It might go something like “first to the bank, then to drop off the dry-cleaning. Since the post office is on the way to the grocery store, I’ll pop by and send that box that’s been sitting in the trunk for a week.”

This sort of mental gymnastics doesn’t come naturally to machines — it’s actually a famous problem in computer science known as the traveling salesman problem. While it is classified in the industry as an NP-hard problem in combinatorial optimization, a more succinct and understandable definition would be: given a list of destinations, what’s the best round-trip route that visits every location?

This summer brought news that the 44-year old record for solving the problem has been broken. Let’s take a look at why this is a hard problem, and how the research team from the University of Washington took a different approach to achieve the speed up.

Continue reading “Taking A Crack At The Traveling Salesman Problem” →

Grab A Stanford Computer Science Education

October 14, 2020 by 18 Comments

There are two reasons to go to school: learn about something and to get a coveted piece of paper that helps you get jobs, or at least, job interviews. With so many schools putting material online, you can do the first part without spending much money as long as you don’t expect the school to help you or grant you that piece of paper. Stanford has a huge computer science department and [Rui Ma] cataloged over 150 computer science classes available online in some form from the University. Just the thing to while away time during the quarantine.

Apparently, [Rui] grabbed the 2020 course catalog to find on-campus classes and found the companion website for each class, organizing them for our benefit. The list doesn’t include the actual online class offerings, which you can find directly from Stanford, although there is another list for that.

Continue reading “Grab A Stanford Computer Science Education” →

A Turing-Complete CPU From RAM

February 20, 2020 by 16 Comments

Building a general-purpose computer means that you’ll have to take a lot of use cases into consideration, and while the end product might be useful for a lot of situations, it will inherently contain a lot of inefficiencies. On the other hand, if you want your computer to do one thing and do it very well, you can optimize to extremes and still get results. This computer, built from RAM, is just such an example.

The single task in this case was to build a computer that can compute the Fibonacci sequence.  Since it only does one thing, another part of the computer that can be simplified (besides the parts list) is the instruction set. In this case, the computer uses a single instruction: byte-byte-jump. Essentially all this computer does is copy one byte to another, and then perform an unconditional jump. Doing this single task properly is enough to build every other operation from, so this was chosen for simplicity even though the science behind why this works is a little less intuitive.

Of course, a single instruction set requires a lot of clock cycles to work (around 200 for a single operation). The hardware used in this build is also interesting and although it uses a Raspberry Pi to handle some of the minutiae, it’s still mostly done entirely in RAM chips, only cost around $15, and is a fascinating illustration of some of the more interesting fundamentals of computer science. If you’re interested, you can build similar computers out of 74-series chips as well.

Tony Brooker And Autocode – The First High-level Language

January 2, 2020 by 32 Comments

The field of computer science has undeniably changed the world for virtually every single person by now. Certainly for you as Hackaday reader, but also for everyone around you, whether they’re working in the field themselves, or are simply enjoying the fruits of convenience it bears. What was once a highly specialized niche field for a few chosen people has since grown into a discipline that not only created one of the biggest industry in modern times, but also revolutionized every other industry, some a few times over.

The fascinating part about all this is the relatively short time span it took to get here, and with that the privilege to live in an era where some of the pioneers and innovators, the proverbial giants whose shoulders every one of us is standing on, are still among us. Sadly, one of them, [Tony Brooker], a pioneer of the early programming language concept known as Autocode, passed away in November. Reaching the remarkable age of 94, the truly sad part however is that this might be the first time you hear his name, and there’s a fair chance you never heard of Autocode either.

But Autocode was probably the first high-level computer language, and as such played a fundamental role in the development of whatever you’re coding in today. So to honor the memory of [Tony Brooker], let’s remember the work he did with Autocode, and the leap in computer science history that it represented.

Continue reading “Tony Brooker And Autocode – The First High-level Language” →

A Nurse Call System Becomes Turing Complete

March 9, 2019 by 3 Comments

George Mallory, a famous English mountaineer, once suggested that it was of no use to climb mountains. Instead, he posited, the only reason to climb a mountain is because it is there. Likewise, when you become an expert in nurse call systems like those found in hospitals, you may find that you do things with them that are of similar use. Making a Turing-complete nurse call system is something you do because you can.

[Erik] has been working on this particular call system, known as Netrix, and used Wireshark to sniff out all of its protocols. With this information he realized that it would be possible to use the system’s routing features to perform all of the tasks that any Turing complete system can do: conditional branching and memory access. He set up a virtual machine and set about implementing all of these tasks using the nurse call system’s features.

The setup for this project is impressive, and belies an extensive knowledge of this one proprietary system but also of computer science in general. It’s interesting to see how something can be formed into a working computer system from parts that otherwise might not be used that way. Even things that aren’t electronic can be used as Turing-complete computers.

Photo via Wikimedia Commons

A Compiler In Plain Text Also Plays Music

January 17, 2019 by 18 Comments

As a layperson reading about some branches of mathematics, it often seems like mathematicians are just people who really like to create and solve puzzles. And, knowing that computer science shares a lot of its fundamentals with mathematics, we can assume that most computer scientists are also puzzle-solvers as well. This latest project from [tom7] shows off his puzzle creating and solving skills with a readable file which is also a paper, which is also a compiler for C programs, which can also play music.

[tom7] started off with the instruction set for the Intel 8086 processor. Of the instructions available, he wanted to use only instructions which are also readable in a text file. This limits him dramatically in what this file will be able to execute, but also sets up the puzzle. He walks through each of the hurdles he found by only using instructions that also code to text, including limited memory space, no obvious way of exiting the program once it was complete, not being able to jump backward in the program (i.e. looping), and a flurry of other issues that come up once the instruction set is limited in this way.

The result is a sort of C compiler which might not be the most efficient way of executing programs, but it sure is the most effective way of showing off [tom7]’s PhD in computer science. As a bonus, the file can also play an antiquated type of sound file due to one of the available instructions being a call for the processor to interact with I/O. If you want to learn a little bit more about compilers, you can check out a primer we have for investigating some of their features.

Thanks to [Greg] for the tip!

Continue reading “A Compiler In Plain Text Also Plays Music” →